From 3ca5033e1ddd578dd5c6a3b0e8488751c879f10b Mon Sep 17 00:00:00 2001 From: Tom Smeding Date: Sun, 13 Dec 2020 20:43:59 +0100 Subject: Day 9 --- 2020/9.hs | 40 +++ 2020/9.in | 1000 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 1040 insertions(+) create mode 100644 2020/9.hs create mode 100644 2020/9.in diff --git a/2020/9.hs b/2020/9.hs new file mode 100644 index 0000000..d593681 --- /dev/null +++ b/2020/9.hs @@ -0,0 +1,40 @@ +module Main where + +import Data.List (find) +import Data.Maybe (fromJust) +import qualified Data.Set as Set +import qualified Data.Map.Strict as Map +import Data.Map.Strict (Map) + +import Input + + +preludeLen :: Int +preludeLen = 25 + +findRun :: Int -> [Int] -> (Int, Int) +findRun target input = go input 0 0 mempty + where + go :: [Int] -> Int -> Int -> Map Int Int -> (Int, Int) + go (x:xs) index beforeTotal prevs + | Just index' <- Map.lookup (beforeTotal + x - target) prevs + , index - index' >= 2 + = (index', index) + | otherwise + = go xs (index + 1) (beforeTotal + x) (Map.insert (beforeTotal + x) index prevs) + go [] _ _ _ = error "Run not found" + +main :: IO () +main = do + input <- map read <$> getInput 9 :: IO [Int] + let (prelude, rest) = splitAt preludeLen input + sets = scanl (\s (i1, i2) -> Set.insert i2 (Set.delete i1 s)) + (Set.fromList prelude) + (zip input rest) + isValid s i = any (`Set.member` s) [i - n | n <- Set.toList s, n /= i - n] + weakness = snd (fromJust (find (not . uncurry isValid) (zip sets rest))) + print weakness + + let (index1, index2) = findRun weakness input + run = drop (index1 + 1) (take index2 input) + print (minimum run + maximum run) diff --git a/2020/9.in b/2020/9.in new file mode 100644 index 0000000..16654e9 --- /dev/null +++ b/2020/9.in @@ -0,0 +1,1000 @@ +19 +20 +22 +10 +11 +29 +4 +41 +38 +46 +7 +2 +49 +26 +48 +6 +47 +42 +18 +40 +43 +45 +14 +30 +8 +55 +9 +12 +54 +10 +69 +11 +57 +13 +15 +32 +21 +53 +20 +16 +17 +19 +36 +22 +34 +23 +77 +18 +24 +25 +47 +26 +51 +39 +54 +29 +27 +49 +28 +62 +73 +33 +42 +41 +70 +40 +37 +43 +58 +44 +82 +45 +83 +55 +52 +84 +53 +56 +99 +57 +80 +119 +61 +65 +74 +122 +75 +110 +77 +81 +85 +87 +88 +144 +89 +106 +97 +105 +107 +108 +180 +113 +164 +118 +126 +136 +135 +138 +139 +155 +152 +156 +158 +162 +166 +200 +175 +177 +186 +194 +215 +202 +212 +225 +226 +231 +282 +326 +244 +277 +271 +273 +290 +291 +307 +548 +564 +377 +328 +341 +352 +361 +398 +380 +396 +414 +639 +438 +475 +470 +1203 +515 +567 +916 +544 +561 +563 +581 +619 +689 +669 +873 +680 +724 +852 +750 +1404 +776 +810 +957 +884 +908 +913 +945 +1182 +1560 +1317 +1105 +1107 +1797 +1124 +1144 +1200 +1288 +1393 +1349 +1456 +1862 +1474 +1526 +2231 +1586 +1694 +1718 +1792 +1858 +2057 +3720 +2306 +2212 +2344 +2229 +2537 +3632 +2324 +2268 +2549 +2488 +3517 +3580 +2805 +4499 +3168 +3000 +3112 +3280 +3304 +3412 +5268 +3650 +4202 +4269 +4480 +4441 +4497 +4553 +6109 +5354 +4592 +4812 +4756 +5549 +5293 +5805 +7777 +6112 +6280 +6168 +7062 +6416 +11463 +6716 +10609 +9292 +7919 +9365 +8710 +8921 +8938 +10105 +10842 +13174 +9348 +10397 +14057 +10049 +11098 +12521 +11917 +12280 +12884 +12448 +23726 +13132 +21093 +23571 +14635 +17267 +21645 +18759 +27469 +18058 +31039 +37574 +28109 +44819 +19745 +21147 +21966 +22329 +49114 +23015 +24197 +24728 +38360 +36645 +25580 +27767 +30399 +47057 +31902 +53547 +35325 +36817 +37803 +39205 +40387 +41711 +40892 +42074 +45325 +49777 +46694 +48595 +54231 +48925 +47212 +50308 +52495 +55979 +53347 +72142 +88104 +82210 +68719 +79114 +93734 +73128 +74620 +118319 +79592 +81279 +89487 +135557 +95619 +92019 +96989 +170766 +108474 +96137 +99707 +97520 +102803 +168747 +109326 +122066 +143339 +198813 +141847 +185753 +147748 +243894 +152720 +154212 +217685 +169079 +173298 +186476 +187638 +200493 +188156 +244737 +197227 +205463 +289595 +200323 +285676 +320879 +231392 +310222 +342340 +402690 +310926 +294567 +300468 +301960 +306932 +321799 +341850 +623759 +611394 +359774 +374114 +375794 +388649 +405786 +397550 +428619 +603013 +707746 +542318 +517068 +553191 +595035 +663649 +596527 +1148226 +715964 +681573 +648782 +661734 +1128462 +701624 +730499 +1008799 +1077401 +779900 +749908 +764443 +981810 +803336 +1258684 +970937 +1059386 +1394148 +1113595 +1070259 +1201973 +1191562 +1446463 +1245309 +1990609 +1343307 +1383197 +1310516 +1411642 +1432123 +1893186 +1862722 +2648436 +1514351 +1544343 +1878038 +1746253 +2481901 +1994898 +3595496 +2030323 +2315568 +2261821 +3325309 +2516722 +2393535 +2436871 +2555825 +2759660 +2653823 +2693713 +2722158 +2925993 +2843765 +2946474 +3058694 +3260604 +3392389 +3996252 +3290596 +3624291 +5502299 +5497588 +4025221 +4292144 +4345891 +5159029 +9126590 +4830406 +5087248 +5209648 +4992696 +5249538 +5347536 +6237070 +5415871 +5565923 +10296896 +5790239 +8317365 +9155281 +9176297 +7620543 +6914887 +8792895 +9122550 +8638035 +8371112 +8855627 +9284840 +12613239 +9917654 +18411430 +10815461 +10242234 +10202344 +10340232 +18010908 +19072935 +10981794 +17915445 +15552922 +12705126 +13410782 +15285999 +29888396 +14535430 +17164007 +15707782 +17009147 +27295748 +18711344 +18573456 +18140467 +19202494 +20119998 +25528233 +20444578 +22907470 +20542576 +24737774 +28258048 +31101792 +29555250 +23686920 +30838921 +41081155 +55553796 +27946212 +40564576 +30243212 +33246774 +38831342 +32716929 +44730727 +43668700 +36713923 +43352048 +39647072 +39745070 +49215153 +40987154 +43450046 +61451697 +48488788 +48424694 +51633132 +53242170 +53930132 +88399427 +72461999 +62960141 +58189424 +83916624 +63489986 +76598822 +87020748 +69430852 +96363859 +76360995 +77701077 +100057826 +80634226 +119811041 +153096225 +84437200 +128231954 +178000465 +106678212 +96913482 +101666864 +104875302 +122673022 +126392131 +121149565 +181350682 +249065153 +121679410 +132920838 +312555139 +203042071 +254624085 +435228161 +414222003 +180692052 +158335303 +331096690 +165071426 +186104064 +189312502 +266738290 +198580346 +201788784 +243822587 +254070403 +206542166 +438947270 +248071541 +242828975 +254600248 +322233340 +532885474 +366796116 +291256141 +339027355 +799623764 +419141829 +344439367 +323406729 +345763478 +347647805 +433135089 +351175490 +508670651 +387892848 +602248053 +581856330 +408330950 +751499626 +449371141 +529948895 +502671789 +662434084 +497429223 +599039615 +671054534 +875466767 +614662870 +630283496 +667846096 +905263059 +827472779 +1270094149 +556543474 +1079285553 +698823295 +853847279 +837263989 +796223798 +857702091 +1484130775 +905760173 +911002739 +1378138556 +1324837908 +1525548187 +1053972697 +1127712719 +1408431962 +1155583089 +2182954070 +1171206344 +1186826970 +1224389570 +1255366769 +2303675123 +1964976708 +2604833740 +2061653559 +1536087284 +1694966080 +1633487787 +1653925889 +2564928628 +1763462264 +2605968819 +2235840647 +1964975436 +2278362267 +3791660710 +2181685416 +2209555786 +2919355650 +2326789433 +2342410059 +2358033314 +4340015826 +3529237029 +2479756339 +2791454053 +3695141346 +3169575071 +3190013173 +3231053364 +4021755513 +5196028800 +3287413676 +3417388153 +5548046487 +6134070769 +4417526063 +4620772326 +4146660852 +4567589100 +4391241202 +4508474849 +4536345219 +9939287689 +4669199492 +4700443373 +4837789653 +5271210392 +6946625182 +6421066537 +15487334176 +6885154519 +6359588244 +9369642865 +6518467040 +12878055284 +6704801829 +9421484445 +7564049005 +8537902054 +8564186915 +8655135701 +8714249952 +9807555611 +8927586421 +9044820068 +13985115542 +9205544711 +9506989145 +9538233026 +11258856190 +10109000045 +13223268869 +12780654781 +17679922727 +13589956348 +18907875891 +14897490298 +15419051781 +16126286274 +14268850834 +15242703883 +16128235920 +16101951059 +17193037755 +17219322616 +17369385653 +18221239097 +22761501895 +21825474849 +31363707875 +18712533856 +20464400901 +25006490343 +24848812538 +22889654826 +23698956393 +26003923650 +26370611129 +28832660231 +27858807182 +29511554717 +40130887548 +29687902615 +39117663372 +36592636821 +31344654942 +33321273675 +33294988814 +34412360371 +34588708269 +45228192835 +36933772953 +55146748524 +39176934757 +41602188682 +42411490249 +43354055727 +54536715153 +46588611219 +48893578476 +59203462124 +57348578592 +55203271360 +57370361899 +62806543531 +59199457332 +61032557557 +116548035924 +79946692548 +64639643756 +77933266161 +67707349185 +67883697083 +77000198518 +125672201313 +103430293629 +139146149880 +80779123439 +81588425006 +145640615346 +85765545976 +102553513059 +101125326372 +106263940375 +104096849836 +112551849952 +118402919456 +114402728692 +116569819231 +180435547035 +120232014889 +245075190791 +132346992941 +365307205680 +145816963244 +135591046268 +248370476303 +248142896220 +183332636498 +162367548445 +227229040352 +181904449811 +166544669415 +182713751378 +186890872348 +241854986643 +203678839431 +205222176208 +230972547923 +294714541386 +226954578644 +234972738687 +248916812172 +384114386466 +252579007830 +255823061157 +345081299823 +267938039209 +281408009512 +388554812706 +297958594713 +328912217860 +511625969238 +414119912700 +344271998256 +348449119226 +349258420793 +508362588156 +498393380817 +390569711779 +408901015639 +432176754852 +436194724131 +457927126567 +475871390816 +461927317331 +502910777896 +501495820002 +684755762682 +641133820536 +673993517683 +1098875675382 +565896633922 +825129811609 +1196381731920 +642230592969 +673184216116 +1109378940247 +1174680036118 +734841710035 +739018831005 +807185547360 +1074407347821 +799470727418 +956466345701 +1050034836175 +868371478983 +1414393472268 +919854443898 +1269112864691 +1237752487931 +1207030454458 +1067392453924 +1208127226891 +2007597954309 +2336505318615 +1239080850038 +1300738343957 +1606656274778 +1315414809085 +1377072303004 +1691308055736 +1473860541040 +1658873274903 +2117427290099 +1824837824684 +1755937073119 +4125025244408 +1719325171316 +2023858799625 +1788225922881 +2508865570848 +2578727718801 +1987246897822 +2616153153042 +2274422908382 +2415157681349 +2996353149772 +2447208076929 +2539819193995 +3356508140137 +4862365758278 +6741178397450 +2692487112089 +2789275350125 +4141286089724 +3132733815943 +3262086463921 +3447099197784 +4298052890117 +3812084722506 +4411812283405 +3507551094197 +3706572069138 +3775472820703 +4062648831263 +4983600047594 +9188386474379 +4261669806204 +4689580589731 +4814242102377 +4954976875344 +7274019905667 +7847858158862 +5232306306084 +5954573576010 +6296826444322 +5481762462214 +5825220928032 +7769220900401 +6394820279864 +7037559284624 +6709185661705 +8501665312237 +9769218977721 +7214123163335 +7283023914900 +9216646681548 +7482044889841 +11049492726370 +12465644937435 +13570846349989 +15001525283805 +12122047372354 +12220041207896 +14311579190291 +21396345563669 +11186879882094 +10714068768298 +11306983390246 +11778588906536 +12190948123919 +11876582742078 +21645801719799 +16499670596448 +13104005941569 +15715788475572 +13923308825040 +14497147078235 +17052242892621 +14696168053176 +14765068804741 +16698691571389 +18196113658139 +21763561494668 +25294954065488 +21900948650392 +22021052158544 +23429030762600 +29802697512958 +22492657674834 +22493863272340 +22905016892217 +33799641065080 +23085572296782 +23655171648614 +33750934464010 +24980588683647 +27601153019804 +27027314766609 +27800173994745 +28420455903275 +28619476878216 +29193315131411 +29461236857917 +31394859624565 +31463760376130 +34894805229528 +40097062308531 +47473246358481 +43922000808936 +61551108458755 +45106624455326 +44986520947174 +45397674567051 +45398880164557 +56220629898020 +55050031273179 +46740743945396 +48635760332261 +88800965737189 +52007903450256 +52581741703451 +77829075463672 +54827488761354 +57039932781491 +135541709682585 +57812792009627 -- cgit v1.2.3-54-g00ecf