diff options
Diffstat (limited to '')
| -rw-r--r-- | 2023/14-Parabolic_Reflector_Dish/example | 10 | ||||
| -rw-r--r-- | 2023/14-Parabolic_Reflector_Dish/first.hs | 70 | ||||
| -rw-r--r-- | 2023/14-Parabolic_Reflector_Dish/input | 100 | ||||
| -rw-r--r-- | 2023/14-Parabolic_Reflector_Dish/second.hs | 81 |
4 files changed, 261 insertions, 0 deletions
diff --git a/2023/14-Parabolic_Reflector_Dish/example b/2023/14-Parabolic_Reflector_Dish/example new file mode 100644 index 0000000..5a24dce --- /dev/null +++ b/2023/14-Parabolic_Reflector_Dish/example @@ -0,0 +1,10 @@ +O....#.... +O.OO#....# +.....##... +OO.#O....O +.O.....O#. +O.#..O.#.# +..O..#O..O +.......O.. +#....###.. +#OO..#.... diff --git a/2023/14-Parabolic_Reflector_Dish/first.hs b/2023/14-Parabolic_Reflector_Dish/first.hs new file mode 100644 index 0000000..0061d3e --- /dev/null +++ b/2023/14-Parabolic_Reflector_Dish/first.hs @@ -0,0 +1,70 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Vector qualified as V +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 136 + +data Tile = Cube | Empty | Round deriving (Eq) +instance Show Tile where + show Cube = "#" + show Empty = "." + show Round = "O" +type Row = [Tile] +type Input = [Row] + +type Parser = Parsec Void String + +parseTile :: Parser Tile +parseTile = char '#' $> Cube + <|> char '.' $> Empty + <|> char 'O' $> Round + +parseRow :: Parser Row +parseRow = some parseTile <* eol + +parseInput' :: Parser Input +parseInput' = some parseRow <* eof + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute input = sum $ map (fst . L.foldr weight (0, 1)) shiftedInput + where + transposedInput = L.transpose input + shiftedInput = map (shift 0) transposedInput + shift :: Int -> Row -> Row + shift n [] = replicate n Empty + shift n (Cube:xs) = replicate n Empty ++ Cube : shift 0 xs + shift n (Empty:xs) = shift (n+1) xs + shift n (Round:xs) = Round : shift n xs + weight :: Tile -> (Int, Int) -> (Int, Int) + weight Round (acc, i) = (acc + i, i+1) + weight _ (acc, i) = (acc, i+1) + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input diff --git a/2023/14-Parabolic_Reflector_Dish/input b/2023/14-Parabolic_Reflector_Dish/input new file mode 100644 index 0000000..5328513 --- /dev/null +++ b/2023/14-Parabolic_Reflector_Dish/input @@ -0,0 +1,100 @@ +...#O#O#.#...O...O...##...#..O#OO..OO....#.#OO....#.#.......O..O.#..#O.#......#.OO.....#....OO#....# +.#.##......O.O.#..#.OO..........#O.#....O.#..O............#.O.......#....OO.#.#..#O.O..#....O....O.. +.#OO......O.O.O#O.#.##.....O...O....#O.O.OO.....OO...O..#O..O...O..#...O.#...#.....#O......O.....#.. +O...##OO..O.O..##...O#..O#O.......#.OO..#....#...#.O....#.O..#O..#O...O.###.#....#.#..##.#...O...#.# +...#.#.....#....#O#...#..OO...#..#.......O.O..O##....O#.OOOOO.##.....O..#.O.OO..O.....O....#.O....OO +O#......O..#O##O........OO..#......#...#O..O..##.............O..#........O...##OOO.###O.O.##.O.#.O.O +.#O...OOO...#..O#.#.O.O..........#.O#..#.#....OO#O##.#...OO....#O.OO..#......#.......#...O..#.O.O##. +.#......#O..O..#..#.#.........O...#.#........O.#...O....#.O...#.......O#.O..#.#.....O...##....#.#O.. +#..O..#OO...O##......#........O....O#..O.O..OO.OO....##O.OO...O##.#OO#...O..#..O....O.O.O.O...O.OO.. +....##.O..OO.#.....##.#O#O.O.#..#...#..OO#......OO.......O.O.O.O..##..O.##......O...O.#..O...O.O.### +.O.#O......O.O.#....#......O#.......O......O#.O...#...O...#..#.#..#...##.#..##...O#O#.O.#.#...#.#.O. +#O.O....##....#..O.###..O.......OOOO#O#O.#OO.##...OO.O#........O..#OO.#.#...O.O.O....O....#O.##...#O +.OOO...O....#O.#....#..O#..OO.....#.#......#OO..#........O.O.O.....#....O.O#.O.....O.OO.##O..O##.... +...O#....#O...O..##..O.#..O#..OOOO#..OOO.#O#..#OO.O...O..#.#..#..#..#O..O.OO..O...O.O..OO........... +..OO###..##..#.....O....O.....O.#O.......O..O..##...O#...O#..#...O..O....O#.O##..............#....O# +.##.###.....###O....O.O..O...O.O..O.#......#O.#..O.O#.#O##O..O#.....O.#...........O..O....O...O.O... +...O.................#...........#.O.......O.....#..O.O.O.....O........##.OOO.#.....O.OO...........# +..O.O#...#O...O.#....#.OO..#O..#.....#.##.....OO....O..O...#...#..OO..O.O....#OO........#O.##....O.. +O..#..O.#.O....O..#OO##.OO...O.##O..#..#.##..O#.#.OO.O........O....#O.OO.O.#O.O.#...##O##..OO..#.O.. +...#.O#..........O###...#.O.#.O#.#.OO...OO#...O.....O..O..#.OO.....##...O#........#.O.O......#.O.... +OO#..O.##..##OO..#....O..#.O..#..O.#...#O#.O..O###....O#O#.#..O#.##.#......#.....O..OO..........#O.. +#O.##..#.....###.#O#...#O.##....#...O..#..#..##...#.#..#.#O...O.#.#O....##O..O.O...O.#.OO.##..O#.O.. +#O#.....#O.....#.##.O..O....#..O.........#....#.O#.O..........#...O.O#..#.O.#....#.O..O.O#O.O.#O.#.. +.O#.O..O#...#......O..#O#.O#....#...###.#.#.##.O#...#..#O#O.O...#.#...O...##.O#.#O.....O....O....... +O........O....##..##.OO.....OO...O..#..O#...O..O..OOO...O...O......#..##....O.#...O#O............#.. +..#OO.OO.O..##...#........O......O.#O..O#.#O#.#...#.#...O.O....O......#....#.#..#.#............#..OO +...##O.O.......#...#O#..OO..O.O.#.#..##.........O##O..O..O#..O#.#O..O...O.......##OO..OO..#O..###O#. +.....#..O..........O.....O#...O.O#....#O#...O..#.#O#....#.#O......O....##......O..OOO#O...#...##O..# +......O##...OO.OO#.OO#..#...#...#.#...#OO...O.......#..O.O.O.##..#......O##....#......OO.#O..#O.O... +....OO....O##..O..O.O.......#....O.O....#.OO...O..#O.#..#.#O.#.....O..#.OO.OO..#....O.....O.O#O...O. +OOOO.O.#.#O#.O.........#O..O#O...O.#..#...O...O.OO..OO...#O#.##O.O.#...OO##...O..##OO..#O...O..O.OOO +#O.O.#.O.OO.O...#O#.#O.OO..O#O...O###....O....O.O.O.....O...#.OO.##....O.O..#......#..#O.O##...#.O#. +O#......O.#...O.....O.O..#.##.OO...O...O.......O.O.#...#OO..OO...OO..O.##.O...#O#.O........OO#....## +OO......O#.#..O...O...O..##O...O.###..O..OO...OO..O.#O...#.#...O.#.OO.......#.##...O......O#.....O.. +.#..##.....OO...O...O..#.......O.O.#....O..#...O....O..O#...OO.......O...O.O.#..O.O....O.O.#.O.O.OO. +....O....O.#O#....#O#O..O.....#..#.O.O.O..O...O.O..O...O..#O#....O.O.............O..O...O....O...... +..#.O....OOOO#OO#.#.O..O....O....O.#.#..O....#.O#.O......O...#.............O##.......#....O..######. +......OO##O..##O#.....O..OO.#..#O..##..#.O#........O.O...##OO......OO.#.#...#.OO...O.OO......O.O...# +OO..O....O..#.#.O#..O#O...###.O#.....O...##....OOO...#O..O..#OO.O#....##.O..O.........OOO.........O# +..O.O.O#O...OO..##....#.#...O...#.##.......##...#O.#O..#...##.....O.....OOO..O...O......#...OO...#.O +#O...OO.........OO.O....#OO......O##.O..##....O..#.O.O.O#.O.OO#O..O...#.#...#.#...O.OO...##.....##.O +...OOOOO.O...O#.......OO#.O..OO..#OO......O...#..O##.#....O#....O.O...#.....##.O....#..##..O..#..... +.OO.....O#....#....#O..O..OO#OOO..O#.......#O#..O.O..O..O##..O.......OO.......O.##...O.O..#........O +....O#.O......#..O.OO...OO#.#..O#....O..O#.#..#...O#..OO...#O#.....O...O.....##.#..#O.O..O#OO.O.#O.O +..O.#.#.....O#.O.....OOOO.O..#..#O.#.#O.#OO.....O..#..O..O..#O......##O.#O..#.OOO....#O.O.#O...#..O. +......#.O...O.O#....OO#..O#....#..O...O.......#OO...#...##O#O##.O...O...O......O##.O.O#.#OO.OO.O#... +....O...O.O..#..O........O..OO...OO#...OO.......O#.OOO#...OO#OO#O.O.O#OO.....O.###O..O#.O...#....... +#O.#OO.....##O.O....O..O.OO.#...O...#.O.O..O.OOO#.....O....#.....O...##...#...#..#........#..#.O..O. +...O#......O..O.#.......#....#O...OOOO...O..O.O.O.#O....#.....O..#...O..#..O..............#O....OO.. +OO....O.#..O.#..#.#OO#...OO...O.#O...OO......#..O#..O..O#O...#OOO#..#.O...##.......#.#OO.O.###.O...# +.OO...#.O...#O.O.....O...##.#..O.#O.O.....O..O.....##...OO...O..#O..........#OO.#......O#...O#...O.. +.O.#.O.O..........O...O.#.##OO....##........O.#.....O#O...#.O.....OOO#..........#..O..#..O.#O.#..O.. +.O..#.....#O......O....O....O....#..#.....O...O...OO#...O..#...O...#...O.##OO.#.O#.OOO#OO#...#....#. +.OOO#.....O.O.#.OO.........#O##.OO##O..#..#OO.OOOO...O..#.#..O#....OO..#...O#O....#OOO.#...O.#..#... +...O#...#..#.#...O.#O..#.......#...#...O#......#O.O.#.OO.O#O.O.#.O....##..O#O.##.#.....OO..O......O. +..#.#.O.O.#..O..#.O....OO....O##.O.#...#O...O.OO.O......#..O.....#........O.#......O.#.##..OO...OO.# +....O...##....OO#O#O..#.O.##..O....##OO....O..OOO..#O..#.O...#.......O#.......OO.O.#..#.OO.O..#OO... +.#.....#O#.#OO#.#.#O##.O#....#.....#.##..O...#.....O#.O.O...O.O....#........#O...#..OO..O.#.OOOOO.O# +O....#O......O...O..O#..#.O..O.OO.....#.O.OO.O...#O.OOO....O.........#....#.#.O.##.#O...O.O#O.O#..#. +.OO.O..OOOO#.#.......O..................O......#..#...O.#O#O.....#..O..#O.#..........##.#O#.O..##... +..O...O.OO#.O##.##.#O....O....#...#...O...OOO........O.O..#.##......###.........##...O..O...OO...O.# +OOOO......#.O..OO.OO#..#...O.##.#O..O#.OO#.......#.O.O.OO.O.#OO#O.#...#......O#O..O.O....#O##.O..O.# +.......O..O...OO.#O..O....O#..#.##.......O...........#..#.....O......#.#..O.......O.O#..#.O.#O.OOO#. +#.#.O...##.......O...O..O.#..#....O##......O.##OO......OO.....O.O.##.#....#...O....#O#.#....#.O#..#. +O.O......O#.....#...#..#.O#..##O..O#O......O.......##..O.....#O.O...O..#..O..O...#.O.#..O..#.O#.#.O. +.#...OO#.O#.#.O.O.O..OO....OO....O...O#.O.#......#.O#.OO#.O..O.OO.O.#.O...OO.....###O..#.O.....O.O#O +..##OO...#..##.O#.......#......#.......O..OO.....O...OO...#..O..O..O..OO.O.O.O......O#...O.#..O.O#.. +...#.O..#...O.#.##.O.OO..OO.....#..#..O..#..O.#..O..OO..O.#.#...##......#...#O.#....#O#...OOO#...#.. +.......#O...#......O..O...#..O..#....#.O..O.##........#.....O....O...#O#OOOOOO..O.....##..O..#O.O... +#.O...OOO..O.O.###.#..O..OO.O....O##...#.O....OO.......O..........##...O...#.#.OO.###...O..........O +#....O#OO.OO#O..............#.#.#...O#OO.##.#...O.O....O....#O.#..#......O.....O..O.O#O......OO....O +...O.OO....OO.O..O#O.O.O.....O.#.O.#..O....#.O#O.#.......OO....#.#.O...O.#.#..#O.O##..#.#...#....O#. +..#.O...OOO..O..#..O#.O....#O#O.O##....O.O.....O...........O#...##.....#....O....O.OOO#O..##O..O.O.. +O#..........#..O#OO....OOO..O#..O..OO.....O....#.....OOOOO.#....O#O..O.....#....#..O....O...#.O#..#. +.O.#.#.O..#.O#O...#.O.O...#..#...#.....#....##O.OOO#...OO..O..................O.#OO...O#.....O...#O. +##..#.#..#.#.O###O#.O..###.......#O..O......#..#.#......O..OO#..#OO...O#...#..OO#O.#.OO#..#..O...O.. +........O....O..#..#..O.OOO....O.#O.....#O......O..OO##O#O.#.OO........O.#...OOO..O#...O..O.....#... +..OO.O.O..O...#.......O#.O.O.#O..O..#...#......#.#O#.O....#...#..O......O#...O.##.O....O.O.O.O..O#.. +..#..O..#.#O.O...O.#..#..#.##...O.#..#.O..O.#..O....#..OO..OO.#.#...O..OO.......O...#.O#OO..O...#.#O +.#......OO#...##.#.#.....O...#.................O....#....##.O#O.#...O...O#....#O....O....O....###... +...OO.##.OOO...OO..O.O...#......O.....O.......O.O.OO..#O#O.O#....#....#..O##O....#OO#.......O..#...# +O.O..O#O....O.O#O.OO.O.....OOO..O...O.O.##.O.#O.O#.#.#O#......O.#.O..O.#.O....OO##.....#...O.#OOO... +#.#.....#.O.O#.O..O...#OO....O#.......#.#..O..##..#O..O...##.##..O..O#....#...OO...O..OO...#..#..O.. +#.O.#.O#..#...O....O..O.O.OO##..........#..O...#.O#OO..O.O.#.........O#.O...O.....#O.O.O...#O...O.## +....#O...O....##.#.O.##O...#..#.#..O.O#..O..#O.#......#.......OO..O.....OOO#O....OO..#O.....O..#..O. +.OO#.....#.OOO....#.....#O###....O.##O...#.##..O.....O......O..O.OOOO.#...O.#..#.###...O..#..O..OO.# +...#O#..O#.O....O.OO.O.#.O..#...........O..#O.....O.....#OO.O#.O....O...#..O..O.#.O..##....##....O.O +###....#..O..#....O.............O#O..........O.O...#.O........#...#.O.....O##...O.#O#...O.O.#O.....O +..O.#.......O.....#..#....O.O.#.O#OO...#.#.#.....#OO.#..#......#...#...#..#.......O#.....O####OO.#.O +.O#....O..O.......#O..#.O#.#..OO.#...#.#.O.O.....O.O.#......#O.#O........O.OO.....OO..O..#OO.....#.. +...#.#...O#O.##....O.#....OO..O.OO#...O.OO.OO..O....OO..#..O..O.##.#.OO.#OO..#..O.O.O#.O..OO.O.O#.O. +...#...O.....O...#....O...#...OO#.O#..#....O...........###.O#.....O.##O.O....O...O#....#...#.O...#.. +...#..#....#.O.O..#O.#O.........##O....O.#OOO#.O##.#..O....#..#.O....O...OO#O..O.O.#....#.....#O#O#O +..#..#...#.#O......OOO..#.OOO..OO.O#...OO....#O.O.#.#....O...OO#...OO....O..##...#.#O....#.#OO.OO.O. +O.O...#..#O...O##..#..O.#............#..#...##O.O.O....O..O.O...O##.#..O...O..OO..#...O........#.... +#.O##..#.....OOO.O..##O...#.O...####.OOO...#...O..#..#......O...#.....#.O.O.O...O##......#...O....#. +...###O.#.O.OO.........O##.#...O..#......O#.#...##O........O.O..O#....O..#.#.O.#.##.O.O#O#....O#.O#O +O...O.O..O.#.......O..O.O....O..O..#..#.........#O.OO..O..O.#O..O.....O.....#O.........#..O.#.#..O.. +..O#...#......O..OO...O.#.##O.OO.#...OO..#OO#....#.#.O#..#O.#.OO..O...O#.OO.O...O.#.#.....O..#O....# +....O..#.....#..#.#O.O.OO.#...#.O...#.....##.#..#...OO........O#..O.OO..O.O..O.#...#....O..##..O.... diff --git a/2023/14-Parabolic_Reflector_Dish/second.hs b/2023/14-Parabolic_Reflector_Dish/second.hs new file mode 100644 index 0000000..2479daa --- /dev/null +++ b/2023/14-Parabolic_Reflector_Dish/second.hs @@ -0,0 +1,81 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Vector qualified as V +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 64 + +data Tile = Cube | Empty | Round deriving (Eq, Ord) +instance Show Tile where + show Cube = "#" + show Empty = "." + show Round = "O" +type Row = [Tile] +type Input = [Row] + +type Parser = Parsec Void String + +parseTile :: Parser Tile +parseTile = char '#' $> Cube + <|> char '.' $> Empty + <|> char 'O' $> Round + +parseRow :: Parser Row +parseRow = some parseTile <* eol + +parseInput' :: Parser Input +parseInput' = some parseRow <* eof + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseInput' filename input of + Left bundle -> error $ errorBundlePretty bundle + Right input' -> return input' + +compute :: Input -> Int +compute input = sum $ map (fst . L.foldr weight (0, 1)) (allPossibilities L.!! theOne) + where + transposedInput = L.transpose input + shift :: Int -> Row -> Row + shift n [] = replicate n Empty + shift n (Cube:xs) = replicate n Empty ++ Cube : shift 0 xs + shift n (Empty:xs) = shift (n+1) xs + shift n (Round:xs) = Round : shift n xs + weight :: Tile -> (Int, Int) -> (Int, Int) + weight Round (acc, i) = (acc + i, i+1) + weight _ (acc, i) = (acc, i+1) + theOne = start + (1_000_000_000 - start) `rem` (end - start) + (start, end) = cycle M.empty 0 allPossibilities + allPossibilities = iterate process transposedInput + process = step 4 (L.transpose . map (reverse . shift 0)) + step :: Int -> (a -> a) -> a -> a + step 0 _ x = x + step n f x = step (n-1) f $ f x + cycle :: M.Map Input Int -> Int -> [Input] -> (Int, Int) + cycle m i (x:xs) = case M.lookup x m of + Just j -> (j, i) + Nothing -> cycle (M.insert x i m) (i+1) xs + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input + |