commit 127cd7561eb98b0095a614344525097c58e898b3
parent 65de606774a770e14adfc354c1701d15f62d985a
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Wed, 16 Dec 2020 19:10:37 -0600
Add 2020 day 16
Diffstat:
| A | 2020/day16/input.txt | | | 265 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2020/day16/main.go | | | 141 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 406 insertions(+), 0 deletions(-)
diff --git a/2020/day16/input.txt b/2020/day16/input.txt
@@ -0,0 +1,265 @@
+departure location: 42-570 or 579-960
+departure station: 45-101 or 118-967
+departure platform: 36-374 or 394-958
+departure track: 48-212 or 233-950
+departure date: 41-481 or 492-953
+departure time: 38-266 or 274-955
+arrival location: 32-560 or 567-951
+arrival station: 44-738 or 762-970
+arrival platform: 40-675 or 685-949
+arrival track: 25-320 or 344-954
+class: 32-806 or 815-959
+duration: 38-121 or 129-958
+price: 35-692 or 706-957
+route: 36-890 or 901-951
+row: 35-282 or 288-964
+seat: 35-445 or 469-954
+train: 45-294 or 317-968
+type: 44-240 or 265-960
+wagon: 32-816 or 825-971
+zone: 30-629 or 637-968
+
+your ticket:
+79,149,97,163,59,151,101,89,173,139,167,61,73,71,137,53,83,157,131,67
+
+nearby tickets:
+945,134,238,221,801,428,519,660,523,537,481,156,845,873,52,172,918,179,188,77
+689,374,471,415,317,722,768,556,557,526,812,508,673,350,481,525,915,788,374,655
+350,537,762,88,926,71,629,611,356,515,413,947,935,826,770,487,358,716,688,907
+767,512,167,728,581,539,819,427,869,709,936,841,275,765,419,275,75,147,790,780
+662,791,783,858,920,77,924,627,151,349,131,130,880,191,816,357,675,69,51,756
+132,688,724,792,164,372,654,351,504,994,430,50,865,279,621,425,266,142,469,606
+267,66,827,164,121,164,511,407,685,712,733,184,64,688,430,440,146,397,873,600
+569,938,841,511,541,546,144,274,708,165,856,280,52,435,428,370,397,868,483,720
+906,890,180,511,758,879,211,844,470,203,198,365,82,407,675,437,717,211,689,521
+140,783,88,234,485,238,71,504,436,84,877,475,627,280,512,816,553,775,437,606
+534,802,823,72,816,545,673,354,541,622,154,92,199,290,639,81,905,345,514,598
+166,431,568,624,602,477,715,97,101,611,479,598,772,613,727,443,617,277,471,383
+240,723,134,540,519,194,935,78,501,130,236,238,586,805,596,103,675,208,649,620
+443,838,591,546,398,91,848,911,522,186,194,864,929,348,206,550,528,177,782,303
+274,194,556,885,400,274,780,135,568,153,823,923,472,281,883,438,604,554,162,919
+637,159,162,53,206,625,473,14,509,721,624,75,68,780,506,539,239,202,606,686
+657,346,600,475,107,794,187,945,76,238,669,771,762,240,762,938,773,832,533,609
+396,96,830,175,783,406,439,867,355,437,230,646,706,97,641,598,595,710,171,495
+60,361,592,159,501,797,829,866,837,292,129,582,606,521,177,836,442,284,552,186
+367,219,665,440,139,79,282,82,639,167,939,864,620,852,672,179,366,873,879,722
+882,627,659,512,544,576,568,531,168,145,477,236,56,841,945,663,930,199,921,837
+163,494,941,848,733,659,658,829,778,796,337,706,476,238,834,524,288,881,870,508
+363,721,826,797,784,152,644,510,670,478,655,406,594,199,706,405,612,296,604,514
+527,524,707,532,737,683,671,353,587,629,707,690,709,156,527,738,289,674,504,906
+819,557,146,199,171,406,785,788,131,208,931,56,947,940,319,169,399,367,240,685
+889,803,875,179,787,762,470,686,147,612,638,235,729,147,859,851,601,831,982,507
+842,187,440,913,480,849,531,432,400,828,470,834,205,409,175,363,183,663,817,715
+673,140,475,441,492,403,504,94,944,659,67,542,776,998,792,205,373,348,850,786
+61,274,773,176,686,553,539,183,530,285,842,370,660,84,72,910,238,854,707,83
+519,76,170,610,837,519,90,651,427,516,471,235,823,919,863,318,292,288,865,850
+769,613,843,94,655,825,545,768,800,917,514,847,445,201,530,869,914,495,568,898
+535,783,164,421,363,912,194,667,425,592,167,76,410,296,79,517,774,173,504,62
+942,290,841,854,397,472,186,795,922,473,234,358,148,442,292,203,949,73,99,284
+187,622,933,191,3,361,948,369,443,520,415,443,81,916,520,880,785,188,544,588
+481,692,437,405,625,162,912,942,395,819,905,860,95,917,481,620,236,879,76,852
+554,88,748,728,158,798,205,348,203,865,413,129,920,589,904,765,71,355,497,923
+129,717,190,398,278,929,511,173,342,906,275,79,205,584,623,785,424,64,848,650
+520,98,702,829,196,509,647,545,212,805,411,161,153,609,96,768,134,399,734,528
+317,731,172,875,395,74,623,374,667,546,595,481,767,159,697,168,556,947,642,293
+800,877,655,940,51,707,274,691,143,831,615,420,240,700,365,60,415,265,544,604
+593,763,217,730,517,429,98,552,535,157,913,515,396,472,407,796,860,347,785,526
+854,400,772,876,637,589,859,732,704,470,83,625,618,80,922,182,603,884,99,61
+395,151,522,889,4,920,542,603,716,663,294,78,56,945,841,611,671,606,688,422
+913,616,83,913,436,669,207,724,502,583,180,725,697,651,196,445,719,777,543,175
+62,343,788,404,654,97,64,890,904,593,97,320,870,174,685,720,320,689,531,816
+627,605,929,719,779,659,637,145,927,707,168,825,723,197,899,521,795,152,353,149
+981,711,274,191,507,914,732,786,193,582,348,834,437,98,93,55,79,712,427,598
+403,234,173,906,427,646,405,98,685,548,880,549,624,356,134,977,166,193,798,92
+93,686,839,270,767,531,776,357,621,294,405,915,690,766,621,943,766,53,291,557
+238,533,370,210,664,366,924,925,90,766,944,692,857,486,621,369,148,927,131,642
+155,847,567,782,494,929,147,828,183,910,554,348,846,771,918,583,829,736,442,818
+509,418,857,638,928,174,833,139,482,445,643,595,201,779,132,532,550,418,288,666
+925,875,443,415,768,784,92,583,65,783,684,799,854,786,212,826,944,913,667,586
+187,841,917,600,70,631,558,539,476,504,733,505,605,427,192,203,594,922,674,501
+659,540,347,435,538,154,551,606,867,295,194,444,652,527,508,201,558,729,79,408
+374,672,588,351,206,885,353,778,70,280,240,152,911,109,728,494,653,153,825,580
+890,910,828,940,945,515,836,941,834,422,527,579,162,137,23,539,831,358,827,830
+851,151,516,142,598,336,523,593,289,275,718,690,929,587,201,706,539,361,524,816
+995,541,618,685,173,522,833,153,352,612,163,479,805,658,579,861,947,135,155,154
+876,909,430,936,661,71,623,827,653,364,933,803,782,685,717,621,52,703,777,947
+171,620,510,345,530,211,717,425,937,711,898,816,615,777,714,785,502,603,724,656
+73,94,781,362,719,369,368,277,285,938,771,198,151,653,159,946,902,692,852,98
+83,904,469,644,849,905,947,946,879,434,914,146,179,569,527,470,847,839,909,636
+234,143,944,764,907,140,435,901,442,179,395,875,139,75,191,784,527,495,3,194
+167,698,532,795,277,403,424,859,557,187,560,656,352,797,805,608,477,907,717,620
+418,551,146,893,409,785,518,72,202,353,554,441,517,364,888,776,912,730,615,834
+709,8,729,589,859,716,200,558,915,477,936,556,733,550,629,265,236,537,345,805
+415,576,146,146,726,52,132,118,649,151,924,320,516,939,54,75,58,911,525,932
+171,548,118,883,547,397,781,585,75,354,659,84,898,830,865,397,144,515,472,152
+403,77,404,939,143,919,752,843,101,594,235,91,413,550,856,568,355,76,803,266
+691,88,925,101,354,629,169,800,74,668,166,72,711,81,625,79,503,762,300,604
+121,624,587,190,200,706,904,59,845,191,101,822,208,850,558,801,64,180,939,546
+11,917,784,673,786,207,429,834,883,833,351,505,526,591,772,278,834,716,442,883
+746,774,550,443,666,78,848,469,832,189,547,854,907,836,913,875,361,627,847,816
+845,553,495,516,359,845,618,556,173,471,612,688,532,276,409,92,164,555,362,271
+166,779,470,167,653,485,604,170,54,198,266,728,533,799,95,171,517,67,769,170
+707,918,513,358,660,433,604,858,371,869,907,886,232,942,359,735,420,880,853,361
+516,860,152,613,827,481,945,826,152,240,360,913,723,949,785,570,637,404,864,2
+275,768,836,589,948,755,583,872,815,650,345,55,402,859,53,602,775,96,591,731
+202,171,541,586,860,77,205,672,858,498,736,782,175,338,364,151,919,438,690,589
+842,139,666,282,587,776,93,876,268,638,499,145,162,171,61,407,721,715,511,764
+165,92,905,582,856,357,366,888,226,88,514,179,913,289,888,932,492,471,672,56
+346,729,706,492,894,200,669,500,638,906,796,645,610,470,878,538,515,568,233,542
+207,920,858,519,437,830,944,152,545,928,715,473,146,383,423,234,541,802,398,937
+687,143,424,532,804,68,732,210,948,997,638,405,503,425,177,625,170,292,209,826
+865,590,502,500,917,78,876,369,69,319,662,998,867,558,396,518,413,908,516,861
+621,522,713,508,685,275,89,730,192,929,497,238,826,997,205,885,715,592,368,901
+589,935,863,187,516,813,600,793,815,355,533,529,735,617,365,787,535,860,943,642
+148,895,915,345,88,599,829,829,212,180,948,668,851,417,801,198,194,555,938,478
+530,621,120,606,865,500,720,85,933,395,155,424,844,285,656,606,206,642,643,405
+470,935,178,427,577,593,804,591,149,493,644,724,517,554,185,729,850,417,878,796
+133,545,165,663,237,565,934,651,54,166,595,290,202,204,403,640,663,528,857,579
+359,160,58,603,931,659,131,545,469,473,482,522,142,607,864,888,909,154,61,502
+185,405,62,779,85,217,651,778,165,796,725,834,881,771,764,828,131,292,372,593
+437,158,541,155,119,792,71,854,633,159,363,621,352,523,170,915,150,873,549,236
+805,65,873,389,728,825,716,830,595,888,568,878,797,616,265,933,445,592,775,169
+84,715,718,924,131,181,75,914,825,622,295,606,579,692,833,614,84,58,526,788
+54,587,526,925,322,471,505,836,923,945,196,534,235,443,932,629,422,361,544,614
+585,363,776,66,945,884,586,622,650,544,265,985,294,858,920,801,658,930,590,661
+176,86,137,523,612,799,184,212,916,908,825,152,710,120,943,584,985,87,68,919
+618,439,874,479,432,873,887,350,354,170,578,862,835,844,883,716,907,501,66,774
+74,827,345,927,133,140,90,65,362,157,983,188,707,182,83,616,869,873,593,584
+96,137,583,67,411,96,601,512,707,93,3,597,136,719,508,674,764,99,707,142
+314,441,508,933,915,866,688,443,471,163,430,519,587,907,944,781,546,276,938,526
+143,408,910,583,828,441,914,186,366,95,886,158,721,840,975,493,121,494,119,63
+771,781,274,599,153,560,531,320,498,590,350,131,401,75,356,749,237,64,156,589
+788,424,62,399,902,368,589,855,539,183,760,591,94,131,924,203,614,76,849,913
+618,432,718,540,407,854,639,579,866,349,471,601,266,548,766,790,798,597,792,216
+805,499,378,903,100,429,722,926,265,345,918,928,601,850,690,570,945,167,778,233
+642,586,879,856,54,395,891,183,182,602,625,637,374,405,621,907,620,538,423,872
+368,423,655,287,942,208,797,600,481,413,88,166,732,657,783,949,794,155,130,853
+724,177,780,490,506,409,278,205,530,648,629,238,834,669,871,551,854,856,650,873
+717,820,200,653,435,266,656,160,692,170,400,877,690,727,54,191,792,294,539,409
+569,121,738,521,401,769,186,638,146,73,392,151,868,560,537,289,612,428,64,685
+523,584,233,804,187,139,409,624,897,430,205,94,674,519,278,204,506,611,266,663
+879,424,770,62,73,419,346,860,194,594,707,911,915,203,308,918,288,360,925,618
+90,350,366,871,211,786,598,439,512,279,285,120,855,481,513,864,100,282,732,601
+601,151,480,498,178,725,496,363,782,918,235,875,474,237,145,948,20,673,830,191
+176,155,626,212,890,860,298,181,590,607,718,945,617,863,915,660,164,580,177,648
+478,780,927,824,397,348,189,368,776,854,613,798,179,519,542,917,363,603,525,233
+354,131,865,805,594,539,405,233,155,472,875,516,912,276,135,379,833,729,239,612
+628,913,145,757,549,907,137,592,163,602,140,567,847,500,503,643,608,832,481,510
+197,567,12,281,909,265,444,207,727,606,848,366,431,293,626,166,274,55,178,558
+539,485,881,477,150,178,119,506,856,710,129,366,918,530,294,806,157,432,603,131
+790,372,713,148,623,422,233,81,407,151,53,506,669,644,74,658,443,840,894,879
+68,422,591,396,849,85,782,733,514,801,151,611,75,147,423,838,69,533,741,722
+854,437,597,95,799,158,674,602,499,836,542,629,92,647,320,203,557,617,183,486
+766,545,898,767,714,842,569,516,544,664,403,438,552,157,840,707,187,876,154,722
+645,56,616,909,978,798,825,414,886,608,90,173,119,939,668,142,559,579,204,148
+399,595,908,205,527,670,355,152,706,75,89,363,277,473,824,921,910,208,922,141
+736,415,512,207,194,797,697,876,873,860,771,178,87,445,149,943,770,548,547,827
+77,816,668,299,144,691,946,150,233,518,235,94,829,825,436,168,239,156,198,536
+130,781,319,856,735,188,642,590,174,170,504,844,711,904,499,817,841,367,100,780
+638,943,445,139,280,598,947,153,979,404,936,437,474,168,496,155,442,345,52,856
+920,725,526,637,495,606,767,670,88,204,621,723,931,846,373,218,508,766,92,869
+548,683,597,81,716,480,586,644,118,184,911,348,690,865,801,628,202,656,421,781
+732,188,518,837,347,520,543,923,930,777,650,712,179,841,2,917,539,873,317,726
+70,74,190,686,555,502,286,359,803,592,234,413,862,762,713,786,54,516,579,590
+855,60,405,724,303,718,867,690,887,834,618,423,847,591,638,165,513,804,420,802
+114,477,659,67,595,675,687,512,170,583,366,733,499,481,941,830,523,926,538,481
+286,675,598,906,206,182,394,724,883,146,497,829,132,854,148,768,357,191,480,916
+121,779,876,926,346,199,132,668,626,557,591,547,790,157,51,653,646,157,654,574
+151,643,618,862,690,935,157,180,430,265,590,88,238,503,286,844,787,83,602,410
+663,202,92,589,709,916,52,866,863,661,694,498,799,832,560,766,75,63,522,588
+232,826,184,776,362,410,189,201,424,711,781,872,206,133,730,319,618,806,773,516
+789,731,361,904,190,454,82,70,400,850,133,711,500,773,480,282,427,144,931,724
+195,69,786,54,908,805,292,50,615,946,804,932,975,367,666,396,344,642,733,197
+947,783,55,802,287,860,796,866,281,523,317,150,691,52,174,716,56,603,671,395
+662,594,555,781,569,140,184,559,502,815,318,266,774,780,934,925,606,479,590,983
+792,520,160,163,599,61,602,200,864,423,402,627,616,934,658,431,472,791,920,982
+64,437,690,155,433,507,98,346,239,904,359,208,986,906,90,609,878,167,937,352
+975,738,119,364,522,789,946,71,169,183,495,614,568,175,424,345,666,801,602,554
+735,406,417,360,724,406,196,344,171,872,113,858,646,394,143,608,773,886,504,675
+904,500,590,374,387,79,374,864,666,614,361,593,847,416,357,725,804,77,59,177
+902,380,346,883,528,901,581,419,371,190,728,668,168,620,594,98,602,777,140,371
+237,528,783,371,225,544,837,643,674,919,424,779,658,568,147,182,717,138,715,639
+781,412,145,603,524,715,433,397,781,911,351,906,155,406,847,520,551,712,979,470
+937,532,490,498,857,266,801,945,422,598,645,148,65,792,901,912,826,917,802,907
+827,292,401,137,589,555,657,210,118,164,793,138,769,88,99,784,409,886,50,103
+438,865,538,644,419,90,906,711,689,864,605,441,121,714,798,24,590,647,434,96
+355,604,587,293,694,75,77,531,614,772,557,82,531,239,883,591,426,71,581,721
+649,367,151,198,567,317,176,907,605,492,127,587,614,907,864,666,235,901,908,415
+513,810,54,730,181,500,539,471,374,612,673,209,671,921,350,608,172,647,613,120
+486,440,906,145,471,840,73,403,858,669,146,863,552,98,816,946,516,207,441,604
+237,532,775,638,517,665,516,600,751,585,499,712,626,570,943,515,943,420,89,173
+942,850,768,872,603,376,797,706,509,669,725,358,786,352,922,281,529,653,194,919
+594,190,559,350,58,847,210,14,435,411,773,825,414,804,942,276,729,922,827,197
+943,664,348,540,147,653,146,436,157,474,56,405,99,536,361,316,87,517,516,887
+444,537,278,533,163,625,61,766,738,608,52,795,361,896,137,396,142,646,843,348
+318,189,614,905,175,480,121,685,292,158,511,353,52,640,618,892,169,422,642,348
+657,98,291,721,403,283,410,887,935,736,132,872,933,433,918,834,277,394,142,121
+785,233,18,472,938,187,265,717,626,727,768,706,58,884,279,100,429,476,882,595
+212,559,928,643,193,730,835,550,172,58,18,920,764,735,568,364,431,496,583,764
+619,522,588,834,797,985,509,519,204,348,288,890,419,555,799,399,840,374,880,579
+420,591,501,598,737,93,364,587,403,778,778,348,826,571,363,831,925,620,766,527
+647,549,692,407,97,828,656,863,905,472,775,603,648,880,865,84,172,715,88,683
+205,133,764,481,137,787,407,295,196,152,118,642,549,57,860,852,802,789,67,148
+598,287,932,932,833,918,172,210,690,872,179,662,722,54,282,85,860,615,661,186
+410,792,668,716,846,675,842,619,790,874,665,610,187,537,417,58,795,399,169,991
+696,516,860,356,529,93,525,890,907,569,435,947,531,722,943,207,944,57,793,266
+356,928,764,165,671,186,366,590,150,510,877,191,484,929,92,641,885,602,884,345
+100,240,662,614,763,123,212,121,194,647,148,773,405,406,767,548,790,587,790,51
+597,414,427,68,634,194,605,672,722,137,156,149,645,581,946,923,774,828,845,767
+185,657,285,133,395,830,83,880,473,141,514,403,72,910,608,86,422,145,887,664
+59,851,426,594,663,949,581,879,315,98,568,412,877,191,78,177,92,515,776,317
+864,904,525,239,147,833,76,854,544,734,239,187,355,201,850,785,279,280,134,811
+558,118,602,917,474,765,399,882,533,504,55,145,142,758,90,167,137,420,411,57
+906,949,628,480,138,762,708,947,384,765,655,440,79,170,120,855,435,187,914,525
+877,732,179,96,180,865,619,626,571,294,544,579,623,500,629,588,653,797,932,845
+291,855,424,640,474,771,721,517,320,185,610,943,758,276,499,581,99,433,199,282
+167,581,347,770,651,177,62,474,709,879,660,671,772,943,185,911,878,791,532,696
+370,789,931,910,935,21,521,727,935,443,185,628,935,53,554,505,793,548,583,531
+639,134,400,872,825,304,517,492,686,597,144,469,99,478,772,840,202,716,879,500
+716,849,911,781,868,704,201,533,431,612,432,647,598,430,733,406,280,551,835,729
+162,274,170,135,772,347,403,736,182,475,803,398,547,277,789,692,18,443,667,276
+571,645,87,364,931,368,836,494,408,902,73,616,197,67,907,816,622,438,471,372
+156,434,856,497,23,879,872,166,59,130,95,171,278,53,147,53,768,534,537,774
+440,238,163,647,907,691,735,159,177,927,448,430,623,721,627,553,856,839,200,288
+363,886,625,716,945,858,618,445,294,550,625,354,176,196,644,207,355,823,476,358
+203,368,942,887,652,397,719,686,622,850,55,141,346,97,868,68,98,100,148,24
+437,841,527,783,825,345,738,916,945,82,353,977,353,534,349,646,884,662,843,600
+614,59,793,441,643,846,20,588,166,649,524,668,425,166,922,238,509,886,881,607
+54,198,784,704,265,580,281,177,873,708,200,764,71,99,781,428,767,930,792,404
+91,765,304,551,360,65,670,136,481,666,502,401,830,579,55,560,672,210,437,851
+408,636,909,289,408,529,54,622,510,833,506,135,494,938,403,206,523,806,417,133
+665,642,585,685,282,268,921,367,211,524,736,846,169,479,904,581,560,174,717,350
+946,365,920,692,180,819,802,586,208,541,686,767,726,210,580,555,395,716,883,359
+773,832,685,638,848,611,118,367,654,591,927,883,778,227,928,406,492,118,58,617
+83,729,417,805,717,836,816,537,199,84,630,318,291,496,945,395,802,776,522,477
+57,780,644,69,506,835,785,130,436,773,131,58,352,271,874,188,641,548,193,86
+862,69,948,720,474,540,619,118,586,594,233,643,471,820,494,845,504,539,844,362
+520,570,405,1,559,609,732,434,349,440,582,798,768,940,472,510,706,423,173,589
+806,413,173,542,525,409,686,708,640,294,706,197,737,627,619,948,713,344,284,919
+60,669,873,830,63,655,768,519,819,617,640,639,803,96,546,672,717,502,616,664
+160,471,365,672,424,783,865,351,73,50,707,864,433,165,929,702,587,55,932,208
+774,924,724,92,597,99,445,187,102,442,405,766,853,61,542,320,800,292,493,839
+854,275,477,775,23,165,911,359,55,153,501,889,906,439,73,667,599,280,179,586
+391,598,317,63,532,769,611,649,949,369,550,692,806,276,947,146,924,920,803,513
+410,765,190,833,623,608,444,175,638,658,157,306,141,601,145,524,794,266,885,783
+265,908,349,288,194,895,843,876,533,706,398,588,162,405,544,646,805,685,198,711
+592,737,373,654,164,669,583,435,367,65,887,402,371,995,234,538,570,432,166,357
+88,101,904,166,293,84,783,199,275,729,732,661,916,939,886,949,353,16,627,159
+206,904,480,94,269,500,781,68,349,412,853,194,95,289,556,627,541,429,197,595
+434,109,777,99,87,345,351,76,721,196,920,929,854,429,494,570,551,623,616,545
+208,81,365,611,614,358,147,511,73,606,149,442,316,98,276,787,428,202,856,367
+856,301,599,922,737,686,147,195,524,873,365,860,276,292,474,799,613,57,669,601
+514,472,55,946,291,941,204,524,59,63,271,589,570,194,713,71,537,720,602,529
+428,268,540,690,501,237,426,716,346,84,928,692,426,555,767,180,129,194,650,883
+601,403,374,179,834,279,119,843,604,396,186,881,183,167,96,722,719,647,696,479
+723,618,210,203,292,470,842,777,610,139,395,477,286,785,862,834,514,560,600,888
+52,568,531,173,684,65,529,415,500,130,670,176,430,533,281,908,349,192,848,204
+723,649,550,492,410,781,556,234,870,708,72,567,181,524,861,435,394,349,351,334
+508,186,169,281,822,501,945,501,403,706,499,210,649,371,764,707,916,166,366,725
+772,94,775,53,397,114,408,365,362,736,592,777,92,410,835,190,479,863,349,940
+939,400,583,790,445,471,211,51,82,848,164,886,515,362,406,272,929,513,180,548
+649,758,193,854,204,709,834,736,709,168,422,366,848,948,351,787,838,838,674,475
+432,467,368,168,670,134,442,407,806,319,927,627,519,398,919,354,551,363,904,720
+897,569,266,908,801,859,861,609,690,120,142,209,195,558,833,85,797,472,503,167
+910,282,800,842,182,146,88,210,768,133,276,815,349,787,582,283,172,833,942,712
+431,411,560,940,410,553,928,492,838,623,277,646,737,134,169,23,845,552,826,93
diff --git a/2020/day16/main.go b/2020/day16/main.go
@@ -0,0 +1,141 @@
+package main
+
+import (
+ "bufio"
+ "fmt"
+ "os"
+ "regexp"
+ "strconv"
+ "strings"
+)
+
+type req struct {
+ min1 int
+ max1 int
+ min2 int
+ max2 int
+}
+
+func (this req) isValid(x int) bool {
+ return (x >= this.min1 && x <= this.max1) || (x >= this.min2 && x <= this.max2)
+}
+
+func readInput(filename string) (reqs map[string]req, tickets [][]int) {
+ file, _ := os.Open(filename)
+ defer file.Close()
+
+ reqs = map[string]req{}
+ tickets = [][]int{}
+ scanner := bufio.NewScanner(file)
+ reqMatcher := regexp.MustCompile(`([a-z ]+): ([0-9]+)-([0-9]+) or ([0-9]+)-([0-9]+)`)
+ ticketMatcher := regexp.MustCompile(`([0-9]+),?`)
+ for scanner.Scan() {
+ if line := scanner.Text(); line == "" {
+ break
+ } else {
+ matches := reqMatcher.FindAllStringSubmatch(line, -1)
+ min1, _ := strconv.Atoi(matches[0][2])
+ max1, _ := strconv.Atoi(matches[0][3])
+ min2, _ := strconv.Atoi(matches[0][4])
+ max2, _ := strconv.Atoi(matches[0][5])
+ reqs[matches[0][1]] = req{min1, max1, min2, max2}
+ }
+ }
+ for scanner.Scan() {
+ matches := ticketMatcher.FindAllStringSubmatch(scanner.Text(), -1)
+ if len(matches) > 0 {
+ newTicket := []int{}
+ for _, v := range matches {
+ num, _ := strconv.Atoi(v[1])
+ newTicket = append(newTicket, num)
+ }
+ tickets = append(tickets, newTicket)
+ }
+ }
+ return
+}
+
+func main() {
+ reqs, tickets := readInput("./input.txt")
+ // 24980
+ fmt.Println(part1(reqs, tickets))
+ // 809376774329
+ fmt.Println(part2(reqs, tickets))
+}
+
+func part1(reqs map[string]req, tickets [][]int) (errRate int) {
+ for _, ticket := range tickets[1:] { // Skip my ticket
+ for _, num := range ticket {
+ anyValid := false
+ for _, req := range reqs {
+ if req.isValid(num) {
+ anyValid = true
+ break
+ }
+ }
+ if !anyValid {
+ errRate += num
+ }
+ }
+ }
+ return
+}
+
+func countZeros(x []int) (count int, lastZeroIdx int) {
+ for i, v := range x {
+ if v == 0 {
+ count += 1
+ lastZeroIdx = i
+ }
+ }
+ return
+}
+
+func part2(reqs map[string]req, tickets [][]int) (res int) {
+ invalidCount := map[string][]int{}
+ for field, _ := range reqs {
+ invalidCount[field] = make([]int, len(tickets[0]))
+ }
+TicketCheck:
+ for _, ticket := range tickets[1:] { // Skip my ticket
+ for _, num := range ticket {
+ anyValid := false
+ for _, req := range reqs {
+ if req.isValid(num) {
+ anyValid = true
+ break
+ }
+ }
+ if !anyValid {
+ continue TicketCheck
+ }
+ }
+ for i, num := range ticket {
+ for field, req := range reqs {
+ if !req.isValid(num) {
+ invalidCount[field][i] += 1
+ }
+ }
+ }
+ }
+ fieldIdx := map[string]int{}
+ for len(invalidCount) > 0 {
+ for field, counts := range invalidCount {
+ if count, idx := countZeros(counts); count == 1 {
+ fieldIdx[field] = idx
+ delete(invalidCount, field)
+ for _, counts := range invalidCount {
+ counts[idx] = 1
+ }
+ break
+ }
+ }
+ }
+ res = 1
+ for field, idx := range fieldIdx {
+ if strings.HasPrefix(field, "departure") {
+ res *= tickets[0][idx]
+ }
+ }
+ return
+}