Last active
December 9, 2020 06:20
-
-
Save SleeplessByte/d5f31923df3e22e6c3d38108880e892f to your computer and use it in GitHub Desktop.
Advent of Code 2020: Day 9 - Encoding Error
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require 'benchmark' | |
| def find_sum_of_uniques(candidates, check) | |
| skip = check / 2.to_f | |
| candidates.each do |x| | |
| next if x == skip | |
| candidates.each do |y| | |
| next if y == skip | |
| return true if x + y == check | |
| end | |
| end | |
| false | |
| end | |
| def find_invalid(numbers, preamble: 25) | |
| pointer = preamble | |
| candidates = numbers[0...preamble] | |
| while pointer < numbers.length | |
| check = numbers[pointer] | |
| unless find_sum_of_uniques(candidates, check) | |
| return check | |
| end | |
| candidates.shift | |
| candidates.push(numbers[pointer]) | |
| pointer += 1 | |
| end | |
| end | |
| def find_sum_set(numbers, match) | |
| pointer_left = 0 | |
| pointer_right = 1 | |
| sum = numbers[pointer_left..pointer_right].sum | |
| checks = 0 | |
| while sum != match | |
| checks += 1 | |
| # puts "#{match} != #{numbers[pointer_left]} + (...#{[pointer_right - pointer_left - 2, 0].max} numbers) + #{numbers[pointer_right]}" | |
| if sum < match | |
| pointer_right += 1 | |
| sum += numbers[pointer_right] | |
| elsif sum > match | |
| sum -= numbers[pointer_left] | |
| pointer_left += 1 | |
| end | |
| end | |
| numbers[pointer_left...pointer_right].tap do |x| | |
| # puts "#{match} == #{numbers[pointer_left..pointer_right].sort.join(" + ")}" | |
| puts "\nChecked #{checks} sets to find the sum set" | |
| end | |
| end | |
| numbers = File.readlines('input.txt').map(&:to_i) | |
| Benchmark.bmbm do |b| | |
| b.report do | |
| invalid = find_invalid(numbers, preamble: 25) | |
| set = find_sum_set(numbers, invalid) | |
| puts "xmas: #{set.minmax.sum}" | |
| end | |
| end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 35 | |
| 20 | |
| 15 | |
| 25 | |
| 47 | |
| 40 | |
| 62 | |
| 55 | |
| 65 | |
| 95 | |
| 102 | |
| 117 | |
| 150 | |
| 182 | |
| 127 | |
| 219 | |
| 299 | |
| 277 | |
| 309 | |
| 576 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 11 | |
| 1 | |
| 33 | |
| 5 | |
| 20 | |
| 31 | |
| 49 | |
| 26 | |
| 3 | |
| 35 | |
| 25 | |
| 39 | |
| 29 | |
| 28 | |
| 23 | |
| 44 | |
| 19 | |
| 4 | |
| 21 | |
| 2 | |
| 7 | |
| 41 | |
| 10 | |
| 32 | |
| 14 | |
| 68 | |
| 6 | |
| 11 | |
| 8 | |
| 18 | |
| 27 | |
| 20 | |
| 71 | |
| 13 | |
| 9 | |
| 16 | |
| 73 | |
| 52 | |
| 34 | |
| 25 | |
| 79 | |
| 15 | |
| 12 | |
| 17 | |
| 113 | |
| 94 | |
| 19 | |
| 24 | |
| 21 | |
| 22 | |
| 114 | |
| 31 | |
| 23 | |
| 26 | |
| 28 | |
| 29 | |
| 32 | |
| 47 | |
| 27 | |
| 39 | |
| 33 | |
| 80 | |
| 35 | |
| 38 | |
| 34 | |
| 36 | |
| 127 | |
| 40 | |
| 41 | |
| 227 | |
| 42 | |
| 43 | |
| 45 | |
| 44 | |
| 48 | |
| 54 | |
| 70 | |
| 71 | |
| 65 | |
| 55 | |
| 110 | |
| 60 | |
| 72 | |
| 74 | |
| 114 | |
| 77 | |
| 69 | |
| 90 | |
| 75 | |
| 187 | |
| 78 | |
| 100 | |
| 81 | |
| 83 | |
| 85 | |
| 86 | |
| 118 | |
| 93 | |
| 92 | |
| 102 | |
| 115 | |
| 120 | |
| 127 | |
| 175 | |
| 129 | |
| 160 | |
| 132 | |
| 144 | |
| 169 | |
| 147 | |
| 252 | |
| 150 | |
| 153 | |
| 156 | |
| 179 | |
| 178 | |
| 164 | |
| 166 | |
| 168 | |
| 185 | |
| 204 | |
| 208 | |
| 222 | |
| 194 | |
| 284 | |
| 235 | |
| 276 | |
| 256 | |
| 261 | |
| 273 | |
| 330 | |
| 297 | |
| 291 | |
| 447 | |
| 300 | |
| 303 | |
| 306 | |
| 378 | |
| 320 | |
| 332 | |
| 334 | |
| 374 | |
| 351 | |
| 485 | |
| 379 | |
| 398 | |
| 455 | |
| 478 | |
| 634 | |
| 491 | |
| 647 | |
| 517 | |
| 553 | |
| 896 | |
| 977 | |
| 750 | |
| 588 | |
| 591 | |
| 606 | |
| 603 | |
| 623 | |
| 626 | |
| 652 | |
| 654 | |
| 685 | |
| 829 | |
| 725 | |
| 1132 | |
| 777 | |
| 1084 | |
| 946 | |
| 969 | |
| 995 | |
| 1008 | |
| 1120 | |
| 1123 | |
| 1070 | |
| 1707 | |
| 1722 | |
| 1431 | |
| 1273 | |
| 1179 | |
| 1217 | |
| 1876 | |
| 1857 | |
| 1249 | |
| 1337 | |
| 1306 | |
| 1339 | |
| 1502 | |
| 1554 | |
| 1671 | |
| 1785 | |
| 2625 | |
| 1964 | |
| 2319 | |
| 2039 | |
| 2901 | |
| 2078 | |
| 2190 | |
| 3215 | |
| 2886 | |
| 2704 | |
| 2396 | |
| 4375 | |
| 3149 | |
| 2428 | |
| 2466 | |
| 2555 | |
| 2588 | |
| 2645 | |
| 2643 | |
| 2808 | |
| 2841 | |
| 3456 | |
| 3225 | |
| 4358 | |
| 3749 | |
| 4951 | |
| 4229 | |
| 4435 | |
| 4117 | |
| 4778 | |
| 5363 | |
| 5681 | |
| 4824 | |
| 5100 | |
| 7333 | |
| 5274 | |
| 12433 | |
| 5016 | |
| 5288 | |
| 5021 | |
| 6304 | |
| 7664 | |
| 5451 | |
| 5484 | |
| 7759 | |
| 9386 | |
| 6681 | |
| 9138 | |
| 7978 | |
| 7866 | |
| 8552 | |
| 8664 | |
| 10500 | |
| 8895 | |
| 9602 | |
| 9840 | |
| 14426 | |
| 9845 | |
| 10037 | |
| 19175 | |
| 10290 | |
| 14346 | |
| 11697 | |
| 10309 | |
| 10472 | |
| 10935 | |
| 12165 | |
| 12132 | |
| 14036 | |
| 19447 | |
| 14547 | |
| 17818 | |
| 15844 | |
| 16418 | |
| 28111 | |
| 22202 | |
| 27420 | |
| 18497 | |
| 18735 | |
| 19442 | |
| 20154 | |
| 26134 | |
| 19882 | |
| 20327 | |
| 24837 | |
| 20762 | |
| 24655 | |
| 20781 | |
| 21244 | |
| 27353 | |
| 45850 | |
| 24297 | |
| 44991 | |
| 28583 | |
| 32262 | |
| 34429 | |
| 34236 | |
| 46016 | |
| 35153 | |
| 38617 | |
| 37232 | |
| 39741 | |
| 37939 | |
| 38177 | |
| 39596 | |
| 40036 | |
| 59183 | |
| 66612 | |
| 41089 | |
| 45078 | |
| 41543 | |
| 49827 | |
| 78278 | |
| 63736 | |
| 68665 | |
| 78112 | |
| 75849 | |
| 73574 | |
| 79482 | |
| 66498 | |
| 108406 | |
| 69389 | |
| 119821 | |
| 72385 | |
| 78321 | |
| 75171 | |
| 81579 | |
| 77535 | |
| 98779 | |
| 79632 | |
| 85114 | |
| 82632 | |
| 122613 | |
| 116260 | |
| 86621 | |
| 133125 | |
| 147501 | |
| 156390 | |
| 130234 | |
| 177795 | |
| 135887 | |
| 138883 | |
| 151109 | |
| 144560 | |
| 141669 | |
| 159006 | |
| 141774 | |
| 147556 | |
| 157167 | |
| 200934 | |
| 152706 | |
| 183893 | |
| 209866 | |
| 167746 | |
| 212866 | |
| 219746 | |
| 228395 | |
| 268966 | |
| 202881 | |
| 481832 | |
| 410635 | |
| 283443 | |
| 266121 | |
| 269117 | |
| 274770 | |
| 280447 | |
| 354535 | |
| 286229 | |
| 344655 | |
| 289225 | |
| 535238 | |
| 637978 | |
| 300262 | |
| 1048613 | |
| 320452 | |
| 907095 | |
| 351639 | |
| 370627 | |
| 436712 | |
| 415747 | |
| 644917 | |
| 431276 | |
| 469002 | |
| 492106 | |
| 540891 | |
| 543887 | |
| 549564 | |
| 751728 | |
| 786374 | |
| 736974 | |
| 846641 | |
| 836761 | |
| 575454 | |
| 589487 | |
| 609677 | |
| 1015544 | |
| 875716 | |
| 620714 | |
| 946081 | |
| 672091 | |
| 1507650 | |
| 722266 | |
| 801903 | |
| 847023 | |
| 1566795 | |
| 900278 | |
| 1292805 | |
| 961108 | |
| 1032997 | |
| 1090455 | |
| 1093451 | |
| 1125018 | |
| 1583997 | |
| 1164941 | |
| 1210201 | |
| 1185131 | |
| 1196168 | |
| 1199164 | |
| 2085917 | |
| 1774618 | |
| 1342980 | |
| 1714165 | |
| 1868259 | |
| 1705088 | |
| 2540350 | |
| 2025296 | |
| 1524169 | |
| 1834900 | |
| 2783161 | |
| 1861386 | |
| 1933275 | |
| 2433435 | |
| 1994105 | |
| 2928351 | |
| 2183906 | |
| 2350072 | |
| 2324182 | |
| 4307330 | |
| 2553181 | |
| 4639098 | |
| 3575551 | |
| 6332626 | |
| 3392428 | |
| 3048068 | |
| 2867149 | |
| 4716436 | |
| 3229257 | |
| 3359069 | |
| 3549465 | |
| 3385555 | |
| 5733371 | |
| 3457444 | |
| 3696286 | |
| 3794661 | |
| 3855491 | |
| 5579329 | |
| 6633203 | |
| 4178011 | |
| 4674254 | |
| 5398140 | |
| 6778722 | |
| 6961106 | |
| 5420330 | |
| 5601249 | |
| 5915217 | |
| 6096406 | |
| 6252704 | |
| 8782366 | |
| 6226218 | |
| 6563435 | |
| 6588326 | |
| 6614812 | |
| 7081841 | |
| 6842999 | |
| 7972672 | |
| 7635455 | |
| 7153730 | |
| 13411925 | |
| 7650152 | |
| 8033502 | |
| 8852265 | |
| 11262580 | |
| 9576151 | |
| 10072394 | |
| 13932452 | |
| 11021579 | |
| 11335547 | |
| 11516466 | |
| 11697655 | |
| 12011623 | |
| 13696653 | |
| 19803945 | |
| 12789653 | |
| 12841030 | |
| 13151761 | |
| 13431325 | |
| 17950359 | |
| 13924840 | |
| 13996729 | |
| 15126402 | |
| 19166618 | |
| 31501600 | |
| 17226303 | |
| 15683654 | |
| 19731157 | |
| 21588860 | |
| 43513223 | |
| 23997234 | |
| 21093973 | |
| 22719234 | |
| 28247882 | |
| 23033202 | |
| 25513195 | |
| 24487308 | |
| 30922956 | |
| 25630683 | |
| 25941414 | |
| 35513700 | |
| 21806024 | |
| 37272514 | |
| 27356165 | |
| 32909957 | |
| 75014823 | |
| 29123131 | |
| 45091207 | |
| 34850272 | |
| 41713611 | |
| 35414811 | |
| 76014163 | |
| 40825130 | |
| 42682833 | |
| 42899997 | |
| 43813207 | |
| 44525258 | |
| 52156333 | |
| 44839226 | |
| 46293332 | |
| 60928006 | |
| 66766544 | |
| 47436707 | |
| 47747438 | |
| 89364484 | |
| 49162189 | |
| 69553462 | |
| 104039058 | |
| 60266122 | |
| 73648389 | |
| 70836742 | |
| 63973403 | |
| 70265083 | |
| 127694550 | |
| 112422455 | |
| 76239941 | |
| 95455521 | |
| 83507963 | |
| 87208091 | |
| 88652433 | |
| 88338465 | |
| 105767232 | |
| 91132558 | |
| 92275933 | |
| 95184145 | |
| 96909627 | |
| 107702829 | |
| 151398680 | |
| 109428311 | |
| 187547021 | |
| 113135592 | |
| 141101825 | |
| 124239525 | |
| 130531205 | |
| 134238486 | |
| 153773046 | |
| 217341766 | |
| 146505024 | |
| 159747904 | |
| 194419665 | |
| 163448032 | |
| 170716054 | |
| 222890919 | |
| 175546556 | |
| 231942354 | |
| 179471023 | |
| 186316703 | |
| 198835387 | |
| 187460078 | |
| 267625681 | |
| 204612456 | |
| 272883496 | |
| 222563903 | |
| 233667836 | |
| 472238137 | |
| 316648381 | |
| 254770730 | |
| 258478011 | |
| 264769691 | |
| 386338951 | |
| 309953056 | |
| 306252928 | |
| 334164086 | |
| 335294460 | |
| 378306410 | |
| 338994588 | |
| 346262610 | |
| 361863259 | |
| 355017579 | |
| 402034926 | |
| 365787726 | |
| 373776781 | |
| 487333594 | |
| 392072534 | |
| 427176359 | |
| 438280292 | |
| 568431067 | |
| 456231739 | |
| 488438566 | |
| 513248741 | |
| 519540421 | |
| 523247702 | |
| 611032301 | |
| 643076101 | |
| 616205984 | |
| 640417014 | |
| 848304273 | |
| 669458546 | |
| 674289048 | |
| 712771369 | |
| 685257198 | |
| 701280189 | |
| 716880838 | |
| 1036496443 | |
| 1096648753 | |
| 765849315 | |
| 800953140 | |
| 915614925 | |
| 894512031 | |
| 865456651 | |
| 926718858 | |
| 1081679808 | |
| 1798560646 | |
| 1007978987 | |
| 1042788123 | |
| 1130572722 | |
| 1134280003 | |
| 1227238285 | |
| 1256622998 | |
| 1749267812 | |
| 1309875560 | |
| 1391169886 | |
| 1755968856 | |
| 1359546246 | |
| 1386537387 | |
| 1402138036 | |
| 2230928756 | |
| 1482730153 | |
| 1666409791 | |
| 1566802455 | |
| 2361518288 | |
| 3055183644 | |
| 1958403048 | |
| 2286265104 | |
| 2658761034 | |
| 2409449011 | |
| 2142258990 | |
| 4189331804 | |
| 2050767110 | |
| 4325170825 | |
| 2440448282 | |
| 2390903001 | |
| 2483861283 | |
| 2566498558 | |
| 2876678015 | |
| 3158106892 | |
| 2842276399 | |
| 2746083633 | |
| 2761684282 | |
| 2788675423 | |
| 3624989143 | |
| 3957705456 | |
| 4812451392 | |
| 3624812839 | |
| 3617569565 | |
| 4009170158 | |
| 4524901606 | |
| 5251725410 | |
| 4337032214 | |
| 4533161991 | |
| 4193026100 | |
| 6065261121 | |
| 4441670111 | |
| 4924309565 | |
| 4831351283 | |
| 4874764284 | |
| 7008168669 | |
| 5050359841 | |
| 5312582191 | |
| 5507767915 | |
| 5534759056 | |
| 10459068621 | |
| 5550359705 | |
| 7634159301 | |
| 6406244988 | |
| 7242558708 | |
| 9706115567 | |
| 7242382404 | |
| 8534071764 | |
| 7954601779 | |
| 10059660662 | |
| 8870194205 | |
| 8530058314 | |
| 8634696211 | |
| 8726188091 | |
| 9024377383 | |
| 15040941199 | |
| 9925124125 | |
| 9755660848 | |
| 9881711124 | |
| 10187346475 | |
| 10820350106 | |
| 10362942032 | |
| 10847341247 | |
| 14080418019 | |
| 15610020367 | |
| 15196984183 | |
| 13184519006 | |
| 19680784973 | |
| 13648627392 | |
| 16112752913 | |
| 23573751517 | |
| 15772440718 | |
| 16484660093 | |
| 16824795984 | |
| 18893000346 | |
| 17164754525 | |
| 19943007323 | |
| 17750565474 | |
| 22940179854 | |
| 20729052371 | |
| 38573785319 | |
| 20244653156 | |
| 21183292138 | |
| 25559926215 | |
| 29255942378 | |
| 21210283279 | |
| 23547461038 | |
| 24031860253 | |
| 53770769502 | |
| 30935084480 | |
| 29761380305 | |
| 26833146398 | |
| 29421068110 | |
| 30133287485 | |
| 31885193631 | |
| 36982723997 | |
| 33523006192 | |
| 33309456077 | |
| 33989550509 | |
| 37409407681 | |
| 34915319999 | |
| 37693572797 | |
| 46972040107 | |
| 40973705527 | |
| 41427945294 | |
| 64975406332 | |
| 42393575417 | |
| 44730753176 | |
| 44757744317 | |
| 47579321291 | |
| 64244540557 | |
| 50380607436 | |
| 50865006651 | |
| 56254214508 | |
| 62944074302 | |
| 78837352975 | |
| 56966433883 | |
| 70972274506 | |
| 97227920035 | |
| 65194649708 | |
| 70292180074 | |
| 66832462269 | |
| 83821520711 | |
| 68904870508 | |
| 84988728972 | |
| 72608892796 | |
| 78667278324 | |
| 82401650821 | |
| 83367280944 | |
| 86185689611 | |
| 93258582068 | |
| 115049924391 | |
| 89488497493 | |
| 92337065608 | |
| 103833535799 | |
| 101245614087 | |
| 151276171120 | |
| 107119221159 | |
| 121448864216 | |
| 122161083591 | |
| 127258613957 | |
| 123798896152 | |
| 231092149756 | |
| 132027111977 | |
| 134099520216 | |
| 137124642343 | |
| 150199743213 | |
| 254033279012 | |
| 141513763304 | |
| 207149812563 | |
| 155010543617 | |
| 161068929145 | |
| 165768931765 | |
| 169552970555 | |
| 372918744328 | |
| 273540875281 | |
| 249419697548 | |
| 190734111580 | |
| 193582679695 | |
| 222694478303 | |
| 253475976193 | |
| 284299263429 | |
| 311066733859 | |
| 268772377261 | |
| 257898416368 | |
| 251057510109 | |
| 255826008129 | |
| 419802210777 | |
| 325609791672 | |
| 271224162559 | |
| 292135185960 | |
| 291713506517 | |
| 332247874884 | |
| 527929287945 | |
| 420610480664 | |
| 360287082135 | |
| 565254381798 | |
| 413428589883 | |
| 363135650250 | |
| 384316791275 | |
| 416277157998 | |
| 464806842254 | |
| 444210087773 | |
| 514829664263 | |
| 555523425988 | |
| 504533486302 | |
| 508955926477 | |
| 583848692477 | |
| 670859720886 | |
| 527050170688 | |
| 506883518238 | |
| 616113090264 | |
| 709926582947 | |
| 562937669076 | |
| 563359348519 | |
| 623961381401 | |
| 981531539796 | |
| 887771300872 | |
| 723422732385 | |
| 925233084475 | |
| 744603873410 | |
| 779412808248 | |
| 1704645892723 | |
| 807345738023 | |
| 800593949273 | |
| 920810644300 | |
| 909016930027 | |
| 1251487391648 | |
| 1011417004540 | |
| 1013489412779 | |
| 1089987839764 | |
| 1015839444715 | |
| 1216810101185 | |
| 1544772025701 | |
| 1489339391195 | |
| 1069821187314 | |
| 1240074471665 | |
| 2686177432519 | |
| 1347384113786 | |
| 1549194465876 | |
| 1368565254811 | |
| 1468026605795 | |
| 1580006757521 | |
| 1524016681658 | |
| 1820835150802 | |
| 2019487279913 | |
| 1586758546271 | |
| 1607939687296 | |
| 2058833129671 | |
| 2289933340468 | |
| 1829827574327 | |
| 2101404844304 | |
| 3109475119677 | |
| 2623779132011 | |
| 2029328857494 | |
| 2537847793109 | |
| 2085660632029 | |
| 2286631288499 | |
| 2309895658979 | |
| 2417205301100 | |
| 2438386442125 | |
| 2820081229186 | |
| 2715949368597 | |
| 2815410719581 | |
| 2892581936469 | |
| 2836591860606 | |
| 2992043287453 | |
| 3110775227929 | |
| 4921910793963 | |
| 3194698233567 | |
| 3437767261623 | |
| 3416586120598 | |
| 3693600319325 | |
| 5516361068480 | |
| 3859156431821 | |
| 4130733701798 | |
| 4114989489523 | |
| 4315960145993 | |
| 4467715299619 | |
| 4339224516473 | |
| 4372291920528 | |
| 6611284354165 | |
| 4596526947478 | |
| 4727100960079 | |
| 6513681548511 | |
| 5608531305066 | |
| 6408629408051 | |
| 6010108953148 | |
| 9930267669109 | |
| 9046298566689 | |
| 8032686021892 | |
| 8503025622326 | |
| 6305473461496 | |
| 6632465495190 | |
| 6854353382221 | |
| 7110186439923 | |
| 7275742552419 | |
| 7552756751146 | |
| 7974145921344 | |
| 7989890133619 | |
| 8582704789142 | |
| 8454214005996 | |
| 11868716897139 | |
| 12418738361199 | |
| 8711516437001 | |
| 9099392880607 | |
| 12523790501659 | |
| 11032574421575 | |
| 10335632265145 | |
| 11618640258214 | |
| 16444104139615 | |
| 12315582414644 | |
| 13999999086767 | |
| 19169935796865 | |
| 12937938956686 | |
| 13159826843717 | |
| 13415659901419 | |
| 13486818877411 | |
| 20597005317334 | |
| 13964539822144 | |
| 14385928992342 | |
| 14828499303565 | |
| 15526902672490 | |
| 20392884282543 | |
| 16572594922761 | |
| 17036918795138 | |
| 27486817964178 | |
| 17810909317608 | |
| 20718033138821 | |
| 25748435232139 | |
| 31810908404375 | |
| 21368206686720 | |
| 33169934883632 | |
| 25618639344981 | |
| 24556579214900 | |
| 35546532442386 | |
| 52043397179078 | |
| 26097765800403 | |
| 26353598858105 | |
| 46986846031701 | |
| 29912831664832 | |
| 26902478778830 | |
| 28315318180976 | |
| 28350468814486 | |
| 32639408621173 | |
| 51716405145384 | |
| 30355401976055 | |
| 32099497595251 | |
| 33609513717899 | |
| 44923063737247 | |
| 54448234614889 | |
| 38528942456429 | |
| 52650914010969 | |
| 42086239825541 | |
| 83527313549759 | |
| 45924785901620 | |
| 47465972487123 | |
| 50175218559881 | |
| 50910178073005 | |
| 50654345015303 | |
| 52451364658508 | |
| 53000244579233 | |
| 53256077636935 | |
| 54668917039081 | |
| 55252947593316 | |
| 60989877435659 | |
| 55217796959806 | |
| 70401558006517 | |
| 70628440051680 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment