From fb79b0c5e699d81d19698d34b72e5151fcfcf0ef Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 14 Dec 2020 22:08:02 +0000 Subject: [PATCH] Done day 9 --- advent08/src/advent08.hs | 7 - advent09/package.yaml | 58 +++ advent09/src/advent09.hs | 30 ++ data/advent09.txt | 1000 ++++++++++++++++++++++++++++++++++++++ problems/day09.html | 188 +++++++ stack.yaml | 1 + 6 files changed, 1277 insertions(+), 7 deletions(-) create mode 100644 advent09/package.yaml create mode 100644 advent09/src/advent09.hs create mode 100644 data/advent09.txt create mode 100644 problems/day09.html diff --git a/advent08/src/advent08.hs b/advent08/src/advent08.hs index dab483e..ba8134c 100644 --- a/advent08/src/advent08.hs +++ b/advent08/src/advent08.hs @@ -47,13 +47,6 @@ part2 program = filter terminates $ map runProgram programs executeMany visited machine - -- if currentIP `S.member` visited - -- then Looped (machineAcc machine) - -- else if currentIP == programSize - -- then Terminated (machineAcc machine) - -- else if currentIP > programSize - -- then OutOfBounds (machineAcc machine) currentIP - -- else executeMany visited' machine' | currentIP `S.member` visited = Looped (machineAcc machine) | currentIP == programSize = Terminated (machineAcc machine) | currentIP > programSize = OutOfBounds (machineAcc machine) currentIP diff --git a/advent09/package.yaml b/advent09/package.yaml new file mode 100644 index 0000000..7a164a3 --- /dev/null +++ b/advent09/package.yaml @@ -0,0 +1,58 @@ +# This YAML file describes your package. Stack will automatically generate a +# Cabal file when you run `stack build`. See the hpack website for help with +# this file: . + +name: advent09 +synopsis: Advent of Code +version: '0.0.1' + +default-extensions: +- AllowAmbiguousTypes +- ApplicativeDo +- BangPatterns +- BlockArguments +- DataKinds +- DeriveFoldable +- DeriveFunctor +- DeriveGeneric +- DeriveTraversable +- EmptyCase +- FlexibleContexts +- FlexibleInstances +- FunctionalDependencies +- GADTs +- GeneralizedNewtypeDeriving +- ImplicitParams +- KindSignatures +- LambdaCase +- MonadComprehensions +- MonoLocalBinds +- MultiParamTypeClasses +- MultiWayIf +- NamedFieldPuns +- NegativeLiterals +- NumDecimals +# - OverloadedLists +- OverloadedStrings +- PartialTypeSignatures +- PatternGuards +- PatternSynonyms +- PolyKinds +- RankNTypes +- RecordWildCards +- ScopedTypeVariables +- TemplateHaskell +- TransformListComp +- TupleSections +- TypeApplications +- TypeFamilies +- TypeInType +- TypeOperators +- ViewPatterns + +executables: + advent09: + main: advent09.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 diff --git a/advent09/src/advent09.hs b/advent09/src/advent09.hs new file mode 100644 index 0000000..d1c32d4 --- /dev/null +++ b/advent09/src/advent09.hs @@ -0,0 +1,30 @@ +-- import Debug.Trace + +import Data.List + +main :: IO () +main = + do numStrs <- readFile "data/advent09.txt" + let nums = map (read @Int) $ lines numStrs + let firstInvalid = part1 nums + print firstInvalid + print $ part2 firstInvalid nums + -- print $ head $ part2 nums + +part1 nums = fst $ head $ filter (not . valid) $ slidingWindow 25 nums + +slidingWindow winSize nums = + zip (drop winSize nums) $ map (take winSize) $ tails nums + +valid (target, window) = not $ null [(x, y) | x <- window, y <- window, x + y == target] + + +part2 target nums = (maximum section) + (minimum section) + where section = head $ filter (sumsToTarget target) $ subStrings nums + +-- subStrings :: [a] -> [[a]] +subStrings = (concatMap inits) . tails + +-- sumsToTarget :: Int -> [Int] -> Bool +sumsToTarget target ns = sum ns == target + diff --git a/data/advent09.txt b/data/advent09.txt new file mode 100644 index 0000000..eb10606 --- /dev/null +++ b/data/advent09.txt @@ -0,0 +1,1000 @@ +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 diff --git a/problems/day09.html b/problems/day09.html new file mode 100644 index 0000000..d70889c --- /dev/null +++ b/problems/day09.html @@ -0,0 +1,188 @@ + + + + +Day 9 - Advent of Code 2020 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 18*

   0x0000|2020

+ + + +
+ +

--- Day 9: Encoding Error ---

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):

+
35
+20
+15
+25
+47
+40
+62
+55
+65
+95
+102
+117
+150
+182
+127
+219
+299
+277
+309
+576
+
+

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?

+
+

Your puzzle answer was 21806024.

--- Part Two ---

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:

+
35
+20
+15
+25
+47
+40
+62
+55
+65
+95
+102
+117
+150
+182
+127
+219
+299
+277
+309
+576
+
+

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?

+
+

Your puzzle answer was 2986195.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your Advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file diff --git a/stack.yaml b/stack.yaml index 07d779b..1d42438 100644 --- a/stack.yaml +++ b/stack.yaml @@ -43,6 +43,7 @@ packages: - advent06 - advent07 - advent08 +- advent09 # Dependency packages to be pulled from upstream that are not in the resolver. # These entries can reference officially published versions as well as -- 2.34.1