2023-14 in haskell

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
+