diff options
| -rw-r--r-- | 16/Cargo.toml | 11 | ||||
| -rw-r--r-- | 16/input | 262 | ||||
| -rw-r--r-- | 16/input.small | 12 | ||||
| -rw-r--r-- | 16/input.two | 11 | ||||
| -rw-r--r-- | 16/src/main.rs | 185 | ||||
| -rw-r--r-- | 16/tests/main.rs | 14 | ||||
| -rw-r--r-- | Cargo.lock | 8 | ||||
| -rw-r--r-- | Cargo.nix | 35 | ||||
| -rw-r--r-- | Cargo.toml | 1 |
9 files changed, 539 insertions, 0 deletions
diff --git a/16/Cargo.toml b/16/Cargo.toml new file mode 100644 index 0000000..a8b1866 --- /dev/null +++ b/16/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_16" +version = "0.1.0" +authors = ["Irene Knapp <ireneista@gmail.com>"] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/16/input b/16/input new file mode 100644 index 0000000..a9822a0 --- /dev/null +++ b/16/input @@ -0,0 +1,262 @@ +departure location: 48-885 or 906-949 +departure station: 28-420 or 431-970 +departure platform: 45-112 or 129-967 +departure track: 41-447 or 459-956 +departure date: 36-913 or 934-962 +departure time: 34-792 or 815-952 +arrival location: 35-644 or 657-973 +arrival station: 45-550 or 563-970 +arrival platform: 41-533 or 539-973 +arrival track: 33-729 or 745-967 +class: 36-516 or 523-956 +duration: 37-94 or 108-960 +price: 35-669 or 678-974 +route: 37-834 or 847-968 +row: 35-295 or 312-956 +seat: 35-563 or 588-951 +train: 29-210 or 221-968 +type: 50-853 or 877-958 +wagon: 28-341 or 353-971 +zone: 43-413 or 421-962 + +your ticket: +163,151,149,67,71,79,109,61,83,137,89,59,53,179,73,157,139,173,131,167 + +nearby tickets: +850,523,269,266,158,934,526,172,504,475,941,65,179,269,197,130,405,625,471,675 +157,110,437,692,556,370,85,365,460,709,336,174,940,825,194,485,436,383,714,292 +368,277,514,290,164,624,354,688,480,386,746,363,294,668,618,320,486,324,890,83 +515,208,942,4,948,785,280,635,783,473,907,681,533,92,282,76,528,323,395,239 +266,757,435,819,140,272,589,483,665,722,773,66,191,232,701,564,260,393,436,790 +459,830,935,778,479,191,152,390,180,851,483,538,488,695,94,56,357,293,237,495 +153,204,475,146,699,316,790,702,163,63,2,745,512,592,191,153,288,282,72,210 +937,199,602,685,931,374,243,618,81,356,81,712,684,669,620,238,153,389,468,882 +729,318,154,644,762,147,935,699,589,338,92,465,91,92,265,812,949,86,358,226 +83,410,64,88,406,292,76,152,712,232,361,267,668,865,408,602,243,411,729,503 +657,550,819,514,238,884,133,819,678,910,859,791,334,175,764,270,747,503,524,152 +199,466,756,201,705,631,391,375,91,174,61,151,936,512,155,641,259,635,66,522 +225,641,146,466,68,482,482,714,273,992,51,177,635,641,696,183,223,832,275,592 +725,489,474,523,726,158,909,50,595,85,770,823,542,431,756,612,538,472,246,143 +747,315,412,90,256,668,433,441,909,756,1,502,322,374,197,249,749,90,725,911 +182,831,823,543,397,153,529,341,210,220,696,772,659,369,412,171,136,506,163,362 +705,754,548,254,256,541,202,176,224,131,654,907,385,371,400,636,503,824,532,81 +693,616,434,324,466,529,541,640,173,596,720,189,159,134,654,640,748,715,80,750 +467,210,166,337,204,142,512,109,598,949,731,755,160,83,130,129,269,679,270,237 +91,769,821,55,339,197,275,129,242,135,216,853,941,485,906,600,242,412,242,473 +539,771,746,686,726,197,191,609,686,533,0,196,330,533,263,780,726,508,593,386 +777,828,255,792,156,608,677,614,201,621,563,681,616,52,817,757,782,706,358,936 +179,68,773,774,423,512,473,375,686,714,820,605,432,605,617,475,540,258,244,625 +370,631,472,131,530,211,239,396,280,466,789,64,132,616,726,721,234,89,135,377 +76,637,82,604,398,55,728,389,682,533,525,287,444,193,488,61,159,716,323,900 +481,175,767,167,789,830,642,385,465,847,666,170,759,407,284,267,854,543,761,816 +494,272,246,529,620,238,720,525,853,109,550,88,754,630,444,518,380,483,722,679 +167,138,408,62,685,374,134,773,682,0,833,539,54,706,760,291,783,488,479,360 +169,229,622,76,440,823,360,831,75,607,766,411,368,201,248,514,574,190,439,139 +368,438,227,240,755,546,264,62,68,751,745,351,140,372,502,709,280,949,173,76 +980,643,470,87,334,549,487,444,627,477,68,330,165,715,194,544,678,160,173,946 +319,682,760,481,140,312,485,158,678,815,826,522,66,332,947,755,270,627,758,233 +754,64,772,533,395,399,600,143,384,499,89,553,400,911,539,209,91,334,707,111 +224,177,729,270,260,981,324,66,725,78,332,330,680,176,763,627,205,395,259,390 +251,358,913,849,60,285,780,239,275,254,181,476,270,664,383,634,63,143,127,384 +729,410,238,251,333,236,199,907,636,207,81,118,79,81,254,942,826,389,710,382 +723,745,91,934,194,682,879,774,91,180,319,601,784,593,497,129,633,494,819,988 +548,162,330,178,937,540,711,184,470,66,719,411,769,270,614,324,502,562,374,934 +662,288,129,292,275,762,78,240,833,516,877,158,496,219,169,134,593,753,259,488 +145,433,746,152,379,67,526,815,936,207,85,396,133,359,398,199,733,63,831,70 +638,613,697,699,719,398,356,884,321,534,822,282,548,774,240,588,594,279,611,256 +8,59,369,322,784,497,186,69,721,499,172,365,141,433,262,69,789,295,948,491 +447,50,216,711,79,635,712,245,717,62,89,162,194,276,227,624,133,167,192,314 +270,282,467,112,657,258,633,326,183,687,518,378,154,327,589,604,263,319,337,596 +357,828,182,194,607,664,470,112,546,90,489,194,609,882,912,274,626,527,454,820 +337,785,270,280,523,378,438,335,699,186,817,99,230,271,723,830,502,707,762,503 +73,162,723,223,601,194,637,82,403,791,770,409,817,82,938,243,760,674,516,608 +167,947,705,501,228,287,460,482,412,832,469,549,312,703,290,623,949,909,397,452 +550,325,330,628,981,818,599,88,81,848,686,264,614,152,725,591,135,74,498,437 +288,495,360,688,174,475,290,776,76,704,209,704,294,594,108,213,480,498,192,52 +781,946,15,178,481,185,381,847,783,753,848,473,881,288,233,768,512,776,661,784 +396,167,405,849,899,506,749,546,878,515,786,231,361,472,725,609,459,334,191,529 +445,68,182,133,195,513,788,822,218,604,936,226,276,206,510,751,469,725,314,779 +398,132,152,665,758,153,353,131,407,502,671,50,386,768,227,335,393,821,480,664 +825,413,356,689,936,382,227,440,223,187,747,827,169,506,756,162,481,549,828,553 +642,264,83,328,501,55,317,172,611,473,437,725,244,621,755,475,711,733,362,716 +602,154,227,602,492,509,879,277,239,140,272,826,434,767,946,357,656,688,399,906 +612,77,615,787,364,83,246,878,884,76,500,702,512,83,592,286,896,132,502,280 +910,611,720,171,161,660,613,785,689,294,613,514,729,449,288,774,403,465,339,83 +787,936,697,490,608,393,321,132,60,229,820,469,272,743,750,474,763,443,226,616 +398,880,148,410,941,658,223,443,477,284,405,776,144,505,286,788,143,878,338,565 +112,602,716,509,152,512,704,185,75,136,607,369,63,495,723,179,83,680,426,88 +690,327,550,947,546,522,728,175,231,382,165,262,151,688,776,498,710,184,792,171 +73,765,593,827,766,642,521,108,145,848,685,662,688,393,708,92,52,597,224,667 +679,53,695,63,274,277,536,718,255,817,293,683,512,328,481,495,91,135,549,627 +246,197,617,222,457,707,364,483,936,375,230,255,189,682,686,710,260,728,705,182 +404,81,615,502,486,81,594,977,907,935,817,487,152,508,83,705,89,179,321,437 +238,140,126,766,380,885,338,183,389,711,610,210,833,178,173,748,782,251,129,834 +288,481,80,773,499,716,85,518,883,318,445,143,765,776,250,531,386,247,321,755 +934,500,634,781,288,536,339,779,83,946,329,267,511,134,693,476,486,496,234,528 +528,542,258,260,487,390,92,670,376,359,659,146,490,257,63,319,295,313,239,747 +353,411,362,208,244,388,321,621,634,129,408,235,635,689,286,238,550,520,563,51 +327,178,71,381,826,820,598,276,439,277,404,400,714,553,190,314,592,388,154,912 +515,851,487,477,374,939,498,681,312,492,460,447,112,244,731,506,439,82,246,541 +881,603,388,248,773,157,353,708,515,53,539,237,825,771,77,453,328,93,111,613 +65,189,237,185,881,750,447,130,663,729,235,785,789,645,110,183,331,274,210,827 +266,501,450,371,465,545,323,64,54,593,143,748,318,66,818,222,57,502,228,201 +907,474,431,815,675,468,191,689,136,541,181,153,668,513,141,397,370,880,725,378 +935,605,757,380,745,849,591,764,395,74,807,225,853,822,259,697,476,234,285,50 +154,324,398,360,782,272,56,175,153,791,986,198,785,492,509,467,374,373,391,636 +792,913,271,375,945,163,764,498,591,661,607,913,130,462,502,198,333,746,554,73 +657,149,499,701,638,788,820,490,147,144,669,197,149,68,462,162,615,570,197,137 +259,322,626,288,908,341,489,384,164,357,486,246,777,698,822,432,849,850,740,698 +238,588,542,199,779,267,474,382,156,598,401,395,322,618,395,737,194,410,156,199 +547,714,780,942,818,485,678,405,192,267,704,828,331,517,563,907,68,222,87,237 +773,751,470,735,785,73,749,141,713,602,516,695,853,295,401,148,327,781,251,658 +948,295,86,879,723,391,439,399,326,82,697,405,597,885,130,169,551,154,285,230 +274,380,901,76,783,379,262,597,723,409,390,162,365,435,61,466,264,392,768,167 +589,365,256,885,182,170,255,830,847,525,697,413,192,266,294,631,318,235,309,312 +330,611,199,135,172,252,69,272,616,326,902,320,906,166,189,783,182,494,832,771 +635,945,368,479,788,387,396,198,593,734,667,774,51,73,599,880,617,827,222,221 +782,160,282,768,224,779,271,361,822,72,721,709,911,320,153,72,644,493,809,144 +816,147,386,613,326,479,500,405,83,395,134,702,329,112,776,940,165,824,835,943 +146,505,190,321,909,940,530,508,412,364,493,381,406,64,603,188,188,650,619,76 +728,242,707,410,313,877,831,605,284,357,392,69,731,267,412,194,56,850,525,611 +528,186,377,758,505,610,134,910,528,779,70,826,236,280,610,299,496,189,780,479 +477,548,225,532,477,198,199,425,371,267,377,613,93,394,444,539,72,602,432,388 +189,600,678,591,775,629,398,754,223,980,542,775,944,691,782,88,390,750,384,184 +324,474,392,541,413,714,639,174,68,518,498,464,759,630,275,944,333,327,371,172 +68,231,746,470,771,949,525,265,262,179,196,768,334,69,205,222,457,528,485,469 +148,324,787,665,328,936,136,272,614,789,395,212,52,598,175,618,589,178,848,756 +940,205,500,481,357,815,510,476,482,945,196,625,333,65,728,758,325,139,19,205 +176,627,783,724,732,206,706,256,223,716,440,476,161,207,353,640,906,483,151,542 +327,692,326,333,990,544,830,170,382,112,665,530,177,337,508,728,246,696,627,146 +680,728,629,997,232,765,747,523,685,136,767,531,60,254,74,479,50,477,135,134 +111,181,172,503,52,205,679,228,325,341,512,755,466,77,394,382,632,775,870,313 +466,486,443,166,240,322,470,721,179,638,539,480,536,130,329,783,340,143,637,641 +398,367,531,356,684,501,272,766,681,641,620,632,548,82,530,375,675,644,911,330 +991,269,86,725,144,65,605,882,161,664,617,65,714,169,184,353,228,433,65,93 +230,718,362,832,949,225,64,60,93,325,316,155,776,631,179,942,827,376,724,864 +382,269,489,408,573,295,907,146,275,62,472,85,56,238,443,185,635,774,408,848 +136,770,431,289,614,695,368,325,775,319,493,357,828,365,828,104,816,183,685,133 +697,684,662,386,607,592,111,539,480,728,200,433,528,589,535,748,544,322,135,701 +877,407,500,713,268,252,195,158,721,691,162,725,363,469,93,174,404,855,548,92 +207,642,153,74,699,136,526,338,363,858,243,357,488,949,784,693,663,461,782,268 +529,224,702,75,61,138,636,207,193,131,412,587,79,765,55,73,766,412,606,447 +550,81,16,335,282,608,50,366,595,754,400,384,147,55,242,512,438,129,527,591 +189,779,652,816,477,439,295,498,615,644,694,280,495,722,278,165,354,172,824,495 +947,88,293,512,131,722,714,77,164,559,467,229,850,783,336,244,77,271,251,697 +336,659,848,544,355,141,655,189,942,506,328,496,877,729,137,619,162,68,504,78 +472,622,668,268,229,494,466,403,158,701,369,167,135,779,441,617,946,132,538,192 +481,626,203,507,483,292,54,143,910,225,753,137,596,881,254,861,669,616,286,382 +237,248,136,321,431,531,133,360,487,277,660,942,709,130,766,247,169,217,788,623 +822,563,295,112,753,879,321,833,480,191,642,921,881,603,510,241,497,387,283,749 +823,337,158,617,473,979,240,164,505,489,831,147,54,397,486,624,198,852,232,399 +629,994,600,56,406,294,947,158,628,440,329,698,706,202,149,204,337,369,851,729 +396,644,626,777,682,408,205,691,595,717,229,625,356,145,165,821,261,472,352,760 +668,405,160,404,609,608,549,735,435,626,949,825,231,247,341,92,695,403,411,756 +660,151,692,320,937,262,261,372,503,205,467,180,325,712,502,201,220,880,641,294 +945,757,637,145,507,694,532,632,401,232,644,408,3,328,631,145,151,697,388,334 +400,481,239,825,382,706,544,221,818,474,83,330,74,849,213,411,221,75,850,589 +546,375,509,818,660,724,57,534,87,465,93,625,313,681,337,366,162,880,539,623 +592,411,149,563,260,945,383,234,881,292,548,946,262,943,751,918,851,197,543,265 +74,742,246,235,668,882,263,376,289,781,85,176,135,92,634,530,396,588,906,189 +643,605,510,210,868,242,592,530,87,316,168,447,512,209,524,393,909,222,509,357 +632,818,623,593,274,64,208,174,741,314,753,176,162,271,635,508,163,434,822,181 +262,269,986,364,323,698,381,542,909,526,181,942,143,851,667,258,143,761,774,232 +710,694,376,506,948,647,758,501,847,824,627,550,290,206,386,765,718,73,848,705 +749,767,62,206,394,187,441,523,132,339,282,180,328,473,526,887,716,66,90,588 +830,833,728,466,631,111,981,681,466,747,783,935,244,688,478,758,702,180,609,395 +507,225,381,479,745,111,852,758,154,774,188,377,906,762,722,477,4,548,356,355 +372,109,91,776,134,317,710,362,200,821,762,940,526,136,817,752,16,702,817,776 +778,824,249,686,60,196,327,483,89,604,941,773,2,436,155,937,176,82,334,270 +172,318,560,714,251,470,495,515,185,318,83,57,459,548,327,669,170,249,488,698 +205,533,163,412,292,268,699,475,488,202,495,309,150,778,616,400,466,659,146,724 +849,625,805,174,711,678,65,327,438,727,601,150,463,200,641,67,326,745,589,482 +678,643,318,133,372,373,370,368,390,276,137,887,283,410,194,93,158,223,404,591 +191,476,355,258,372,780,217,461,783,413,707,163,137,747,591,690,111,530,195,439 +261,512,873,59,523,909,177,435,688,152,204,787,224,497,513,621,531,386,133,188 +666,253,104,447,86,823,756,833,773,610,179,700,539,702,192,256,265,255,936,637 +168,706,132,337,360,165,85,656,696,188,331,776,244,57,401,779,94,411,611,948 +763,447,135,722,406,910,87,729,287,331,786,503,287,132,706,111,880,174,675,437 +258,269,711,285,404,271,328,158,508,242,81,717,365,203,604,639,224,470,583,181 +604,949,321,621,217,159,151,700,622,339,62,493,528,482,729,180,111,366,701,607 +465,773,709,248,78,136,830,409,748,545,537,636,775,192,547,491,944,376,249,494 +413,510,424,205,715,948,716,383,180,949,788,754,446,685,689,275,530,388,482,149 +718,644,142,68,747,633,91,590,462,792,153,849,770,662,354,287,378,335,727,982 +183,198,353,827,850,191,716,85,203,181,325,934,506,771,987,628,549,273,751,694 +563,353,774,66,185,602,287,547,819,710,317,78,728,784,110,635,186,997,830,254 +669,207,727,152,377,719,80,175,544,285,595,755,136,75,517,697,317,395,243,461 +173,907,193,234,359,63,247,544,384,384,22,151,663,516,505,284,526,709,254,164 +617,285,62,162,549,468,831,780,497,57,478,453,66,241,91,407,945,777,542,446 +658,171,439,749,382,829,94,927,634,664,397,134,705,316,338,444,467,378,663,478 +354,700,621,599,129,524,595,323,260,491,541,466,171,436,592,263,282,486,330,18 +792,638,535,541,401,489,939,334,93,753,601,262,884,884,372,724,246,72,460,277 +57,391,606,144,279,56,143,243,65,333,495,677,466,723,767,155,786,681,61,828 +314,817,500,468,198,849,293,726,630,394,479,67,68,51,168,206,949,208,471,213 +668,511,777,205,175,135,65,256,758,368,283,598,613,674,881,789,595,381,432,662 +55,722,750,358,643,768,761,631,81,644,462,655,317,397,221,852,333,657,201,203 +847,159,608,81,331,436,180,510,432,501,325,180,283,230,502,200,984,237,761,786 +382,476,624,66,232,694,877,693,792,74,481,396,249,503,605,433,521,749,72,604 +276,60,276,937,818,738,393,471,382,59,53,550,392,641,92,264,883,221,147,240 +853,364,164,493,57,411,270,494,713,446,558,436,470,407,232,669,722,849,760,327 +327,188,313,643,153,243,70,315,175,256,232,410,490,5,146,165,188,278,61,753 +404,523,264,207,707,80,885,690,50,161,259,226,624,637,258,645,284,595,108,883 +265,396,605,69,175,609,885,525,879,676,332,267,465,199,71,87,543,693,497,818 +84,749,313,360,766,818,355,583,725,76,697,728,201,137,688,86,279,827,701,637 +188,471,747,157,771,50,231,317,631,203,601,473,214,619,476,191,472,760,54,817 +589,704,735,625,877,540,763,243,943,591,911,852,545,825,541,766,365,59,431,644 +159,546,369,222,382,619,146,448,701,704,825,784,67,482,528,239,784,293,543,512 +626,340,2,823,605,666,403,177,533,433,473,642,275,385,259,355,85,321,318,532 +946,751,442,681,314,108,387,828,936,691,189,936,58,504,378,558,701,361,698,271 +769,817,850,635,704,492,434,548,606,831,789,169,882,532,360,442,789,370,518,947 +601,276,977,272,685,657,662,719,439,643,880,252,880,701,786,384,680,363,336,882 +680,615,698,199,55,378,478,788,532,385,627,460,150,462,322,329,58,360,214,194 +754,336,90,936,912,851,771,663,8,57,397,602,726,148,467,466,254,764,268,944 +180,139,172,545,276,640,501,821,462,205,627,437,511,206,380,949,488,993,657,185 +462,72,239,822,877,938,481,783,160,443,702,644,393,629,725,334,761,878,788,655 +364,526,930,591,263,406,501,61,704,642,640,711,682,667,774,770,57,188,341,509 +262,883,680,359,386,865,817,597,760,719,766,479,245,438,281,206,948,487,399,158 +948,190,441,789,746,433,331,150,110,819,709,609,290,193,331,946,265,942,930,613 +142,975,788,80,60,239,490,183,412,941,628,942,754,324,438,361,139,611,56,248 +189,290,144,770,936,399,529,996,163,176,432,629,482,370,64,341,824,295,65,819 +490,705,852,159,441,437,747,54,760,152,729,752,170,434,323,128,788,148,270,663 +563,354,165,321,777,634,591,869,631,412,631,667,765,691,239,480,382,265,182,530 +394,815,401,700,517,143,669,434,909,368,170,642,268,881,235,512,695,338,57,473 +544,948,203,507,463,395,603,87,641,312,281,719,756,153,166,674,52,326,251,776 +588,629,830,941,535,461,84,364,694,246,910,182,470,853,549,852,226,461,165,174 +691,330,989,727,636,178,906,705,757,747,506,364,724,162,139,668,186,754,162,226 +399,600,325,207,818,74,631,688,544,180,207,321,539,639,541,91,431,203,492,536 +591,285,619,723,801,701,729,355,263,290,753,325,170,779,248,934,140,246,238,703 +664,70,832,669,146,284,659,253,710,382,918,487,851,880,819,208,66,398,433,644 +130,132,108,823,193,672,179,232,252,470,282,701,822,715,230,472,849,65,150,135 +318,721,821,181,948,643,69,618,318,766,163,255,317,642,832,776,290,481,934,731 +79,436,364,767,366,94,173,882,312,276,509,629,775,533,613,200,67,536,151,757 +403,378,986,778,726,111,605,270,372,240,705,200,721,181,632,161,853,268,150,435 +372,908,671,385,433,162,910,679,828,267,683,383,466,470,201,714,787,54,66,597 +324,824,483,705,174,385,72,134,247,50,338,177,436,534,755,177,757,109,690,330 +335,713,235,506,909,254,614,363,488,75,569,330,314,272,678,708,705,700,171,687 +722,658,157,509,0,129,510,748,188,658,232,77,462,697,550,226,496,56,707,334 +906,625,353,678,619,54,468,369,606,695,718,813,438,284,367,246,497,619,592,252 +481,68,727,507,655,822,90,439,359,463,716,406,721,491,624,400,596,714,438,372 +205,365,579,247,763,821,91,167,232,318,274,791,669,93,69,61,59,276,232,746 +75,719,194,266,691,289,539,689,609,603,195,384,680,273,323,315,357,620,475,808 +174,482,249,775,766,178,911,219,827,532,909,248,228,63,528,295,270,691,606,498 +471,512,110,771,224,241,489,65,635,81,680,741,50,817,666,153,943,195,152,714 +290,747,227,225,379,631,236,804,181,550,621,533,253,383,54,164,462,604,727,373 +728,683,624,388,401,912,79,361,757,818,695,428,82,281,751,372,476,179,909,765 +259,80,181,136,589,532,704,376,354,645,405,540,779,906,312,207,754,249,73,259 +159,215,509,607,883,934,402,223,697,112,408,934,183,361,84,182,942,372,937,370 +207,359,642,661,594,321,504,698,751,438,144,857,779,320,403,321,544,771,192,478 +282,604,174,186,123,499,284,490,936,516,447,146,356,945,667,257,432,243,472,720 +728,243,518,640,186,525,432,510,758,285,659,291,400,948,238,470,550,826,162,58 +880,292,662,588,406,174,471,561,501,90,187,89,403,612,500,355,390,751,468,158 +317,762,987,331,434,174,669,883,595,683,167,165,589,362,604,243,723,53,658,591 +317,780,388,747,497,542,734,943,201,481,165,371,548,767,771,907,196,659,155,513 +549,491,269,699,84,850,64,847,773,233,187,911,183,134,729,527,505,275,654,361 +509,829,2,461,550,357,145,151,783,174,65,379,369,412,683,682,54,470,71,384 +232,185,436,398,632,502,754,433,502,643,878,622,510,776,80,421,73,792,504,713 +132,312,271,502,406,539,823,781,208,465,290,601,235,289,62,259,815,484,106,747 +489,438,906,750,437,944,723,911,225,434,247,882,184,790,278,534,681,327,729,93 +700,816,682,543,265,170,461,511,462,851,454,321,527,504,936,830,680,401,247,221 +632,624,232,279,253,939,825,5,385,700,480,879,202,159,206,195,612,729,588,683 +698,534,605,369,530,746,745,711,525,789,338,332,143,321,705,380,882,200,681,501 +55,512,181,758,937,782,698,888,826,658,611,288,87,197,682,279,196,716,531,724 +830,877,690,259,109,146,935,690,205,477,132,230,382,569,130,404,701,852,719,880 +729,389,377,642,261,468,74,377,133,206,313,634,652,156,256,641,175,291,355,319 diff --git a/16/input.small b/16/input.small new file mode 100644 index 0000000..fe34e40 --- /dev/null +++ b/16/input.small @@ -0,0 +1,12 @@ +class: 1-3 or 5-7 +row: 6-11 or 33-44 +seat: 13-40 or 45-50 + +your ticket: +7,1,14 + +nearby tickets: +7,3,47 +40,4,50 +55,2,20 +38,6,12 diff --git a/16/input.two b/16/input.two new file mode 100644 index 0000000..b48bf37 --- /dev/null +++ b/16/input.two @@ -0,0 +1,11 @@ +class: 0-1 or 4-19 +row: 0-5 or 8-19 +seat: 0-13 or 16-19 + +your ticket: +11,12,13 + +nearby tickets: +3,9,18 +15,1,5 +5,14,9 diff --git a/16/src/main.rs b/16/src/main.rs new file mode 100644 index 0000000..10c5877 --- /dev/null +++ b/16/src/main.rs @@ -0,0 +1,185 @@ +use advent_lib::prelude::*; + +use std::collections::BTreeMap; +use std::collections::BTreeSet; + +#[derive(Clone,Debug)] +struct Range { + min: i64, + max: i64, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + let input = advent_lib::group_lines_by_blanks(input); + + let mut rules: BTreeMap<String,Vec<Range>> = BTreeMap::new(); + + for line in &input[0] { + let colon_point = line.find(':').unwrap(); + let (field_name, rest) = line.split_at(colon_point); + let (_, rest) = rest.split_at(2); + + let mut ranges: Vec<Range> = Vec::new(); + for word in rest.split(' ') { + if word == "or" { + continue; + } + + let parts: Vec<&str> = word.split('-').collect(); + ranges.push(Range { + min: parts[0].parse::<i64>().unwrap(), + max: parts[1].parse::<i64>().unwrap(), + }); + + } + rules.insert(field_name.to_string(), ranges); + } + + let player_ticket = parse_comma_separated_ints(&input[1][1]); + + let mut nearby_tickets = Vec::new(); + for line in input[2].iter().skip(1) { + nearby_tickets.push(parse_comma_separated_ints(&line)); + } + + let mut valid_tickets = Vec::new(); + valid_tickets.push(player_ticket.clone()); + + let mut error_sum = 0; + for ticket in &nearby_tickets { + let mut is_valid = true; + for value in ticket { + let mut found_match = false; + for rule in rules.values() { + if value_obeys_rule(*value, rule) { + found_match = true; + break; + } + } + + if !found_match { + error_sum += value; + is_valid = false; + } + } + + if is_valid { + valid_tickets.push(ticket.clone()); + } + } + + println!("{}", error_sum); + + let mut possibilities: Vec<BTreeSet<String>> = Vec::new(); + for _ in 0 .. player_ticket.len() { + let mut all_fields = BTreeSet::new(); + for field_name in rules.keys() { + all_fields.insert(field_name.clone()); + } + possibilities.push(all_fields); + } + + for ticket in valid_tickets { + //println!("{:?}", possibilities); + for i in 0 .. ticket.len() { + let mut fields_to_remove = Vec::new(); + + for field_name in possibilities[i].iter() { + let rule = rules.get(field_name).unwrap(); + if !value_obeys_rule(ticket[i], rule) { + /* + println!("{}: value {} does not obey rule for {}", + i, ticket[i], field_name); + */ + fields_to_remove.push(field_name.clone()); + } + } + + for field_name in fields_to_remove { + possibilities[i].remove(&field_name); + } + } + } + + //println!("{:?}", possibilities); + + let mut finalized_fields = BTreeSet::new(); + loop { + let mut removed_any = false; + + for i in 0 .. player_ticket.len() { + let mut unique_field = None; + if possibilities[i].len() == 1 { + let field_name = possibilities[i].iter().next().unwrap().clone(); + if finalized_fields.contains(&field_name) { + continue; + } + unique_field = Some((i, field_name)); + } + + match unique_field { + Some((i_to_skip, field_name)) => { + removed_any = true; + + for j in 0 .. possibilities.len() { + if j == i_to_skip { + continue; + } + + possibilities[j].remove(&field_name); + } + + finalized_fields.insert(field_name); + }, + None => { }, + } + } + + if !removed_any { + break; + } + } + + let mut product = 1; + for i in 0 .. possibilities.len() { + let field_name = possibilities[i].iter().next().unwrap(); + if field_name.starts_with("departure ") { + product *= player_ticket[i]; + } + } + + println!("{}", product); + + Ok(()) +} + + +fn parse_comma_separated_ints(line: &str) -> Vec<i64> { + let mut result = Vec::new(); + + for word in line.split(',') { + result.push(word.parse::<i64>().unwrap()); + } + + result +} + + +fn value_obeys_rule(value: i64, rule: &Vec<Range>) -> bool { + for range in rule { + if value >= range.min && value <= range.max { + return true; + } + } + false +} + diff --git a/16/tests/main.rs b/16/tests/main.rs new file mode 100644 index 0000000..ed02398 --- /dev/null +++ b/16/tests/main.rs @@ -0,0 +1,14 @@ +use assert_cmd::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box<dyn std::error::Error>> { + let mut command = Command::cargo_bin("advent_16")?; + + command.arg("input"); + command.assert().success().stdout("25788\n3902565915559\n"); + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index a63ce03..4bad3d1 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -123,6 +123,14 @@ dependencies = [ ] [[package]] +name = "advent_16" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", +] + +[[package]] name = "advent_lib" version = "0.1.0" diff --git a/Cargo.nix b/Cargo.nix index 8ee5464..c2d0abb 100644 --- a/Cargo.nix +++ b/Cargo.nix @@ -178,6 +178,16 @@ rec { # File a bug if you depend on any for non-debug work! debug = internal.debugCrate { inherit packageId; }; }; + "advent_16" = rec { + packageId = "advent_16"; + build = internal.buildRustCrateWithFeatures { + packageId = "advent_16"; + }; + + # Debug support which might change between releases. + # File a bug if you depend on any for non-debug work! + debug = internal.debugCrate { inherit packageId; }; + }; "advent_lib" = rec { packageId = "advent_lib"; build = internal.buildRustCrateWithFeatures { @@ -593,6 +603,31 @@ rec { ]; }; + "advent_16" = rec { + crateName = "advent_16"; + version = "0.1.0"; + edition = "2018"; + crateBin = [ + { name = "advent_16"; path = "src/main.rs"; } + ]; + src = (builtins.filterSource sourceFilter ./16); + authors = [ + "Irene Knapp <ireneista@gmail.com>" + ]; + dependencies = [ + { + name = "advent_lib"; + packageId = "advent_lib"; + } + ]; + devDependencies = [ + { + name = "assert_cmd"; + packageId = "assert_cmd"; + } + ]; + + }; "advent_lib" = rec { crateName = "advent_lib"; version = "0.1.0"; diff --git a/Cargo.toml b/Cargo.toml index d8cc993..4a97c58 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -16,4 +16,5 @@ members = [ "13", "14", "15", + "16", ] |