commit 4e6f21582d9227d70475791ac29421d5bf3e4f44
from: Lukas Henkel <lh@entf.net>
date: Sun Dec 15 08:16:21 2024 UTC

Day 15

commit - 4a940e998f54d87e8893913334872f90b7a3e73c
commit + 4e6f21582d9227d70475791ac29421d5bf3e4f44
blob - /dev/null
blob + bc7883d10c82d7ff727f2f6fd7d3531fd1e1a157 (mode 644)
--- /dev/null
+++ input/15.txt
@@ -0,0 +1,71 @@
+##################################################
+##.#...OO#O...O.O..#.#O.............O...O.O.O.OO.#
+#O#O.....O...O..O#OO..O..OO....OO........#..#....#
+#..O.O.O...OOO..O..#.#..O.OOO....O.....OO#.O#.#.O#
+#.....#....O.O..#.#.O...OOO..#...O...O....OO.....#
+#O.O#.....O....O#.O..OO.O...#O.........O...O.O.OO#
+#..O..#OO.........O.#...O....O..OOOOO.O....O..O.##
+##O#....OOO......#O#.#.##O..O...O.O.OOO#.........#
+#O....O...O...O#OO.........O.........O.O.......O##
+#......OOO...OOO.O........OOOO.....O..O.O......O.#
+#.O....O#...#O.O.OOO...O...O..O...#OO.........O..#
+#....#O..O.O#.............O...O#.O.#.O....#......#
+##..O..O.OOO.O...................O#...O.....#...O#
+#....O.O........O.O.#O.OO...O....O.....OO....O...#
+#O...O.O....OOOO.O..#..O..O.#....OOOO#.....OOO.#.#
+#...#O.........O......OO..O.O..#...OO#.##.#...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.....O.##
+#O..O.........O.......O.O.O..O#.OO.O.O.OO......#.#
+#OO.O..OOO.....OO.#..#....OO..O.#.#.O..O.O.O.O.#.#
+#..O...O.....OO..#..O...#....O..OO.#O.O...O.O..OO#
+#.....#OO.O...O...#O..#..OO...O..#OO...........OO#
+#..#O...O..#.O...O#.....#O.OOOOOO...#.O.O.O.O..O.#
+#O......##.O..O........#@.....O..O#......O..OO...#
+#......OOO..O.......#.....OO##...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.#.#OO##
+#.O.....OO...OO#........OO....O...O....#........O#
+#.#.....OO..O.O.#O#.##.O..#O#................OO.##
+#.........O#OO.O.....#..#...O#O....O.O..O..O.....#
+#OO....OOO.....O.............#OO#...#....#.O.....#
+#.O#.....O#...#.O..O...O...#.OO..O...OOO#..#....O#
+#.#.O.O..O......#...OOO.......##.O..OOO#.O.O.....#
+#.........#.......#..O.OO.#.OO..O..O.....OOO..O..#
+#..#...O#O...............OO.O.O.O..O..OO.....#.#.#
+#O#.O.O.#.O..O#...O..O....O....OO#O.O.OOO.#..O...#
+#...#.##........OO.O.O..O.....O.O#OO..O.O.O.##O..#
+#O#...##.#...OO.OO.#O..O..#OO..O.O......O.O......#
+#.OO....#.O...O........OO..O.......O.O#..O.......#
+#O..O..O...O...O......OO..O..O.OOO.#...O....#O...#
+#.....#...#...OO.O...O.#..#..#OO..........O.O.#O.#
+#....O......O#.O.O...#...O..O.O.....O.O..O.....OO#
+#..O...#.O..O.O...O......#.#OOO..................#
+#.O.....OO.O...OO.......O.#...#...O....O.....O...#
+#O##O.#..OOO...#......O..O..#OO.........O..O...OO#
+#..O.O...O....O..O....#O.......O......O..OOOO##.O#
+#..O.#O..O.OOO..#O.......O.#.#OO.O.O.O.O..O.#..#.#
+#.....O.OOO...#.O.O..O...O.OO...OOO..#.O.O.OO.OOO#
+##################################################
+
+<v><v><><vv>v<v<^>><><>v^v>v>v<>^v<<>>v>>v>v^><>><v^v><v>v^v>v<^vv>vv><>v^^v>>v>^>>^v<v<^<v^^^<<<<v>>vvv<v<vv^><<>>^>v^^v>v^v>>^vv<^>^v>>^^>>>>v<<>^v>^^><^v>^<<<^<<<v<<v^>>^v<>v>>v<v^^v>v><<^vvv<>>v>>v^^^<vv<>^><^>^<<>>^<>v>v<v<><^>^v>^<^<^^^v>^>v<v^vv^<vvv><v><v><<^<v<v>vv<>>v>>^^v>v<<^<^v<<<^>v<<<^><>v<>v>vvv^^^<v><v^<vv>v^^<v^vv<<^<^v^>v<vvv^^^^<>v>>^>>>>^<>><>v<^^<v<>v^<^v<^v^^^v<><<vv<><vv^>v<><vv^>vv>vv^>vv>v>v>>><v>vv^>v^^v>^vvv^>^v^^<<<^>^>>>^<>^>^v^v^<>v^>^<vv>v<>^^v>>v^<>^><vv^<<<>v>^>>^<<v>vvv>><^><^^<v^>v<^>^<><^><vv<v>v<^><>^^>v^<v<>>vv^><^>v^^<^^vv^>vv^^v>>v<^^v^v>><v<v^^v^v^vv>>^^vv^^v^vv^v<^^>>><><^^<<>v><>v<^^>^<^<v><^vv>v>>>v<<v<<^^>><^>>^^v^<v<>vvvv<vv>^^<>><>>>^^v<><>>^<<<v<<v^^>>>v^>^v><><>^vvv^>>v^^^v>^><v^v^><^^<>v>vvv>vvvv>>>v<^v^^^vv>>v><<v>^<>>^<v^<v>>>v>^v<<^v<^^<^<^vv^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<><<^^<>>>vvvv<<^>v>^>v>^<^v<^^v^<v^><>^^^<^>><<^^><<
+>^><<>vvv^<>>>^>vv<v^v<<^<><<><<>>^>^>v>vv<v<vvv<<<vv<v><^^><^>vv^v<v>vvv>^^^<>>v^<v<^v<>>^<vv^<v^^v<vv^<<^<>^v><v><>^^>>>^<^v><^^^><<vv^>^>v<<<<>>><>>^>v^^vvvv<>v^^v><v<>><>v<^^<>>vv^v<^<>>>^^^<^^>vvv<^<<v<><v>><^^<^vv<v>vv><>v<v><^^>vvv<><<>v<<^<<<<^v>>><<v^vvv>><v><v><^^^>vvvv><<>^<^>^^>>^^<<^^v^^<<^vvvv<v>vv><>>^v>^>v^<<>>><v><>><<>vv><v^><<v<>><>v><<<>v>v<>^^^v<^>^<^<^<>>>><>v>vv^<<<^v^<<^<>^<v>^^v^>>v^<<^^<><><<<^>>><><v>vv^>v^>><^>>^v>>vv^<v^v<v<v><<^vv<<vv>^vv<v^v>v>v>>v^<vv^<v<>^>>v><>>vvv><>>>>v^<<^^<<^vv>^v>v<v<^<^^><<v>^^>>^<^<vv>>><^vv^^^>v<^^<>v>^^^>^<<<><>vv>^^<^<^<<<vv^v><^>v^v^<>^><^v<<>^>>^v^<<v>v^><v^^<^<<v^^v>v<><v>vvv^<>^v>>^^^v><>>v<<vv^v<^<>^<>>v<><<v<^>^<^v^^^vv><^vv>>^<>>>v<vv^<v^<^>v>>^<v<><>>>>><>v><v^<v^<v^<>vv^v<v^<v^^<v^<>v^v^>vvv<>^v<><^>>v>^<><<^<>^<v^>><^^v<<<vv^v^<v^>^><^^v><><v>v^<<<><v^>v<>^^<<<><>v<^<<<><^^>^^v<<v>v>><<v^vv^>^>^vv^v>v<<v^<v^<<>^<v^><>v>>v><>^v^<^vv<v^<vvv>vv<^vv>v<<>v^^<^<<>^><^^<^v^<v<v>^v<v<<<>^^><<<v<v>v>v><>^<<v^>v<vvv>^v^vvv<<<
+vv^^><^>v<<vv<<vvvvvv>^>v^><^<v^<><^<v>^v>^<>^^^^><<>^^>>>^>^<>v^<^v^^v<v>vv><><<>>^>>>v<vvvvvv<^>>v<<><<>v^^v<v>^>^<v>^v>vvvv^vv<^><^<v^vvv>>>vv^v<>^>^>^>vvv^><v^<v^>^^^v>>v<^>><<^^v^<>v>><^v<v>v<v<<>^^vv^^v<<<<vv><>>^vv^<^vv<>>v^>vv<^<v>><<^>^>>>^v>vvvv^<v<^^<>vvv><^v<>^<<v<>>v<<^^><v<<v^>>><vv>>v^^<<>v>v^^^<<v<^>v^>^v<^<v^^>><<><^<<<><>^^<v<<><>^v^>>^<>>v>>v<<vv^vv>>>^>vv^v^<>v<<v<<^^<^^<<vv>>>^>v<v^^^v>^<^^<^<>vv>v<^v^><<vv^^^v>>>>^^^>^<v^>>>>^><>><<v^><v^^<<^><v^^<>>>>vv><v^^vv^v>^v^><>v^^<><><^<><<<<v>>v<^>^vv^^v^<^>>>>^v^^^<v^v<^vv>vvvv^^vv<^<>><vv^^<^<>^^<^v^^><<>>^v>><^>v^vvvv><<^v>v>>^v^v<<>v^<^^<v^v>^vv^v<^v<>^v<vv>^>vv>>v<v^><^v<<>^^<v><^>><vv><>v<>^>^>vv^v><vv<v>vv^<<>v>v^^><>vvv>v^<<>^v<<>v>v>>><v<^^^^<>^^v<^vv<v<vv>vv>^vvv>>^^<v>v><^vvv<>^v^<^vv^<vvv^v^v^^><<<>^vv>>>>v><v^<^^^<vvv<^^^^<><>v^v>>^^^^v^>^<v<^^^^>^^>^^><^<^><^<<vv^<vv>>vv<v^<v^^><>^>>><^^^<v<vv^<<^vv><><vv<>>>v^>>v<>v>>>^v^>^<<<^<>v^>^v>>^<<v^<><^<>>v^v<^>^><^>v>><^v^^^>v^>^^<^v^^v>vv>v<^^^<^><^vv^v>v<>v<^vv
+^^>v<><<^vvvv>^v>>><^^<vv>v>><<>v>vv>^>>^^>>^><<v^<<><vv<<>v><<><>vv<v><<vv<^<^><v><>^v^<>v>^^>v>^<<<^<>v<<>v<><>v<<v><^>v<<^v<<^v>>v<^<<<^<><^>>^<>^^>>^<v^>^vv<>>^v^<><>^v><<<<^^><^^>>^^^>^v><v<><<^>^<<^<^^<v^>^vv>^>^v<>>>><^v>v^^^>>><>^<>>^^<vv^v>^>>><v>v>><^^v<^><vvv><><>v^><>>>^v<>>vvv><>v><<v>>>v<>v><^><<^<v<>v<><<^><<^v>>^^>><^^v^><v>vv<<^><><v>^>><^><^<^>^v><v>^^v<^^<v^<>v<vv><^<>v^>^^<^v>^<^^>v><<^>^>v>^>^><>^<v>>^<v<^>v<^vvv><v^v<^v^>^v^^^>>>vv<^<>^>>>>v^>^>v^vv^^v<^^v^^>>>^^vv>v>^v<^^v<vv^^>>v^^^^>^^>^^<vv^>v^v<><v^vv^vv><^<^><<<<<<v><<>^vv><vv>><<<v<^^<^<v><^><>>v>>v<v<v>^^v<^^<>^^v<>>v<>>><^>^<><<v<><>^^v<<vv><^v^<<<>v^<^<<^vv^^^<<<>v<^^>^^v>>>>v>>^>^>^<^v^vv^^<>v>><<^v<>v>>><<v>vv^><v>>^^<><<>>>>><^^^<<^>vv^v>^<>>^^^v><v^<<>v>^>vv^<v<^<<^v^v<^<<<vv^<v<vv><^^^><<v<vv^v><<<v><vv<vv<>^^^^v^^vv>>vv^v><^vv<^^v^v<v^>v<<v^>v<>^>>>><^>^>>vv>^>v^v<<<<<v<v<^<>^>vv^<^^><^<^<<>><>^>>>^v><^<<>>^><><<>v<<^v^^<^>v><vv^^vv>^^>^v>>^>vv<<>>>>v<<^>>v<^<><^<>^<<^^v^^<<v><<<^v>v<^>^v<<^><^<^v^
+^>v><>^>v^>^vv^^v<<<<><^^<^><<^v<v>v<<>>>><>^^^v><>v<^v><<<<^<>v>v>^>^><vv<<^>^<><vv>^^>v<v>vvvv>^^^<>vv^>><v>^<^vv<<v<<^^<vv<^<^v^vv><v^^vv^<^>^>^^^^>><^>v^v^^v^<vv^>>><^^^v<^v>>v^<^^v>v>^v>^<vv<^v^v^vvv>>v^><v^><<<>>v^^><v>v><<<^v><>v^^vv^v>>v><>^^^v<v>^<vv>v>^>^v<>><>>v^<><><^vvvv^>^^<>vv<v<<>><<<>><<<<>^v>>v^^^v>vv<<v<vv^<v>><>vv<v<<<<><v^<>^v^v<^>><^<<>^>v>^>v>^>^>>>v^>v>v^v^^^v<^>>>v>><<<<v^v<^<v^v^vv>vv^vv>v^v^><<^<><<<^^>vv<<^<^<v<vv^v>vv^<^^>>>vv^><<<^<><>^>>v<^^v><<<>v^v<<<^<<v<<^v<^v^^^>^<^^<<vv>^<^>^vvv>^^><^><^v>v^>v<v><<<><>v^vv^v<<<<>v^<^^v>v>v^^>^v>^<<>v<^<><^<vv<^<>>^<>>^<v^^vv<<<v<<^>^><^^vv^<<<^vvv^^^>^v^^v^<><^^>^^<^<><>>><^v^>vv^>>><v^v^>v^<<>v<v^<vv>^<^^^<<>^<v^vv>>^^<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^<>^vvv<<<>^>><><^^^v^<^^>v^<v^<^^v^>^<^^<>v<<>>v>^>^<<>vv^^^<>^v>v^<^v<<v^><v>>^^<<vv<<>>v<<><v>>^v
+<^>^vvv>>^vv<><>v<v><^>>vv^v^v^<^<<<^<vv<>v>><<v<^>><vv<<v>vv<><>v^v>^><^>>^v<^<<<^v><><><<v^<<<^^<vvv<v>vv<^<v<^v<<><<^v^^v<^<><^<<><<^v<<<><<^v<<^<^<v>^>>v>>>^^>>^vv>>^>v<^v^>^<^<v<^<<<v^v^^><v^^><^<>^v^^><v<>v^><^<<vv^v>v<>v<>^<v^vvv^^v<^^>v^><>><^^>vv><>>v<>>vv^>v^^vvv<v<v>>^v<v>>v>v><vvv<>^>><^vv^<<^>^>^vv^vv<>v^<vv^^><>vv^<<^><^v>>^^^>v^v<><>><v>^^vv<><<^<^v^<>v^v>^<><<<>vv>^<^^>v<>>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^vv>v^^>^><<>^<^<>vv<<v<^^^>><^v^v<v^^<^v^<^^v<^v<><^^v^<^<^^>>^>vvv^<<<^v<<<<<^v^^<>^<>v<<v<^>>^>^>vv^v<vv<^v>vv^v^v<>>^>v^v<v^^v>^v^v^^v^^<<><<^>><>^<>v^<<<><<<^vv>v<vv^>v<vvv<<><<^<<vv^^^v<vvv<^<vvvv>v>^>^v<>>><><^<vv<<v<^<v>^v><<><<v>^<^<<vv<^>v>^>>vv^^>>v<>^vvv>>v><^<<v^v^^^>^>v<><>><>v><<<>v^^vv<^>v<>>^vv>v<^^>v>^>v<<^<^<><v^^<^><v<<<>^^vv^>><v<v<>>^>^^^v^<>^v>>>v^v<>^<<^>>><<v>^>vv<>v>v>^vv^vv^v<v<^^<>><>^v^>^>v><^^^>>^vv^>v>v>v<vvv^v^><^>v^^^>vv>^^>><^^^^<^v<v<><v>^>^
+>vv^^vv<^vv>^>^v>^^<^^^<>^^<<^<v><vv<>v><vv^v^<>>vv><<^^<<>^>v^<<v^v<>v^v>v>v<^^v<<vv<>^^<><v^<>^>^<^>><>v^^^>^vv>v<<><v<<<v>><^v<^v^^<>>v^<^vv^<^v^v^^v^^^>^v^^><^><^>^><v>^v>^<>v^v>v^^^^>>v<v<><^^v>><<v^<>>>>^v^v>vvv^v><v>vv<^^v>v<^<vv^<<v>>vv^>v<^^<<^<^v>v^v>>>v^v^v<v>v^v^>><v^>vvvv^>v><^^vvv<vv<<<><>^^<^<>><vv^vv<^>>^v<v^<>^^v<v>>>><v<>v><^v^^<<v^>><^<^v^^>vv<<<v><v^>v>v<vv><v<<v^<^>>v^^<<>v><<<v><>>>>vv<<^v<v^v^v<>>vvv^v^v<^>>v^>^<v><><>><>^<<>v^vv><<><>^^vv^v^^v^><v<<^^>>v^v>v^>>^<v>^<>v^vv^^v^v>v<>^v^<^<>v>v<^v^><vvv^><v<><<^v<>><^v^>>^v<<v^^<<<><v<vv^><><^>vv<<v>^>^<v<^v^>^vv^><v<^>>v<^v^vv<vvv<<^^<<<v><<^^v^^<^<>^v^><><<^^><><<<v^>><>v<>>v>><^^v<v>>vvv>vv>>>><>vv><v<<vv><vv<<^v>^^^>vvvvv>^^<<<v>^vv^^><^<^>^vv^><>>v<>v<^>v>>v^^><^v>>v<>vv^^v<v^v<v>^><>^^<>^^<^>^<>><<v<v>>><>v>vv^<^<<>>^>^vvv>v^><^<<<>><v^v<v^<<<>^>><v<^<v>v^<^>^><v>^><v^vv^>>v<^^^v<<<v<v<v>v<<^<vv^vv^v>>^<>>>v^^vv^<<^><^v<>><^<^<<<^<^v<>><^v^<^v^<<<vv<v^<^<^^v<>v<>vvvvvv>>><>><v>^^<>^>><v^vv^v^>vvv>^>v<v><v^>^vv
+<<vv><>v>>v>>vvv^>v><<<v>^>^<>^<<^v><^v^v<<v>^<>v>^>vvv<><^^>vvv^v^>><<><<>^<<<><v^^>vvvv>vv>^vv<^>v<>v<^v>v<^^>v<^vvv^^<<<vv<v<<v<v>vv>v><v>><v^v^<<>>>v>^^v^>v^^^>^><<v^vv^v<^v<><v<^<^><vvv>>vv>v^<vv^><><>v>><^v><>vv^^<vv<^v<>>v>^<<^>>>^>vv^<><v<^>v>vv<v><v^<<v<^><^>>><v<^<>>^<v^<<^>^>^v^<<v^v<^^v><>v<<^<v^vv<^>^^^^<>^vvv<<^>>><^><^<v^^^v<>^>^vvv<>^<<>>v<<^^<v^<vv>>^>><^v^<<^^vv><vv<<^v^>><v^^<<v<<vv<<^vv<<vv^v>>^^>v>>v^v^^<v>^><<>^^^>>^v^<v<^^^<v<>v^^v>^>^<<^>>v^v^^^><>>>v^>>^<^><<>^v><<v>^<^>v>><<>>>>v<v>^><^^>>^^>vv>^>^<^v>v^v<<><^v^<^vv>^<<v><<<<v>^v<vv^v>vv<<<><>>><^v^>^><^>>>v<>>^v>>^v^v^>>>v<<^><>v<v<^>>^>^<^><^<v<<^^v^^><vv^>^<><vvv<v<v^^^<v<^><vv^v>>v<<>^<>vv^<<><<<^<>^vv>v^>^v^v^<^<>^><^>>v^^<<<v>>^><<>><<v>><^<<<>^><>vv><^v><<>v^^^^^^>^vvv^^>v>v<^vv^^<<vv>>v^v^>^<<v<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<vv<^<^^<^v<<>^<^<<^v<><v>^>^<>>v>>v^v<<^^^^<v<>><>>v>><^><v^>>^^>^^<vv^^<<^^>^>^<vvv><<>>vv<<>>><^vvv>><
+<<^vv><v><>v><>v^<>>v^v<v<>v^^>vv><>v>>>^v^^>v<^>^^<><^<^<v^^<<>>>^^v><>^<vv^vvv^^vvvv><><^^vv>>^^<^<v<><^^^v>^v^>>^<v^>^^^><<v>><^^>vv<^<^vv^>^>^>^><^v^>^^><v>^<<vv<>v^<^^<vv<<v^^v<^>>^>vvvv<^^<><><vv<>v<^v><v^<<vv>>v<^v><v>^v^^v<^<>>^>v>^<v<<>>>^v>^><<<v<^<vv><v^v^v>^<<><^v<<>^>^vv<<^v><>vvv>vv<v^v>>^<<<v>>v>>>^<^<v>>^>^>^><^<>^>>v><^<v^^<v><>^^<^<^^<^v^^<><^<>>v<^>v<^<v><^v>^>v^>>v>v<<><><<>^<<>vv>v<<^v^^^><v^><><v^><^<<vvv>^<^^vv<><<vv><v>v>^v><v^<<<<>v>v>v<v<v>^>^><vv><<^>vv<>vv^^>>vvv^><><v<^>>^<>v><>vv>>><<>>^>^<<<v^<<^>>>^^^><>>v>>>>>v<>vv<><<^vv>^<^<vv<>>v^vv>>^<^v>v^v^<>>^>>^^<<><^<<>v<<>>>^<<<>v^^>><<vv<>v^v^>><v^^>>^<v^v<vv>>><<v<>vv^v^<v<^vv<<vv>v>^^v><><>v><<>^^<^^^>^v^^>vvv<><><>^><vv^<^v><><<>>v>>>^v^<^v<<<<v>v<><<<>>^<<>^^<<><><>v><<vv^>v^<v<v^vv<v>v>v^^v^v^^v>vv<v>^^>v<>v^<>v>^v^>^>^<v<^^<^v<vv^^>v^^^vv>>>^v>vv>v^^vv^^v^^v^>>^>><^v^>^v<^^>^>>^>^>>>>>vv<>v>^><^^^vvv><v^<^v^<v<>>^vvv<v<>v<<>v^v^<^v<<>>^^v<><^^<vvv>^v<v^^>^v^>><v><^<<>v^<v<>vv>>>><v<>v^v<^<><v^v^vvvv<^<>
+^>><>^v^vv<^v^v<^>>vv<<^^^^<><^>>><v<v>^v^^>^<>>vv>vv<><^>>v<<<><^<><^<>^<<><v^<v><v^<^>>>v<^^>^<>^>^<^^>><^>^vvvv^^v^v^>^<>vvvv<>^<v<^v>^^>^<<^><<v^<><vv<^v<v^>^>^<<v^v^v>vv^><<^<v<<v>v<<^>^<>>vv>v<>>>^>v^v>><>>>>v>>^<vv^>^>>vv<vv>v<<^><v>>vvv<<><^^<>^>v^<vv><vv><<^<>^<>vvv><vv^>^vv^vvv^^>^v>>^><vv>v<v^^<^vvv^<<><^>>v^<^<v<<^<vvv<>^><<^><>v<<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^^^<>^>><>>><v>v<^vv<^v^>>>^^^^v^<><vv>vv>^^v^<v>vv^^^<v>^v>v>^^v<v<v^vv<>><<^^<<^<v^v^^^^>vv^><vv<^>>^><v<vv>^^<^<^^>^^<<<v>>v<vv>v<>>>>v<v>^^^>>vv<^v<><v<<^<>^v>^>v>>^<<^>v<vv><<v<v^>>^v^>>><v>>vv<<<v>>^v<<><vvvv<vv<^<<vv>^<><^<^v<<>v>v^v><vv<^>^>>vvv^^>>v^<vv^<^^<<^>>^>><^>v<<^<>^vv<><^v<^>vv>vvvv^v>^<vv<>vvvv>>>>>v>v>^<>vv<<v>>^v^v<v>>>^vvvv<v><^>vv><>>v>^<^<<^^<>vv>v<^v<^<^><v^vv<>><>^vv<v^<^>^^<v^^>^vvv^>^v^v>v^v><<<<<vv<^^vv^^<>>>>vvv^<^>v^<^>>vv^>v<>^v^<v>vvv>><<>^<v<^>v<v^>^^<v>><vv><v^^v^v<<<<<<<<>>>>>v<^^^v<<^^v^<>v<<<>v>^<>>^^^>><
+><<>v<^<<^v>v^^>vvv^>vvv^>^v><^<v<^<^^<v^v<v>>^><>>vv^<>^>><>^v^><<><vvv<^^^vv<vv^<><><<v^<^v>^^v^<<^<>vvvvv<v>v^><^>v<<^<^^<^>^>v^vv<>vv<>><<>vvv<>vv>^^^v<><v<<<>vv<<>>v^^<^<v>^v>v<<vv^^vv<^<<<<>>><^>>vv<<>^v<<v>^<<v^vv><v>^<^<>v<^vvv>>v>vvv><vvv^<^v><>v<v^<v<v^^^><^>>><vv<^v>^v<^>v^v^v><^>^><<>v^<vv>vvvvv^<v<<vvv<^<>>v>^<<v^<<^^>><v>>vvv<<<>^^<^>^^^<<<v^><^>^>>v>v<^v<^>vvv>vvv^v^v>v>v<^^v<^v>^>><<^><<<><<>>^<<<<^<v^vv><<>vv>^v>>vv>^^>>^<>>^<<<<>v>^^^<^<^<<^^>^v^v^^vv^<>><^vv^>>v>^>>>>vv>^><<v<v^><^v<>^<>>v<v^v<^<v<^><<<v><^<<v>^>><^<><vv<^<^>v<^>v^^v^v<<^>^><vvv>>><<v<<><vv^vv<><^v^>>>vvvv<vv<^v^>v^^v<<<^^<<<v>>^<>^v<<>^^>^^v^<vv^<<>><^<^><>><^^<vv>v<<v>vv<><^^v><<<^v^^>vv<^<<^v^v^^>^><vv><>^vvvvv>>>>^v>><^<><<<>^>v^^^><><^v<^vv^^v<^>>>^><^^<>>v<v^^<<<<<>^v^^><^<<<>^<>^v<>>><>v><<<^vvv<^v^<<v^v^^<v<vvv^<^<^^<v<v^<v^vv^<^vv>v><v^vv<v^<^vv>v^><^>vv>vv<^<v<v^<^^>^<><><<^>^^>v^<^>^^v^v^^<<v^v^v>>v<>v>>^v>>^><v<^v<v><<<><<<v>^v><><^<^v<><<><<>v^<<>v<>vvvv<><^^^<<^^>^>>^>><v<>vv^<<^vv^>>^<
+<^vv><v^>v>^v><>^<<^>v<>v><^<<><<^v><<v>^>^^<<v^<^><>>v><v>^<><^<v<v^>v<^v>>^^>v><>^>^v^vv>>><<^vv>^<>^<^v^>vv><v>vvvv>^v>>>>v^v^v^v^>><^v^>v<^<v<<^<<vv<^^v>>^>>>^>^^^v<vv>v^<^^>^>^v^^v>v<^<vv^^^>^<^v^v>^vvv<>>vv^v<<v^>^v>>v>^<^^>>>v><<^<<^<^v<v<v>vv^^>>^<^^><<<^^^>^^<>>^<<v<v><^vv>>^v<vvv<>v><><^<v>v<><v<<^v^^>vvv<>^^^><<<<v>^^>>>vv<^v^^>^>^v>>><v^<v<^<<v>^><>^^<<^v^<^>>v<^v^^^>^><><vv<v<v<^^>^v^^<vv<><<^v^><<>>^^^>^^><<<v>v^>^<vv<><<>v><>>v^<^<><><>^^^^>>^v^<v<>^^^<^^>v^^v<vvv<>><v<>v>^<>^vv<^<^^>>vv<<>^^>vvvv><v^v>vv<v>><^v^>^^vv><>v><>v^^><v>^>^^>^<v^^vvv^v>v<^>^<^v<v<vv^>^><>^v<><vv>^<<v<<<>>v>v>v^<v<>^>v<>v^<<^v>^vvvv^v>^vvv<<v>vv>><^v>^<<v<^vv^>vv<v<>^^v<v<<v<^^v^vvv<<vv>v<<<^>vv>v^^v^^^<<><^<v<^^<v^^^>v<^^v<><>^>>><><>^^^v^<>><vv<v><<>v<>>^>^v>^>vv^<<^v^^^<<^vv>>>>^^^^^^<<<<<^vv^v<<<^v<<<<><^^><^<<>>v><<<v^^<>^>>><^^v<^v>>><>v<>>v<^>><^>vv<^><<v>v<<>^^^<<<v^>>>v<v>^<^>>^v<>>^^<^v>v^vv>>^vv>^>>v<<><>^><<>vv<^v><v^<vvvv<^^v<v><^>><^<^<^<<<v<v<>>^vv>^<<^<v^v>>>vv<v<^<v^>v^v>^^^<v<
+<^>v^^<v^<v^>^>vv<<^<^vv>v>^><^<<vv><^^vvv^>^><v<^v<<^>>v<vvv<v>^>^v>vv^^>^^><v<>>>vv<<^<^v^^^^>^^vv<<<>><^v<<>^^>v^<<v>>vv<v>vvv^v<v>>>vvv>vv^>^^^^^>^v^<<><v<^v><v<v^v>^><v>>v><<<>v^v<>>v>v>^>^<^v>v^v<v>^><>vv^^^>><v<v<<>><>^v^v^^<vv^<^<<vv<^^>>v>v<>^>^^v<v<vv>^>vvv>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^><v^<<^^^^<^<>v<<<^^>>v^<><v>>v^<>^>><><><<^>^<^>>^v^vv>^<^<>><v<>^<^^^^>^^>^^><v<>v>>><>^^<v^^^^vv<vv^^>^<>v><><^>^^<><><<^<vv><>><^^>>^<v<v<v^<^<<<^v>>v>v>^v^v^^^<^vv<<v<vv^<^<v>>^<v^v>v^>>v<^>^<<><<^<><v^^v><>^v>vv>>>vv><^<v^<^^^^>v^v<<v>>v<>v<<^<><v<<^^vv><><^>^<vv^<<>>>>vv>^>>^^>vv^>^<<v<<^v^><^<>^^^><>v<<>><<>v><^><^v<>^><>v><^<><^v^^vv>>v>^^<^>^^<<^^<<<>^>^>^<><<^>^vv<<^>^v^v<v<>>v^<<<<^>v><>^><v<v>^>v<>^v>>>v^<><<>>v<<<v<<><^>v<vv<v<^>v<^^v^><<>^<^^v^^>>><>v<<<v<^<vv><v<<^<>vv>v>v>v^<>>^<^^<^>vv^<^>^<>^>^vv<vv<>>^><^v^v^>>vvvvv<^<v<<^<^><v<><v>^^vvv<v<^^<>>v^^v<<vv<^^v^<^v><^<<><^><^>^>v
+<^vv^>^^v^<^v>vv<><<v<^>><v<><<<>>>vv^>^>vv<v<<^^>^^v>v^>^^<<v^v>^<v<<^^<v<><<v^v>^>v^v^vv>>vv<v^>v^><^<^>>>^<<vv><vv^^v^<<<^vvv><v>v>><vv^^>^<^v>v^^>>>><v^<v^<>^vvv<v<v><<>^v<^<<>v>^v<vv<>>v<<^^<v^^v<v<<<>>v><>^v><<v^v>>^v<><<<^v^^^<v>^v^<^vvv<><>>><^^^^<^^^v^v<^>vvvv>vv^>>v<>vvv<v<><>v>v<^vv>v^<<^^<><>v<><<>>>^<vvv<>>^<<>>^vvv>^v>>>>v^>^^<^>>v>>^v^v><^^<>vv^>v^<>v<^>v><<^>^^<>^^v><<<<^v>^v^^^^^v^><v^<^><^^>>>^<^v<^v<>v<vvv<v>^>>v<v<^v>>^>>^^>>v^<>v<>^>v^vv>v^^vv^><>v>^><^v<>>^>>^><>v^^>^^><^v><><<<<><vv^^v^>^<<>^^v^>>><vvv^>^v^v^><^<>vv^vv>^<vv<>v^v>^^<>>vvvv^v^^<^><v><>vvv<<><vv^>><<<^^<<^<>>^>^<>>^<<^^>>>>vv>><v^v^<v^>^<^vv<>v^><>>><vvv<v>vv>vv<v<v^^<>v><>vvv<^^^>vv><vv>>v<^>^<>^<<<^<<^^>v>^vv^>v<<^^^><^>^v><^v>vv^^^v>><v^<^><<^<>><^>v<>^<v>v^<<v><^>>^<<^<vv^><<^^vv^v<vvv><vv^^^<^^^^<vv><<v<v><^v<v^<^vv^>^^<><<>^^^v^<^<<^^v<^><^<<<><><<vv>>^>>>v<<^v^<v><^vv<>><>>^^v<<v><<>>^<>>>^<>^vv<<>v<>vvv>v<^^^v<>>v><^v^^<^^>v<><<^<<^>^^vv>v<v^v><>^^^vv^^>>^vvv>>^>>^v^^>v<>><^><vvvv<><v><^v^>>
+<v^<^v^^>><^>v><^^<><>v>^>v^<>v<<vvvv>v^^>>^<<vv^vvv>^v^><^>^>>><v^^<>^>>^<v^<^v^^<v^v^>v<>v^<vv^><><v<^<v^v^^><v<^>v^<<<><^v^^>v><>v^<vv<>><^>>^^vv>^^>>vv^<<<^v^vv^>>^<<v>>v>^><vv^^v<^>>v^<^><^<^^^>^^>^v<<>v^<^v>v><<v<<v^>^v^>^^<v<><<^>^v^^vv>vv^^^v>^v>>vv^v^^^>^v^^^^<<<>^^vv^^^><<^vvv^v<vvv><>^<v^v^<v^^<^vvvv<^^<vv<^<>><<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^>>^v^>>vvv^^v<^^v^>>v^v><^>^>>^>vv<^><<^^^><>^<v^^v<<<<^^vv^^vv>>^<<<>^>>vv<<v<>>v^v>^^^<^<v^>>^<^>^v^>>^^>>^vv^><^v>>^><<>>^>>v^v<>^^v<<<<^<>v^>><>>v^v^^^^^^vv>vv<^v^><^<>vv>^v<><>vv><v>>^>v^vv^><<><v<vv><<<<v>>^^v<v>>^v>^^><v<v^vv^v^^v<<^<^^v^<<^><<>><vv<^><^>>v^<^^><>^^<>v<^<v<<>>^v^v>>>><vv>v><>>><><^<>^<><v<v>v^>v<>vv<^<<vvv<><v>v<v^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^<>>><vv>v^<<>v<<v>>v><>^<>vv<^^^v<<v^v<^><>>>>>^^v^^<<<><>>^v^v^^v>>>><vv<<>>v^<vv><^^^>v^<v^>><<v>v<<<<>v<>>><<<vv<<>^^>v>^v<v><v>>><^<^><^<>vv>v<>vv<><v>^>^v^^v<<>vv<v>v<<<^v>^><<<>^>v><<><^<>^^^^v^>^><>><v^>>^<v<><>^^<^><>>v<v>vv>^<v^^>^<^^><^^<v>v^<^>>vvv<vvv>v>>><<<><<><>vv^^<v^>^^<>>><>>v>^>^<>>v><v^^vv^vv^<><^<vv>>v<^<<^^<<^>>v>><<v<^v<<<>^>>>^v^<v^<vv>>^v<^vv<v^vv^<v<v<<<v<v<^^<v^<><<^<v<<>>v>^vv^><^v<<v>^v>>v^v^><^<^^>^>vv>>^^<><v>v^^<v^^>>>v^>><>>^<>>>>>v>v<<vv^>v^^^^<v>><><^<^^<v>^^>^>^<<<><v^<>>v><<<>^v^^<v>>^>^><>^v>><vvv>v>^><^^<v<><vv^>v^<<<^v^^^v<>v><^^<vv^^v><^v><^^^>^<>vv^^v<vv>^^<<^^><><><<^>^v>><v^>^>>^^v>>^>>>v^<^<^<v<>v<<<<vv^^><<>^>v^^>^>vvv>>^v>^^^><><^<vv<><<<>v>v>v^<<^^<^vv^<vv^>>^v<<^<>^>>^>^<^^v<v<>>v>>^<^>^<^>^^<^>>>><<<vv>vv^^^<^<v><<^^<v^^<>><<v>^v^v^^^^vv^><<v<^<><>^v<^v<^>v^<><^^^>^v<>><^<^v<^v<^^>^<v^v^^^>v^><v>vv<>^><v>>v>v>^<vvvv<^>v<v<>v^<<<v<>v^^^^><<v^^^<^^<v>v>^>v>^v<^<^><<v^v<<^^v>>>><^<>v^><<v<^^^<v<<^vv>^^<^<>v^vv><<<^<<>v^<>^v><^<<
+^<^^><v<vv<<<>vvv<v^>>^^><^vv><<^^<<>>>v^v<><v^><v>>>>>^<v^<>^><>vvv^^^<vv>><^<v^><v^^>vv^<>^^v^^v<v^v<>vv>^v^<<<<v>>v<>>><v>^<<>^>>v><^^^>v><<vv<>v<^<<<vv^^^<^>>^<v<>>^>v<><<<><><<vv<^><><><<vv<>>^<<v^>>v>>^<v<v>>><<><v><<><^<>^v^<>^vvv^v<^<<^v^<<^v<^v^^^^v<^>^^<vv>v^><^^^>v>v^>^<>v>vvv^<>v^v<^>>^^>^>^<>>^^<<^>v<<>>^>^<<<><^vv><>><><<^><v^vv<^>v>>^v>^^vv^^<v>^<<v<^<<<^<><v^>v>vv<^><^v^v>vv^>>>v>^>^>vv^>v<v>>vvv^<^v^^<<>><vvv<<v>>^<><<>^<^>^vv^>^vvvv<><<<<^^>v><^^v>^<>>vv^<^v>><^>>^>><^v<^^^>v><<^<<>^^v>vv><^>v^v<>><vv^v>^^<^><^>^>v<<><^<v>^<v^<v<<^^vv<>v^>^^vv>^<vvv<^v>^v><v^v>^<><<><<v>v<^>>v<>^>><v^<<><<><vv<^<>>^v<v<<>>><v^><<<vv<>>v^>vv^^^^<v^^^^vv<^v<<^vv><<v^<<><>^>vv>>^>^>^<>vv><<^^><v^vv<<^><vv^^<^<>^v>^<v<vv^^><^v>^^^<>^vv<v>v>vv>^^><v^^^<^^v<v<<vvv<>v><>>^>>vv^^v^><<<^^<v<v<v>>><v>^^^>^vvv^v<<^<>vv^<<>>><<^<>><>><v><^<v><^vv<^^<v^^v<vvv<<vvv><vvv^vvvv^^<^<^^^<^<^v><^^^<v>v^<<^^>^vvvv^<<vv<^^v^>v>vv<vv<>v^v^^v<^vvv^>>v^<v<^<><v<><v<^v<vv<v<v><^>>^><^v>^vvvv><v<>^^^vv>v^<><^vv
+^><<^<<>v^>>v><vvv^v<^>vvvv<>^>>vv<^>>v<v^<<>^^<^<^^^^^^<<^<v^>v^>^^vv^^>v<^><^^><v^<v><<^v>v>>>^^<v>><^^>><<^^>^^^<v^>vv<><vv>>>vv^v^<>v<><^>>v^<v>v>^><<v^v>>^v^^^<<<>v^><v^<^vv<>>>>^>>>>^v^v>><<^>^>>^><^v^>^<v<v><<^>>^>^v<<v^<>^v^v<^>vv>vv^v^<vv<v>^^^v^^>vv>^^^>>v^<<v<>^^<<v>v^v^<v^v><<<v<vv<^v^^vv<vv^vv<<v>><^>v<v<<v>><v^^^<^<v^<>v^vv^>><^>v>>^><<v<^<^v^<<><>v>^<>>v><<^^vv<<v<>^<v^^v^vv>>^v><<>v>v<^<vv^^>v>^<^^<v^^<<v<^<^^>^<^v>>^<<v<>><v<v>v^^^>vv^>^<>v^>v^<<>^<><^>v<v<<v><^<<vvv>^v<><v^><><>>>^<<^<<>v<v<><<^<v<>v>vv>v<><<^v>>><v<^^v^<v>vv>>^<<v^<^>^><<<v^>>^<v>v<<>^>v>>>v<v^vv>^^v<v<<^<^^>^<>>vvvv^v>^^vv^<^><v><<^^><>>><<>^<v^^vv>><<^v><><v<vv><v<<><><vvv^<^^<^><<^<<^<><><>vv<>>^>^^vvv<v^v<<v<><<>^^^^vv<><>^<><v>^<>>>v^v<>^><<<<^<^>^<>vv<>^<v^v<>>><vv>v^<^<><<^>vv^v>v>^>>>^vv<><^>>>>>^^<>^>^^>^^>>vv>v>vv^^v<><v^<^><^<<>v>^<><^v<<><^v><><>^^<^^v^>^^>v^<><><^>v><^><<^vv<<<>^v^<<^^<^<><^<>^<><v<v<^<^<vvv>>><<<v^v^>vv<^>v><<><<^<^v>vv^<>^^v>v^>^<<>v><^<><<v<v><>>^>>v>v>^>v<>^<<v^vvvv>
+^^^<><vv<><<<vv<^v>v>>v><><v>><<<v^^vv<><^v><>vv^<^><<<^v>>vv>v<>v<><>>>^^v>>vv<^^<<<v>^^^>v<<>^v^^<<^>^v^<<<<^^>>vv><>>^<v^^v^<<><>>>v>^<v><vv><<v<>^>^<<^v^<>^>vvvv>>>>^><^vv>>^<<^>v^<^^>vv^^>v<<>^<>>v<<^<vvv<^^^><>v>>>^><^^<^><^^<>^>v<>>><<<v^v^vvvvvv^<<^v>><<^><>>v<^<v^<^<>>><v<>vv^><v><^^>v<^vv><><<^<<vv^v>v^><v>^^v<^<v<v^vv>>^^<<<<vvvvvv^>v<>><v>>>^<<^^<v>>^<<v^><><>vv<v^^^<^><>^v^<v^vv^vv>><<^><><v^>^v>^v<v<>^v^v>v>^^v><<>v<<<<>v>v>^<><<><><>v<v^^>^vv>vv><<><<><v<v>^^^^^vv><vvv<><><>><<<>>^>^v>^^<^v^^^>v^><v><><<^<v>^><>vv>vv<^^v<^><^><^<v^<>^<>v^vv<v^v>^>v^^>^^>><>^>>>vv<^^^<<<>v^><<^v><>v><<vv^^><vv^<^><<>>>^^><v<v><<<vv^v><>v><<^<^<v<v^<^<vv<>>><><v^>vv<<v^<vv><v^<><>^v^><><<<v<^^^>v<<vv<<^>>>^^v><>>>vv>><vvv^vv^><<<^v^^^vv<<<^^^<>><v^<v>v>>^><>^^vv<^^vv<^^^vv^>v^>^^<v<v>>>vv^v<<<v^vvv><v<^><v^>^^<v<^>v<^<^v>v^<^v^<^<>>v>>>>v^v>^^<v><^v^v<v<v<>><v^v<>v<^>v<>^<vv>^^<<vvvv<^v^<<<>v^v<^v<><^>><^^^v<<^^<v^v^>>vv^<vvv>>>v>^^>>>^>>^v^>>><>>>>^v^vv<^>><^<v>v>^v><>^^><>v<<v<>>>^<<>><^
+>v^^v<<>>^>^<v<<<^^vv<<><^^^v>^>^>v^<>^^<^v><<v>v^><v^>^>>>vv^vv<<<v^<v>^vv^v><^v<<^vv>>^><v>v><>v^v<<>v<<v^v>v><><v>^v<v<v>v^^v>^^>^><^<^v<^>v<vv><v<^^>v<>>^^^v<^vvv<>^<<><>^<^>^v>>^>v<^^>v><<>v<^^>>><^<^>vv<>^<v^<^^<>^^vv>^v><^<^v^^v^><<<^<v>vv<<^^v^^^<^^^^vv>^v>^v^<<v>v^<v>>v<^v>^v^<^><<vv>>v>^>^^<vv<>^^vvvv>^>vvv>><v>vv<v>^><v<^^>>^^vvv>v<<vvv<^^><>v<v<<<<><v^v<<<^^>v<v>>>^>vv^<><v^<v>v<<<>^^v<>^v^v>v>>^<<>>^v>^<v>^<^>^<><>^v^^>>v^<<v><v^>vvv^>><^^>>v^<>^^^>>>><^>^<<^>^<><^<^v>^>^<<v<v<>^^v^^>v><<<<v>>>v^<<^>v^v<><^<>^^vv^vv<^<^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>^<vvv<^^v^>^<v<^vv<>><<<^v^v><^v^<v^<<>^>^>^<^^^>><><v<v<<vv>^^><>><^v><v^v<><<^^v>>^v<v>>v<>v>^>vvv>>v>^<^^v>vv^^<^>^<><>>>>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<vvv^^<<>^<^v
blob - /dev/null
blob + 473acc26cfc3a93b5abbe7f5f4beccd16f95c81a (mode 644)
--- /dev/null
+++ src/day-15.lisp
@@ -0,0 +1,125 @@
+(defpackage #:aoc/day-15
+  (:use #:cl #:aoc/utils)
+  (:export
+   #:follow-directions
+   #:day-15))
+(in-package #:aoc/day-15)
+
+(defparameter *moves* '(:up   (0 . -1) :down  (0 . 1)
+                        :left (-1 . 0) :right (1 . 0)))
+
+(defun read-directions (input)
+  (loop for line = (read-line input nil)
+        until (null line)
+        nconc (mapcar (lambda (c)
+                        (ecase c
+                          (#\^ :up)
+                          (#\< :left)
+                          (#\> :right)
+                          (#\v :down)))
+                      (coerce line 'list))))
+
+(defun expand-map (map)
+  (loop with width = (* (input-map-width map) 2)
+        with height = (input-map-height map)
+        with new-map = (make-empty-map width height)
+        for y from 0 below (input-map-height map)
+        do (loop for x from 0 below (input-map-width map)
+                 for point = (cons x y)
+                 for new-point-left = (cons (* x 2) y)
+                 for new-point-right = (cons (+ (* x 2) 1) y)
+                 for cell = (map-cell map point)
+                 unless (char= cell #\.)
+                   do (setf (map-cell new-map new-point-left)
+                            (ecase cell
+                              (#\# #\#)
+                              (#\O #\[))
+                            (map-cell new-map new-point-right)
+                            (ecase cell
+                              (#\# #\#)
+                              (#\O #\]))))
+        finally (return new-map)))
+
+(defun find-robot (map)
+  (loop for y from 0 below (input-map-height map)
+        thereis (loop for x from 0 below (input-map-width map)
+                      for pos = (cons x y)
+                      when (char= #\@ (map-cell map pos))
+                        do (return pos))))
+
+(defun move-boxes-basic (map pos direction)
+  (let* ((cell (map-cell map pos))
+         (diff (getf *moves* direction))
+         (next (point+ pos diff)))
+    (case cell
+      (#\. (return-from move-boxes-basic t))
+      (#\# (return-from move-boxes-basic nil)))
+    (when (move-boxes map next direction)
+      (setf (map-cell map next) cell
+            (map-cell map pos) #\.)
+      t)))
+
+(defun box-positions (map pos)
+  (case (map-cell map pos)
+    (#\[ (list pos (point+ pos '(1 . 0))))
+    (#\] (list pos (point- pos '(1 . 0))))))
+
+(defun clean-positions (positions)
+  (remove-duplicates (remove nil positions) :test #'equal))
+
+(defun move-boxes (map pos direction)
+  (case (map-cell map pos)
+    (#\. (return-from move-boxes t))
+    (#\O (return-from move-boxes
+           (move-boxes-basic map pos direction)))
+    (#\# (return-from move-boxes nil)))
+  (when (member direction '(:left :right))
+    (return-from move-boxes (move-boxes-basic map pos direction)))
+  (loop with diff = (getf *moves* direction)
+        with positions = (box-positions map pos)
+        with to-be-moved = (list positions)
+        for y = (point-y pos) then (+ y (point-y diff))
+        do (setf positions
+                 (clean-positions
+                  (loop for position in positions
+                        for next = (point+ position diff)
+                        nconc (case (map-cell map next)
+                                (#\# (return-from move-boxes nil))
+                                (#\. nil)
+                                (t (box-positions map next))))))
+           (push positions to-be-moved)
+        until (null positions)
+        finally (loop for set in to-be-moved
+                      do (loop for position in set
+                               for next = (point+ position diff)
+                               do (setf (map-cell map next) (map-cell map position)
+                                        (map-cell map position) #\.))))
+  t)
+
+(defun all-boxes-gps-coords (map)
+  (loop for y from 0 below (input-map-height map)
+        sum (loop for x from 0 below (input-map-width map)
+                  for pos = (cons x y)
+                  for cell = (map-cell map pos)
+                  when (or (char= cell #\O)
+                           (char= cell #\[))
+                    sum (+ (* y 100) x))))
+
+(defun follow-directions (map pos directions)
+  (loop for direction in directions
+        for i from 0
+        for new-pos = (point+ pos (getf *moves* direction))
+        when (move-boxes map new-pos direction)
+          do (setf pos new-pos)))
+
+(defun day-15 (input)
+  (let* ((map-1 (make-map input))
+         (pos (find-robot map-1))
+         (map-2 (progn
+                  (setf (map-cell map-1 pos) #\.)
+                  (expand-map map-1)))
+         (directions (read-directions input)))
+    (follow-directions map-1 pos directions)
+    (follow-directions map-2 (point* pos (cons 2 1)) directions)
+    (values (all-boxes-gps-coords map-1)
+            (all-boxes-gps-coords map-2))))
blob - 319428bc76d8b327693cbeffd71b6a24ca073679
blob + 47b8bae5c57636dded7d94322e776d29b057d45e
--- src/utils.lisp
+++ src/utils.lisp
@@ -10,6 +10,7 @@
    #:read-input-match
    #:char-number
    #:make-map
+   #:make-empty-map
    #:print-map
    #:input-map
    #:input-map-width
@@ -116,9 +117,29 @@
                                              :width width
                                              :height height)))))
 
-(defun print-map (map &key (stream *standard-output*))
+(defun make-empty-map (width height &key (initial-element #\.))
+  (make-input-map :data (loop with array = (make-array height
+                                                       :element-type 'simple-string)
+                              for y below height
+                              do (setf (aref array y)
+                                       (make-array width
+                                                   :element-type 'character
+                                                   :initial-element initial-element))
+                              finally (return array))
+                  :width width
+                  :height height))
+
+(defun print-map (map &key (stream *standard-output*) position)
   (loop for y from 0 below (input-map-height map)
-        do (format stream "~A~%" (aref (input-map-data map) y))))
+        for line = (aref (input-map-data map) y)
+        if (and (not (null position))
+                (= (point-y position) y))
+          do (loop for c across line
+                   for x from 0
+                   do (format stream "~A" (if (equal (cons x y) position) #\@ c))
+                   finally (format stream "~%"))
+        else
+          do (format stream "~A~%" line)))
 
 (declaim (inline point+ point- point* point-mod point-x point-y)
          (ftype (function (cons) fixnum) point-x point-y))
blob - /dev/null
blob + 6593ccde130f69fa6cc5be76c91555c920dd89b0 (mode 644)
--- /dev/null
+++ t/day-15.lisp
@@ -0,0 +1,50 @@
+(defpackage #:aoc-test/day-15
+  (:use #:cl #:lisp-unit2)
+  (:import-from #:aoc/day-15))
+(in-package #:aoc-test/day-15)
+
+(define-test test-day-15
+    ()
+  (assert= 2028 (aoc:run-day 15 "########
+#..O.O.#
+##@.O..#
+#...O..#
+#.#.O..#
+#...O..#
+#......#
+########
+
+<^^>>>vv<v>>v<<"))
+  (multiple-value-bind (task-1 task-2)
+      (aoc:run-day 15 "##########
+#..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^<<^")
+    (assert= 10092 task-1)
+    (assert= 9021 task-2))
+  (assert= 618 (nth-value 1 (aoc:run-day 15 "#######
+#...#.#
+#.....#
+#..OO@#
+#..O..#
+#.....#
+#######
+
+<vv<<^^<<^^"))))