diff options
author | Julien Dessaux | 2024-12-19 09:21:11 +0100 |
---|---|---|
committer | Julien Dessaux | 2024-12-19 09:21:11 +0100 |
commit | fe10994cdea4698fa93638b474ab07636fbf9262 (patch) | |
tree | d6846df94ffac829322ac9df6d085402d154b6bb | |
parent | 2024-14 in haskell (diff) | |
download | advent-of-code-fe10994cdea4698fa93638b474ab07636fbf9262.tar.gz advent-of-code-fe10994cdea4698fa93638b474ab07636fbf9262.tar.bz2 advent-of-code-fe10994cdea4698fa93638b474ab07636fbf9262.zip |
2024-15 in haskell
Diffstat (limited to '')
-rw-r--r-- | 2024/15-Warehouse_Woes/example | 10 | ||||
-rw-r--r-- | 2024/15-Warehouse_Woes/example2 | 21 | ||||
-rw-r--r-- | 2024/15-Warehouse_Woes/first.hs | 109 | ||||
-rw-r--r-- | 2024/15-Warehouse_Woes/input | 71 | ||||
-rw-r--r-- | 2024/15-Warehouse_Woes/second.hs | 164 |
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 |