From 75972c351184fd9226a5f8e7464a0383c4ab966b Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 24 Dec 2021 12:24:05 +0000 Subject: [PATCH] Day 21 part 1 --- advent-of-code21.cabal | 5 +++ advent20/Main.hs | 31 +++++++------ advent21/Main.hs | 100 +++++++++++++++++++++++++++++++++++++++++ data/advent21.txt | 2 + data/advent21a.txt | 2 + 5 files changed, 127 insertions(+), 13 deletions(-) create mode 100644 advent21/Main.hs create mode 100644 data/advent21.txt create mode 100644 data/advent21a.txt diff --git a/advent-of-code21.cabal b/advent-of-code21.cabal index 7134dcd..121c742 100644 --- a/advent-of-code21.cabal +++ b/advent-of-code21.cabal @@ -206,3 +206,8 @@ executable advent20 import: common-extensions, build-directives main-is: advent20/Main.hs build-depends: linear, mtl, containers + +executable advent21 + import: common-extensions, build-directives + main-is: advent21/Main.hs + build-depends: text, attoparsec, mtl, containers, monad-loops diff --git a/advent20/Main.hs b/advent20/Main.hs index fbc4fb6..2c258a7 100644 --- a/advent20/Main.hs +++ b/advent20/Main.hs @@ -1,5 +1,4 @@ --- Writeup at https://work.njae.me.uk/2021/12/18/advent-of-code-2021-day-16/ - +-- Writeup at https://work.njae.me.uk/2021/12/23/advent-of-code-2021-day-20/ import Control.Monad.State.Strict import Control.Monad.Reader @@ -44,20 +43,19 @@ enhanceImage 0 = do image <- get enhanceImage n = do newImage enhanceImage (n - 1) + newImage :: ImageEnhancer () newImage = - do image <- get - let region = explicitRegion image + do region <- gets explicitRegion let region' = expandRegion region let heres = range region' - let distant = distantPixel image - newPixelStates <- mapM newPixel heres - let grid' = S.fromList $ catMaybes newPixelStates + newPixels <- mapM newPixel heres + let grid' = S.fromList $ catMaybes newPixels + distant <- gets distantPixel enhancement <- ask let distant' = if distant then (last enhancement) else (head enhancement) put $ Image {grid = grid', distantPixel = distant', explicitRegion = region'} - showImage :: Image -> String showImage image = unlines $ [ [showPixel (V2 r c) | c <- [minC..maxC] ] | r <- [minR..maxR]] @@ -79,12 +77,22 @@ findStencil here = d <- gets distantPixel r <- gets explicitRegion return $ map (findContents g d r) nbrs + -- mapM findContents nbrs findContents :: S.Set Pixel -> Bool -> (Pixel, Pixel) -> Pixel -> Bool findContents grid distant region here | inRange region here = here `S.member` grid | otherwise = distant +-- more consitent but much slower +-- findContents :: Pixel -> ImageEnhancer Bool +-- findContents here = +-- do g <- gets grid +-- distant <- gets distantPixel +-- region <- gets explicitRegion +-- return $ if inRange region here +-- then (here `S.member` g) +-- else distant neighbours :: [Pixel] neighbours = [V2 r c | r <- [-1, 0, 1], c <- [-1, 0, 1]] @@ -92,6 +100,7 @@ neighbours = [V2 r c | r <- [-1, 0, 1], c <- [-1, 0, 1]] expandRegion :: (Pixel, Pixel) -> (Pixel, Pixel) expandRegion ((V2 r0 c0), (V2 r1 c1)) = (V2 (r0 - 1) (c0 - 1), V2 (r1 + 1) (c1 + 1)) +parse :: String -> (Enhancement, Image) parse text = (enhancement, image) where ls = lines text enhancement = [ c == '#' | c <- head ls] @@ -106,10 +115,6 @@ mkImage rows = Image { grid = grid, distantPixel = False maxCol = (length $ head rows) - 1 grid = S.fromList [V2 r c | r <- [0..maxRow], c <- [0..maxCol], (rows!!r)!!c == '#'] - +intify :: [Bool] -> Int intify pixels = foldl' addBit 0 pixels where addBit w b = (w * 2) + (if b then 1 else 0) - --- wordify :: BS.BitString -> Integer --- wordify bs = foldl' addBit 0 $ BS.to01List bs --- where addBit w b = (w * 2) + (fromIntegral b) diff --git a/advent21/Main.hs b/advent21/Main.hs new file mode 100644 index 0000000..5a76130 --- /dev/null +++ b/advent21/Main.hs @@ -0,0 +1,100 @@ +-- Writeup at https://work.njae.me.uk/2021/12/23/advent-of-code-2021-day-20/ + +import Data.Text () +import qualified Data.Text.IO as TIO +import Data.Attoparsec.Text hiding (take, takeWhile, dropWhile) +import Control.Applicative + +-- import Control.Monad.State.Strict +-- import Control.Monad.Reader +-- import Control.Monad.Writer +-- import Control.Monad.RWS.Strict +-- import Control.Monad.Loops + +import qualified Data.Map.Strict as M +import Data.Map.Strict ((!)) + +data Player = Player1 | Player2 deriving (Eq, Ord, Show) + +data PlayerState = PlayerState + { position :: Int + , score :: Int + } deriving (Eq, Show) + +data Game = Game + { players :: M.Map Player PlayerState + , current :: Player + , rolls :: Int + } deriving (Eq, Show) + + +-- type GameState = State Game + + +main :: IO () +main = + do text <- TIO.readFile "data/advent21.txt" + let game = successfulParse text + print game + print $ gameStep game + print $ take 8 $ iterate gameStep game + print $ finished game + print $ part1 game + -- let (enhancement, image) = parse text + -- print $ part1 enhancement image + -- print $ part2 enhancement image + +part1 game = scoreGame finalGame + where finalGame = head $ dropWhile (not . finished) $ iterate gameStep game + +finished game = any (>= 1000) $ map score $ M.elems (players game) + +scoreGame game = (rolls game) * losingScore + where losingScore = minimum $ map score $ M.elems (players game) + + +gameStep :: Game -> Game +gameStep game = game' + where rs = rolls game + 1 + theseRolls = [n `mod1` 100 | n <- [rs..(rs + 2)]] :: [Int] + activePlayer = (players game) ! (current game) + pos = position activePlayer + sc = score activePlayer + pos' = (pos + (sum theseRolls)) `mod1` 10 + sc' = sc + pos' + activePlayer' = PlayerState {position = pos', score = sc'} + current' = nextPlayer (current game) + players' = M.insert (current game) activePlayer' (players game) + game' = Game { players = players' + , current = current' + , rolls = rolls game + 3 + } + + + + + +nextPlayer :: Player -> Player +nextPlayer Player1 = Player2 +nextPlayer Player2 = Player1 + +mod1 :: Int -> Int -> Int +mod1 a b = ((a - 1) `mod` b) + 1 + +-- Parsing + +playerP = ("1" *> pure Player1) <|> ("2" *> pure Player2) + +playerStateP = playerify <$> ("Player " *> playerP) <*> (" starting position: " *> decimal) + where playerify name pos = (name, PlayerState {position = pos, score = 0}) + +gameP = gamify <$> playerStateP `sepBy` endOfLine + where gamify ps = Game {rolls = 0, current = Player1, players = M.fromList ps} + + +-- successfulParse :: Text -> (Integer, [Maybe Integer]) +successfulParse input = + case parseOnly gameP input of + Left _err -> Game {rolls=0, current=Player1, players=M.empty} -- TIO.putStr $ T.pack $ parseErrorPretty err + Right game -> game + diff --git a/data/advent21.txt b/data/advent21.txt new file mode 100644 index 0000000..b2f61cc --- /dev/null +++ b/data/advent21.txt @@ -0,0 +1,2 @@ +Player 1 starting position: 4 +Player 2 starting position: 3 diff --git a/data/advent21a.txt b/data/advent21a.txt new file mode 100644 index 0000000..3f69194 --- /dev/null +++ b/data/advent21a.txt @@ -0,0 +1,2 @@ +Player 1 starting position: 4 +Player 2 starting position: 8 -- 2.34.1