From a2f46a9f4b4122929d8340bc20f42322bd4aefd6 Mon Sep 17 00:00:00 2001 From: Andinus Date: Wed, 9 Dec 2020 18:32:59 +0530 Subject: Add day-09 solution --- 2020/day-09/README.org | 179 +++++++++ 2020/day-09/day-09.raku | 52 +++ 2020/day-09/input | 1000 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1231 insertions(+) create mode 100644 2020/day-09/README.org create mode 100755 2020/day-09/day-09.raku create mode 100644 2020/day-09/input diff --git a/2020/day-09/README.org b/2020/day-09/README.org new file mode 100644 index 0000000..db1eeab --- /dev/null +++ b/2020/day-09/README.org @@ -0,0 +1,179 @@ +#+SETUPFILE: ~/.emacs.d/org-templates/level-3.org +#+HTML_LINK_UP: ../../index.html#2020 +#+OPTIONS: toc:1 +#+EXPORT_FILE_NAME: index +#+TITLE: Day 09 - Encoding Error + +* Puzzle +- This puzzle is taken from: https://adventofcode.com/2020/day/9 + +With your neighbor happily enjoying their video game, you turn your +attention to an open data port on the little screen in the seat in front +of you. + +Though the port is non-standard, you manage to connect it to your +computer through the clever use of several paperclips. Upon connection, +the port outputs a series of numbers (your puzzle input). + +The data appears to be encrypted with the eXchange-Masking Addition +System (XMAS) which, conveniently for you, is an old cypher with an +important weakness. + +XMAS starts by transmitting a preamble of 25 numbers. After that, each +number you receive should be the sum of any two of the 25 immediately +previous numbers. The two numbers will have different values, and there +might be more than one such pair. + +For example, suppose your preamble consists of the numbers 1 through 25 +in a random order. To be valid, the next number must be the sum of two +of those numbers: + +- 26 would be a valid next number, as it could be 1 plus 25 (or many + other pairs, like 2 and 24). +- 49 would be a valid next number, as it is the sum of 24 and 25. +- 100 would not be valid; no two of the previous 25 numbers sum to 100. +- 50 would also not be valid; although 25 appears in the previous 25 + numbers, the two numbers in the pair must be different. + +Suppose the 26th number is 45, and the first number (no longer an +option, as it is more than 25 numbers ago) was 20. Now, for the next +number to be valid, there needs to be some pair of numbers among 1-19, +21-25, or 45 that add up to it: + +- 26 would still be a valid next number, as 1 and 25 are still within + the previous 25 numbers. +- 65 would not be valid, as no two of the available numbers sum to it. +- 64 and 66 would both be valid, as they are the result of 19+45 and + 21+45 respectively. + +Here is a larger example which only considers the previous 5 numbers +(and has a preamble of length 5): +#+BEGIN_SRC +35 +20 +15 +25 +47 +40 +62 +55 +65 +95 +102 +117 +150 +182 +127 +219 +299 +277 +309 +576 +#+END_SRC + +In this example, after the 5-number preamble, almost every number is the +sum of two of the previous 5 numbers; the only number that does not +follow this rule is 127. + +The first step of attacking the weakness in the XMAS data is to find the +first number in the list (after the preamble) which is not the sum of +two of the 25 numbers before it. What is the first number that does not +have this property? +** Part 2 +The final step in breaking the XMAS encryption relies on the invalid +number you just found: you must find a contiguous set of at least two +numbers in your list which sum to the invalid number from step 1. + +Again consider the above example: +#+BEGIN_SRC +35 +20 +15 +25 +47 +40 +62 +55 +65 +95 +102 +117 +150 +182 +127 +219 +299 +277 +309 +576 +#+END_SRC + +In this list, adding up all of the numbers from 15 through 40 produces +the invalid number from step 1, 127. (Of course, the contiguous set of +numbers in your actual list might be much longer.) + +To find the encryption weakness, add together the smallest and largest +number in this contiguous range; in this example, these are 15 and 47, +producing 62. + +What is the encryption weakness in your XMAS-encrypted list of numbers? +* Solution +Second part is dependent on the first part so we find the invalid number +in all cases. =%invalid= stores the invalid number along with it's index. +We check all possible combinations. + +I'm too tired to explain this in detail, maybe I'll add explanation +later. Also, the solution isn't good. +#+BEGIN_SRC raku +my @numbers = "input".IO.lines>>.Int; +my Int $solution; + +my Int $preamble_length = 25; +my Int %invalid; + +MAIN: for @numbers.kv -> $idx, $num { + next if $idx < $preamble_length; + + my @preamble = @numbers[$idx - $preamble_length..$idx - 1].sort; + + my Bool $valid; + while pop @preamble -> $num_1 { + my $diff = $num - $num_1; + for @preamble -> $num_2 { + if $num_2 == $diff { + $valid = True; + next MAIN; + } + } + } + + unless $valid { + %invalid = $num; + %invalid = $idx; + $solution = %invalid if $part == 1; + last MAIN; + } +} + +if $part == 2 { + ... +} + +say "Part $part: ", $solution; +#+END_SRC +** Part 2 +We brute force the second part too. +#+BEGIN_SRC raku +my @set = @numbers[0..%invalid - $preamble_length - 1]; + +PART2: for @set.elems - 1 ... 0 -> $idx_1 { + for @set.elems - 1 ... 0 -> $idx_2 { + my $sum = [+] @set[$idx_1..$idx_2]; + if $sum == %invalid { + my @tmp = @set[$idx_1..$idx_2].sort; + $solution = @tmp[0] + @tmp[*-1]; + last PART2; + } + } +} +#+END_SRC diff --git a/2020/day-09/day-09.raku b/2020/day-09/day-09.raku new file mode 100755 index 0000000..e9b6683 --- /dev/null +++ b/2020/day-09/day-09.raku @@ -0,0 +1,52 @@ +#!/usr/bin/env raku + +sub MAIN ( + Int $part where * == 1|2 = 1 #= part to run (1 or 2) +) { + my @numbers = "input".IO.lines>>.Int; + my Int $solution; + + my Int $preamble_length = 25; + my Int %invalid; + + MAIN: for @numbers.kv -> $idx, $num { + next if $idx < $preamble_length; + + my @preamble = @numbers[$idx - $preamble_length..$idx - 1].sort; + + my Bool $valid; + while pop @preamble -> $num_1 { + my $diff = $num - $num_1; + for @preamble -> $num_2 { + if $num_2 == $diff { + $valid = True; + next MAIN; + } + } + } + + unless $valid { + %invalid = $num; + %invalid = $idx; + $solution = %invalid if $part == 1; + last MAIN; + } + } + + if $part == 2 { + my @set = @numbers[0..%invalid - $preamble_length - 1]; + + PART2: for @set.elems - 1 ... 0 -> $idx_1 { + for @set.elems - 1 ... 0 -> $idx_2 { + my $sum = [+] @set[$idx_1..$idx_2]; + if $sum == %invalid { + my @tmp = @set[$idx_1..$idx_2].sort; + $solution = @tmp[0] + @tmp[*-1]; + last PART2; + } + } + } + } + + say "Part $part: ", $solution; +} diff --git a/2020/day-09/input b/2020/day-09/input new file mode 100644 index 0000000..afaf5cb --- /dev/null +++ b/2020/day-09/input @@ -0,0 +1,1000 @@ +1 +15 +32 +16 +6 +20 +25 +30 +38 +31 +48 +47 +19 +23 +39 +50 +41 +4 +27 +12 +21 +24 +26 +43 +2 +3 +5 +7 +8 +9 +6 +72 +10 +20 +11 +13 +14 +30 +25 +23 +15 +16 +17 +18 +19 +22 +21 +12 +32 +24 +28 +26 +27 +35 +29 +31 +33 +34 +36 +37 +38 +42 +39 +30 +40 +43 +41 +47 +46 +44 +50 +49 +45 +75 +51 +53 +57 +56 +81 +59 +83 +70 +64 +72 +67 +91 +69 +71 +73 +84 +85 +92 +89 +90 +93 +96 +94 +98 +123 +104 +120 +154 +115 +126 +141 +133 +131 +157 +139 +287 +238 +209 +144 +158 +175 +185 +179 +182 +183 +187 +190 +192 +286 +289 +264 +257 +241 +256 +259 +466 +270 +275 +283 +324 +462 +302 +323 +331 +333 +362 +361 +372 +365 +370 +377 +524 +475 +497 +498 +521 +844 +500 +515 +529 +545 +553 +558 +585 +1013 +887 +1210 +654 +995 +694 +735 +876 +872 +894 +747 +906 +1060 +972 +1607 +998 +1268 +1247 +1292 +1199 +1074 +1239 +1111 +1768 +1696 +1348 +1389 +1401 +1429 +1611 +1441 +1870 +1619 +1641 +1653 +1745 +1878 +1970 +3279 +2072 +5024 +2273 +2185 +2310 +2313 +3424 +3307 +2459 +3052 +3349 +2737 +2790 +4155 +4732 +4720 +3311 +3623 +4898 +6214 +3398 +3715 +5534 +4042 +4257 +4345 +4458 +4495 +7033 +6618 +4772 +5196 +8673 +6994 +5527 +8940 +9525 +6832 +6934 +8838 +10016 +6709 +7021 +7113 +7440 +14107 +11805 +9238 +16380 +8602 +9230 +8953 +9267 +13639 +14200 +11706 +15536 +13541 +15961 +13766 +21313 +13643 +15859 +13730 +16678 +13822 +14134 +14461 +16042 +16393 +17555 +17832 +17840 +17869 +18183 +29175 +30215 +25126 +45853 +25247 +25349 +27184 +27271 +27373 +33414 +27777 +27465 +27552 +27864 +34576 +32330 +28595 +30503 +43079 +35395 +35387 +35672 +60798 +58540 +43309 +50373 +57588 +50475 +50596 +52518 +55017 +54455 +54838 +54925 +58280 +55242 +70943 +55416 +56459 +125868 +59098 +85983 +73582 +70782 +71059 +85862 +98234 +100969 +172028 +109293 +105891 +101071 +105434 +159351 +125514 +109380 +109697 +109763 +176673 +251382 +156765 +111875 +115557 +144364 +144960 +129880 +141841 +144641 +270262 +223748 +184096 +199203 +202040 +211325 +206505 +250255 +210768 +274244 +219077 +219143 +253744 +340648 +221638 +355132 +227432 +286482 +271721 +245437 +348957 +274840 +366279 +449458 +721179 +383299 +386136 +394864 +996019 +408545 +417273 +605387 +429845 +440715 +505625 +464580 +627130 +576770 +449070 +467075 +472869 +499153 +517158 +520277 +735093 +623797 +660976 +885289 +778163 +791844 +769435 +781000 +803409 +849260 +825818 +990027 +870560 +947003 +948223 +931655 +966228 +916145 +1025840 +1404797 +1090872 +972022 +1486794 +1289712 +2351800 +1464385 +1603981 +1430411 +1547598 +2396858 +1550435 +1673969 +3641512 +1974063 +2115530 +1956255 +1920245 +2495821 +2498658 +1847800 +1882373 +2007017 +1888167 +3735967 +2261734 +3963043 +2402433 +2720123 +4199600 +2894796 +2980846 +3098033 +4217989 +3556342 +4452076 +3224404 +3562136 +3770540 +3730173 +3895184 +3768045 +3802618 +4290600 +3854817 +3889390 +5992829 +8306893 +5690785 +8712952 +7692008 +5122556 +6748891 +6450296 +5875642 +6078879 +9846924 +8346960 +9554965 +16595815 +6786540 +6954577 +9458830 +7498218 +7532791 +13567650 +7570663 +7657435 +7744207 +12529175 +9011946 +10813341 +12077133 +14134502 +14525240 +12865419 +14698784 +11954521 +12325938 +12662182 +13033456 +22890474 +13741117 +20406389 +26211635 +14284758 +14452795 +21951013 +15031009 +15103454 +18384004 +15228098 +15401642 +16756153 +27486251 +15690279 +24988120 +27896428 +52474371 +24280459 +30918377 +24616703 +24987977 +25359394 +25695638 +38392850 +28025875 +42115547 +30134463 +39644152 +29512856 +29483804 +30259107 +30505096 +30629740 +31091921 +69127956 +60113544 +60764203 +39970738 +40306982 +58030891 +48897162 +49268436 +54129559 +49604680 +60575725 +50347371 +56787559 +53721513 +57509679 +98873116 +79860227 +70229845 +80977111 +83642415 +59742911 +80852467 +61134836 +79526902 +97480417 +121159449 +116901103 +80277720 +96758297 +89204144 +140102627 +129128663 +102989949 +99952051 +113464424 +133989786 +111231192 +110509072 +238060552 +153872260 +139603138 +120877747 +129972756 +140020631 +168731046 +141412556 +237778850 +326982994 +196710348 +169481864 +218332807 +228132295 +177036017 +330700134 +189156195 +202942000 +240359855 +210461123 +211183243 +399652348 +456393359 +240481828 +308751677 +549032941 +317056648 +458692662 +358353438 +269993387 +414814867 +345767063 +310894420 +346517881 +458814635 +358638059 +366192212 +628346825 +986700263 +487930437 +399617318 +705155940 +549233505 +421644366 +450942951 +451665071 +510475215 +598835266 +625808325 +578745064 +580887807 +587050035 +615760450 +616511268 +628631446 +962140286 +939241245 +762559491 +712710093 +724830271 +758255377 +1139106661 +1059708720 +909574803 +938873388 +821261684 +873309437 +872587317 +902608022 +961418166 +1030410135 +1089220279 +1337000441 +1194505514 +1202810485 +1299760128 +1203561303 +1232271718 +1341341539 +1353461717 +1919335785 +1487389762 +1437540364 +1470965470 +1483085648 +1693849001 +1694571121 +1848448191 +2958355232 +1723869706 +2173069565 +1745896754 +1775195339 +1991828301 +2164228651 +3613184786 +2283725793 +2406371788 +2397315999 +3183437118 +2557023020 +3262585101 +2573613257 +2694803256 +4311816949 +3462793771 +3994563384 +3228982402 +3165536591 +3176934649 +4860107712 +3418440827 +3469766460 +3521092093 +3715698007 +3737725055 +3767023640 +4058921132 +4447954444 +4561544650 +4681041792 +5574250648 +4803687787 +5659901100 +5130636277 +5251826276 +10463588887 +8803233050 +8597832767 +6342471240 +6394518993 +6405917051 +6647423229 +6583977418 +7185464467 +6888207287 +6939532920 +10401392372 +10340942892 +18999225139 +7504748695 +9426924740 +8506875576 +9251642231 +9242586442 +9484729579 +9934324064 +10055514063 +16807309423 +12989894469 +13334051913 +13053340280 +12736990233 +12748388291 +13579983460 +12800436044 +13231400647 +13472184705 +20170933567 +16372936866 +13827740207 +16191175151 +25675904730 +16756390926 +16011624271 +18441199640 +17749462018 +22483042878 +18494228673 +18727316021 +19419053643 +22734760108 +34452823911 +31527752065 +25485378524 +25548824335 +31464306254 +25537426277 +25979788938 +35483706947 +36476778039 +49213768272 +27299924912 +29839364478 +30018915358 +35197590566 +37221544694 +42305215261 +36243690691 +45850988749 +36190661658 +37168515661 +37913282316 +38146369664 +41462076129 +42153813751 +48220138632 +51022804801 +51034202859 +51086250612 +63201333632 +51517215215 +52837351189 +74103943974 +114235536491 +57318840270 +79375358445 +59858279836 +67932197674 +87337755628 +92516430836 +72434352349 +112017226290 +73359177319 +143550633695 +74337031322 +75081797977 +79608445793 +83615889880 +115566020103 +90373952383 +99242943433 +123951567564 +136927286063 +103923601801 +104354566404 +212009084040 +186354257612 +178027545775 +130678017589 +129753192619 +127790477510 +261643435655 +140366550023 +360886379088 +220127145002 +162808304732 +147696208641 +165455750360 +153945477115 +149418829299 +390036629815 +169982398176 +228306133968 +189616895816 +194297554184 +203166545234 +232145043914 +208278168205 +324481711406 +234107759023 +257543670129 +258468495099 +293486322321 +277449401260 +268157027533 +275486686151 +313151959001 +288062758664 +297115037940 +471323572767 +319401227475 +301641685756 +467097436116 +404090157199 +478653231385 +364279952360 +442385927228 +383914450000 +392783441050 +485727569465 +411444713439 +559185355885 +465821838334 +621042913231 +890097944824 +516012165228 +723491384674 +703315677475 +641729353620 +581308986534 +563549444815 +585177796604 +944475069719 +1426807062149 +788004607199 +871436672435 +945588938894 +1025007194219 +908795606278 +2011984858753 +748194402360 +2477806697087 +776697891050 +804228154489 +1430622028320 +1406110110052 +1047130824868 +981834003562 +1079561610043 +1097321151762 +1101189961832 +1144858431349 +1345045031095 +1148727241419 +1525784056253 +1311743847175 +1675664826924 +1524892293410 +1992719763762 +1619631074795 +2149273185584 +1552422556849 +1580926045539 +1656990008638 +1730028405922 +2493772272514 +1758531894612 +1786062158051 +1851358979357 +2028964828430 +2599553381717 +2446234992927 +2242179583111 +2176882761805 +2697280988198 +3106710101792 +3516090563973 +2460471088594 +3255812462175 +2931374921970 +3470990054152 +4113403347309 +3077314850259 +3172053631644 +3209412565487 +3133348602388 +3282450962771 +3237916054177 +6103428553614 +3488560300534 +5375528185499 +4874163750003 +5618288624571 +4093538562468 +6240058704180 +5173554505081 +4623117754732 +9385879516385 +6169290976147 +9106848925105 +5391846010564 +6959550354686 +5537785938853 +6008689772229 +6210663452647 +8709839570497 +10882853522232 +8856204678748 +9412112335824 +9998645940231 +8864088486033 +12138655641519 +18249968002418 +8716656317200 +7582098863002 +14787640521323 +8967702312471 +9711827187039 +15136993288618 +9796672259813 +10160903693585 +10014963765296 +10929631949417 +11546475711082 +11400535782793 +11602509463211 +11748449391500 +13590788635231 +14718529342726 +14920503023144 +16291938433499 +16298755180202 +16438303541750 +16446187349035 +16549801175473 +24948544214908 +17293926050041 +17378771122815 +17597062628298 +26346473435286 +18679529499510 +41266976458430 +19957575953398 +27894447896710 +19811636025109 +20175867458881 +28194636740535 +22330167732210 +25339238026731 +32737058721952 +23350958854711 +29042375441541 +34035366170048 +31156832884476 +31212441456643 +53233685923441 +43640399485327 +37554638581696 +54240921331996 +61237462113625 +34672697172856 +34890988678339 +38637105452908 +37408698653407 +38491165524619 +38855396958391 +47706083921819 +39769211978507 +45515105485612 +39987503483990 +84390518807917 +65749275322231 +45681126586921 +58241947533050 +61779434163493 +52393334296252 +70981653435150 +89454388989693 +151233823153186 +77396202137397 +72227335754552 +69563685851195 +100416539616401 +72081395826263 +72299687331746 +73163862697475 +73382154202958 +75899864178026 +76264095611798 +77346562483010 +78624608936898 +79756715462497 -- cgit 1.4.1-2-gfad0