From 68817bdbe7f37d4035261fbe78772b9ae8900181 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 31 Dec 2020 11:26:19 +0000 Subject: [PATCH] Done day 20 --- advent19/src/advent19atto.hs | 1 - advent20/package.yaml | 62 ++ advent20/src/advent20.hs | 202 ++++ data/advent20.txt | 1727 ++++++++++++++++++++++++++++++++++ data/advent20a.txt | 107 +++ data/advent20seamonster.txt | 3 + problems/day20.html | 365 +++++++ stack.yaml | 1 + 8 files changed, 2467 insertions(+), 1 deletion(-) create mode 100644 advent20/package.yaml create mode 100644 advent20/src/advent20.hs create mode 100644 data/advent20.txt create mode 100644 data/advent20a.txt create mode 100644 data/advent20seamonster.txt create mode 100644 problems/day20.html diff --git a/advent19/src/advent19atto.hs b/advent19/src/advent19atto.hs index 6210406..30ecd93 100644 --- a/advent19/src/advent19atto.hs +++ b/advent19/src/advent19atto.hs @@ -22,7 +22,6 @@ data Rule = Letter Char | See Int deriving (Show, Eq) - type RuleSet = M.IntMap Rule diff --git a/advent20/package.yaml b/advent20/package.yaml new file mode 100644 index 0000000..b8a3866 --- /dev/null +++ b/advent20/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: advent20 +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: + advent20: + main: advent20.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - text + - attoparsec + - array + - containers diff --git a/advent20/src/advent20.hs b/advent20/src/advent20.hs new file mode 100644 index 0000000..57a141d --- /dev/null +++ b/advent20/src/advent20.hs @@ -0,0 +1,202 @@ +-- 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.Array.Unboxed as A +import Data.Array.Unboxed ((!)) +import qualified Data.Map.Strict as M +import Data.Bool (bool) +import Data.List (delete) +import Control.Monad (guard) +-- import Data.Either (fromRight) + + +type Coord = (Int, Int) +type Pixels = A.UArray Coord Bool +type Border = A.UArray Int Bool + +data Tile = Tile + { tId :: Integer + , pixels :: Pixels + } deriving (Show, Eq) + +type Arrangement = M.Map Coord Tile + + +main :: IO () +main = + do text <- TIO.readFile "data/advent20.txt" + let tiles = successfulParse text + let arrangeRMax = (floor $ sqrt @Double $ fromIntegral $ length tiles) - 1 + let arrangement = arrangeTiles arrangeRMax tiles + let image = assembleImage arrangeRMax arrangement + seaMonster <- readSeaMonster + print $ part1 arrangeRMax arrangement + print $ part2 seaMonster image + + +part1 rMax arrangement + = product $ M.elems + $ M.map tId + $ M.filterWithKey (isCorner rMax) arrangement + +part2 seaMonster image = minimum $ map (countRoughness seaMonster) transImages + where imgTile = Tile 0 image + transImages = map pixels $ transforms imgTile + + +readSeaMonster :: IO Pixels +readSeaMonster = + do text <- TIO.readFile "data/advent20seamonster.txt" + -- return $ fromRight (A.listArray ((0, 0), (1, 1)) []) $ parseOnly pixelsP text + return $ case parseOnly pixelsP text of + Left _err -> A.listArray ((0, 0), (1, 1)) [] + Right seaMonster -> seaMonster + + +isCorner _ (0, 0) _ = True +isCorner l (0, c) _ = c == l +isCorner l (r, 0) _ = r == l +isCorner l (r, c) _ = r == l && c == l + +arrangeTiles :: Int -> [Tile] -> Arrangement +arrangeTiles rMax tiles = head $ arrange (0, 0) rMax M.empty tiles + +arrange :: Coord -> Int -> Arrangement -> [Tile] -> [Arrangement] +-- arrange h _ g ts | trace (show h ++ " " ++ show (M.map tId g) ++ " > " ++ show (length ts)) False = undefined +arrange _ _ grid [] = return grid +arrange (r, c) cMax grid tiles = + do tile <- tiles + transTile <- transforms tile + guard $ if r == 0 then True else matchVertical tileAbove transTile + guard $ if c == 0 then True else matchHorizontal tileLeft transTile + arrange (r', c') + cMax + (M.insert (r, c) transTile grid) + (delete tile tiles) + where tileAbove = grid M.! (r - 1 , c) + tileLeft = grid M.! (r, c - 1) + (r', c') = if c == cMax then (r + 1, 0) else (r, c + 1) + + +matchHorizontal tile1 tile2 = (rightBorder tile1) == (leftBorder tile2) +matchVertical tile1 tile2 = (bottomBorder tile1) == (topBorder tile2) + + +topBorder :: Tile -> Border +topBorder Tile{..} = A.listArray (0, c1) [pixels!(0, c) | c <- [0..c1] ] + where (_, (_, c1)) = A.bounds pixels + +bottomBorder :: Tile -> Border +bottomBorder Tile{..} = A.listArray (0, c1) [pixels!(r1, c) | c <- [0..c1] ] + where (_, (r1, c1)) = A.bounds pixels + +leftBorder :: Tile -> Border +leftBorder Tile{..} = A.listArray (0, r1) [pixels!(r, 0) | r <- [0..r1] ] + where (_, (r1, _)) = A.bounds pixels + +rightBorder :: Tile -> Border +rightBorder Tile{..} = A.listArray (0, r1) [pixels!(r, c1) | r <- [0..r1] ] + where (_, (r1, c1)) = A.bounds pixels + + +transforms :: Tile -> [Tile] +transforms tile = + [ r $ f tile + | r <- [id, tRotate, tRotate . tRotate, tRotate . tRotate . tRotate] + , f <- [id, tFlip] + ] + +-- rotate quarter turn clockwise +tRotate tile = tile {pixels = pixels'} + where bs = pixels tile + (_, (r1, c1)) = A.bounds bs + pixels' = A.ixmap ((0, 0), (c1, r1)) rotateIndex bs + rotateIndex (r, c) = (r1 - c, r) -- how to get to the old index from the new one + +tFlip tile = tile {pixels = pixels'} + where bs = pixels tile + (_, (r1, c1)) = A.bounds bs + pixels' = A.ixmap ((0, 0), (r1, c1)) flipIndex bs + flipIndex (r, c) = (r, c1 - c) -- how to get to the old index from the new one + + +assembleImage :: Int -> Arrangement -> Pixels +assembleImage arrangeRMax arrangement = + A.array ((0,0), (imageRMax, imageRMax)) imageElements + where (_, (tileRMax, _)) = A.bounds $ pixels $ arrangement M.! (0, 0) + tRM1 = tileRMax - 1 + imageRMax = tRM1 * (arrangeRMax + 1) - 1 + imageElements = + do ar <- [0..arrangeRMax] -- arrangement row + ac <- [0..arrangeRMax] + tr <- [1..tRM1] -- tile pixels row + tc <- [1..tRM1] + let px = (pixels $ arrangement M.! (ar, ac)) ! (tr, tc) + let ir = (ar * tRM1) + (tr - 1) -- assembled image row + let ic = (ac * tRM1) + (tc - 1) + return ((ir, ic), px) + + +countRoughness sm image = imPixels - (smPixels * nSeaMonsters) + where smPixels = countPixels sm + imPixels = countPixels image + nSeaMonsters = length $ findSeaMonsters sm image + +countPixels :: Pixels -> Int +countPixels = length . filter (== True) . A.elems + +findSeaMonsters :: Pixels -> Pixels -> [Coord] +findSeaMonsters sm image = [ (r, c) + | r <- [0..(imR - smR)] + , c <- [0..(imC - smC)] + , seaMonsterPresent sm image r c + ] + where (_, (smR, smC)) = A.bounds sm + (_, (imR, imC)) = A.bounds image + +seaMonsterPresent sm image dr dc = all bothPresent $ A.indices sm + where bothPresent (r, c) = if (sm!(r, c)) + then (image!(r + dr, c + dc)) + else True + + +showTile Tile{..} = show tId ++ "\n" ++ (showP pixels) + +showP ps = unlines [[bool ' ' '\x2588' (ps!(r, c)) | c <- [0..cMax] ] | r <- [0..rMax]] + where (_, (rMax, cMax)) = A.bounds ps + -- sb b = bool '.' '#' b + +-- -- Parse the input file + +tilesP = tileP `sepBy` blankLines + +blankLines = many endOfLine + +tileP = Tile <$> ("Tile " *> decimal) <* ":" <* endOfLine <*> pixelsP + +pixelsP = pixify <$> (pixelsRowP `sepBy` endOfLine) +pixelsRowP = many1 (satisfy (inClass " .#")) + +pixify :: [String] -> Pixels +pixify rows = A.array ((0, 0), (nRows, nCols)) + [ ((r, c), (rows!!r)!!c == '#') + | r <- [0..nRows] + , c <- [0..nCols] + ] + where nRows = length rows - 1 + nCols = (length $ head rows) - 1 + + +-- successfulParse :: Text -> (Integer, [Maybe Integer]) +successfulParse input = + case parseOnly tilesP input of + Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err + Right tiles -> tiles diff --git a/data/advent20.txt b/data/advent20.txt new file mode 100644 index 0000000..d7191b5 --- /dev/null +++ b/data/advent20.txt @@ -0,0 +1,1727 @@ +Tile 1621: +.#.##...#. +#..#..#.#. +#.#..#..## +.....#..#. +.#..#...## +#....#...# +.#........ +#.#.#....# +...#...#.. +.#..#....# + +Tile 3671: +..#.#.###. +#.##....## +#......... +##..#.#... +#..###.... +..#.#....# +##..###..# +..#......# +.........# +......###. + +Tile 2803: +#.#.#..#.. +#.....#... +...##..### +#.#.....## +#...#..#.# +..#...##.# +..#...#..# +####.#..## +#..##....# +#..#.##.#. + +Tile 1531: +####.##### +.###...### +##..#..#.# +##.#..#..# +#....#..## +##.#....#. +#.#.##.... +....#..#.. +#...#..... +##....#... + +Tile 1811: +#.#...#..# +##....#.## +#...##.#.. +#..##..... +.#.#.....# +##..#..... +##.#...... +..#...##.. +.#.##....# +##...##..# + +Tile 2143: +##.###.#.# +#..##.##.. +###....... +..##.#...# +#.......#. +#.#....##. +...#..#### +..##...#.# +#.#..#.##. +#.#.#...## + +Tile 2887: +.......##. +#..#..#..# +....#..... +...#..##.. +..#....... +#...##..## +..#...##.. +#.....#.## +##..#..##. +#...#.#### + +Tile 3511: +.#.##....# +#.#...##.# +#...##.### +....#..... +..#......# +.###.#..#. +#......... +#.#....### +.......#.# +#..####### + +Tile 3911: +.#..#.###. +#...#.##.. +.#..#...## +##.#.##.## +....#.#..# +...###.... +.....#...# +...##..#.. +###.#.#.#. +##.....#.# + +Tile 3821: +#####..#.. +##..#..... +....##.#.# +#....#.... +#...##.#.# +#........# +####...... +#.#.#....# +....###### +..#...###. + +Tile 3539: +#####.##.. +#........# +####.#.... +.##..#.#.# +#.....#... +#.#......# +##...###.# +.#..#..... +#.#....... +...#...#.. + +Tile 3251: +....#..##. +.###.#...# +#..#.....# +...#.....# +..#....... +.##..#...# +#.......## +#.....#... +....#..#.# +######.#.# + +Tile 2677: +.#...#...# +...#.###.. +......##.. +#.##.##... +#.#...#.## +#..#####.. +......##.. +......##.# +#..#..#... +..##.####. + +Tile 3011: +#.#..#..## +#.###..#.. +#..#..##.. +#.#..#...# +##...##### +....#..### +.#..#..#.# +..#...#..# +##.##..#.# +.#.##..... + +Tile 1489: +#...##.### +#.#..#.... +#.....#..# +##..#..... +...#....## +.##.##.#.# +#.#......# +#........# +....#..... +##.#.##### + +Tile 3769: +.....####. +##....#### +###....#.# +.##..#.#.# +.......... +##....#### +#...#..#.. +...#.....# +##.#.....# +#...##.### + +Tile 2293: +.#..#.#... +####...... +##...#.... +###.#.#... +.##.##...# +......#.#. +##.....#.. +#..#.##.## +.##....##. +.#.....#.. + +Tile 3947: +.#.#...##. +.......... +..#...##.# +..###..#.# +##...#.### +.#..#..#.. +#.#....#.. +....#.#..# +.#....#### +######..#. + +Tile 1223: +#..#####.# +###..#..## +##.###.... +...##.#... +..#.##.#.. +##.###...# +...#..#.## +...#..#... +.#....#..# +#..####... + +Tile 3331: +#.....##.. +##..###.#. +.##.#...#. +.##..#.#.. +#......#.. +...#.....# +###.#.#... +.##......# +#..#...... +...#...### + +Tile 3691: +#..#..#.## +......#..# +#.#..##..# +###....... +#.#....##. +##.#..##.. +#......#.. +..#....... +...#.#..#. +#..#...... + +Tile 1289: +#.......#. +##.##....# +####...... +.#..#.#..# +#.#.#..### +#..#...... +##.#####.. +.#........ +##.##....# +##.####### + +Tile 2857: +.#.#..#.## +.....#.#.. +#..#...#.. +.##...#..# +##..#..#.# +#..#..#..# +...#...... +#.#.#..... +##...#.... +....#.##.. + +Tile 3559: +#.##..##.. +..#.##.### +##..#....# +#.#..#..#. +##.####..# +.....#...# +#....#.... +##..#.##.. +#..#.....# +###.##..## + +Tile 2633: +...#.#..## +##.......# +#...##..#. +#.#....#.# +.........# +...#.....# +.#.##....# +...#..#... +#.#.##.... +..#..##... + +Tile 1973: +#.#.....#. +#.......#. +#....#.... +.#.#...##. +.........# +#.......#. +...#.##..# +.##...#... +##..#..#.. +####..##.# + +Tile 1373: +#####.#..# +##.##..### +#.####...# +..###.#... +....##...# +#...#....# +##.#....## +.......#.. +##.#.##.#. +#.###.##.# + +Tile 1759: +.#.....##. +#.#..#...# +....###..# +........## +....#..... +.....#..#. +#...#....# +.#..#...#. +...#.#.#.. +##...#..## + +Tile 1213: +#....###.# +###...##.# +.#.....#.# +#......##. +.#...#.##. +.##....... +....##...# +#......... +.........# +#.....#.## + +Tile 2341: +#.....#.#. +...##.#..# +.....##..# +......##.# +#...#....# +..#...###. +..##.#.#.# +.#.#....## +.#.....### +.#.#...##. + +Tile 3547: +####.#.#.# +...###...# +#..#.##... +##..#.#... +#....#.#.# +.#.......# +.#.#...... +###.....#. +#.#....### +.#.##.#... + +Tile 2003: +#####.#### +...#..#..# +.#.......# +#.#.#...## +.#.#.#..#. +#......#.. +...#..#... +.#...#.#.. +#........# +####.###.. + +Tile 2861: +#..##.##.. +..#.#....# +....##.#.. +##........ +#......... +##.....#.# +##.....##. +####.....# +###..##### +.........# + +Tile 3697: +#..##.#### +.....#.... +#.#.#.#.#. +#.##...### +..##.....# +.#.......# +.##....... +#.#..#...# +.#.###.#.. +####.####. + +Tile 3929: +.#.##..#.# +##.#....## +....#.#..# +....#.#.#. +##........ +...#..#... +###....#.# +#........# +.###.##.## +###..##### + +Tile 3527: +#.#.#...#. +####.#.... +......#... +.##......# +.#......## +.##.#.#.## +#..#...... +#.....#... +.#........ +..#..####. + +Tile 1777: +.#..#...## +#....###.. +..#..##.## +..##...#.. +....#.#... +#...##.#.. +#..##.#..# +...##..... +.#....#..# +.#..#..### + +Tile 1543: +......#... +.#...##... +#...#..#.# +.......... +#..##....# +..#.#...## +...#.####. +##....#... +...#..#### +.#.#..#### + +Tile 2063: +##....#... +#.....#... +###.##...# +......#..# +...##..#.. +###.#..... +##.....##. +#..#.##... +##.###..## +#....###.. + +Tile 1181: +#.##...### +####.#.... +.........# +####..##.# +.....#..#. +.......#.. +..###....# +##..##.... +#.#...#..# +.#.#.#...# + +Tile 3491: +#...###.## +..##..#.## +.......##. +.......... +.....#..#. +#..#...... +##....#.#. +...##...#. +..###..... +..#.##..#. + +Tile 1873: +...#.....# +...#.#..#. +##.#...... +.#...#.### +#.#.#..#.. +.....###.# +#..#..#... +....#..... +.....#.#.# +######...# + +Tile 2579: +.####...#. +#..#..#..# +.....#...# +#.#..#...# +#.....##.. +......#..# +#......##. +.#...##... +.#...##... +.##.####.. + +Tile 1481: +.#.#.##### +..#.#.##.. +.###...#.# +...##..... +..#.#.#.#. +.#.......# +##.#....#. +#.#...#... +.###..#... +......##.# + +Tile 2417: +.#..#..#.# +.#.#.....# +.###..##.# +#.#.#..... +#....#.### +..#..#.... +#....#.#.. +####....## +..#.#...## +....###### + +Tile 3581: +..##.....# +.....##..# +#......... +#....##..# +#..#....#. +#.....#..# +.#..#.#.#. +...#...... +.....##..# +#......... + +Tile 3593: +#.##.###.. +###.....## +##.#....#. +###.#....# +###....#.# +#.#..#..## +......#.## +...#....#. +.#...#..#. +..#####..# + +Tile 3167: +#...#.#.#. +......#.## +##.##.#.## +#...#.##.# +....#...#. +..#....##. +...#...##. +...##..#.. +....#.##.# +##.#....#. + +Tile 1439: +...##..### +#.#......# +..#..###.# +....#.#... +#......... +......#..# +..#.#.#..# +##.#.#.... +..#...#..# +#.###.#... + +Tile 1249: +..#.##...# +#.#......# +.......#.. +##.#.#.#.# +.#..#..#.. +..#.#..#.# +.....##.#. +#........# +..#..##.## +..#..##### + +Tile 2687: +##...##... +###.###.#. +#...###..# +.#.......# +....#.#... +.....##### +##.#####.. +#....#.... +..#.####.# +##....#.#. + +Tile 2693: +..#..#..#. +....#..### +....##.... +.#.##..... +.#..###... +..##.#.... +#......... +....##.##. +..#..#.... +.#.#...... + +Tile 1741: +.#.###..## +......#### +#.......## +#.#......# +##..#...#. +##.....#.# +#..#...... +..##.#..## +#..#...... +#.#..###.# + +Tile 3413: +...####.#. +.#..#.##.. +#....#.##. +##.#.....# +##.###..## +.......### +.#....###. +#....##..# +##.####..# +....#.###. + +Tile 3191: +.....####. +##.##..#.. +.##.#.##.# +.......### +....####.. +.#.#..#.#. +...#...#.. +##..#..#.# +...#..#... +..##..#.#. + +Tile 2897: +#.#######. +...#....#. +#.....##.# +###.#...#. +##.#####.# +..#.##..## +#.##...... +##.#.##..# +#.#....#.. +#.##.#.### + +Tile 2017: +##.##...## +#...#.##.. +#..#.#...# +.##....... +##.......# +##..#.#..# +##.#.#.#.# +.......... +.......... +..######.# + +Tile 2939: +#...##.##. +.....#.##. +....#.#... +#.#......# +.#.....#.# +.........# +###.....## +......#..# +#..#..##.. +.##..#.##. + +Tile 1753: +#...#.#.## +.#...#...# +###..#.### +#..##....# +#..#...... +#.##...#.. +..#...#... +#..#...... +.#.......# +....#.#.## + +Tile 3229: +#..####.#. +#.....#..# +......##.. +#.#...##.# +#...#...## +#.#....#.# +.#..##..#. +#..#.....# +#..##..... +.#.#.#..## + +Tile 1367: +####.....# +...#.##... +...#...#.. +.#.###..#. +.........# +.#........ +.......... +.#...###.# +##........ +...##..#.# + +Tile 2851: +..#.#...## +#.....##.# +.##.#..#.# +#...###..# +###...#... +....#..#.# +..#....... +#.....#... +...#.#...# +.###..#..# + +Tile 2357: +....##.#.# +###...#.## +####..##.# +#.####...# +#...##...# +#.#......# +#..##.#.#. +#.#....#.# +.###...#.. +####..#.## + +Tile 1697: +#..#.#.##. +.......#.. +...##....# +##........ +....#....# +##.#.....# +.##......# +#....#..#. +##.##...## +#....#...# + +Tile 1571: +#.###...#. +##..#..#.. +.........# +...#.#.#.. +#........# +#..##.#... +##...##.#. +.......... +....#.#... +.##.....#. + +Tile 3323: +#.#.#..### +#...#...## +.......#.# +#.##...... +..#.#..##. +#.......#. +....####.# +....##...# +..##....## +######.### + +Tile 3461: +#....##.#. +....#..... +#......##. +##.....##. +#..#...##. +.#.......# +##.#...... +.......... +.....#..## +.....#.### + +Tile 2719: +.#.#.#.... +..#..#.##. +..##...### +..#..#...# +##.......# +.#........ +.##..#.... +..##..#... +..#....#.. +.#.#.#..#. + +Tile 3359: +.###...#.# +.....###.# +#..####.#. +.....##..# +..#.#...#. +#.#..###.. +..#....#.# +....#.#..# +.....#..#. +#.###.#..# + +Tile 3803: +.####.#..# +...#...### +.......##. +.......##. +#..#..#..# +##...#.... +....##.... +##........ +..#..##### +..#..##... + +Tile 3019: +##..###.#. +..#....... +##..#.##.# +##......#. +#......#.. +#.#....#.. +.###.###.# +#..#.##..# +###.##.#.# +.###.###.# + +Tile 2791: +......#.#. +#....#.... +##...##### +....##.... +#.....##.# +..##...... +#.#...#..# +...##...#. +..##....#. +##.##..#.. + +Tile 3881: +#....##..# +...#..#..# +.###..#..# +...#....## +#...#..#.# +#.#.#..#.# +#..##..... +...#...... +#.#....#.. +.#..##.### + +Tile 2087: +.#..#.#... +###....### +.###..#.## +........## +###.##..## +...#...#.# +#...#....# +##..#....# +#..####.#. +##..#####. + +Tile 1789: +######.#.. +........#. +..#...##.# +.#.......# +.#...#.... +#..#.#..## +#####.#..# +#...###..# +.#.#....## +####.##.#. + +Tile 2539: +#.###.#..# +..#..#...# +##.##.#... +#.....##.. +#..##..#.. +..###.##.# +#..###...# +.###.#.#.. +#...#..... +..###.##.. + +Tile 2111: +####..###. +#....###.. +..#.....## +#....##.## +#.....#... +#..#.#.... +...#..#### +##..##..#. +##.....#.# +#.#...#.#. + +Tile 1433: +#.....#..# +.#.###.#.# +.#...#.#.# +.......### +#..##.#... +.#...##.#. +#..#....## +#......#.. +....#..#.# +..#.#..##. + +Tile 1667: +..##...... +#..#....#. +.##.#..#.# +.....#.... +#.#.##..#. +...##..... +..#.#....# +#.#..#...# +...#...##. +....#....# + +Tile 2389: +.#.#...#.. +.#.......# +.....#.... +#...###..# +.......... +.#........ +.#.###.#.# +#....#..#. +..#......# +##...#...# + +Tile 1069: +...###..## +...#.....# +##......## +....##.... +..#..##..# +##..#..#.# +##.#.#.#.# +.#..###..# +#.#....... +.#.#.#.... + +Tile 1103: +..###.##.. +...##..#.# +#....##..# +....#..#.# +#....#.#.. +###....### +..#...##.. +..##.....# +#........# +.####..#.. + +Tile 3761: +....#.##.. +###....... +#...#..... +..##.#...# +#........# +.###...... +...#..#... +...#.#.#.. +#....#.#.# +....#...#. + +Tile 2473: +........## +.#.#..#... +.#........ +.####.#.## +##..##...# +##.....#.. +###.#..#.# +.......... +.#.#..##.# +..#....#.# + +Tile 1987: +...#..#.#. +......#... +#....#.### +..#....#.. +..#..##..# +........#. +#..#.....# +...#..#..# +.......#.# +...###.##. + +Tile 1187: +..#.#.#..# +##.#...##. +#......#.# +....#....# +..##...#.# +#..#..#.## +.......... +..##...#.# +...####..# +.#.#.##### + +Tile 2699: +###.#.##.# +.#.#####.# +.#..#..#.. +.###....## +..#..##..# +.....#...# +.......... +#...##...# +#......... +##..#..#.# + +Tile 3643: +..##...#.. +#..#..#.## +#.###.#### +..##..##.. +......#... +##.##..#.. +...#.##.## +....#..#.# +##..#....# +#....#...# + +Tile 3463: +..###.##.# +......##.# +#........# +......##.# +##.......# +##..#..#.# +##.......# +##......#. +##.#.##... +.###..#.## + +Tile 1117: +#.#.##.... +..#..#.### +.#..#..... +...#.#.... +........#. +##.###...# +..#..#.#.# +....#..#.. +..#.#....# +..#.#..#.. + +Tile 1163: +.##.##..## +....#..#.. +##..#..#.. +#..#.....# +#..#.....# +..#.##.... +...#.#.... +..###..#.# +...#...#.# +###.###### + +Tile 3557: +#.#....#.. +....####.# +.#....#### +..#...###. +#......#.. +.......#.. +##....#... +##.....#.. +...#..#.#. +...###.#.. + +Tile 2467: +.####....# +.#.#..##.# +####...... +......#.#. +#.#....#.# +##.....#.. +..#....#.# +..#.##...# +.#.....### +#...##.##. + +Tile 1471: +.###..#.## +##.#...##. +.#...#.... +....##..#. +........#. +##....##.# +###..##.#. +#....###.# +##.....##. +#..#..##.# + +Tile 3931: +#....#..## +#...#..#.. +.#..###### +#.###...#. +....#.##.# +#.#...#### +#....#..#. +....##.#.. +#..#..#### +#.#.#..... + +Tile 2029: +##.#.##### +#.#......# +#...##...# +#...#..... +#..##..... +#.....##.# +....##.... +..##.#.### +###.#.###. +..####.##. + +Tile 1913: +#..###.### +.......### +.#..#.#### +.#..#.#... +..#....... +.#....###. +.###..#.#. +#....#..#. +#.#..#.#.. +.#..#.#.#. + +Tile 2213: +..#.##.### +......###. +..#..#...# +#..#..#.## +#....###.. +...#....#. +#.##.#..#. +##.#...#.. +.##....### +####.#..#. + +Tile 1511: +###.#...## +.##.....#. +.##...#..# +...##.##.. +#.#..#.#.# +##...###.# +###..#.### +.##.##..#. +#......#.. +###.....## + +Tile 2243: +#..#.#...# +##...#.... +.....#.#.# +....##..#. +#..######. +.#..#.##.. +#......... +...#.##.#. +.#.......# +.##...#.## + +Tile 3701: +...####### +#..#...##. +...####..# +..#..#...# +##........ +#.....#..# +##..#.#... +##.#.##.#. +.##....... +###.#...## + +Tile 3137: +.#.####... +#..#.#...# +.......#.# +#..#.....# +#.....#... +#...###.## +.###...#.# +##......## +#.#....#.# +##...####. + +Tile 2437: +#...#..### +.#.#....#. +....#...#. +.......#.# +#.#...##.# +###..#...# +#.##..#... +....#..... +#.#.#.##.. +.#.#.#.### + +Tile 1009: +..#.#.#... +...#..##.. +##...##..# +........## +##...###.# +#....#...# +..#..#...# +..####.### +#......... +####..#..# + +Tile 2399: +..####.#.. +###..#.... +#..#..##.. +...#.#.... +##.##..... +##.###..#. +##..##..## +###....#.# +..#......# +#.###..##. + +Tile 2843: +.....#.... +......#... +.##.#....# +..#....#.. +.##.....## +.#...##.#. +####..##.. +.##....##. +....##...# +#..###...# + +Tile 1193: +##.....### +.......#.. +.#...#.#.. +#.#...#.## +..#.....## +.#.....#.. +#...#....# +##.#..#.#. +##.....#.# +#..#.....# + +Tile 1951: +###......# +.......... +.......... +#####..... +#.##..#... +.........# +##.##..... +#.#..#.##. +.#...#...# +..#.###... + +Tile 1879: +#...#..... +.#.......# +###....... +#####..... +#..#.#.... +...###.##. +#.......#. +#.#......# +.#..##.... +..#.##.### + +Tile 3469: +..####...# +#...#...#. +......###. +........#. +####.....# +#...#...#. +...#....## +#..#..#..# +..#...##.# +#####..#.# + +Tile 2161: +####.####. +###...#.## +.##...#... +#..#...#.. +##...##.#. +#......... +#...##...# +....#.#..# +..#.##..## +#.......## + +Tile 2083: +##.##.#..# +#.##.#..#. +...#.....# +##.#.##.#. +.....#..#. +#.......#. +...###.#.# +....##...# +#.##.#...# +##.#...### + +Tile 2089: +#.#.###.#. +#..##..... +.....#...# +#......... +.##...#### +#...##...# +.#.......# +....#...## +#..##....# +.....##.#. + +Tile 1051: +#.....##.# +.....##.#. +#...#....# +.#.#...... +........#. +.......#.. +##....#.## +#.......## +#........# +####.##.#. + +Tile 3347: +....##.#.. +#.#.#..#.# +##........ +..#....#.. +##...##... +.##.#..... +#........# +#..###.... +.....#...# +##.##.#..# + +Tile 2927: +#.##...... +...#..#.## +.#.#.#.##. +.......... +##....#... +##.#...#.. +....##.##. +#....#.#.. +..#.....#. +##.###.#.. + +Tile 1301: +#..##.#.#. +#.#......# +..#...#..# +##....#..# +#......... +.......#.# +....##.#.. +#..#.###.. +..#.###### +...###.### + +Tile 2459: +#..###.... +...###.### +##........ +##..#..#.. +##.#.##.## +#.##.#..#. +#..##..##. +.#...##..# +#........# +..#.###### + +Tile 1583: +.#.#..#..# +#.#.#....# +.##....... +.........# +#....#.... +##...###.# +#.#....... +.........# +#...#....# +#.###..#.# + +Tile 3533: +.#.##.#..# +.#.......# +........#. +.#...#...# +#......... +.......#.# +...#...#.. +##..#..#.# +...#.###.. +.###..#### + +Tile 1993: +#.####..#. +..##.#.#.# +.#.#...... +.#........ +..#....... +#.##..#..# +##..#..... +.#.##..#.. +........#. +.#.#.###.# + +Tile 3853: +..#.####.# +##....##.# +..#......# +....#..... +.....#.##. +......#..# +..#..#.#.# +##....#... +###.#..##. +##...#.#.# + +Tile 2113: +#..#.#.#.# +#.....#.## +#.....#..# +.##....#.# +##.#.##### +#..#...... +...#...#.. +...#.#..## +.......##. +..##....## + +Tile 3319: +####.#..## +##....#.#. +#.......#. +......#..# +####...##. +.......... +##.....#.. +..#..#..## +#...#..... +.##..#...# + +Tile 3847: +...##..#.# +..#.##...# +...#..#### +#..#.#.#.. +#........# +#....##..# +#....#..## +.#.#.##.## +.####..... +#....##..# + +Tile 1283: +..##..###. +##.......# +#.#.#..... +.#.#....#. +..#..#.... +#...#..... +##.......# +.##.#...## +##.####... +##..#..### + +Tile 2957: +#.####.#.# +#..#..##.. +#..###...# +#.#..#.#.. +#.......#. +#.#..#...# +######.... +#.......## +#...#...#. +.##..#.##. + +Tile 1097: +.###.#.### +#......##. +#........# +....#...#. +..##..#.#. +#....#..## +.###...##. +..##.#...# +#..#.####. +#.#....... + +Tile 1399: +#.###..### +#...##.### +....#.#... +#...##.#.. +..#...#..# +#...###... +.......#.. +..#.#.#... +...##...#. +...##..##. + +Tile 1451: +#.#...#.#. +#........# +#.#....#.# +###.#..... +....##.... +.##.#..#.. +.#.####..# +..#..###.# +...#...#.# +#...##.#.# + +Tile 1559: +#..#.#.### +......#... +.....#..## +#......... +##..#..... +...#...#.. +##.#.#.... +.....#.##. +#...#.#.#. +...#####.. + +Tile 3391: +#.#.#.#..# +##..#..... +.#...###.. +......#..# +#.#.....#. +...#..#... +.#......#. +.......#.. +.....#.#.# +#.#.#.##.# + +Tile 2423: +#.#.#....# +#......#.. +#.#.#.#.## +...#.#.#.# +....#.#.#. +.......#.. +.##.....#. +.........# +#.#..#...# +...##..##. + +Tile 2297: +.....##### +#..#...... +#...#..... +##...#.#.. +.......##. +#.......#. +###....### +..#.....#. +.....##... +##.##.###. + +Tile 2011: +#######... +#.#...#.#. +...##..#.. +...##..#.# +......#..# +#..#.....# +...#.#.... +....#.#... +..#.###..# +#.#####.#. + +Tile 1049: +#.#...#... +.......### +#..#.#..## +##.......# +.#.###...# +##....#... +...#.##... +........#. +...#..#.#. +##...##.## + +Tile 3943: +..#...#### +...#.##... +#.#.###... +.#...###.# +....#.##.. +.##...#..# +####.....# +####.##.#. +##...#.... +.##.#...#. + +Tile 2039: +#####.#..# +#.#....### +.....#.... +##.....#.# +.......#.. +#......#.. +..#...#..# +#.#...#... +..##...#.. +##.####### + +Tile 1297: +.#..##.### +#.....#..# +###..##..# +.##..#..## +...#...... +#..#....## +..#......# +...##.#..# +....##.... +#..###.#.. + +Tile 1597: +.#..#.##.. +###......# +#...##...# +.#.#....## +...##.##.. +#.###....# +###.#..... +..#....#.# +...##....# +###.##.... + +Tile 1319: +...#.##..# +#.#####... +.......... +.#..#..#.. +#...#.#.#. +.#.##..#.. +###....... +#...#.##.. +...#.....# +##.#####.# + +Tile 2333: +#..##..##. +...#...#.# +..##.#.... +#....#.##. +..##..##.# +..##..###. +...##.#..# +.....#.#.# +#......#.# +########.. + +Tile 1423: +#.##..##.. +#.##.....# +#.#..##... +##.#####.. +...#.#..#. +.#..#.#.#. +#.##....## +...###..## +#.#.#...#. +#..##.###. + +Tile 1303: +.######### +##..#....# +..#.#.#### +.......... +#...#..... +#.#..#...# +###.#..... +.##.#....# +#.#.#..#.. +##..##..#. diff --git a/data/advent20a.txt b/data/advent20a.txt new file mode 100644 index 0000000..b3aed46 --- /dev/null +++ b/data/advent20a.txt @@ -0,0 +1,107 @@ +Tile 2311: +..##.#..#. +##..#..... +#...##..#. +####.#...# +##.##.###. +##...#.### +.#.#.#..## +..#....#.. +###...#.#. +..###..### + +Tile 1951: +#.##...##. +#.####...# +.....#..## +#...###### +.##.#....# +.###.##### +###.##.##. +.###....#. +..#.#..#.# +#...##.#.. + +Tile 1171: +####...##. +#..##.#..# +##.#..#.#. +.###.####. +..###.#### +.##....##. +.#...####. +#.##.####. +####..#... +.....##... + +Tile 1427: +###.##.#.. +.#..#.##.. +.#.##.#..# +#.#.#.##.# +....#...## +...##..##. +...#.##### +.#.####.#. +..#..###.# +..##.#..#. + +Tile 1489: +##.#.#.... +..##...#.. +.##..##... +..#...#... +#####...#. +#..#.#.#.# +...#.#.#.. +##.#...##. +..##.##.## +###.##.#.. + +Tile 2473: +#....####. +#..#.##... +#.##..#... +######.#.# +.#...#.#.# +.######### +.###.#..#. +########.# +##...##.#. +..###.#.#. + +Tile 2971: +..#.#....# +#...###... +#.#.###... +##.##..#.. +.#####..## +.#..####.# +#..#.#..#. +..####.### +..#.#.###. +...#.#.#.# + +Tile 2729: +...#.#.#.# +####.#.... +..#.#..... +....#..#.# +.##..##.#. +.#.####... +####.#.#.. +##.####... +##..#.##.. +#.##...##. + +Tile 3079: +#.#.#####. +.#..###### +..#....... +######.... +####.#..#. +.#...#.##. +#.#####.## +..#.###... +..#....... +..#.###... \ No newline at end of file diff --git a/data/advent20seamonster.txt b/data/advent20seamonster.txt new file mode 100644 index 0000000..ab9cbbf --- /dev/null +++ b/data/advent20seamonster.txt @@ -0,0 +1,3 @@ + # +# ## ## ### + # # # # # # diff --git a/problems/day20.html b/problems/day20.html new file mode 100644 index 0000000..ea347bb --- /dev/null +++ b/problems/day20.html @@ -0,0 +1,365 @@ + + + + +Day 20 - Advent of Code 2020 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 40*

   $year=2020;

+ + + +
+ +

--- Day 20: Jurassic Jigsaw ---

The high-speed train leaves the forest and quickly carries you south. You can even see a desert in the distance! Since you have some spare time, you might as well see if there was anything interesting in the image the Mythical Information Bureau satellite captured.

+

After decoding the satellite messages, you discover that the data actually contains many small images created by the satellite's camera array. The camera array consists of many cameras; rather than produce a single square image, they produce many smaller square image tiles that need to be reassembled back into a single image.

+

Each camera in the camera array returns a single monochrome image tile with a random unique ID number. The tiles (your puzzle input) arrived in a random order.

+

Worse yet, the camera array appears to be malfunctioning: each image tile has been rotated and flipped to a random orientation. Your first task is to reassemble the original image by orienting the tiles so they fit together.

+

To show how the tiles should be reassembled, each tile's image data includes a border that should line up exactly with its adjacent tiles. All tiles have this border, and the border lines up exactly when the tiles are both oriented correctly. Tiles at the edge of the image also have this border, but the outermost edges won't line up with any other tiles.

+

For example, suppose you have the following nine tiles:

+
Tile 2311:
+..##.#..#.
+##..#.....
+#...##..#.
+####.#...#
+##.##.###.
+##...#.###
+.#.#.#..##
+..#....#..
+###...#.#.
+..###..###
+
+Tile 1951:
+#.##...##.
+#.####...#
+.....#..##
+#...######
+.##.#....#
+.###.#####
+###.##.##.
+.###....#.
+..#.#..#.#
+#...##.#..
+
+Tile 1171:
+####...##.
+#..##.#..#
+##.#..#.#.
+.###.####.
+..###.####
+.##....##.
+.#...####.
+#.##.####.
+####..#...
+.....##...
+
+Tile 1427:
+###.##.#..
+.#..#.##..
+.#.##.#..#
+#.#.#.##.#
+....#...##
+...##..##.
+...#.#####
+.#.####.#.
+..#..###.#
+..##.#..#.
+
+Tile 1489:
+##.#.#....
+..##...#..
+.##..##...
+..#...#...
+#####...#.
+#..#.#.#.#
+...#.#.#..
+##.#...##.
+..##.##.##
+###.##.#..
+
+Tile 2473:
+#....####.
+#..#.##...
+#.##..#...
+######.#.#
+.#...#.#.#
+.#########
+.###.#..#.
+########.#
+##...##.#.
+..###.#.#.
+
+Tile 2971:
+..#.#....#
+#...###...
+#.#.###...
+##.##..#..
+.#####..##
+.#..####.#
+#..#.#..#.
+..####.###
+..#.#.###.
+...#.#.#.#
+
+Tile 2729:
+...#.#.#.#
+####.#....
+..#.#.....
+....#..#.#
+.##..##.#.
+.#.####...
+####.#.#..
+##.####...
+##..#.##..
+#.##...##.
+
+Tile 3079:
+#.#.#####.
+.#..######
+..#.......
+######....
+####.#..#.
+.#...#.##.
+#.#####.##
+..#.###...
+..#.......
+..#.###...
+
+

By rotating, flipping, and rearranging them, you can find a square arrangement that causes all adjacent borders to line up:

+
#...##.#.. ..###..### #.#.#####.
+..#.#..#.# ###...#.#. .#..######
+.###....#. ..#....#.. ..#.......
+###.##.##. .#.#.#..## ######....
+.###.##### ##...#.### ####.#..#.
+.##.#....# ##.##.###. .#...#.##.
+#...###### ####.#...# #.#####.##
+.....#..## #...##..#. ..#.###...
+#.####...# ##..#..... ..#.......
+#.##...##. ..##.#..#. ..#.###...
+
+#.##...##. ..##.#..#. ..#.###...
+##..#.##.. ..#..###.# ##.##....#
+##.####... .#.####.#. ..#.###..#
+####.#.#.. ...#.##### ###.#..###
+.#.####... ...##..##. .######.##
+.##..##.#. ....#...## #.#.#.#...
+....#..#.# #.#.#.##.# #.###.###.
+..#.#..... .#.##.#..# #.###.##..
+####.#.... .#..#.##.. .######...
+...#.#.#.# ###.##.#.. .##...####
+
+...#.#.#.# ###.##.#.. .##...####
+..#.#.###. ..##.##.## #..#.##..#
+..####.### ##.#...##. .#.#..#.##
+#..#.#..#. ...#.#.#.. .####.###.
+.#..####.# #..#.#.#.# ####.###..
+.#####..## #####...#. .##....##.
+##.##..#.. ..#...#... .####...#.
+#.#.###... .##..##... .####.##.#
+#...###... ..##...#.. ...#..####
+..#.#....# ##.#.#.... ...##.....
+
+

For reference, the IDs of the above tiles are:

+
1951    2311    3079
+2729    1427    2473
+2971    1489    1171
+
+

To check that you've assembled the image correctly, multiply the IDs of the four corner tiles together. If you do this with the assembled tiles from the example above, you get 1951 * 3079 * 2971 * 1171 = 20899048083289.

+

Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?

+
+

Your puzzle answer was 30425930368573.

--- Part Two ---

Now, you're ready to check the image for sea monsters.

+

The borders of each tile are not part of the actual image; start by removing them.

+

In the example above, the tiles become:

+
.#.#..#. ##...#.# #..#####
+###....# .#....#. .#......
+##.##.## #.#.#..# #####...
+###.#### #...#.## ###.#..#
+##.#.... #.##.### #...#.##
+...##### ###.#... .#####.#
+....#..# ...##..# .#.###..
+.####... #..#.... .#......
+
+#..#.##. .#..###. #.##....
+#.####.. #.####.# .#.###..
+###.#.#. ..#.#### ##.#..##
+#.####.. ..##..## ######.#
+##..##.# ...#...# .#.#.#..
+...#..#. .#.#.##. .###.###
+.#.#.... #.##.#.. .###.##.
+###.#... #..#.##. ######..
+
+.#.#.### .##.##.# ..#.##..
+.####.## #.#...## #.#..#.#
+..#.#..# ..#.#.#. ####.###
+#..####. ..#.#.#. ###.###.
+#####..# ####...# ##....##
+#.##..#. .#...#.. ####...#
+.#.###.. ##..##.. ####.##.
+...###.. .##...#. ..#..###
+
+

Remove the gaps to form the actual image:

+
.#.#..#.##...#.##..#####
+###....#.#....#..#......
+##.##.###.#.#..######...
+###.#####...#.#####.#..#
+##.#....#.##.####...#.##
+...########.#....#####.#
+....#..#...##..#.#.###..
+.####...#..#.....#......
+#..#.##..#..###.#.##....
+#.####..#.####.#.#.###..
+###.#.#...#.######.#..##
+#.####....##..########.#
+##..##.#...#...#.#.#.#..
+...#..#..#.#.##..###.###
+.#.#....#.##.#...###.##.
+###.#...#..#.##.######..
+.#.#.###.##.##.#..#.##..
+.####.###.#...###.#..#.#
+..#.#..#..#.#.#.####.###
+#..####...#.#.#.###.###.
+#####..#####...###....##
+#.##..#..#...#..####...#
+.#.###..##..##..####.##.
+...###...##...#...#..###
+
+

Now, you're ready to search for sea monsters! Because your image is monochrome, a sea monster will look like this:

+
                  # 
+#    ##    ##    ###
+ #  #  #  #  #  #   
+
+

When looking for this pattern in the image, the spaces can be anything; only the # need to match. Also, you might need to rotate or flip your image before it's oriented correctly to find sea monsters. In the above image, after flipping and rotating it to the appropriate orientation, there are two sea monsters (marked with O):

+
.####...#####..#...###..
+#####..#..#.#.####..#.#.
+.#.#...#.###...#.##.O#..
+#.O.##.OO#.#.OO.##.OOO##
+..#O.#O#.O##O..O.#O##.##
+...#.#..##.##...#..#..##
+#.##.#..#.#..#..##.#.#..
+.###.##.....#...###.#...
+#.####.#.#....##.#..#.#.
+##...#..#....#..#...####
+..#.##...###..#.#####..#
+....#.##.#.#####....#...
+..##.##.###.....#.##..#.
+#...#...###..####....##.
+.#.##...#.##.#.#.###...#
+#.###.#..####...##..#...
+#.###...#.##...#.##O###.
+.O##.#OO.###OO##..OOO##.
+..O#.O..O..O.#O##O##.###
+#.#..##.########..#..##.
+#.#####..#.#...##..#....
+#....##..#.#########..##
+#...#.....#..##...###.##
+#..###....##.#...##.##.#
+
+

Determine how rough the waters are in the sea monsters' habitat by counting the number of # that are not part of a sea monster. In the above example, the habitat's water roughness is 273.

+

How many # are not part of a sea monster?

+
+

Your puzzle answer was 2453.

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 f6be361..40f3816 100644 --- a/stack.yaml +++ b/stack.yaml @@ -54,6 +54,7 @@ packages: - advent17 - advent18 - advent19 +- advent20 # 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