From 644c38de8b633dc5e03bff5216f68b2bfde4a645 Mon Sep 17 00:00:00 2001 From: Akshay Date: Wed, 9 Dec 2020 11:03:39 +0530 Subject: add initial solution for day09 --- aoc.cabal | 6 + default.nix | 3 +- execs/Day08.hs | 4 +- execs/Day09.hs | 35 ++ input/09 | 1000 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ input/09sample | 20 ++ lib/Utils.hs | 5 + 7 files changed, 1070 insertions(+), 3 deletions(-) create mode 100644 execs/Day09.hs create mode 100644 input/09 create mode 100644 input/09sample diff --git a/aoc.cabal b/aoc.cabal index 01cebc9..0957baa 100644 --- a/aoc.cabal +++ b/aoc.cabal @@ -69,3 +69,9 @@ executable Day08 build-depends: base, aoc, containers default-language: Haskell2010 hs-source-dirs: execs + +executable Day09 + main-is: Day09.hs + build-depends: base, aoc, containers, parsec + default-language: Haskell2010 + hs-source-dirs: execs diff --git a/default.nix b/default.nix index 64861a5..78e9f1f 100644 --- a/default.nix +++ b/default.nix @@ -3,8 +3,9 @@ mkDerivation { pname = "aoc"; version = "0.1.0.0"; src = ./.; - isLibrary = false; + isLibrary = true; isExecutable = true; + libraryHaskellDepends = [ base ]; executableHaskellDepends = [ base containers parsec ]; license = "unknown"; hydraPlatforms = stdenv.lib.platforms.none; diff --git a/execs/Day08.hs b/execs/Day08.hs index 7d3fce8..6546990 100644 --- a/execs/Day08.hs +++ b/execs/Day08.hs @@ -40,6 +40,6 @@ genAll (acc:rest) = map (acc:) $ genAll rest main :: IO () main = do n <- map (parseLine . words) . lines <$> readFile "input/08" - let solve1 = run 0 0 Set.empty . Map.fromList . zip [0..] + let solve1 = run 0 0 mempty . Map.fromList . zip [0..] print $ solve1 n - print $ solve1 $ head $ filter (doesEnd 0 0 Set.empty . Map.fromList . zip [0..]) $ genAll n + print $ solve1 $ head $ filter (doesEnd 0 0 mempty . Map.fromList . zip [0..]) $ genAll n diff --git a/execs/Day09.hs b/execs/Day09.hs new file mode 100644 index 0000000..e2e5fd4 --- /dev/null +++ b/execs/Day09.hs @@ -0,0 +1,35 @@ + +module Main where + +import Utils +import Data.List (inits, tails, find) +import Data.Bifunctor + +parseLine :: String -> Int +parseLine = read + +doCheck :: [Int] -> Int -> Bool +doCheck preamble target = target `elem` p + where p = [x + y | x <- preamble, y <- preamble, x /= y] + +checkAll :: [Int] -> [Int] -> [(Int, Bool)] +checkAll preamble [x] = [(x, doCheck preamble x)] +checkAll preamble@(p:ps) (x:xs) = (x, doCheck preamble x) : checkAll (ps++[x]) xs + + +findWeakness :: [[Int]] -> Int -> Int +findWeakness subs target = mn + mx + where Just t = find ((== target) . sum) subs + mn = minimum t + mx = maximum t + +main :: IO () +main = do + n <- map parseLine . lines <$> readFile "input/09" + let preambleLen = 25 + Just (target, _) = find (not . snd) + $ uncurry checkAll + $ bimap (take preambleLen) (drop preambleLen) + $ (,) n n + print target + print $ findWeakness (sublists n) target diff --git a/input/09 b/input/09 new file mode 100644 index 0000000..e8a2fe7 --- /dev/null +++ b/input/09 @@ -0,0 +1,1000 @@ +29 +44 +11 +5 +42 +8 +17 +23 +18 +16 +50 +47 +21 +3 +25 +28 +36 +34 +48 +30 +32 +40 +22 +19 +41 +13 +56 +14 +11 +20 +39 +43 +17 +64 +57 +66 +31 +16 +106 +27 +79 +25 +36 +24 +46 +38 +28 +33 +92 +29 +30 +34 +89 +35 +53 +83 +42 +40 +137 +41 +50 +43 +68 +49 +69 +52 +79 +60 +54 +62 +165 +57 +87 +102 +95 +110 +114 +75 +76 +239 +81 +94 +176 +84 +163 +92 +119 +173 +143 +167 +106 +111 +116 +197 +132 +133 +194 +151 +156 +157 +159 +160 +313 +165 +175 +249 +178 +240 +176 +269 +198 +217 +286 +310 +227 +424 +289 +273 +434 +265 +393 +332 +415 +337 +444 +530 +325 +340 +341 +351 +354 +451 +374 +403 +492 +649 +922 +500 +537 +516 +538 +554 +590 +639 +597 +825 +867 +662 +665 +666 +841 +676 +1113 +715 +705 +957 +777 +1242 +1134 +1016 +1037 +1038 +1328 +1054 +1155 +1092 +1144 +1187 +1236 +1312 +1327 +1799 +1623 +1331 +1342 +1381 +2518 +1420 +1482 +1662 +2049 +1814 +2419 +2146 +2404 +3382 +2342 +2209 +2247 +3141 +2236 +3296 +2563 +2567 +2654 +4727 +2673 +2712 +2863 +2723 +2801 +4050 +3469 +3144 +6270 +5287 +3960 +4456 +4355 +4445 +4483 +4551 +5236 +7099 +5099 +5217 +9278 +6142 +8568 +5327 +5385 +5396 +8540 +5524 +5867 +5945 +8996 +9196 +7104 +8315 +12316 +8405 +9681 +8800 +8928 +9034 +11341 +10316 +12203 +10909 +10544 +10712 +10723 +10781 +10851 +10920 +11263 +14979 +11391 +11812 +18609 +18445 +15419 +17827 +17205 +17333 +17439 +17962 +17834 +19244 +19350 +20860 +21028 +31447 +29956 +35796 +21504 +30270 +22732 +23203 +22183 +35273 +47289 +26810 +27231 +32858 +40566 +53718 +41976 +34538 +37206 +35401 +38694 +53888 +47838 +40854 +41888 +53159 +54041 +78108 +82830 +43687 +44915 +57741 +58604 +48993 +59668 +60089 +61348 +86576 +83531 +69939 +71744 +73232 +72607 +74095 +98362 +91853 +82742 +127430 +84541 +85575 +93908 +103519 +88602 +92680 +101428 +106263 +106734 +107597 +108661 +121016 +135443 +134580 +175178 +141683 +171344 +144351 +145839 +181104 +158636 +193172 +250489 +167283 +173143 +170116 +174177 +245779 +313122 +200277 +194108 +207691 +311799 +214331 +216258 +295193 +255596 +356014 +278931 +286034 +287522 +374974 +290190 +304475 +325919 +328752 +340426 +361391 +341460 +343259 +462037 +374454 +401799 +394385 +407968 +408439 +422022 +430589 +501853 +506448 +534527 +628982 +700893 +564965 +683685 +695961 +594665 +1223647 +776253 +836491 +669178 +681886 +772049 +1351064 +717713 +824974 +768839 +989050 +802353 +816407 +830461 +852611 +932442 +1036380 +1571192 +1248650 +1295558 +1379646 +1159630 +1263843 +1276551 +1312378 +1386891 +1399599 +2560242 +2097911 +1450725 +1540888 +1520066 +1542687 +1593813 +1585246 +2763103 +2435979 +1646868 +1683072 +1785053 +1968822 +2821433 +2436181 +2408280 +2423473 +2539276 +2472008 +2995450 +2711977 +2929578 +3691724 +2850324 +2970791 +2991613 +5257614 +3060954 +3276885 +4444137 +3179059 +3232114 +3468125 +6229190 +5183985 +5655587 +3753875 +4908189 +6007401 +4831753 +4880288 +9920914 +5011284 +5322332 +5562301 +10563776 +5779902 +5821115 +5841937 +14752667 +6932934 +9843037 +6240013 +6745010 +8585628 +8937860 +9076207 +7222000 +8634163 +9316176 +9739942 +10442589 +10470490 +9891572 +9712041 +12774871 +10333616 +10573585 +16824506 +11342203 +14427565 +16682602 +12061128 +13063937 +15330638 +12985023 +13462013 +13967010 +15379173 +17664589 +15856163 +16538176 +16934041 +25747735 +20465157 +19451983 +21773169 +19603613 +20045657 +20285626 +20907201 +38597675 +21915788 +25046151 +23403331 +25125065 +25523141 +26028138 +28364196 +42331206 +26447036 +27429023 +35424830 +39649270 +32394339 +36141789 +33472217 +36386024 +47816179 +42855314 +58057577 +39889239 +51970177 +82504584 +41192827 +48336224 +59500355 +47040853 +48926472 +48528396 +54392334 +53876059 +79241338 +76275263 +134332840 +76617657 +62853853 +65866556 +73587166 +68780363 +83182642 +93163004 +111933636 +87705418 +81082066 +86930092 +91859416 +88233680 +122513638 +135274533 +162423980 +207920006 +111382249 +102802531 +131711038 +108268393 +116729912 +246266476 +142367529 +185367491 +131634216 +134646919 +370343986 +149862429 +195965535 +168012158 +204963592 +144381670 +258130822 +169315746 +175163772 +180093096 +284742070 +279394407 +211070924 +214184780 +219532443 +224998305 +234436747 +239902609 +434604499 +248364128 +519178817 +519297016 +281496645 +266281135 +279028589 +294244099 +344479518 +312393828 +380127364 +563770659 +363914113 +519643290 +388848189 +399625539 +453969190 +425255704 +430603367 +433717223 +908491479 +444530748 +459435052 +678967495 +683092288 +591422417 +733327707 +1252970997 +712745812 +1472262138 +545309724 +573272688 +701242017 +708393631 +1499913896 +833342762 +752762302 +844156287 +788473728 +1556902099 +853594729 +855859071 +893152275 +864320590 +1752647766 +1004744776 +903965800 +1032707740 +1118582412 +1501219540 +1424765179 +1745453552 +1326034990 +1246551741 +1253703355 +1274514705 +1454004319 +1534584779 +1461155933 +1541236030 +1596918589 +1644332799 +1632630015 +2445201830 +1709453800 +1717915319 +2995240349 +2871230178 +2151290152 +1908710576 +1936673540 +2178480505 +2707707674 +2365134153 +2500255096 +2600549695 +2521066446 +4672356598 +2528218060 +2714859288 +4405814957 +4424313088 +4304626263 +4074587953 +4244882494 +5100804791 +3896395824 +3342083815 +3427369119 +3618164376 +3845384116 +7692752329 +4060000728 +4087191081 +4115154045 +4886200599 +4543614658 +5079993441 +4865389249 +6424613884 +8568752422 +5049284506 +8269697204 +5243077348 +6142228407 +13669557213 +7501957072 +6769452934 +6960248191 +8360036539 +18749550654 +7272753235 +11779943410 +7045533495 +7463548492 +8388998774 +16081751103 +24441787642 +8202345126 +8658768703 +9409003907 +20625365761 +12911681341 +10292361854 +12012530282 +14652081255 +19811785620 +11385305755 +12203325539 +13644185479 +14509081987 +18658058990 +14318286730 +14005781686 +14736301727 +15247878621 +21114026467 +15665893618 +33100556345 +15852547266 +16591343900 +27962472209 +16861113829 +22304892136 +18067772610 +19701365761 +23588631294 +28159559962 +25391087441 +23397836037 +36779920085 +25029491234 +25894387742 +26939627266 +27649967165 +28324068416 +28742083413 +29054588457 +44511080994 +37552770757 +50628960552 +46391841026 +32713661095 +32443891166 +45020673791 +45717739775 +40258949866 +34928886439 +58326722476 +37769138371 +43099201798 +48427327271 +48788923478 +53353559650 +49292223779 +77481915728 +50923878976 +61037729511 +54589594431 +56392050578 +57066151829 +71841285211 +70213029537 +70266431852 +84160979397 +65157552261 +67372777605 +67642547534 +72698024810 +75187836305 +104277438626 +115392874305 +105141915976 +87061362150 +86196465642 +91526529069 +97216250749 +103881818210 +100216102755 +150179940538 +111655746260 +105513473407 +204769534969 +126658482430 +113458202407 +122223704090 +142107717063 +156409495179 +137855577071 +132530329866 +179298293794 +158899306674 +154703909684 +147885861115 +190473904268 +197040002476 +206919403374 +173257827792 +177722994711 +183412716391 +235681906497 +217340020617 +350980822503 +217169219667 +247621190470 +328824965927 +227737177497 +301007023737 +240116684837 +361135711102 +380151520336 +292559486755 +287234239550 +328329481339 +280416190981 +327184154909 +302589770799 +395063015328 +321143688907 +356670544183 +475798591334 +390332119765 +390427047459 +394892214378 +573744836156 +434509240284 +444906397164 +504403459217 +530326948296 +581423214718 +620888968094 +716206704235 +520532875818 +527350924387 +755652929191 +567650430531 +682126453928 +1151215916390 +1057221806052 +675479206309 +1043390859144 +659260314982 +1095001354918 +677814233090 +1065811326074 +835238516929 +1208141181386 +1077018668306 +829401454662 +879415637448 +938912699501 +1551445221164 +1752497874615 +1047883800205 +1088183306349 +1141421843912 +1635068566639 +1179793190800 +1341386768910 +1488661769644 +1226910745513 +1747443621331 +1334739521291 +1337074548072 +2482808612822 +1494498831911 +1743625559164 +1507215687752 +1513052750019 +1923421823278 +2015931367807 +1708817092110 +1768314154163 +1818328336949 +1927299437653 +2273652220792 +2136067106554 +3650999934446 +2189305644117 +2429570075259 +2476161365203 +2976455335549 +2568297514423 +2561650266804 +3695613591816 +4991220342063 +2671814069363 +2847792271310 +2831573379983 +3001714519663 +3007551581930 +3216032779862 +5808028715532 +5233464336167 +3850721260931 +3477131246273 +3586642491112 +4091980557741 +4775091708963 +4063366544207 +4325372750671 +4565637181813 +5147975434566 +4618875719376 +9473348185237 +5323953636513 +5129947781227 +5416089785733 +5679365651293 +8314489311192 +5839124961913 +5503387449346 +7977740052537 +5833287899646 +6693164026135 +8625106680839 +6802675270974 +9766851153942 +7063773737385 +7327852507204 +7540497790480 +7650009035319 +15642341818396 +9942829355889 +12688473225046 +14868350297684 +10034965505109 +9748823500603 +10122263168722 +10453901417740 +12017117662648 +11182753100639 +11512653550939 +11342512411259 +11336675348992 +12526451925781 +12897061637031 +17726563553140 +18877173139472 +13495839297109 +13866449008359 +14130527778178 +14977861542523 +17362818012313 +15190506825799 +23809278364248 +17398832535922 +32917070378939 +19691652856492 +45605543603985 +21790576766732 +24409715187970 +19871086669325 +20576164586462 +23353793011640 +22519428449631 +31207762018317 +32218104782273 +22679187760251 +26763510645390 +33473226223493 +41080356564780 +28473700839632 +27362288305468 +27626367075287 +27996976786537 +63599785014411 +42390515118956 +60215081568810 +32589339361721 +37090485392414 +37269919205247 +39562739525817 +42366741353194 +40447251255787 +50264277606364 +61099593298780 +58981615427663 +54125798950858 +45873221461271 +61063040201353 +49442698405641 +61946927063125 +50041476065719 +54988655380755 +104431353786396 +64632207510715 +105079458766502 +55359265092005 +55623343861824 +67559716312354 +69859258566968 +72152078887538 +89889949661428 +69679824754135 +144878605042183 +95315919866912 +80009990781604 +82813992608981 +152162069669142 +101496565323095 +104854836888934 +95914697526990 +99484174471360 +100861876842026 diff --git a/input/09sample b/input/09sample new file mode 100644 index 0000000..28d66e4 --- /dev/null +++ b/input/09sample @@ -0,0 +1,20 @@ +35 +20 +15 +25 +47 +40 +62 +55 +65 +95 +102 +117 +150 +182 +127 +219 +299 +277 +309 +576 diff --git a/lib/Utils.hs b/lib/Utils.hs index 4319714..89b1bd3 100644 --- a/lib/Utils.hs +++ b/lib/Utils.hs @@ -5,11 +5,13 @@ module Utils ( binaryToInt , bet , (&+) , howMany + , sublists ) where import Data.Char (digitToInt) import Control.Monad import Data.Either +import Data.List (inits, tails) binaryToInt :: String -> Int @@ -34,3 +36,6 @@ bet k (l, u) = k >= l && k <= u howMany :: (a -> Bool) -> [a] -> Int howMany predicate = length . filter predicate + +sublists :: [a] -> [[a]] +sublists = concatMap inits . tails -- cgit v1.2.3