From fd1a5d57031cffaa3ed70935690e5cf8a4bc6061 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sun, 3 Jan 2021 17:39:36 +0000 Subject: [PATCH] Done day 21 --- advent21/package.yaml | 62 +++++++++++++++++ advent21/src/advent21.hs | 81 ++++++++++++++++++++++ data/advent21.txt | 41 +++++++++++ data/advent21a.txt | 4 ++ problems/day21.html | 143 +++++++++++++++++++++++++++++++++++++++ stack.yaml | 1 + 6 files changed, 332 insertions(+) create mode 100644 advent21/package.yaml create mode 100644 advent21/src/advent21.hs create mode 100644 data/advent21.txt create mode 100644 data/advent21a.txt create mode 100644 problems/day21.html diff --git a/advent21/package.yaml b/advent21/package.yaml new file mode 100644 index 0000000..49b2786 --- /dev/null +++ b/advent21/package.yaml @@ -0,0 +1,62 @@ +# 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: advent21 +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: + advent21: + main: advent21.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - text + - attoparsec + - containers + - csp diff --git a/advent21/src/advent21.hs b/advent21/src/advent21.hs new file mode 100644 index 0000000..1b2f418 --- /dev/null +++ b/advent21/src/advent21.hs @@ -0,0 +1,81 @@ +-- import Debug.Trace + +-- import Data.Text (Text) +-- import qualified Data.Text as T +import qualified Data.Text.IO as TIO + +import Data.Attoparsec.Text hiding (take) +-- import Data.Attoparsec.Combinator +-- import Control.Applicative +-- import Control.Applicative.Combinators + +import qualified Data.Set as S +import qualified Data.Map.Strict as M +import Data.List +import Control.Monad.CSP + + +type Ingredient = String +type Allergen = String +data Food = Food + { ingredients :: S.Set Ingredient + , allergens :: S.Set Allergen + } deriving (Show, Eq) + +type CandidateIngredients = M.Map Allergen (S.Set Ingredient) + + + +main :: IO () +main = + do text <- TIO.readFile "data/advent21.txt" + let foods = successfulParse text + let candidates = M.unionsWith S.intersection $ map allergenMap foods + -- print candidates + print $ part1 candidates foods + putStrLn $ part2 candidates + + +part1 candidates foods = sum $ map countSafe foods + where possibleAllergens = S.unions $ M.elems candidates + countSafe food = S.size $ (ingredients food) `S.difference` possibleAllergens + +part2 candidates = intercalate "," $ map snd $ sortOn fst assignments + where assignments = knownAllergens candidates + + +allergenMap :: Food -> CandidateIngredients +allergenMap food = M.fromList $ S.toList $ S.map (, ingredients food) $ allergens food + +knownAllergens :: CandidateIngredients -> [(Allergen, Ingredient)] +knownAllergens candidates = zip allergens assignedIngredients + where + (allergens, possibleIngredients) = unzip $ M.toList candidates + assignedIngredients = solveAllergens $ map S.toList possibleIngredients + +solveAllergens :: [[Ingredient]] -> [Ingredient] +solveAllergens possibleIngredients = oneCSPSolution $ do + dvs <- mapM mkDV possibleIngredients + mapAllPairsM_ (constraint2 (/=)) dvs + return dvs + +mapAllPairsM_ :: Monad m => (a -> a -> m b) -> [a] -> m () +mapAllPairsM_ _f [] = return () +mapAllPairsM_ _f (_:[]) = return () +mapAllPairsM_ f (a:l) = mapM_ (f a) l >> mapAllPairsM_ f l + + +-- Parse the input file + +foodsP = foodP `sepBy` endOfLine +foodP = Food <$> ingredientsP <* " (contains " <*> allergensP <* ")" + +ingredientsP = S.fromList <$> (many1 letter) `sepBy` (many1 space) +allergensP = S.fromList <$> (many1 letter) `sepBy` (string ", ") + + +-- successfulParse :: Text -> (Integer, [Maybe Integer]) +successfulParse input = + case parseOnly foodsP input of + Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err + Right foods -> foods diff --git a/data/advent21.txt b/data/advent21.txt new file mode 100644 index 0000000..7c1175f --- /dev/null +++ b/data/advent21.txt @@ -0,0 +1,41 @@ +rhvbn qmsvv ljxg xstb kfdnn djvbx jfv vsvp jnnm fmhnz mmcpg htlcct tcdh dnbjj nsgxgt pqbqdf nlcs zjbbf rprxk lhtgpq trpsgj jgtb lpxpd jtnkgm czznp tnhxbg fvk lpdg hzdr zrb vmmzf vtvz jfzxh rjnfhjr zjtdlhx qjlnrd xpm zfxkdm dqqc ph lbmt thmn kjf cjdnjs lszkg dtgphg jkdxh tvfvbt zqtx jndhc tvmgpm jnxdf qzks (contains nuts, wheat) +jnnm dzss btfdjt lpdg dpzf jjttj xhxdcsbp qsbs ntlb xrsfms kdzfph lnjv rhvbn jkdxh vtrbv qmsvv fpxxp mrktkf ph csdm trpsgj cjdnjs thmn bbmd jnxdf pgrh kflqfz ccvrnj hcbdb cvlxbh ptzbsppb tcdh hrvcrn fvk tqkfz kjf zrb lbmt dnbjj htlcct hpzbmr czznp gggjklx vmczz dqqc kzqbp xpm nhnggd xsxqg cdxd btcz blvtr scz jztg mmcpg kfdnn chnz gjttzr zjtdlhx vncr kctgrh xstb lfd lkcdpq xntshr pqbqdf hckjb fnvhs qjblr brlnlxn xqhhzhm pmctk hnjj drtg (contains nuts, fish) +hcbdb zqtx zrb ptzbsppb lkcdpq xhxdcsbp bqsdns czznp ntlb gjxfhp kjf lpdg gglt lcmgk jgtb xvkt hnjj sft pmpzd kzqbp rhvbn szfjpqr tvmgpm fvk gggjklx pqbqdf btfdjt cmmzk xbcvfz zjrchqf dpzf brlnlxn pdhmbzv jmf qrdxd kpftvl mmcpg dqqc vhsfl jnxdf btcz bfmsp nskq hrfntmq cjdnjs zvrvcd jkdxh lsmm kflqfz fnvhs qsbs gttbj hlcpn cbsscr dgphkk (contains wheat) +hjqcsln rshbrd fjzpl hrvcrn tmcbg dtgphg hzdr dqqc vjbcvv gmgkzt qrdxd jgtb lbmt lcmgk pqbqdf zjbbf rhvbn lnjv fmhnz mmcpg dgphkk dpzf thmn pgrh hznmc zjrchqf dnbjj mtnpmq tqkfz cjdnjs fvk gtrbsg lszkg jfv tvmgpm gzlb hpzbmr scz hcjfd qvhsvb dzss hnjj xbcvfz nlcs kctgrh nhnggd ggjjh gglt czznp djvbx kjf trkmvj zrb ccvrnj pmpzd ncdkz drtg kzqbp cdxd crn ljxg pmctk dfxjkx fnvhs bfmsp btcz ntlb cftpt (contains fish, wheat, shellfish) +nlcs zqtx nhxqsg tdkg zktbh jkxhfh scz kjf ph chnz hbr zrb csdm rhvbn ntpz dzss jgtb ngmbqm blvtr drtg pmctk jfv qmsvv gjxfhp vmczz hnjj dqqc lsrbpp hcbdb krzfjbq fjzpl lbmt jfzxh dtgphg lnjv gzlb sft mmcpg jjttj (contains dairy) +qvhsvb hznmc chssff ph kjf kpftvl hcbdb hlcpn mmcpg gjxfhp btfdjt bfmsp gjttzr jztg nhxqsg htlcct vnxkjmn jkdxh lrtmj btcz hrvcrn bqsdns rhvbn fvk nsgxgt dpzf dddp zfxkdm nlcs dtgphg jgtb vsvp zrb qjlnrd cftpt lfd zvtdk vmmzf thmn zjtdlhx hckjb mfhtz jvmbjc lcmgk jndhc fnvhs lzsghj jkxhfh vhsfl (contains dairy, nuts, fish) +zrb vmczz hff jnxdf nhnggd vnxkjmn jndhc xbcvfz bfmsp xntshr pdhmbzv zjbbf plbhvfj vhsfl fzk vtrbv mfhtz ccvrnj tvmgpm hbr dddp jnnm lrtmj nsgxgt qzks lvgtf xstb kgktfrk kpftvl lkcdpq rpbddtn chssff gttbj rhvbn nskq hnjgghfl vsvp xpm dnbjj jgtb ncdkz dpfbzrv blvtr mtnpmq vmmzf lzsghj vtvz btcz tgvst hctzbr gj dpzf fzpgzs ljxg cdxd htlcct jmf krzfjbq mzsjc fvk thmn lbmt jkxhfh vznjkl bqsdns chnz hcbdb tmcbg xjjst zvrvcd ptzbsppb rshbrd kjf xqhhzhm hznmc qjblr sft nlcs dfxjkx ntlb qvhsvb xsxqg (contains shellfish, sesame) +fdxbq pgrh blvtr fpxxp mfhtz rpbddtn ttrb cftpt htlcct tcdh hnjj hrvcrn rhvbn zrb mfczrq tvfvbt vtvz hcjfd zqtx chssff vsvp pmpzd kjf jnxdf xpm cctf gggjklx mmcpg dpzf hnjgghfl thmn kzjrpl tvmgpm lbmt btcz jkdxh hlcpn jfzxh fmhnz vhsfl ccvrnj ncdkz hckjb lsrbpp xqhhzhm vznjkl ddmtvx fjzpl cbsscr cvlxbh hznmc ljxg pqbqdf kchz zvtdk mzsjc vmczz kgktfrk hcbdb hnjqd lnjv jztg mqmfbc lsmm kpftvl dpfbzrv fzpgzs zjtdlhx vnxkjmn mtxxxm djvbx jtktgz scz xsxqg gjxfhp czznp mtnpmq gjttzr cmmzk bbhxjj ph vtrbv xvkt zvrvcd dnbjj cjdnjs fvk (contains soy, dairy, fish) +rhvbn ccvrnj lcmgk gtnkm vznjkl hzdr jtnkgm ntlb zvrvcd mtxxxm blvtr vtvz lbmt hnjj xntshr qzks lpxpd dddp gkqzl djvbx krzfjbq zrb qjblr hvjql kzjrpl jgtb pgrh hctzbr mfczrq xbcvfz jnxdf hcjfd lnjv rprxk zjbbf gttbj jvmbjc zvtdk dtgphg dpfbzrv zfxkdm tgvst csdm xqhhzhm vnxkjmn fvk jfzxh mmcpg hnjqd xhxdcsbp hcbdb ph hckjb hpzbmr brlnlxn hjqcsln hnjgghfl (contains wheat, soy) +nhxqsg vjbcvv zqtx rhvbn bbhxjj tgvst kdzfph vmmzf lbmt htlcct hnjgghfl lszkg vsvp mfhtz hvjql gzlb kgktfrk qsbs qjblr fzpgzs pdtkd cmmzk bbmd jnnm jkdxh jtnkgm xpm hff qmsvv kchz xsxqg kzqbp hrvcrn hvgms fdxbq nsgxgt cftpt cctf dpzf xstb tdkg vhsfl hpzbmr dnbjj jfv szfjpqr tvmgpm kpftvl hctzbr ncdkz czznp vnxkjmn chssff fvk mmcpg fjzpl ttrb tnhxbg lfd jgtb zrb lvgtf xqhhzhm kfdnn jtktgz gjttzr lrtmj kdh djvbx kflqfz cjdnjs gglt qjlnrd jvmbjc mrktkf xjjst tmcbg kjf ngmbqm ptzbsppb jnxdf sft jmf tcdh tqkfz (contains sesame, eggs) +jfv qjlnrd krzfjbq gtnkm jgtb hbr zjbbf hrvcrn ccvrnj rprxk gjxfhp gtrbsg lbmt dnbjj fjzpl vtvz tqkfz pgrh jtnkgm hcbdb dzss bfmsp hctzbr kctgrh lpxpd kzqbp gggjklx jndhc zktbh vjbcvv dfxjkx tvmgpm ngmbqm csdm bqsdns nhnggd mtxxxm vncr zjtdlhx tgvst xstb fmhnz trpsgj djvbx vnxkjmn xqhhzhm mfhtz mtnpmq ttrb kzjrpl hrfntmq rhvbn jjttj dddp jkxhfh czznp zrb qjblr cftpt cbsscr kflqfz szfjpqr hckjb fvk mmcpg hnjqd cctf ncdkz jtktgz rpbddtn gj jvmbjc mqmfbc dpfbzrv vznjkl dgphkk mrktkf kdzfph blvtr tcdh kfdnn hznmc hnjj ntlb cvlxbh (contains soy) +ntlb cbsscr rhvbn gtrbsg bbhxjj zrb mfczrq fnvhs chnz vsvp kjf ptzbsppb qsbs lpdg scz kzjrpl xpm jgtb gjttzr zjrchqf zjbbf hcbdb vmczz drtg hnjqd xqhhzhm kgktfrk hbr jkdxh jztg zfxkdm jfzxh nskq xvkt lbmt kplm dnbjj cctf zvtdk tvmgpm hvjql hznmc fvk gggjklx vmmzf hff zjtdlhx ncdkz (contains fish) +jfzxh btfdjt hcjfd zjtdlhx lcmgk thmn ddmtvx zrb kjf mqmfbc pmctk hcbdb nlcs plbhvfj gttbj rhvbn jgtb fjzpl bbmd brlnlxn mtnpmq xrsfms hvgms chssff jmf pmpzd drtg hff kzqbp qjlnrd hrfntmq hckjb lnjv sft cctf lbmt tgvst gjttzr tvmgpm chnz kflqfz hctzbr fvk dpfbzrv tnhxbg dqqc jnnm zqtx xvkt bbhxjj rshbrd hbr vtvz htlcct (contains fish, dairy) +sft plbhvfj cdxd jztg hjqcsln hbr rshbrd ncdkz zjtdlhx tvfvbt btfdjt tqvv crn tgvst zjrchqf scz kpftvl xvkt krzfjbq jgtb tmcbg pmctk rhvbn hcbdb vnxkjmn cjdnjs vncr lbmt fzk xrsfms hvgms qsbs kjf hctzbr jnnm nskq fpxxp hrvcrn gttbj zrb nmn fvk lpxpd vtvz zjbbf gglt lrtmj lsmm jvmbjc fdxbq (contains nuts, sesame, dairy) +lpxpd lsmm kpftvl qjblr lrtmj jfzxh xstb zrb jfv rkdmz gjxfhp vmmzf ncdkz mzsjc hzdr kdzfph pmpzd xsxqg vmczz gj chnz vsvp ntlb hckjb tvfvbt fvk ddmtvx hff xvkt nhnggd mfhtz cjdnjs mmcpg rhvbn btfdjt gkqzl kgktfrk jnxdf nsgxgt gggjklx ntpz kjf tqvv tnhxbg bqsdns ph fpxxp qsbs zjtdlhx jjttj fzpgzs fdxbq tgvst vhsfl hcbdb lzsghj dpzf dgphkk zfxkdm cftpt bbmd rjnfhjr pdtkd qrdxd jgtb gzlb (contains soy, dairy, shellfish) +chssff btfdjt fzk lszkg jmf tqkfz jnnm vtvz vtrbv fmhnz fvk hrvcrn ptzbsppb xpm jfv cdxd kgktfrk gggjklx tnhxbg vznjkl qzks brlnlxn djvbx mrktkf tcdh kflqfz kctgrh gzlb cftpt hnjj hcbdb jgtb kdzfph tvmgpm gglt cjdnjs mmcpg jnxdf bqsdns tvfvbt dqqc tgvst lbmt crn zktbh trkmvj kfdnn xsxqg pmpzd scz hjqcsln lvgtf lpxpd zjtdlhx csdm krzfjbq mzsjc lsrbpp dpfbzrv fzpgzs zrb rhvbn hff xstb (contains dairy, nuts) +fmhnz mmcpg qvhsvb dpfbzrv hvjql gtrbsg mtxxxm rhvbn tvmgpm tqkfz kzqbp brlnlxn kjf tgvst rshbrd bbmd hcbdb trpsgj vznjkl dgphkk pmctk gttbj mqmfbc jjttj dzss tvfvbt zrb hlcpn kdzfph lpxpd fnvhs fvk szfjpqr hrfntmq zjrchqf thmn xjjst qvbbs bfmsp ccvrnj tqvv xstb cjdnjs kgktfrk tnhxbg qzks ph fpxxp djvbx qrdxd gjxfhp lcmgk hff htlcct xntshr tcdh qjblr qjlnrd kplm vhsfl jkdxh kchz trkmvj cvlxbh jmf rpbddtn pdtkd gj kflqfz ggjjh mzsjc nskq xqhhzhm kctgrh hctzbr fdxbq zfxkdm jnnm dddp gmgkzt tmcbg bqsdns hckjb gkqzl mrktkf lhtgpq jgtb xpm hcjfd xsxqg vjbcvv (contains shellfish, dairy, nuts) +lpdg xhxdcsbp gtnkm hpzbmr tgvst dtgphg lnjv cbsscr jtktgz dgphkk hznmc kzqbp xsxqg nskq kchz lbmt zvrvcd tvfvbt fjzpl jztg crn mrktkf jfzxh ntpz jgtb rshbrd trkmvj fvk hcbdb xbcvfz vsvp zvtdk kflqfz tvmgpm zjrchqf hnjj jkxhfh czznp qsbs rpbddtn hzdr zktbh gzlb dfxjkx lkcdpq vznjkl xstb gj plbhvfj cmmzk htlcct zrb qvhsvb mmcpg jnxdf nhnggd pdhmbzv ncdkz mzsjc zjtdlhx thmn lpxpd kjf lzsghj bfmsp hjqcsln gkqzl tcdh hckjb rprxk gmgkzt hctzbr tqkfz ccvrnj hvgms lcmgk gglt vtvz (contains soy, fish) +tmcbg pgrh gjxfhp jgtb ddmtvx dpfbzrv lnjv xpm mfhtz sft plbhvfj ncdkz gmgkzt hckjb dfxjkx lbmt qsbs rhvbn jnxdf xsxqg dpzf mrktkf jkxhfh kdzfph jnnm kdh vjbcvv kjf bfmsp dqqc lpdg ntpz fjzpl rpbddtn xjjst chssff dddp jndhc qvhsvb zrb btfdjt gtnkm hjqcsln hnjqd zvtdk vznjkl rshbrd kzjrpl brlnlxn lhtgpq vmmzf zjtdlhx fvk pqbqdf jmf hrfntmq nskq mtnpmq btcz hff jztg zktbh hnjgghfl hcbdb zjrchqf tdkg vsvp tgvst jtnkgm lzsghj djvbx blvtr fzpgzs czznp qrdxd (contains dairy, shellfish, wheat) +pgrh vsvp tdkg xntshr hzdr csdm jtnkgm qrdxd pdtkd vhsfl chssff tqvv hctzbr lfd ddmtvx tnhxbg hcbdb nsgxgt ccvrnj tcdh hjqcsln bbmd kzqbp pdhmbzv fpxxp kplm cvlxbh ttrb lsmm jjttj vmmzf jkxhfh xqhhzhm gzlb gtrbsg gttbj lbmt mzsjc fnvhs rhvbn bbhxjj kctgrh mqmfbc zrb jgtb rprxk crn mmcpg gj ntlb pmctk jkdxh kdzfph vznjkl cctf ntpz hbr hnjj mrktkf qjblr tgvst zjtdlhx xjjst fzk vmczz nskq jnxdf hckjb kjf czznp scz (contains fish, sesame) +nsgxgt hznmc jmf fmhnz btfdjt dtgphg lpxpd tqkfz ptzbsppb hnjj crn gjxfhp nskq cftpt fnvhs ntlb dpzf qsbs jgtb hzdr ddmtvx rhvbn qjblr ngmbqm nhxqsg zqtx kfdnn sft hctzbr hrfntmq dfxjkx gzlb cbsscr plbhvfj hnjgghfl zfxkdm gmgkzt lvgtf vhsfl tcdh xvkt tnhxbg qjlnrd lrtmj fpxxp xbcvfz hbr jtnkgm kjf gtnkm vmmzf kplm qmsvv tdkg pgrh chnz gggjklx cvlxbh vmczz lfd rpbddtn kzqbp mfczrq lszkg tgvst bbhxjj hcbdb lsrbpp lpdg fvk kctgrh mtxxxm szfjpqr brlnlxn hckjb jztg zrb jnnm xpm lbmt fzpgzs vjbcvv hnjqd jndhc jjttj (contains fish, wheat) +rkdmz lzsghj fzpgzs lsmm pmpzd fpxxp pqbqdf jjttj kdh mmcpg xbcvfz qrdxd fvk qjblr kjf dpfbzrv lsrbpp gtnkm trkmvj ptzbsppb hlcpn bfmsp jndhc lcmgk xpm xqhhzhm kplm ph fmhnz jgtb tnhxbg xjjst gmgkzt vmczz lpxpd jkxhfh jfzxh rpbddtn scz jtnkgm blvtr rprxk kgktfrk plbhvfj gtrbsg gttbj gkqzl zrb rhvbn hctzbr kflqfz hnjgghfl nsgxgt bbhxjj xsxqg btfdjt nhnggd tqkfz kdzfph hrfntmq ntlb lbmt tqvv tvfvbt vtrbv qmsvv qvhsvb hckjb hrvcrn tcdh xrsfms chssff pdhmbzv dpzf rjnfhjr kctgrh lkcdpq mtxxxm djvbx vhsfl zqtx gjxfhp ncdkz vznjkl gjttzr ntpz zvtdk dgphkk cdxd (contains dairy, shellfish) +lszkg chssff kdzfph drtg ntlb xhxdcsbp vsvp vncr mrktkf fmhnz lrtmj tqvv vnxkjmn fvk xstb xvkt jgtb lzsghj zjbbf hctzbr hcjfd xqhhzhm hznmc kctgrh rhvbn btfdjt jjttj jtktgz xrsfms tmcbg lsmm xpm gj lbmt tgvst sft plbhvfj zktbh hcbdb dzss fjzpl mtxxxm tdkg kpftvl zrb rpbddtn mmcpg hjqcsln (contains sesame, nuts, dairy) +lfd jgtb vnxkjmn gtnkm zqtx hvgms lszkg ggjjh dgphkk fvk lnjv tqkfz gglt krzfjbq ncdkz jfzxh rkdmz hcbdb pmpzd rjnfhjr qsbs hnjgghfl dpzf csdm crn mfczrq lrtmj sft tdkg lzsghj gzlb zrb ntpz rshbrd xbcvfz kdzfph bqsdns cvlxbh lbmt nlcs kflqfz tmcbg hznmc lvgtf scz hvjql jjttj rhvbn hbr hcjfd pgrh btcz jtnkgm jtktgz ph hrvcrn tvmgpm zjrchqf vtrbv mmcpg ntlb vncr hrfntmq fzpgzs ngmbqm thmn chnz fdxbq dfxjkx tgvst pdtkd hnjj qjlnrd jndhc (contains sesame, dairy, shellfish) +mfhtz trkmvj vhsfl zktbh mqmfbc hrfntmq vsvp ddmtvx fmhnz ngmbqm crn cmmzk rkdmz nlcs szfjpqr pqbqdf xstb mtnpmq rpbddtn cvlxbh kzqbp xqhhzhm lzsghj xsxqg fvk hcbdb pmpzd kzjrpl hlcpn qzks kdh jnxdf mmcpg jkxhfh fzpgzs djvbx lbmt cftpt dpfbzrv ljxg ntpz rprxk zqtx rjnfhjr cjdnjs lnjv lfd hckjb dgphkk jgtb qrdxd btcz gjxfhp qmsvv sft zjrchqf cctf zvtdk xvkt hrvcrn mfczrq blvtr hbr fjzpl rhvbn drtg vmmzf zrb (contains sesame, eggs, soy) +pmpzd jgtb jtktgz jvmbjc zrb gjxfhp tqkfz mmcpg vsvp pdhmbzv tgvst tdkg hpzbmr lbmt vtvz hnjj ljxg trkmvj hckjb mfczrq lcmgk vjbcvv qvhsvb cbsscr xvkt fmhnz lsrbpp hrfntmq kjf krzfjbq jndhc vtrbv xpm dgphkk jfv gtrbsg gj fvk tcdh trpsgj chnz ccvrnj nhxqsg xrsfms hlcpn rhvbn (contains sesame) +zvrvcd hrvcrn jgtb mmcpg cbsscr pgrh djvbx xhxdcsbp plbhvfj lszkg fvk szfjpqr jkdxh gtrbsg hrfntmq dpzf bfmsp jkxhfh jfv ngmbqm nsgxgt cctf kjf crn dpfbzrv hvgms jtnkgm gmgkzt nmn mfczrq ddmtvx trpsgj xntshr xvkt bbhxjj xstb dqqc qzks ph jvmbjc mtnpmq mqmfbc jmf hctzbr brlnlxn hpzbmr kdh hcjfd mrktkf gtnkm nlcs kchz rhvbn zjtdlhx fzk czznp zrb xsxqg kzjrpl htlcct sft hcbdb qjblr pqbqdf hzdr kflqfz kgktfrk vsvp cmmzk rjnfhjr dfxjkx xpm cftpt tqvv nhxqsg (contains eggs, shellfish) +hbr tqkfz lsmm gkqzl jtnkgm tvfvbt plbhvfj kzjrpl rkdmz zrb hjqcsln gggjklx nhnggd zvtdk kchz lcmgk hnjj tgvst gmgkzt vsvp pmctk fvk jtktgz xpm hvgms ntpz vmczz zjrchqf hvjql nhxqsg mmcpg tdkg dqqc zjbbf gjttzr crn gzlb mzsjc zqtx rhvbn dgphkk hnjqd hzdr dpfbzrv trpsgj kpftvl czznp mfhtz zktbh dddp mtxxxm lbmt jvmbjc qvhsvb xqhhzhm fjzpl xntshr vznjkl rjnfhjr fmhnz htlcct qrdxd nlcs gjxfhp qvbbs hrfntmq lfd nskq tnhxbg pgrh gtrbsg hff pdhmbzv ph fdxbq jgtb vmmzf cftpt kjf hcjfd (contains nuts, fish) +dddp ptzbsppb ljxg vjbcvv djvbx mfczrq hbr gzlb btcz gggjklx vhsfl kzqbp pgrh thmn gtrbsg jfv hpzbmr fvk csdm ccvrnj gkqzl tqkfz mtxxxm dzss bbhxjj lpxpd qvhsvb rkdmz pdhmbzv hcjfd vmczz hrvcrn jvmbjc kdzfph zvrvcd mqmfbc hcbdb zrb tqvv lsrbpp trpsgj lbmt gglt kdh szfjpqr drtg xvkt zjtdlhx czznp mmcpg kfdnn rshbrd nhxqsg brlnlxn ntpz kpftvl sft cdxd kjf fzk tnhxbg jztg fjzpl dtgphg vtvz jgtb hvgms (contains sesame) +jgtb hcbdb vnxkjmn ph pgrh zjtdlhx xntshr tvfvbt xjjst mmcpg hjqcsln xsxqg jmf brlnlxn jnxdf cjdnjs hctzbr hzdr ljxg ptzbsppb jndhc kchz ngmbqm krzfjbq fzpgzs mtxxxm kfdnn fmhnz bqsdns crn ntlb rhvbn qvbbs zvtdk plbhvfj fdxbq zjrchqf jfv szfjpqr kzqbp ddmtvx vmczz cmmzk fvk thmn qvhsvb nskq lpxpd hlcpn cbsscr fnvhs lbmt kjf zfxkdm xpm qzks rpbddtn tdkg gglt chssff gjttzr dpzf trpsgj lsmm mqmfbc (contains eggs, nuts, dairy) +xqhhzhm nlcs jgtb blvtr zfxkdm hvjql hff kflqfz jnxdf ntpz lkcdpq qsbs qvhsvb mfhtz kfdnn zrb gtrbsg lhtgpq tqkfz lbmt bbmd dgphkk vhsfl cftpt qrdxd pmctk jmf kpftvl qzks zjrchqf kzqbp kzjrpl crn qvbbs cmmzk rhvbn fmhnz dzss kjf vmczz hrfntmq pmpzd mmcpg pqbqdf lpxpd tdkg ph xntshr rpbddtn fvk zqtx vtrbv vjbcvv tgvst xhxdcsbp thmn vmmzf (contains wheat, eggs, fish) +kpftvl bfmsp kflqfz xhxdcsbp brlnlxn jfv gmgkzt xntshr hvjql hlcpn zjtdlhx kdh lbmt xvkt ccvrnj djvbx gkqzl cftpt pdtkd hcbdb fdxbq lpxpd cctf ljxg vmmzf cmmzk jkxhfh fvk tmcbg bbmd pmctk hnjj rshbrd jkdxh zjrchqf fzk lfd ntpz mmcpg lsrbpp vnxkjmn qsbs htlcct hff xbcvfz dpzf lnjv qvhsvb gttbj tnhxbg mtxxxm dzss mfhtz hnjqd ttrb xqhhzhm zqtx jnxdf hpzbmr jgtb kjf zrb qvbbs lsmm tqkfz tvfvbt dtgphg jtnkgm hjqcsln cvlxbh dddp dpfbzrv kzjrpl (contains soy, shellfish) +lcmgk ccvrnj hcbdb ttrb nmn lpxpd qmsvv xntshr zrb zjrchqf mtxxxm hcjfd trkmvj bfmsp zvtdk dtgphg fvk tqkfz lnjv scz xrsfms tmcbg kdh pqbqdf vtvz hznmc htlcct nskq tdkg lhtgpq vncr kjf tgvst cmmzk hnjj dnbjj bbhxjj xqhhzhm tcdh jgtb fdxbq jkxhfh ph qsbs tqvv lbmt kfdnn kchz tvmgpm jztg ntpz pdtkd ntlb hvjql hctzbr ljxg hff zktbh rhvbn hnjqd vtrbv gkqzl nsgxgt kplm cctf dpzf djvbx nlcs (contains shellfish, wheat, dairy) +thmn nlcs hpzbmr hvgms vncr cbsscr btcz pmpzd rpbddtn hzdr gmgkzt csdm rhvbn zvtdk lsmm lcmgk gjttzr blvtr gjxfhp fvk cctf lrtmj bfmsp dpfbzrv dgphkk kjf pqbqdf tqkfz btfdjt mmcpg tnhxbg zktbh hnjj zfxkdm tvmgpm jndhc kzqbp plbhvfj gzlb fzk lnjv scz ttrb xstb zqtx hcbdb pdtkd kdh jkdxh vhsfl jjttj jnxdf dddp vznjkl zrb lbmt gtrbsg fpxxp krzfjbq qjblr lzsghj kpftvl xvkt dnbjj jztg (contains wheat, soy, fish) +kflqfz vtrbv bbhxjj cbsscr tnhxbg tqvv jkxhfh chssff fnvhs zjtdlhx hnjj gtnkm hvgms dqqc dgphkk cftpt tvfvbt jfv lsrbpp lbmt lvgtf fpxxp bbmd mmcpg lpdg xhxdcsbp lhtgpq jndhc trkmvj qvbbs pgrh hckjb jmf htlcct zfxkdm gj nhxqsg mtxxxm dzss lrtmj xvkt xsxqg vncr hvjql xbcvfz fdxbq xstb zvtdk hcbdb qzks dtgphg jgtb gtrbsg rhvbn mzsjc rprxk kfdnn djvbx ljxg hzdr pdtkd hnjqd qmsvv mfhtz xpm qrdxd jtktgz jtnkgm brlnlxn kjf xrsfms fvk czznp ngmbqm kplm (contains soy, nuts, shellfish) +xjjst fvk hnjqd trkmvj ntlb ntpz lsmm bfmsp hznmc mrktkf tdkg jjttj kgktfrk vznjkl gglt lrtmj ggjjh dqqc hrfntmq dzss cvlxbh dpfbzrv zjtdlhx bbmd rhvbn ttrb gggjklx rpbddtn jkxhfh lszkg hlcpn cctf ptzbsppb kpftvl tmcbg dddp zqtx gtrbsg mmcpg vmczz pdtkd ljxg cjdnjs plbhvfj kfdnn vnxkjmn ngmbqm pqbqdf kflqfz lcmgk dpzf pmpzd hbr lpxpd qjblr gtnkm mzsjc ph qrdxd jgtb lbmt gkqzl qvhsvb zvtdk qsbs nhnggd zrb lhtgpq chssff hckjb djvbx kdh cmmzk hzdr lvgtf kjf rkdmz bbhxjj qjlnrd lnjv xbcvfz jmf xntshr tcdh jvmbjc btcz fpxxp lfd (contains sesame, wheat) +tqvv nsgxgt kjf lsrbpp zrb vncr dqqc qzks vmmzf dpzf hcjfd lszkg lzsghj rjnfhjr hznmc fvk djvbx chssff kfdnn zjbbf mmcpg vznjkl kpftvl vsvp xvkt kplm mqmfbc qmsvv gtrbsg pmctk xrsfms jfzxh hzdr hrvcrn crn xhxdcsbp xqhhzhm zjrchqf ptzbsppb xpm pmpzd hcbdb mrktkf kzqbp cdxd gjxfhp vtvz mfhtz jgtb mzsjc dfxjkx lbmt nskq jjttj jtktgz qsbs ddmtvx (contains soy, shellfish) +hnjj qsbs cdxd mfczrq dddp qmsvv kdzfph qjblr gjxfhp zfxkdm crn zjtdlhx dnbjj kjf jkdxh jztg lhtgpq lzsghj lcmgk htlcct qvhsvb ggjjh fzpgzs gmgkzt vmczz btcz qjlnrd cftpt rkdmz jnnm mrktkf lkcdpq hlcpn xbcvfz tqkfz tvmgpm rprxk hckjb dpzf drtg jtnkgm xrsfms qvbbs lsrbpp xsxqg hff czznp ddmtvx btfdjt cvlxbh lrtmj mmcpg xstb vtrbv fvk csdm xjjst rhvbn hpzbmr xntshr tvfvbt xvkt xqhhzhm rjnfhjr lbmt dpfbzrv gj hcbdb tqvv dqqc kchz dzss zqtx hrvcrn nsgxgt zrb kzjrpl cjdnjs vtvz nskq dfxjkx hvgms (contains fish, sesame) +hbr dpfbzrv kgktfrk tcdh trkmvj plbhvfj hcbdb lpdg kdzfph ttrb pdhmbzv tvfvbt mtnpmq zqtx kjf qjlnrd xntshr fmhnz cjdnjs dqqc dddp ptzbsppb hrvcrn lzsghj lfd vhsfl lsrbpp kpftvl rkdmz mmcpg mzsjc lpxpd rshbrd lnjv ngmbqm zjtdlhx xstb rpbddtn nskq lsmm tgvst mfczrq lkcdpq fvk mqmfbc ccvrnj gttbj lszkg gj dtgphg lcmgk drtg qsbs rhvbn pmctk zvtdk qmsvv pdtkd jnnm cctf kdh ddmtvx kplm trpsgj pmpzd nsgxgt ljxg zrb zjrchqf hnjqd ggjjh kchz hff jvmbjc tdkg dgphkk hctzbr fnvhs gtnkm fpxxp hjqcsln jfv hvgms tqkfz fzk jgtb (contains eggs) +gtrbsg vmczz vmmzf ddmtvx zvtdk zjbbf drtg dddp vjbcvv fnvhs chnz pqbqdf dfxjkx hctzbr jkxhfh jztg ljxg rprxk fvk qzks nhnggd mmcpg csdm xqhhzhm tvfvbt zrb xsxqg kfdnn zjrchqf hnjj jkdxh ngmbqm lrtmj jgtb kzjrpl cvlxbh dtgphg hnjgghfl vtrbv jtktgz ttrb hff rhvbn fzk jndhc dzss tdkg hcbdb lbmt ptzbsppb (contains dairy) +rjnfhjr cbsscr vtrbv kzqbp ttrb vmmzf vsvp blvtr dfxjkx nlcs chnz kpftvl lbmt htlcct rhvbn kflqfz gjxfhp ptzbsppb tmcbg tnhxbg mtnpmq lhtgpq dnbjj fzk lszkg kdzfph cvlxbh hpzbmr mmcpg djvbx jgtb krzfjbq kjf xpm fvk brlnlxn mfhtz vjbcvv qjlnrd ljxg kzjrpl jndhc qjblr jztg gggjklx nskq rprxk fmhnz mzsjc xntshr hckjb ccvrnj lrtmj vmczz trkmvj nhxqsg zvrvcd bfmsp btfdjt zrb tcdh zjbbf hvgms mrktkf chssff dqqc fpxxp rshbrd szfjpqr plbhvfj ntlb drtg hzdr qmsvv gkqzl (contains nuts) \ No newline at end of file diff --git a/data/advent21a.txt b/data/advent21a.txt new file mode 100644 index 0000000..6940ed2 --- /dev/null +++ b/data/advent21a.txt @@ -0,0 +1,4 @@ +mxmxvkd kfcds sqjhc nhms (contains dairy, fish) +trh fvjkl sbzzf mxmxvkd (contains dairy) +sqjhc fvjkl (contains soy) +sqjhc mxmxvkd sbzzf (contains fish) \ No newline at end of file diff --git a/problems/day21.html b/problems/day21.html new file mode 100644 index 0000000..dd0921e --- /dev/null +++ b/problems/day21.html @@ -0,0 +1,143 @@ + + + + +Day 21 - Advent of Code 2020 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 42*

        //2020

+ + + +
+ +

--- Day 21: Allergen Assessment ---

You reach the train's last stop and the closest you can get to your vacation island without getting wet. There aren't even any boats here, but nothing can stop you now: you build a raft. You just need a few days' worth of food for your journey.

+

You don't speak the local language, so you can't read any ingredients lists. However, sometimes, allergens are listed in a language you do understand. You should be able to use this information to determine which ingredient contains which allergen and work out which foods are safe to take with you on your trip.

+

You start by compiling a list of foods (your puzzle input), one food per line. Each line includes that food's ingredients list followed by some or all of the allergens the food contains.

+

Each allergen is found in exactly one ingredient. Each ingredient contains zero or one allergen. Allergens aren't always marked; when they're listed (as in (contains nuts, shellfish) after an ingredients list), the ingredient that contains each listed allergen will be somewhere in the corresponding ingredients list. However, even if an allergen isn't listed, the ingredient that contains that allergen could still be present: maybe they forgot to label it, or maybe it was labeled in a language you don't know.

+

For example, consider the following list of foods:

+
mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
+trh fvjkl sbzzf mxmxvkd (contains dairy)
+sqjhc fvjkl (contains soy)
+sqjhc mxmxvkd sbzzf (contains fish)
+
+

The first food in the list has four ingredients (written in a language you don't understand): mxmxvkd, kfcds, sqjhc, and nhms. While the food might contain other allergens, a few allergens the food definitely contains are listed afterward: dairy and fish.

+

The first step is to determine which ingredients can't possibly contain any of the allergens in any food in your list. In the above example, none of the ingredients kfcds, nhms, sbzzf, or trh can contain an allergen. Counting the number of times any of these ingredients appear in any ingredients list produces 5: they all appear once each except sbzzf, which appears twice.

+

Determine which ingredients cannot possibly contain any of the allergens in your list. How many times do any of those ingredients appear?

+
+

Your puzzle answer was 2517.

--- Part Two ---

Now that you've isolated the inert ingredients, you should have enough information to figure out which ingredient contains which allergen.

+

In the above example:

+
    +
  • mxmxvkd contains dairy.
    • +
  • sqjhc contains fish.
    • +
  • fvjkl contains soy.
    • +
+

Arrange the ingredients alphabetically by their allergen and separate them by commas to produce your canonical dangerous ingredient list. (There should not be any spaces in your canonical dangerous ingredient list.) In the above example, this would be mxmxvkd,sqjhc,fvjkl.

+

Time to stock your raft with supplies. What is your canonical dangerous ingredient list?

+
+

Your puzzle answer was rhvbn,mmcpg,kjf,fvk,lbmt,jgtb,hcbdb,zrb.

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 40f3816..49a90a7 100644 --- a/stack.yaml +++ b/stack.yaml @@ -55,6 +55,7 @@ packages: - advent18 - advent19 - advent20 +- advent21 # 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