2024-15 in haskell

5 files changed, 375 insertions, 0 deletions

diff --git a/2024/15-Warehouse_Woes/example b/2024/15-Warehouse_Woes/example
new file mode 100644
index 0000000..8163605
--- /dev/null
+++ b/2024/15-Warehouse_Woes/example
@@ -0,0 +1,10 @@
+########
+#..O.O.#
+##@.O..#
+#...O..#
+#.#.O..#
+#...O..#
+#......#
+########
+
+<^^>>>vv<v>>v<<
diff --git a/2024/15-Warehouse_Woes/example2 b/2024/15-Warehouse_Woes/example2
new file mode 100644
index 0000000..84cf1fb
--- /dev/null
+++ b/2024/15-Warehouse_Woes/example2
@@ -0,0 +1,21 @@
+##########
+#..O..O.O#
+#......O.#
+#.OO..O.O#
+#..O@..O.#
+#O#..O...#
+#O..O..O.#
+#.OO.O.OO#
+#....O...#
+##########
+
+<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^
+vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v
+><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv<
+<<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^
+^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^><
+^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^
+>^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^
+<><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>
+^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v>
+v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^
diff --git a/2024/15-Warehouse_Woes/first.hs b/2024/15-Warehouse_Woes/first.hs
new file mode 100644
index 0000000..63299d1
--- /dev/null
+++ b/2024/15-Warehouse_Woes/first.hs
@@ -0,0 +1,109 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import           Control.Monad        (void, when)
+import           Data.Functor
+import qualified Data.List            as L
+import qualified Data.Vector          as V
+import           Data.Void            (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+exampleExpectedOutput = 2028
+example2ExpectedOutput = 10092
+
+data Tile = Wall | Box | Floor | Robot deriving (Eq, Show)
+type Line = V.Vector Tile
+type Warehouse = V.Vector Line
+data Op = N | S | E | W deriving Show
+data Input = Input Warehouse [Op] deriving Show
+
+type Parser = Parsec Void String
+
+parseTile :: Parser Tile
+parseTile = char '#' $> Wall
+        <|> char 'O' $> Box
+        <|> char '.' $> Floor
+        <|> char '@' $> Robot
+
+parseLine :: Parser Line
+parseLine = do
+  line <- some parseTile <* eol
+  return $ V.generate (length line) (line !!)
+
+parseOp :: Parser Op
+parseOp = char '^' $> N
+      <|> char 'v' $> S
+      <|> char '>' $> E
+      <|> char '<' $> W
+
+parseInput' :: Parser Input
+parseInput' = do
+  line <- some parseLine <* eol
+  ops <- some (parseOp <* optional eol) <* eof
+  return $ Input (V.generate (length line) (line !!)) ops
+
+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'
+
+type Coord = (Int, Int)
+
+next :: Coord -> Op -> Coord
+next (x, y) N = (x, y-1)
+next (x, y) S = (x, y+1)
+next (x, y) E = (x+1, y)
+next (x, y) W = (x-1, y)
+
+compute :: Input -> Int
+compute (Input warehouse ops) = V.ifoldl' scoreBoxes 0 warehouse'
+  where
+    scoreBoxes :: Int -> Int -> Line -> Int
+    scoreBoxes acc y line = V.ifoldl' (scoreBox y) acc line
+    scoreBox :: Int -> Int -> Int -> Tile -> Int
+    scoreBox y acc x Box = acc + 100 * y + x
+    scoreBox _ acc _ _   = acc
+    warehouse' = fst $ L.foldl' step (warehouse, start) ops
+    step :: (Warehouse, Coord) -> Op -> (Warehouse, Coord)
+    step a@(w, r@(x, y)) op | t == Wall = a
+                            | t == Box = case push w r' op of
+                                Just w' -> let line = w' V.! y'
+                                               line' = line V.// [(x', Floor)]
+                                               w'' = w' V.// [(y', line')]
+                                           in (w'', r')
+                                Nothing -> a
+                            | otherwise = (w, (x', y'))
+      where
+        r'@(x', y') = next r op
+        t = w V.! y' V.! x'
+    push :: Warehouse -> Coord -> Op -> Maybe Warehouse
+    push w r@(x, y) op | t == Wall = Nothing
+                       | t == Box = push w (x', y') op
+                       | otherwise = Just w'
+      where
+        (x', y') = next r op
+        t = w V.! y' V.! x'
+        line = w V.! y'
+        line' = line V.// [(x', Box)]
+        w' = w V.// [(y', line')]
+    start = V.ifoldl' findRobot (0, 0) warehouse
+    findRobot :: (Int, Int) -> Int -> Line -> (Int, Int)
+    findRobot (0, _) y line = (V.ifoldl' findRobotInLine 0 line, y)
+    findRobot a _ _         = a
+    findRobotInLine :: Int -> Int -> Tile -> Int
+    findRobotInLine 0 x Robot = x
+    findRobotInLine a _ _     = a
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  example2 <- parseInput "example2"
+  let example2Output = compute example2
+  when  (example2Output /= example2ExpectedOutput)  (error $ "example2 failed: got " ++ show example2Output ++ " instead of " ++ show example2ExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input
diff --git a/2024/15-Warehouse_Woes/input b/2024/15-Warehouse_Woes/input
new file mode 100644
index 0000000..9947572
--- /dev/null
+++ b/2024/15-Warehouse_Woes/input
@@ -0,0 +1,71 @@
+##################################################
+##...O...#OO...O.#....#....#O#O..O..O......O..O..#
+#OOOO.#.O.O.....OO#...O.OO.O....O.#..OO....O#OOO.#
+#...#.#O..O...OO......O.......#....O..O#.O..OO...#
+#.O.....O..#.........O......OO..O..OO.OO....O.O..#
+#.....O.OO.O.#.O...O..#.OOOO..#...#.O.OO.O.#.#OO##
+#...OO.#..O.O.#.O..OO..O....O...OO.OOO.......O...#
+##.O.....O..#O...........O..O.....O.......OO.....#
+#...O..O....O...O...O...O..O..O...O......O..OO...#
+#.O##.O.OO.....O.O.#....O#.....OO.O.O.#..O....#O.#
+#.............#.O........OOO.OO..#.............O.#
+#OOO..O.O.........OO....O.#......#.OO.......O..O.#
+#.......#...O..#O.OO...O..#O.O...##O#O......O##..#
+#O#.O..#........O....O.....O...#O..#......O.O..O.#
+#O..O..O#...#.......OO.OO..O.....O..O..O.O.O...O.#
+#...O.O...OO.......#O#O...O.##.....#..O.O.....O..#
+#.#OOOO..OO..O....O.O....OO.#.OO..O.......O....#.#
+#..O...#.....#.....OO..#O....O#.O....O..OOO.O...O#
+#.O.......OO.O.#........OO...O..O#..O.#..##...#.O#
+#.O..#..........OO.O.O..O..O.......O...O.O.OO....#
+#.O..##..........OO..O..O.....#OO#...#..O....O...#
+#O.OOOO.O..O........O#.#OO.OO...OO.#OO..OO#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..OO..O#
+#...O..##O.#....#.......O..OO#..O.O.....##O....O.#
+#....O.O...O.OOO.O.O#..O..OOOOOOOOOO#.....O...#.O#
+#O.....#O..O..#..O....O.O..OOOO.#.O.O#....#.O.O#.#
+#..O.O..#O..............O....###..O#.O.....O.#O#O#
+#O...O.O.#.#..O......OO.OO#..O...O.O....O#.O...OO#
+#..OO.O#.....O##.O##....O..#..#..#O..O.....#....O#
+#....#..O..O....O.OO...O.......OO.OO...O.O.....O.#
+#....O.O.#O.#OO.......O......O........OOO..O.....#
+#..#...##.O......##.....O..O.O#.O...O....O..#.O..#
+#...O.O..O....O..O.OOOOOO...#.O...OO.#.....OO.O..#
+#O.......O....#.OO.OO...OO...##O......O.O........#
+##.O.OO.OO...O..O#......O.O....#.............O.#.#
+#O#O...O..O..OO.O.O...OO..O.O..OOOO..O..O...O..O.#
+#..OO.O#O..O..#.O..O.#...#..O.....OO..OOO..O...O.#
+#.O.O..OO.....O...O.....O..#..O..#.O.#.OOO...O.O.#
+#.O..O.......O...OO#.#..O....O...O....O..........#
+#....O..O.OO...OO..#....#O.OO.OO##.....O.........#
+#..O..O....O...O....OO#.#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.....#OO..O..#.#.#....O.O.OO.O.O......O#.#O..#
+#.O.O..O.O.O.O...O..O..OO..................#OO...#
+#..O....O....O.....OOO...OO..OO.......O....OO....#
+#.O....OO.O................OO....O.O#O.O.........#
+##################################################
+
+>v>>>^>>v>vv^v^^v^^^<v^vv^vv<<>^v^^^<<<vv<>vv^^>v>v^^><>^<v<v><>>^>^<^^v>v<>^^v<><<^><v>v^v<<^>^>^>^>>vvv>^<<^^^^^><vv>>^>^^>^vv>><v^^v^<<<>^^<<<^^^vv^<^<<<>v<^v<v>^<>v<^>>^v^<>><><<^<>v>^>^>v>>v>vv^><v<v^v>vv>><^^<<>>vv<<^vv>^^vv>>><^v^>>v<<<<v>^<><>^>v^vv>v>><><^vvv>^><<>^<<<vvv^>^vv<<>v^^^>v<>^^vv>vv^<>^<>vvv<vvvv^^^<^vv^<v^<<vv^v<><vvvv^>vv<>><><<v>><^>v<>v<v<v>^v>^<>^v>>><^>>v<<<v^>^v>v>^^>^v<v^v^^<vv^v^><<^^<v^v>>^v>>>>>v<v^>^>^v^>vv^v^><^<v>^^<>^v^>><>>><vv<<>^v<^vvv<v^vvv^>v<<v>>^>><<^v^^v>^^>^<<<>v^^>><<v>^<v^<^>v>>>^^^<<vvv^>vvv>^><v>^>vvv^^^v^^>v^><v>><>^<v<<vv^^>>^^v>><vv>vvv>^>>>vv^><^<v<<<^^v>v^<v^^>^^<<<>v^vv<vvv>^v>v<^^>vv>v<>>vv<><v>v<^^<<^>>v<v^<>^<<v>><<vv^<<<<v^^^v^^<^<^<>v><^<>>v>v>v>v>v><v>>v<<^>>><v^v<v>>v^><^v^>>>^>^<<>>^^v><^<v^vv^<><>>v^^>v<vvv>v<>><<<<<>><<><v<>vv><^^^><vv<v<<>v^>v>>^^v^v^>vvv<v^<>><<<^>vvv><^^v>v<>v><^<v>v<^<<^<>v>>>>^<>^^^>v<v<<vv><v>>>^<^>v^><vv>^<<v<>><<^<>>>^v>><<>v^^v<^>v^v^>vvvv>vv<<>^^^<v>^<<v>>><<>>>vv^<^><><^^^>^v^<><>^<vv<^vv^^v>^<
+<^>vv>v>^^>^vvvv<<^><^<>>^<v>v>>^^<v><^<>><<<>^vv<>v<v^>>>^<<^<><<>^^vv^^<<><<vvv>v^^>vv^<v<<>>v><^>v^>>^^v<<<<^v<v<<>>v><v^>vv^<vv^>^v>^^>>><>v<><^v><vvvv^v<<>>^^v><>>vv^>v>v^>^>v<><^v>v^^<<>^v^>^>v<><^v<^^vv<>^^^v^>>><<><<<<v^v^><v<v<^^^><><^<<^^^vv<^^<^<v>v<<v^>>v<>>^<vv<^<v><>^<^v^>^v>>>^v>>v^>^^v^>><<v>>^<v>^vvv<v<<<v>^<>vv<^<v<>^<>v^v^>vv^v>><^>><>^^^<<v<vv^<vv>>v<^^^>vv<^^>vv^^^^<<^<v^>v<v>vvv<v<<^^><v<<^>^^<>v>>v><^v^<v>vv^<v<<v>v>vvv^>v<vv>>>>>^^v<<>^><>v^^^>^^>^>^^vvvv^v<v>>^^^v>>^<v<^^v>>><<>^^><<<^>v^^^v><v<v<v^v^><>^>v<v<^^^>>>vv><<^>><v>><<v<<vv><^^^<<^<>v>^v^v><<<<<<>>vv^<<<><<><><<^<^>^<v<^v>>>^>v^>^v>^v^<^>^v>><<<v>v^^vvv><<^>v^^<><v^>><<v><^^>>v<<<<<^>>><><vv>v<<>>^v<><<^>>v<<<^<^>>^>v^>^v<v>^v>>v<^>><<>><>vvv<<>vv^>v>><><<^><vvv>v><^>^<^v><>>v><v><^v^vv><>^^>>>v<^v^<^v>^v><vv<<v<<v><>>><v<vv<>>v^^>>>vv><v<<<<><v^^>>v>^<v^^>^v<<<><v>v>>^^<vv<v^v>><^<^^<>><v>^<^^<><^^^><>^<v^^^<v<^>>^v>vv^^<^v>><<vv><<v>><v>>>^>>><<<v<<><^vvv^<v>^>vvv^v>>v><<>v><<v<vvvvv^>^>><v^>vv^>>^
+vvv^v^><<v<>><><><<<^v>^v^><>^vvv<<^<<v^v<>>v<v^^>>^>v<v>^v<v^v>^<<vvv<^^v<<<<>v^v<<<v<^>><v^vv^vvvv^v><><v<<^>v>v^v^<v<v<^<><^>^vv<^^v<^^>vv<<>^^<>><<<<^^>>>^<^^>vv<>>>^^^^vv^>^v^v^^>^<<<>v^<v>^^^>v<^^<<^<v><^vvv>v>v>v<^>><^<^<>>>^^<<<vv^>>><>>v><>^<>^^<v^><<vv>vv^v<<>^>v><vvv>v^>>v^^^v<<>>^v><^<>^>^<^>^^<vv<>>><v^v^>>>^^>>^v^^^>>^v>v><^^^v<>>vv>>v^^<><^^v>v<^>>v<v^v^v^v^vv^vvv>v^vv>^v>vv<vv<^<<<v^v><<v>v<<^>vvv^^^^>>^>v>^^<>vv<>^^v><v<<^v><><><^<vv^>v^^>>>^^vv>^v>^<>vvv^v<^vv^<<^<^^<>>^<<><vv^>^>^^v^<v><v^>><^^>><<><<<<<<^>^><^v>^v>><v><v<>vvv>^^<^<<>v>>vv<v<><^<<^<>v<v>><><>^v><v<^^^<>>vvv>^^>>>v><v><^^>><<^<v><<^<v<<vv>>^vv<>v>^><><<<<<v>>>v^^v>^<>^<>v^^>>^<>>v^>^<>>>><>><v^v>>v>^<<^v^><<>>^v>><>><>>>><>vv<<>>^>v^v^<vvvvvvv^>v<<<^^<>vvvv^<<><<v^<<vv^^^v^^<<><v>v^^<^^v^^<>^v<>vvv>>^^v^^^<v>v^^vv<^^^<<>^v^>>^^<<^^v^^v<<vv^<<>>>v<>vv<v^v<<>vvv>^<v>v>^v<^^v<>^>^<><<v>v<>v^>v^v>><<><v><>>>>v^<^<^><>^v^<^><<v<^v><>>^v^^^v^><>^v>v<<^v>>^<<v<>v<^<<<<>>^><<<vv<^v^<^>^^><^^vvv^><v<><^^<>^v^>
+vvvv^vv^>>^v^v<^<vvv<>v>v>vv>^>^><^vv><v^v>v<><>v^v^>vvvv<<>v<^^^vv<^v><>^>^>v<>^>^vvv<>^>^<^^v^<><<>^>^v><v>^v>v^<v^<>>^^>^>v^>v>>^^<v><^<^vv>^vv^v^>v><^vv>^>v>^><>v>v^^>>v>^<<v^<vvv>>v<v>v^^<>^v^vv^<^^<v>>>v>>^v>vvv^^v^>v<vvv^<><v>v>v<>^^v^^<vv<>v<vvv>>><><<>>v>^^<^^^^><v>^>v<^<^>v^^>v>^>>^><<<^vv>vv^v^><v^<v>vv>^<>^vvvv^>vv>^>v^>v<<v^^<v^<v>>vvv<<v<>>>v^>^vv>^<v<>>^^v<vv<^>v<>^<<^^><>^^v>^v>>^<v>vv^v<<^^>^<v<><v>vv<><vv<>>v<^^^><<^^>^v<>vv<v>><<<v><<>>vv^>>^vvvv^><<v<vv^v<vv<>v<><v<<><v>vvv>>vv^^^<><^v<><v<^<v<v<^>>vv<><<>^^>><<v><^>vvv^>^vvv<>v^^<<^<vv>>v>^>v>^^><<>v<v^>^<<<<vv<<^^^>^>^>v<>>vv^><v<><<><^><><^^vv>>^<^vv<^^v<><<><>vvvv^^^<>v>>v^<vvv<v<vv><<v^v<v>>^v^<<^>>vvvv^v<<^<^vv<v<v>^v<^<^^>vv<v^^^>>^<^><^^v<v^v^>^^^v^v>^>^><^>>^v<v<^^^v^>>^v>vv>^v<>^v^^^v^v^>v>><^^<^v<<v<^v<>v^<>^<>^v<v^^v<^>v<v>^v<<><<<>^v><<<^>vvvvv^v^^^<<v>>v^>>^^<<v^^>vv^^vvvv>^>v^<<<^<>v><<^>^v^<^>><<<v<vv>vv<<^>^<^^><>>^^v>vvv^<^>^^^^<^v<<>^<>^>>v>^<><><>>^^vv^<<>><^<v><>^v^vvv<<>>^<>^>v<<^><<^>^<^>^<<><
+<<^<^>><<<vv>v<v<^<>>>v^>vv><>>vvvv<<^><<<>v<>v^v^<>v>v<^^<<v<vv^<<<vv>^<>^^vv<><v<<^v^v<^<v>>vv>><^^^><v<^>v<vvv^v<^<>vv^>v<>>>^vv<<<<<^><>^>^<vv<><^>v<vvv>^v<>><>><>>>>^vv^v^><^^v<vv<<v<>^<^<v<><<>v>^^^vvv>v<<<^^<^>v^^v><>><^^^^<>vv^^v^vv>><v<v>>v^<v>vvv>><v<>v>^>v>^^<v^^<<^<v^<v^v^><>^vv^vvvv^^v<>^><v^^<>>>^vv>v^^^^<v<<^>>>>v>>^>v^^^>><^^vv^v^vv<v<vv^<><^^>v>^vv>>^<v^v><^^^>^<<<^>vv<<>^v>^>v^>>^v<<>^^>vv^v>^v<>vv>v<>v>vvvv><<^^<>^<<v><^v<<<^><^<><>>><v>v<^^vv<^^^v<<>^>>>vv>^<<^<>v<^vv<v<^^><<>^v^v>^v<><<^<<v>>^<^v<>v>^>v>>v>><>v>><v>v^vv<v<^<vv<v><^<><><>^>^><^>>^<^vvv>v<v<<<>><^v<>^>><>^^^^>>v><v^^v^><v^v<^v>><>>^<^^^^v>^^^^>v>v^^vv^^>^^v<<<^>>><^^^^<^^^><^><>^^^vv>vv<>>v^>>>v^<><>^^><v>><><<^<v>>v>>^><vv<^>>^v<vv>>^>v>vvv^>v^^>>^vv^<<<>>^vvvvv<v>vvv^>>v^<>vv^<<<^v><v<<>v<>v^v<<v<<<vv^><>v>>^>vv>v^^<<v^>^><>vv>^^>>>><<<><>v><vv>>>v^<>>>^vv>vv<v^^v>vvvv<v<vv^>v^^<vv<>^<><<>>>v<>v>>v^^>^><<<<>>^<v>v<^^><>>>vv>v>>>^<>^v<v<<<vvv<^v^<v^v<<^^>vv>>vv^>v<<>^^v^>v<^<>>^<>vv^>v<<^v^<v>v<vvv^
+<>vvv^<v^vv>v<>^v>>>^v<^^>v>>v>>^^<^<^v<^v^^>^>>>>^^>><<><^^^^>^^v<>^^v>>v<^v<><^<^vv>v>v^^<<^v>>vv>>v<v<<^<v^<^>^v^^<^<<><^<>>^^>v>v<>>^<^<<>^vvv<>^<><^<v^>v<v<v><^vvv^^<^<^<^v>^^^<>vvvv>>>v^<v<><^^v>>^>v^<v><<><>>>^vv<>>vv>^^^v<^^>vv>v^>>>^^><v>><^>v<><>^^<^>^^^v>^^^<vv><v^^>v<<<^<>><<>^^^vv>>>^^v^^<v^<>v<<^>^^<^<>vv<vv>>^vvv<v<<>v<<<v>v>^v>^>^<vv<^<v^^<^>^<^>^>>^<<>v<<v>vv<><vv^>^^>^^<>^^<^<><<^>v^^^>^<^>v^v^<^vv>v>v<>>v<>v>>>^<<<<^^>><>v<v>^^>v<^^>v>v^v^>>><>>><<^>vv><<vv<<v>^vv<^<>>><v<^>>>^>^><<^<<v<<<>>>vvv<v<>vvvv><><^<><v^v>^v<<<^vvv>v^^><>v^><^<vv>^>>^v>^<^v<<^^<<^v<^><^^^v>v<<^^>v>vvv^v>>><^>v<<^<vv^>^>vv^><^^^><v<^^vv<vv^^v^>vvv^v^<>^>>>><>v^>>^>v<v^^^<<<<v^<vv^>v><^^<vv><v><^<^<^^><v>>><>v<^vv>^^<>^<<><v^^<>v^v<>^>^<>v>>^<>>>v^v^<<<^v<vv^^>><^>v<><^<^>>>>v<^>>>vv<^>v>>>>v^^vv>^^^<v^vv<><^<>>^v>^v^^v<>>v<^>^<v^^^^>>v^v><>^<^>^vv<v^^<<<vv<v<><vv^<v^vv>v>^>>><vv^v^><<^>^v><<><>vv^>^v^^v>^<v^<>v<^<<<v^<><<vv><v>vv<v>>vv<<><vv^v<v<<vvvv>>><^<>>^<^vvv^>v<<<>><^v<>vv^vv<^<v>>^v<v
+v>>><>v>>^^<v>^<v<<v<>^<^<>>vv<^^>vv<<^<^v^<v^v<^^^>>v<vvv>>^>v^v>><<v>vvv<^v^v<>vv>^<^>>>^<v^vvv^vv^v^^>v^vv<>v>^<<<v^^v>v>v>v<>>^v><v^^^><v<^^<^<v^^^>>v>>^>^v><v^>v<>^<vv>^^>v><<vv^<v<vv^>>^<<<v<^v>>^v><^>^>>><<<^<v^^v^^v<^>>>>^>vvvvv<>>v>^v^^v>v>>^<v>^>v<^>>v<<v>^^<^v>v<<<<><^v^<>^<^<><vv^<v^vv<^>^v>>>v<<>v><^><<>>^>^<><^^^^<^^><><<<v<>^>^vvvvv><v><>vv><>v^<>^vvv>>>^><<<><<<v<^<v<<^<vv>>v^>>vv^><><>^<^^<>><v<v^<>>><<v^v^^^vv<>v<^>>v^<><^><v<<<v>v><v><v<^<^vv><^>v<<v^^<^<^><>>v^v>^>>>>v^^v<>^v^v>v><>^v>^v>^vv^<<^^^vvv>><<<vvv<<^>v^v^v<vvvv>^>v<v>^>^v>>v^>^v^><<^><^>>^<>^<^^<^^^vvvvv<>^v^>v><<><^v^v^>^<<>^^><v^v^^><v>^v<><<^vv<>^<>><^>^^>v>^v>>^v>vvv>>^^v<^v>vv><^>>>><^v^<>^>>^<^><><<vv<<>v>^<>><>v^>v>^^<<v<><>>^^<>>>v<v>>><<v<^v^><>>><^^<><<^v>v^>^^<>>vvv^<<<v<<vvvvvvv<^<^v<v^^<<^v<v<v^<^><^v<v>v>>^>v>>vv^<>vv>>v>>v><<<v><<<vv>^<<><^>^v^v^v^>^<^v>><<>v<<^<>v><v<<<<<v<<<<^^v>v<^^^<v^v<<v<^vv<^<<>>^v<<<v>^><>^^<>>v<v^v>^^<<<v^v^v>v^<>vvv<>><<v>v<^<^<v^v^>v<vv<^>>v^>^>vv<^v<v<^<^v^>v>v^
+<>^>vv>^>^vv>v<^<<<v<vvv<v^>>^^<>>><^<v>^v>v><^^^^<^vv<<v^v>v>^vvv<<>><>v>v>v^<><>>v^^>>^v>^^<v^><<><vvv^v>v^<^v^><><<>><^>v<v><<><<v^<>^>^^>v<>>v>vv<^<^v^^<v>^v<<<^>><><v>>^<>^v^>><><<>v>v>>^^v<<^<<^^>^^><>^><v^^>>><v^^<^v^<<>>>^^><^v>><^<><><>^^>>v<><>>>^vv^>^v>vv>^>v^^^<<<>^vvvv>v<^v^^v<>^^<>>v>v<>^>>^^<^>>v<v<>^>><^^>v^v<^^>^^v>^vv>>>vv<vv>^>v^^v>>>>^^>^vv>^>^>><>>>^v>v>><vv>vv>vv<v<v>>^^^<>v^<<v^v>^^vv>^v>>><<<<v^^><v>^vv^^<>^v^<^v^v<vv>>v>^v^vv^vv<^<vv^<>v><<<vv><<<^^^v<^>^^><>vvv>v^>^^>^vv>vv>>^<^v>vv^<v<^><>v^^v>>v^<^vv^v^^<v<><vvvvv<<>vvvv^<vvv<><<^>vvv>v>v><<>>^>v>^<<^vv^<v^v<v^^v<^^^><>vvv<><v<^^>>>^<<>^<<^^>^v><v<<<>^<v^<<<v<^>>^^<<^v>>><^>v>>>^v^>v^>^<^v>^^<^^<^<<v^><vv>^^v<>v^^<^<v><>^^<>v<v><vv<^<<v^^><^v><>^<>^<>v^<<^v>^>vv>>^^v^^><>><<v^><^<v>><>^^vvvvvv^^<^vv<<v<<>^^>^v><v><>^v><^<<^^vv^>v^<^<^^^vv><>^vv<^^v^<><v^v>^v^v>^^^v^<<><vvv<<>>^vv<>^<><^>v>^<v^>^><>^>v^^<<<<><><<>^<<<>><^^<v<<^<<v<<v<^>v<<<^^>>v^v^v^<^><vv^>v^<v^<^^>v^>v>^^^^vv^^<v<><^<<<<v<v<v<^v^v>vv<>^^^^<
+^<<^<<><<<^<>^<<><^<^v><v>^<<v^<^vv<>^><^^<<<^<<vv>^v^><^>>v^vv>v^v^v<^vv<^<v^^<<<^^^v><<v^<>^><^<><><>v>v><<vv>>>vv>v<>v>^<<v<^^vvvv^^v>vv^><vv^<><<<^v^^vv<v<<>v^v<><^^v^^^<<v<v<^<<^<<>>^v<vv>^^vv<vvv>^^v<^^v<v<><^><^v^>^<^^^v>^<v>v<^v><>>>>>^<<><<v^>><>><<^^<v<<>^^v<^<<<><>>v<>^<<^^vv><^vvv>^v>^<>><^><>>^^^^^v<><<v><<^>^<^>v>v>^^>v^v>v>^>^<<<<<v^>^<<v^v>><v>v<^>vvv<^<>>^<v^^v^vv<^vvv>v<>v^<vv<^>>><^^^^>>^><vvv^v<v>>^vv<<^><>>^^vvvv<><>>^><<<v^>v><>>^vv<>v>^>^v>^<>^<<<v>v<v>>^v<>v<<>><^>^^^<>^^v><>^<v^<>>>v^<^>vv<>^<>^v<v<><v<v>v<<<^>^<<>^<>^^>^^>^^><<<<v<^^^^<>><^<>><<^>v>^^v<v<<^v<v^>>^^v<^^>^vv<<>v^<^<><>>^<>v^<^v^<<<>><v<^^^<<^^<v<<v^>v>v^>>v^>v^v^<v<v>>v^^^v^<><vv<<<v<<>^v<<>>^v<<<>><<<<<v^>v>v><><<v^^^^v^<>vv^<vv>^>><v>^<<v<>>v>><>>v^^^>vv^>>><^>^>^>^<<v^^^<><^>^<<v<^^<^^^^<>v^^v><^<^><>>^<vv>^^<><^vv^v^<<^^v<vv^<^v^vv<>>>^vv<^v<v><<^^vv><v<^<>^^<><<>>v^<<>^^>vv>>^>^>>^vv<^><vvv^<vv>v<v^><<><>v>v>vv>^>v<>v^^>^<<>v<v>v>vv>vv^^v<<^v>><v^<<>v^><<<^^>^>><v>>>^<>^<<>><v>^^^^v>^^^^vvv
+^>^><v>v^^v^^<vv<<<><^^<<>v>v^^^<v>><<>v><<<>^^^^<v>^^^v<<>v<v^>^v<v<^vvv<>v^v>>>v<>v<>><^v^<^v<^<<vv><v>>>>v<><>><^vvv^v^><>>>vv<>v><v>^<<>v<<^>v>v<>>>v<^>v<^><<>>>><>><><v<<>vv<v<^vv^vv>v>^v<^^v<v><<^^<<><v^><^<<>v>>>^^<<<<<v>v<>v>v>v<^<>^v<>>v>^<<^<vv<<^v>><^>>>vv><>v<^<<<vvv^v<><<vv^^vv^>^<>^^^<^<>>v<^>>vvv<<>>><^><>^vv<v<<<<>^>v<v>^<<v<<>vvv><>^>>^<<>v>^<<><<^^^<v^vv>><>><vv>>^^<^>>v<<<<<vv^<^<^^<<<^v<^^^v<>>v^>v^vv^v^v<>v>vv<v<^^v<<<v>><>vvv^v>v^v^>><><<<>^>>^<v><>vv<<<v><<v<vvv><^vvv^<v>v^v^^><<^<v>v^vvv>vv^^v^<><>>^^v<>>>><^<<<>>>v>><>>^v^<<^v<v>>^v>>>v><v<>>^^v^^>^vvv<^^vv><v<<v<><><<>v^<><<>>>v<<^v>v^<<>v>^<^^>>v^vv><vv^vv>v^v>v>v>v>v>v><v^<v>^^<<><<vv<^<<><>^vv><<vv><^^^^>vvv>>><><v^vvv^<<>><<><^^v^><><><<v>><>v>^<^<>vvv^>>v^v>>^<<v^<^^v>^^>><>>^v^v>v^^v^^>^<^<<^^v^^^<<^>^^><>vv^^><<v^<>>^^^v^vv<^^^>v^^v^<>>^<v<<^>><^>>>^>>>>^v>>^vv<>v^><>^^^><^<>^<^v<vvv<<<<><v^^^><v><v^<><^^>>>^<^v^<^^>^v<>>v^vv^>>>v><>v<><^<<<>>v>v<>>v^^><<vv><v>^>><^>v><^>v^<<v><v<<^vv>^^>>>v^v^<>v^<v^^^
+^^^v>>^^>>><v>v^<^>v^^<v^v^v>vv<v<<>v<<<>v^v<<^^vv<v>vv<<^^^>v>vv><^>v^<>v><<<v<vvv<v<>>v<^^<<^>^^^^><^^^<<>>v>v<>>>^>>>>vvv^<<>v<>>>>^vv><>>^v<v^<>><^<^v>v^^<vvvv<>vv<^>^>^<<<>v^^>><>v<v<<v>>>v>v>>>>^<>>^^>v>v>v<^>v^v><v>>^^><vv>>^v>^^<^<<>>^v^<<<^>>vv^>^<<>>>v><^<>^^>v^v>v><^<^v<<v><>>>^>><^>v<^<v^<><^><<<<^vv^>v>>^^^>>>^>v<^vv^>v>^<<<v<v<<v<>vv>>^<^<>v>><<<^<v<^^<<v<<^>><<>v<vv><vv^v<<<v^v^>v<><>v<^^<>v<v<><>>v<>v<v<>^v<v<v<^><<^^v>v>>^vv>^^vv^><^v^^>^^<><>^>^>^^<v^^<<v<^>v><v>^<vv>^>v>><<^<^><>^^^<v^v^>v>^^>^^^vvv<<v^vvvv^v^^^v<>>v>>v<^<>>>>>v<>^><^v<^><<<>v>v<vv><<><>v<^v^><>^><>^^v^^^><^^vv^<^^^^^vv<^^^v^>><<^^><^vv>^<^<^<vvv^>vvv<>^>>vv><^><>v^^<>>>^>>>>^v^>v><>^vv><><<<^v<>v<^<v^v>v<><>v^vv^>>^^^^>v>v<>^^<v^^>>>v<^>v>^^<<v><vv<v>>>^<^v^><^>^<<^v<v>^v>^v^^v<^>><<vv<>^<<<<>>v<<^>>^vv>v^^<>v<<v>^<<><<^<>vv^v^vv>^^<>^<>v<>>v^>>^>^><<<^<<>>v><^><<>^^><v^^><^>>^v<^><<<><<<<^v><>>vv<>^^^>>>^<v<^vv^^>v<<vv><^<v^><^v^^^^^<^<^<^><>^>^<v^v>v<><vvv>v<>v<^^<<<<^>>>>vv^><^>>>v>^>^<v^<<<^<>^v
+v^>>^^v<^^vv>^>^>v<v>v^<>>v<^<<><^>>>vv<<v<<^^><<>^>>><<<vvv^v^<^>v<vv>v>^<>>v<<v^<<^vvv^^^^<<^v>^<>^vv><<<<><<>>>^v^>^<v<^<^<>>><^^<<vv<<<v<><v^>>vv><^v<>vvvvvvvv><v^>>^^^^>vv>^><<vv><<^>^^v<<<>>><<^^v<^<^^^v>vv^v>^v^^<^^<>v>^^^<>><^v<<<>vv^<v>^^^v<>^v<>>^^<>>v<<<vv><<<vv^^<vv<<^vv<<>v^^v>>><^<<>>^>>^v>v>^^<v<v^>v><v<vvvv<<<^<^v^>vv^^>v>>v^>^>v<<>>>^v>v^v^v<<v^v<<>v^vv>><><>><v<^vv>>^vvv^>^vv^<v<>^<^^>^v<v^v^>v><^<^>vv<v^<^^^<>^v>v><vv>v^vv>>^<>>>^>>^>^^^^><<v>v^^<>v>>^^^^>>vv>>v^<^v>^<<>><<^v<v<^v><>>^^><<>^><>^v<>>v>^<^<v>>^vvv><>^^><>vv>v<^v<vv^<>^>^^v>v<>^>vv<<v^^><><^<<^>v^v^^>><<^<<><^<v^>>><<<><v<<><<^v<^>v>>v>>><^^<<><^>v>^vv^^vvvv>^v^><>v^^>>v^<><><vvv>v>>^^^^>^<v^^<^v>^><^<<<v>v<><^v<>^<^v^>^>>v<vv<><^^>>>>>>>^v<v^v>><<<v<<>><v^v<<v<>>^^><v>vv>^><>^><<<vv^<<^>>v^v^vvv><v^^><<vv<^<><v^>><<v<^v<^>>><^<^^>^v^^^>vv^>^^^v^v<v<vv>^vvvv^v^<>^<^<<>v><v^v>^^>>><^>vv^<^<<^<^^<<^><v^><v<<<<^^<v><vvv>v>^^><v<v^<<^><v>><>^<vvv^>v>vvv^<><<^^<>^<<>^vv<>v^v>><>^v>><v<^v><><v<v<^<^^<^vv^^>^>
+v^vvv^^>^><<v^>^<<v^>v>v<>>>>>>v^<^<v^v^>>^>^><>><<^v^v>>>^^<vv^<<^>>^v^v<v^>>vvv><vv^^^<vv><vv><<v><>vv^<>^<v<^^>>v>^<v<^<^v<>v<v><>v^^<v<<^<<vv>vvvv^>vv^<>^<vv>^<^v<>>^v><v^<<v<<>^^>v^^v><^<vvv^>vvv^>>^>v^^<<v<<>^vv<^^><v<<<>>^^>>^<^v^^^v<v>v^v>>>v<^v>^v<vv<v<<<<^<<^^<<><<v^<v<<<>><^>^>><>><v><v<^>>v^<<v<>v<v>>>v<^^<^>^<v>v^<<v<><>v<^<v><^>v^^<<^^^<^v^>^<v><>v>>^<><<v>v^<^^>v^^<v^<^^<v^<vv^>>>vv>v<^<^<>v^v<<v<<vv^<>>^^>vv><v<>><v^v^^v<v<<>>>v<>>v^<<<>v^^^<<^^^v<>v^v<^v<v>^>^<v<^v<^^>>v^v<<v^<v<vv>>^><vv>>v<<>^>v>><v^v>><^vv^>^v^^<vv<vv<^^<^<><<<^>><v<<v<<>^>^^^<<<<<v><^v^v<v^vv<<v<><^^^<vv>vv^<v<><v>v<vvv><^^v<<<<<<<v<^<<^^^v<<vv^v><<^^^>>>^>v>^vv<>vv>>^<<<>>>^^<^><vv<>v<vv>v^v<<<<^<>^v<>^^v^^^<>>v^<^>^vv^v<^^<v^v^<v>v<^>vvvvv>^<><v>vv<^<>><<v>^^>^>^^>><<^>><^v^^vvv^vv^>v>^v>v^v>v><>^<v<<>v<>^<<v<vv^v^vv<^>v^vvv>^v>v>^^^<>>v^v<^vv>v<<^<^<v><v>vv>v^v><><^>v^<^>v^vv^v>>^v^v<>^^>><>v<vv^>vv<v>><<>^>^^v<v>^>v>^><v^^^v<^<^v<><>v><^v>><^^>>^><><v^v>v><><v^<><^<<>v^<<vv>>><^<>vv<v<<<^v<<v<v
+<v^v>vv><v<<^v^>>>>v^^^^^^>v<v^>>>><<<v<^vv<^<v^^><^vv>^<><>>>>v^<vv^<>v<^^>>><>^^vv>v^v<>>v>vv>v<v>>>>v>^v^^<<>>><>v^<>><>^v<><>^v^^v>><><><<<>>^><>^^v>^v<v^^>^<v^>^^v^<v><vv>vvv<<vvvv^>v<>>>^>>><^><>vv^>>>^^>v^<<v^v^><><vv^^<v<<>><vv>v^^<vv>><<>^^>v>>v^>^v^^v^v<<>vv^>>^^><<v^^<v^vv^v>>^<<v>^^<v>>v><vv><<>^<v^^>>vv>>v<<^v><v^^>vv^>>^<^v^^>v^<vvvv>>>>>^<^><v^v<v><><v^^>>vv<^>v>>>v>v^v<<<vvv<>v>><^vv>v<^<^><<v<<vv^<^><<>^^^^v>>vv<^><^>vv>>>vv^^<><v>^^^<>^v>><^>>v<^v>>^v^><v<><>v<v>^>>>><v>vv>v>^^^^^>^><>^v>><v<v^>>>v^>><><vvv>v<<<>^^vv^v^<v><<><v>>><<<>^<v^<>>v^^<<^v>^<<>^<v^v<>>^>>^>^>v>vv^v>^<><^^<<<^<^^^<>v^v<v<^^>>^>^v^<v^^^v<>vv>>^^v>><<<^v><>>vvvv<<vvvv<^^>^^v^^^v^<>^v>v><>v><<<^^^><^^v><vvvv>vvv<<v>^>^<^<v><v^<>>vv^<v<><><><<^<<^><><vv<^>v^>^v^<>>^<^>^>>>>vv<><>^>v>>v>vv><<^vv<>><v^v<>^v>v>>v^^v>vv<^vv^>>v<<v<<>v><><>v^^><^>>><>v>>v>v^^<v<vv<>><^><<vv<<v^^^^^^<v^><<^vv<^<<<>v><<<>v>^v><<v>^<^>^^^>v>vv><<>>^<>>^^^^^^^<>v>^<vvvvv^v>^^v^v<^>vv<<<^>>><<>>v<^^v^<>^<vv<<v>>>^vv^v^^>v<>
+vv><v^>>v>>^<<>><<>^^<<^>^><v>>>><<>v<v^>>><<v^<>>v>><<v^>vv^>^><<><>^<<^^<<<<v<>v<>><>^>^^<v>^v^^>v^<vv^^v<^<^<<><vv<^>v<>>vv^><>><v<><vv>v<^vvvv^<v><v<>>v<<>v<<^^<<vvvv^>^>>>v>v<^vvv^>^<<<vv<<>^<^v<^^^>>>>^^^<^^<<v<^<>>^<v<>^><><v^v<v<>v<>^v^v<^^^^^<^v<>^v<^^>v<>>v<<<>v<>v<>v<^^v>><>>v>^^v>v^>v^^<><<v<<<vvv><v^><>^^^>><^<<<<v<v^<v<v^v><>v<v<^v><<^>>vv<<>^^^vvv<<^>vvv<^v>>><>^v<^><<^<<v>v<v^><^>><v<>^<^><vv<^^^<v>><<vv<<<v<v<>v^<vv><<>vvv^v^>v^>v<v><^<v<<<<v^v^vv^>>^>v<v^^vv^<>vv>v^>^^v<><><<^v^>>vv<^^^^<v><<<v>vv<<>^^^<^v<^<v^^^v<<<><^>^v<v^<>v<v<vv<v>^<^>>><^>^>v<vv>vv>^vv<<vv>>^vvvv<>v^^v^v<>vvv<>v<<v^>v^<v><<<v^^^>>v<>vv^>>><<v^^<^><^>>>^^^><>v<^v^^vv>v><^<>>^>v><v^<<>v<v^>v^<v><^v<><<^^<^<<v>v<^^>^v<^<<>><v>vvv>v^<<<^>^>^^vv^vv^^<<v<<v<>^v^<>^<<v^^^>vv>^^^>vv><^<<>>v<^^v<^>^>>^>v<<<>vv^^<>^^^^^>vv^<<<>v^v^v<>^>>v<>>^<><<v<><v<v>v^<>><<^<<>>v><^>v^^<>v^^<>^<><vv<v<^^><^>>v><^><<vv>><<<^^>v^<<v>v^<v>v>^^<<vv^>><<vv^v^v^^>>>v^^>><<^v>vv<<<<vv^v<<^>v<>^>>><>>^vv><^^^<<v><^v<>v><<^^^>
+><^>><^vv<^v<^>^<<>v^>vv<vv<>^^v^>v<^><<><vv^<vvvvv<<^v><^^>v^>v<^vvv^>^<v<<<^><<^v<<>>><^^^vvv<<^vv^v<<>v<>>^^>^>>v<^^><>^vv>v^<^v<v>^^^^<vv<<>^<^^^>>^<v>^v>^<v<>>>>^>^<v^^>^^^>^v><^><v^v<vvvvv<>>^<<v<<<>^>>v^v^<^<>^<>^^<<>>>v^<^<<>v<><><^><^><v><v>v>v^^<^^v<v<>>^>v><^>^<^>^^<^^>>vv>vv>v>>^v^v>^<<v^^><^<>v>>v^^v><^v<<<^^v>><<v^>^v>v>^^<<^<><>>>vvv<^><<^vv<>v<><^^^^<<^<<^<^^>v^><<vvv^>vvv>v><>^v<<v>vv<v^<vvvvv>^<v^><^v^>v^><^<<>><^^^^^<<<>^<<^><^<v^^^^vv^v<<v>v^<v<v^>v<^^><^v<^^>v<<v>^v>^vv^<^vv^^^v>>>>>^>^^>^><^>vv>>vv^<<<<>^v^>^^>^>>^>^v><v>v<<v^><<>v<>>><v><v><v<v^^^^v<vv>^<><vv>^<v<^^v^^<vv<>>>^<v<v>v>^v<^^><^>vv>^vv^v<^<vv><><v<<<<<<^^vv>>><<^v><v><^vv<>v^^^<><<^^>vv<^^v>v<vv<^v><v^v^^v^><^^^<^<<^vvv<>vv^vvv^^>v^v^^v<<v>v<<^<>v^>v<<v^<>vv^<>>^v^^>><>vv<>^^<^<v^<>>^^<<><<v^<<v^v>^><>v<^^^><^v<^v>^v<>>>^^v<v><<<<v>^<^>^<>><<>>><>^v>v>v>><^<<v<v><v>^<<<vv>^<v^<>v^v>v^<<>v<vvv>^^^v<^>^<>^><^<<vvvv<<><><^>>><^<^>v><>>v><>v>v^v<<^<>>^<v<v><^^^^^<v^v^^v>>>vv<v^^<v<<vv^v>^v<><<>>v<^^>><^<
+v>><<v^^>>>vv<>><>^vv^<<<><<<v><vv<v^^^<<<^>>^^><v<<>^<^>v<vv><v><v>v^^<vvv>vv>>>v>^<<v^v<v>v>vvv^>^vv^<<<>^^>v^>^<v<<v<v><><v^^vv<^vv<<v^<>>^^<>v><<v<>>>>^<v^v>>^v^^>>><v^v^><^v^>^^v^v>^^>^<^v^<^v^<><v>>v^^^><v^<<^^><><<>vv^^^v^^<><>vv<v^<v<>><>>^^><v^<^v^<^>>v^v<>v^<v>v>vv<^><vvv>><^><v^<^v<>><><>>v^><<<<^v^>^>v><v^><v>^><<v^^v>><v><^>>v>v^^<>>v<>^<>^<<v<>><^v<>v^>><^v><><v>^^^<v<<v><v>v<<vv^<v>^<<v>v<>>vv><>><<>><>v^v>^><v^>>>vv>v^>><vvv<^^<^>^vv<>^<<v<<^>vv>^>v^v<^vvv^<<v>><vv^v<^v<v>v><<^>>^^vvv<<^>>^<<<<v<v>>v^><<<^^<>^<<>v^>vv^>v<^^<^vvv^vv<v><^^>v<<><^^<>>^<^^<vv^v^vvvvv^v<<<<>>vv>vv>>v<^^<<^<<<<v<<vvv^^<v<v<<^^><<><><>^v^^>v^<<><^vv>>^>v<><>v<<^v>v<v<<^<<^^vv<>v>^<<><^<^<^^<v<>v^>v^><vvv>>><<v<>><>v>^<<vv>>^>>>v<<>^><<v<>>^><>><>^^>^^v>vvvv^>^<><<v^><^vvv^>^vvv<<>>v^<>>^^>vvv^<^v>v^<<><v>^>>>>><v<v><>^<^^vv><<v<><vv>vvvvvvv^>>>>><v>^<>v>^>^^>v^^<<<vv<<>^>v<^v^>>v^^^^^^>v^vv>v>>v<><^vv^>vvv<^v>v<>^><^v<^v^<<^<vvv^^vvv>v>^<v^<>v<<>^v^>vv^>v<v^<<vvv<<>^>v>^^>>^vvv^v<<<^v>><^<>^<^
+vv><^^^v>v>>>>><>>^<vv^v^^>^v^<>^<<<<>^v>vv<>><^v<<>v<>>>^^v<^v^<<>>^<>vv<<>^^v^^><<<v>>vv>^><>^<^><><><^v>>>vv<^>^<^>vvv><<^v^^^^<vvvv>>^^^>vv<^vv>>^<^v^^v^>^<v^>^<>vv<v^>>^>^<<>^>^<vv<<>^>v><vvv><<^><><<<<^v><^<v<^vv><v^>v<v<^v<<<>v<<^><^>^v^>v>vv<<v<<<>^v>^^v<v<^>>>><>v>^^<^v>vv^v<>v>^vvvv^v><vvvvv><^<^^^<v^v<vvv^v<v>^<<><>^^>vv<vvv^>v<><^vv<<<^<>>>^>>v^<<^v^>v>v^^>>>^><^<^<>>vv^<^<<v><>>vvv<<><<>v^<<<>>^vvv^>>>vv^^v>v<v>><<v>vv^v>^v^v^<>><^<<><^v^<>>^^><v^^^^vvv^^><<>^><v<^v<^v<<v^v>^<>^>v^><<v^v>^^>>^^>>^^^>^^v><>v^^v>^>><>>^^^v^v^<vvv<v>^^^>v<>^^>>>^<<><v<^^>>v<^vv><^^vv^<v>^v<v<<<<^<>^>^^>v><<v<^^<><>vv^v^<>>v><><^v>v^>^>v>^<v^<v<>v<>^vvv<v>^><><^>v^<>^v>>v>^<vv>>>^v^^^>>^vv^<>^>^^v^v>>><<>^v<^>v^<<<>^vvv<<v<<<<>^^>v^^^v<^^v^vv<v>^vv<v^><><^>>>vv<<>^<<^v>v>><>vv>^v^<>v>^vv>^v<^>>>>>><^>^v>>^>^^v^^^vvv>^<>><>^vvv<<<>^>v<<>vvv<^<<v^v^>v>v>>^^<><>v>>^><>>^>v>^>>v<^<vvv^>vv<>^><vv^^>v<vv<>v<>v><v^^v^^<<^><^v<<v^v>^>>^^v^^^vv>><v^^<^<>>>^^^^^v<^^^<^^vvvvvvv^v<^^<^^v^>>v>>>><v^^v<v<>^
+<>>>^v<>><<<^><v^v<<>>>^<><<^^<>v^v^>^<<<vv>^<^><<<><><>>>^v>>v<<v^>^^>>>><v>>v<v<<^^v>v<<vv^<<^>^<<^v><v<vv^v>v<v^^^^<^^^v>^v<^v<^<>v^^v^v<><<v>v<<v<>^>>v><><^^>><>^>^^^><^<<>>>v^v^^<v<><v<<<<vv<><<<vv^v<<<<v<<<>v<^^vv<<v^>^>v<^><><vv^>^^v>v>v^^^^v^v<<^v<v^>><>>^^v<><>>v>v>^^^^^>v^v^^>^v>vv^<>>>^^^^v<^vv<v<<^v^<vvv<^><<><<<<<^^v^^<v<<>v>^>vv<^>v<<^vvv<^<^>^>^^><^<><vv^<<>v>>>>^^<v<^v<vv^vv>v><>v<^v^<v<>>^<>>><>v<^<<^>>v<^<<<>^^v<^<^v<><^v<^><<<v^^^^^v^v>vv<^v<^>>^^^v><v^v<^^>^<<^>^^<v^<<^v><v<<vv>^v>^<<>^<v^>v<v>v><<^<<>v^<^v^>>v^>^^><v>^<<>v<^v^^<v<^^<v>>^^v><>>^^v>v><vv^<^<<<>^<^^>v>vv<^vvv<^v<<>^v^<v<^>v<v<v<<<v^>>v<<v>^<<v<<v><>^^>^<v<>^>>><v<>>>^v^^^^^v><v^^^>^<^<^^<v><v<<>^<v^v>vv^^<v^v<v^^v>v<><<^v<>v^^<><vv^vv<<<><>^^v^>>>v><><^<>><v<<v^><<>^>v^^<^v<^>>v^>^>^^^v><>v^^<><<^^v^vv>vv^vv<<><>^^v^><><^<<>v^v^<vv<^v<<v>v^<v^<^<><<^<>v^<^><>^^^v<^>^<<><<>^><^vv<>^^>v<v>v>vvv^^>>^^^>^>^^>><vv<vv><<^^<><>vv>^v<<>>^v<v^<^vv>>v>^^^^<v<<^<^^vv>v><v<^vvv<v^v^<>>v^v><vv^vv^^<v><>>><v<v><^<>
+^^>v<<v^^<>><v>^v<>^<>><v><vv<<vvv^^^^>v<>>v^<<>v>vv>vv^<v^v>v<^<v>^>><^<><^><>><^^<^vvvv<^><^v<^>v<<^^>v<^>>v>><v^<^<>^<vv>v<^^v>v<>v>><^v>^^v^>><^v^<vv^<>><v<^^<v><><^^^<^v<>^v><>>^^<><vv^>v>v^>v<^<^^^>>v<^<v<<v<<^<vvv^vv^><<<v<<^vv^<v^^v<^v<vv<<<<v^><^<^vv^><<>^^>>>v>>v<<vvv^^^v<vv>^v<><<<v><^>^^<<<>>>v^v^<^<^<>^>^<<>v<^vv^v^<<v><v<>^^>^vv^vv^v^v<<v^<>>>>v^v>vv^^v>v^>v<<v^v>>>>v^^^>><^<<<^>v^^v<<<^^v>v^^^<><<>v<^v<<><v<<vv<<v<^<^v><<^v^^>>>><^^>^^<<v^<<<v^^>>>^^><<v><>^<^>^^^vv^<<>v^^v<^<vv^>^v<^<vv<^vv<^><^>>>><^^v<>>>><<>^v>^<^<v<v^v<^<^vv<v><^vv<><v>><<^>v^<vv>^>>>^>>v^^^v>vv^<>>^>>>^^vvv<vvvv>^v<^><^>>>^v^>>>^v^^^^^^<>v^vv<^^v^><<v>v^<<<>v><<v<vv^><<v^^v>^v>vv^^^><>vv>>vv<^>v><<>>>v<<>>>^<><<v><<v<<^<^>>v>>^>^v>><><>^<<<^v<<<v><^^v<>vv<<<<<><vv<^<>v<^^>^^v<v^v^>><>v>^v>^<<<v><^v^v<v<^<<>><^vv>^>><>vv<><>^^>><><v^<><vv<<<^v<<>vvvv^><v^><<^v<>><^<^>^^<<v>>>^>^>^v^^v<>^^^^><>>v<^><v<^v^<^^>v<>v<<^<v^^><<>>^^v<vv>>v<>><^>>>>^<<>^^>v^v^>^><v^<<<^<v>>vv^^>^><<v^>^^<>v<<>v><^v^v<^><^^v
diff --git a/2024/15-Warehouse_Woes/second.hs b/2024/15-Warehouse_Woes/second.hs
new file mode 100644
index 0000000..5f5f948
--- /dev/null
+++ b/2024/15-Warehouse_Woes/second.hs
@@ -0,0 +1,164 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import           Control.Monad        (void, when)
+import           Data.Functor
+import qualified Data.List            as L
+import qualified Data.Vector          as V
+import           Data.Void            (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+exampleExpectedOutput = 9021
+
+data Tile = Wall | Box | Lbox | Rbox | Floor | Robot deriving (Eq, Show)
+type Line = V.Vector Tile
+type Warehouse = V.Vector Line
+data Op = N | S | E | W deriving (Eq, Show)
+data Input = Input Warehouse [Op] deriving Show
+
+type Parser = Parsec Void String
+
+parseTile :: Parser Tile
+parseTile = char '#' $> Wall
+        <|> char 'O' $> Box
+        <|> char '.' $> Floor
+        <|> char '@' $> Robot
+
+parseLine :: Parser Line
+parseLine = do
+  line <- some parseTile <* eol
+  return $ V.generate (length line) (line !!)
+
+parseOp :: Parser Op
+parseOp = char '^' $> N
+      <|> char 'v' $> S
+      <|> char '>' $> E
+      <|> char '<' $> W
+
+parseInput' :: Parser Input
+parseInput' = do
+  line <- some parseLine <* eol
+  ops <- some (parseOp <* optional eol) <* eof
+  return $ Input (V.generate (length line) (line !!)) ops
+
+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'
+
+type Coord = (Int, Int)
+
+next :: Coord -> Op -> Coord
+next (x, y) N = (x, y-1)
+next (x, y) S = (x, y+1)
+next (x, y) E = (x+1, y)
+next (x, y) W = (x-1, y)
+
+showWarehouse :: Warehouse -> String
+showWarehouse w = V.foldl' showOne [] w
+showOne acc line = acc ++ (V.foldl' showTile [] line) ++ "\n"
+showTile acc Wall  = acc ++ "#"
+showTile acc Lbox  = acc ++ "["
+showTile acc Rbox  = acc ++ "]"
+showTile acc Floor = acc ++ "."
+showTile acc Robot = acc ++ "@"
+showTile acc Box   = acc ++ "O"
+
+compute :: Input -> Int
+compute (Input warehouse ops) = V.ifoldl' scoreBoxes 0 warehouse''
+  where
+    scoreBoxes :: Int -> Int -> Line -> Int
+    scoreBoxes acc y line = V.ifoldl' (scoreBox y) acc line
+    scoreBox :: Int -> Int -> Int -> Tile -> Int
+    scoreBox y acc x Lbox = acc + 100 * y + x
+    scoreBox _ acc _ _    = acc
+    warehouse'' = fst $ L.foldl' step (warehouse', start) ops
+    step :: (Warehouse, Coord) -> Op -> (Warehouse, Coord)
+    step a@(w, r@(x, y)) op | t == Wall = a
+                            | t == Lbox = case push w r' op of
+                                Just w' -> (w', r')
+                                Nothing -> a
+                            | (op == N || op == S) && t == Rbox = case push w (x'-1, y') op of -- we want to always push boxes from their left side to reduce push cases
+                                Just w' ->(w', r')
+                                Nothing -> a
+                            | t == Rbox = case push w (x', y') op of
+                                Just w' -> (w', r')
+                                Nothing -> a
+                            | otherwise = (w, (x', y'))
+      where
+        r'@(x', y') = next r op
+        t = w V.! y' V.! x'
+    push :: Warehouse -> Coord -> Op -> Maybe Warehouse
+    push w r@(x, y) op | t == Wall = Nothing
+                       | (op == N || op == S) && tr == Wall = Nothing
+                       | (op == N || op == S) && t == Lbox = case push w (x, y') op of -- pushing a boxes that matches ours
+                           Just w' -> let l1 = w' V.! y
+                                          l1' = l1 V.// [(x, Floor), (x+1, Floor)]
+                                          l2 = w' V.! y'
+                                          l2' = l2 V.// [(x, Lbox), (x+1, Rbox)]
+                                      in Just (w' V.// [(y, l1'), (y', l2')])
+                           Nothing -> Nothing
+                       | (op == N || op == S) && t == Rbox = case push w (x-1, y') op of
+                           Just w' -> if tr == Lbox then case push w' (x+1, y') op of -- are we pushing two boxes?
+                                                           Just w'' -> let l1 = w'' V.! y
+                                                                           l1' = l1 V.// [(x, Floor), (x+1, Floor)]
+                                                                           l2 = w'' V.! y'
+                                                                           l2' = l2 V.// [(x, Lbox), (x+1, Rbox)]
+                                                                       in Just (w'' V.// [(y, l1'), (y', l2')])
+                                                           Nothing -> Nothing
+                                                    else let l1 = w' V.! y -- or just one on our left
+                                                             l1' = l1 V.// [(x, Floor), (x+1, Floor)]
+                                                             l2 = w' V.! y'
+                                                             l2' = l2 V.// [(x, Lbox), (x+1, Rbox)]
+                                                         in Just (w' V.// [(y, l1'), (y', l2')])
+                           Nothing -> Nothing
+                       | (op == N || op == S) && tr == Lbox = case push w (x+1, y') op of -- or just one on our right
+                           Just w' -> let l1 = w' V.! y
+                                          l1' = l1 V.// [(x, Floor), (x+1, Floor)]
+                                          l2 = w' V.! y'
+                                          l2' = l2 V.// [(x, Lbox), (x+1, Rbox)]
+                                      in Just (w' V.// [(y, l1'), (y', l2')])
+                           Nothing -> Nothing
+                       | (op == N || op == S) = let l1 = w V.! y -- free space
+                                                    l1' = l1 V.// [(x, Floor), (x+1, Floor)]
+                                                    l2 = w V.! y'
+                                                    l2' = l2 V.// [(x, Lbox), (x+1, Rbox)]
+                                                in Just (w V.// [(y, l1'), (y', l2')])
+                       | t == Lbox || t == Rbox = case push w (x', y) op of -- East-West movements are simpler
+                           Just w' -> let l = w' V.! y
+                                          l' = l V.// [(x, Floor), (x', to)]
+                                      in Just (w' V.// [(y, l')])
+                           Nothing -> Nothing
+                       | otherwise = let l = w V.! y -- free space
+                                         l' = l V.// [(x, Floor), (x', to)]
+                                     in Just (w V.// [(y, l')])
+      where
+        (x', y') = next r op
+        t = w V.! y' V.! x'
+        tr = w V.! y' V.! (x'+1)
+        to = w V.! y V.! x
+    start = V.ifoldl' findRobot (0, 0) warehouse'
+    findRobot :: (Int, Int) -> Int -> Line -> (Int, Int)
+    findRobot (0, _) y line = (V.ifoldl' findRobotInLine 0 line, y)
+    findRobot a _ _         = a
+    findRobotInLine :: Int -> Int -> Tile -> Int
+    findRobotInLine 0 x Robot = x
+    findRobotInLine a _ _     = a
+    wideWidth = 2 * V.length (warehouse V.! 0)
+    warehouse' = V.map widen warehouse
+    widen line = V.ifoldl' widenOne (V.replicate wideWidth Floor) line
+    widenOne acc x Wall  = acc V.// [(2*x, Wall), (2*x+1, Wall)]
+    widenOne acc x Box   = acc V.// [(2*x, Lbox), (2*x+1, Rbox)]
+    widenOne acc x Robot = acc V.// [(2*x, Robot)]
+    widenOne acc _ _     = acc
+
+main :: IO ()
+main = do
+  example <- parseInput "example2"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input