commit d12876e85c885c2f3e6e00241272241689e33960 parent f89b18893aa320fc76f036d542aea31bb12b3fd7 Author: Martin Ashby <martin@ashbysoft.com> Date: Fri, 3 Jan 2025 20:42:38 +0000 Day 15 pt1 Diffstat:
| A | day15.txt | | | 71 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | day15_sample.txt | | | 21 | +++++++++++++++++++++ |
| A | src/main/java/day15_pt1.java | | | 126 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 218 insertions(+), 0 deletions(-)
diff --git a/day15.txt b/day15.txt @@ -0,0 +1,71 @@ +################################################## +##.O...........#..O...O.O....OO......OO...O.O..#.# +#OOO...OO.#O...#..OO.O.....O..##O...O....O....O..# +##....O...O.........OO#...O.O#.#O.O.....#........# +#OO.OO.O.OO.#.O..O.O#.O...OO..O..O#.OOO...O....O.# +#O...O.O..O....O...OO..#...O.#O...OO......O..#.O.# +#..O.......OO..##.#.O.O.O.....#...OO..O....O..O.O# +#.O....OO.O#.#O.O........O.#......O..##O..O....O.# +#O.....O..O.O.O...#......O.O.O...O#.....O#.#..O.## +#.......O..#....#....O....O..##O.......#.....O...# +#.....#...OO.O...O....O..O#.........O..O.O.O.....# +#O.......O.......O..O.O....#.O..........O...#...O# +#.OOOOOO#...O#...#....O...#.##...#..O.OO#OOOO#...# +#..O....O.OOOO.O.#......O.##...#.#O...O....O.O.OO# +##OOOO###..O..O.O.........#...O#.O..O.OO..##..OO.# +#......OOO.....O....O...O.#..O...OO...OO.O...#O..# +#......OO...#O#...OOO.........O........O.....OO..# +#.#...O.O....#.......OOO...O...O#.OO..#.#.O..O...# +#OO.O...O.O.#....OO..#.O.O.......##O..O.O..O.....# +##.O#OOO.....O.....#.....O#..OO...O..O..O.....O..# +#...O.O..O..O.O.....O.OO.....O...O...#..O.....O.O# +#O..OO.O.#..O..O....OOO.O.O.............OO....O.O# +#.OO#O.O.O.OOOO#O...O.#.O....#........O.O..#...#O# +#O.O.#O..#...OOOO..........O...#OOO....#O..#O..O.# +#..O.OO......#...OO..O.O@O#.#.....O.....#.#OO.#..# +#O..O.....OOO....O...#..#....O..#OOOO........O...# +#O..O#.#..O.....O.O.....OOO..O..O.#..#OO.....O.O## +#..........O....O...O.#......O..O.......O........# +#.OO#......O..OO...#O.O.#.O..O.O..........OO....## +#..O#O.O....O#...O.O.O.O.O..O.O.##O.#..O.O.O.#O..# +#..OOO.O.O...#.O.O.......O...#OO..OO.###..#O#..O## +#.#OOO.....#..O....OO.O..#O.OO..#O#.O.#.OO.......# +#.........OOO.OO.....#.....#O.O.OOO...#O...OO.#O## +#...O...O......O...O#..O#O#..O.OO.O..O.O...O.O.O.# +#.O.....OO...OOO.OO..O......OOO...O#.....O....O..# +#O..O.......O........O...O.OOO.O..#..O...O.OO..O.# +#...O..#O.O......#..O.......OO.#..#O..#O.O..#.OO.# +#..OO....#.....OO.O#....O.O#.O...O...O..#..#.OO.O# +#...OO.O........O...O.O......O.O.............#OO.# +#.....#OO......O#..O#O....OO#O....O#...OO.#OOO...# +#.....O.OO......OO#...#O......OO#...........O.#O## +#.OO.O.O.OO....O........#..........O..........O..# +#O.OO..O.O..OO...O...O.OO..O.....#..#.OO.OO.OO.OO# +#..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.OO#.......O.#...O.O......O.O...........# +#.#.....O......O#.#.O...O#O.O.O...O.....O..O.OO.## +#.....O.O..O.......O......O..O...O#O#.....OOO....# +################################################## + +^^^v^^v><vvv>^v^><<^>>^^^<^vv^v>v^><v^v>v>v^<^^v^>v<^><^>^<>>><<<v^><>v^>^^^<<<>^<^<^v<^<><v<vv^^>^>v><^v><v><vv>^v<>v^v^^>>vv<^^^><^>>^^>v^^^v^>^v>>^<<v>v>>v<vv^^v<v>^<vv<><><^><<v<^<>^^<>>^>v^^<<^>v<>^<v<>vvv^v<>>vvv^^v^<v<v^^v^<>^^v><>v><^^<vv<>v<<><v><^^v><v<<>>>><^>^^>vv<><vv^>>>v^>>^^>><>^>>><vv<<v^^^^<<>v>>><>v<vv><v<>v>>v>^vvv><v^>v<^v^^<^^>^<^v<vv>>>^>>^<>^vv^v<^v<v><^>^<<v>>v>^^vv><v>^>vv<><^>><^^>><<^v><>>^><^<^^v><v<<^vvv^^><^^^^v^^v<>v<>>^>^<v>^^<^v>>>^v>>>><<<v<>><<<vvvv>><><><>vvv<>^^<vv^^<>^<vv>v<^^><>>^>^<v><>^v><>v>v<v<<<v<^vv<v>v^v<<^v<>^v<<<v>>vv^<vv<v^^<><^^^<<v^><v><><vvvv>^vv><^><v>^^v^^<v>^vv><<v^>v<<>^>^v>v<v>^^>v<<v>^^v^>^^^v^vv<<v^^^<<<<v>>^vvvv<^<^vv<<<<v>>v^v^<<^^<vvv>^<<v<v<^vvv<>^<>>>>v<^>v>>v>^>v<><vv>^><vvv>^^<^^^^^vv>^>v<<^^vv^>><<>v<vv>v>v^^v<>^^>vv<>vv<>><<^<<>>><v^^^>vv><^^<^<<>>vv<><><^><^>v>>^>v<^^<>vv<<v>>^<<^vv^<vvv<^^>v<^>>^^v><<<><><>><<>^>^>v^>^^<^vv><<vv>>>v<<^<^^v<v^><>^>v><^v<<^v^v<<v<v>>^^>^>v><v^vv<>>^v<<^v^v><<v><v><<^v><v>><>v^<^v^<>^v +^^<vv><^^<>>^><<>><>v^<v>>^v<>>^>>^<>^^v>^<><^v>>^><>>v<v>^^^^vvv>^v<v^<v^v>v<v>^vv><v^<v<^<<><<<^vv^v<^v<>v^vv^^><>>v>vv>v>>^^>v<<>^>^^^^vvv>vv>^<>><<v<^>v<>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>^^^^v>^^<^^>v^^>>v^<><><>v<^vvv^<<<>^^^^^v>>v^v><vv<vvvv>>^><v^v<^^^><^v>^v<vv<<<v^^<>v>^<>v^>>>>v<v>>v<<vv>><>>v<^<>><<v>vvv>>^>>v><<<^^^>vv<><v<^>vvvv^v<vv^^<<>^vv><><>v^<><<v^^>>^>>v><>>>v>v><v^^v>v>vv^>^><vvv>vv<<<^^v<v<v^v^vv^>v^>>>>^<^<^<^>>vv>^>>v><<^>v>^>v<>><><v<>^<^>>v>v<<>^>^<>>vvv>>>^^><^^>^<v><^^>^<v<<<>>^^<>^<><><^<>^<>>^<><>^^<<vvv<<><<>>v<>v^^^^^vvv><<^^><>v^vv>vv>>^v<<>vv^>^<v>vv^>^v<><<^>^>>>v>^>>vv<^^^v>^^^^v<<<<<<^<^v>^vv><^>><^>>^^<v<>^^^<<v><><<^^^>v^^^v^>>>><<<><<<vv<>^^<><>>^^<v^vv><>v>>v>>>>vv<^>>v^^^<v<^><^vv>>>vv<<>>v^^v^^v>v><<^v^><vvvv>v^>>v><^^<<>v>v<^^^>vvvvv^>>>>vv^^v><v<^v>>v>^<<^v<<>>v<>^>vv>vv<<v>v<v<^^<^<<<^<^v<><><>><>v^<><^<<^v<v>v>^<<<<<v>v^>v<>^<>^v>vv>^^vv^^<<^<>^<<>v<v<^><<^<^vv^< +>^^>v^>>vv^^v<<<vv>v<^>><v>^v>^^><^v^^^><v<>vv<>>^><^v><vv^v><<<vv>^><^<vv<<<^v>v<v<^<^^v^<>>>v>v<v>><<vv^^v<v^^>^v^>^v<^><<<>vv<>v<><<v><<^>>v^<^>^v<><^<^<<>v<vv^v^<vvv^>v^^^v<>^<<>>vvv<<<<^<<vv^<<<v><v><<vv^<>^vv>v>><^vv^<v<v^^vvv><>>^v^^^v>v<<<>v^^>>v^<<v>>>^<><>>^^^^^vvvvv>^vv<><><>vvv<^v>>vv<^vvv><^^^>>^>>^<>^>^^>>^^<>^^vvvv><<^><^><>v^><^^v^^<^v>vvv<v^>^>>><<<<v^>v^<^<>^v<<>v<><>v^^^v>^v^^^>v><v^>^^^v<><>^^>v<^^^^v>>v><^v>>^vv>^v<<<<v^>^^<<^<<<v<^<^^<v>>v>>vv<<><^v^^<><><^<<vv<v<^^<v>><^^^<v<v<^>^v^<<^<v<>>>><<v<^^vv>>^^<><vv^v<<<<<<vv><^>>v^<v<v>^>^vv^v^<>v>v<<>v<>v<vv^>^>>^>>^<^^<<^v^v^^^vv>v>^v><^>vv^<<^v>>^^v>^^v>^>>^>v^^>vv>^<v><<>v><vv>^<<>><<<<vv<<>>^^<^^v<vv^^^<>>^><>^>><>>^<><>^<^^<^>>v<^>><<<<<^<v>v>^<v>^>^vvvv^>>^^v^^^^^vvv<^^<<<^<^v<<^<<<<^>>^^>vv^>^^<vvv^^^v<<<><<>v><v<^^>><<>vv>^>v<^^^^<v<<v^v<<<><vv^v><^><>>><^vv<<^vv^>>><v^><v^>v^><vv<v>><^v^>vvvv><^<>><>><v<<v>v>><<<^^>>^^<^^>vv<vvvv><>v^v^v^<>>v^<<><><<<>^<v^^>v>v<><>v>>>^>>^<^^v>><><v^>v>^>^v^^^^>>v^^^v^^^v>>v> +^>v>>^>>>^>^<>^v^^<^<><v^>^vv^<<>v>vvv>>v><>^>v><v<<>^>>>^<>><>>><<^<>^^<>><^<^<^<v<v><<^<v^>><<v^^>^><^>^<^>vv^><v>v>^vv>v<^>vv><^>v><vv>v><v<>^^>vvv<>^^^^><v^<vv<^v^v<>>v>>v>><>>v^<v>vvv<v<^^^>>^^vv>^><<<<v<<v<>^^^vvv>><^^v^v<v^<>^>><^v^^><v^^^>>v<v^^<>>>><<^^>v^vv>^^v>^<<vv<^<vvvv><vv^>^v^v<<^<v<^>vv>vv^<>^<<>^^^^v<^v><v^>v^<^^<<v>^<<^^^^vvv<>^^<>^><<^>>^^<^^^v>><^>>^v>^^<v^><v^^<>><>>^v>>^v>^>><^><>^^v>>^<<<v^v^vvv>>v>^v<^>>>^><^><>v>^v<<<>^>^v>v<^vv<v^<><><><^^^v<v<^><^<^<<<>^<v^v^v^>v><><v<>>>^vv>^<<^^^v<>^^v>><>^v>^^>^<><><<<>>>^<<<v>v>v^<><<><v>>>><vvvvv<>v^^<>v<>v^<<><<><><<>^vv^>v<<<^vvvv<<>><<<>v>>^v<^v<^<^>vv^<^^^<<<^v<v^<>v>>^vv^<<vv^<>v>^v<>^v^v^<<^>^^^^v<<^v>>>^^>^><<^<^>>>vvv<>><>v<>^<vv^^<^^>^<>^<v^<<><^<^<^^><><v^>v<><>^v<<>>v<^>v<v^v>^>v^<^>>>vv^^v<><>^^<><v^^<^vv<^vv^^<^>v^<<^><vvvvv<<<^>v<v^v>>^<<<<v>>v><<v^<v^<^^v<<><^v>>>>v<>v<^<vvvv>v><^v^v^<vv^^>v<v^>>v<>vv^<>^>v>v<><><>v<^vv>v^^^vvv<>><<v<<>^<>>>vvvv<>v<^^<^vv<^v^>^v^v^><>><vv^>>^<<v>>><>>>v^^<^<^<^<^<^><><^<> +^><v>^>v>^<<vv^><^><^^<^>^<><v<>><<v<>>>^^<<<<v><v<vv<v><<<vvv^^<v>^^^>>vvv^^^<<>>^^<^^><vvvv^<>vv<v>>^>^^>v<vv>v^^>^<^<^<vv>>v<<>>v^>v<>^^>v^>^v^>v>>>^><^>^>v<<^<v^><>vv<v<v^<v^vv^<>^^^<v>^<vv><^^^^<v<>^<>^<<^>^>v<>^<^v^<><><>^<^<^^v>>^^><>v<^v<^>>>v>><><><v><<^>v<<^^<v>><^^<>v^>v^^>>>v>^<<v<><<^vvvv<>^^>v^v>^<>^>^v<<><>^<>^>>v^v><v<^>^v>^>vv<<<v>>v>^>^<v^^v^^<vvv<^<<<v^>>vv<<vv^<<<v<^^^>v<^<<^<><><^vv>>>v<<^<^<><<^v^^^v>v><^v<<>>>v^^vv^><<^><v^<v>>v^<v<>>v><vv<<^<<^v>v^<>>v^<^<^<^^vvv<^^v>v><^v<>^v>v>^<<<^vv^^vv^>vv^^>v><v<<<><<<vv><>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<<vv<v<<^v<>><^^v<>^>v<<^>><^v^<<^>vv><>>^><<><>>^<<^<vv>v>^^>v>^><^<><vv>v^v^^v<<<<>vvv^<^<v^v<^^>v><^>^>^v>v<<<v^^v<^vv>vv^v>v^v><^^v<><v<<^<>><<>>>^>>^v^>>^<v<<><vv^><<<<v^^^<^^<^vv^v>>>>^^v^>>v<<^v^v>v^^v<>^^>v>><^<v<^v>^<<>^><v><v>vvv>v^v^^v>>^v<><<><v<^>v^<v<>^><<^<vv<<><vv>^><>^vv^v<v<^>>>>^v>><<>< +<v^^<><<>v><>>^^v<^^vvvvv<>v><v>^><>v>^v^v^v^>><><v>v^>v<^^<v^><^<>^<<>vv>v<<v^>v<<^<v<>^><>^^v<<vvv<v>v^<^>^<v>v<vv>>>v>>v<v^^>v^>v<^><^<v^>^^v>v>v<><vv<>^vv><<^v><<v^v>>v^v>^><^<^>v^^>^>^^v^^<>>vvv^^>^>><vv>v^<^v<<<v<><>^><<><vv<^^^^^v<>^v><^<<>v>^<>v>>^v<<^>^^^<><>^>><>>>v<v<<<v<v^v>v<^>>^><v^vv<v<>>>v><vvv<>>v<<<>v<>^v<<vv<><>><^v^vvv^>^<><><^v><^v<^^vvv>vv^<<^^<v^><^>v^^<^v<v>><<v>v>v<<vv<<>><<>v<^<<<>vv<v^<^<<^v<>v^^>^>v^^^^<v^^v^>><v^v^^^v^>v><^<<^>v^v<>^>>><>^^<>^^<^<v<>v^<^vv>^<>><>^<^^<<v<^>>v<vv<<v<v<>^>v><^v<v^vv<v>>^>^^<v>vv^^^<<^>><^<^>v><>>>v><^<vv<vvv^<><><>v<><<<v><^>^>^>><<<^^><>vv<^v<<vv><^^>^<v^^><v^<<v<<><><v^v>v^vvv^><>vv^<^<^<<<v^vv^><v<<>^<v>>v^v<^<>>^^^>>v>^v<<<^<v^<>><v^^v>>^v><<<<<v>^<>^v^>vv>v>v<v><^v><^vvv>v<^^^^><>>>><^^><<^^^<>>><<<<<<<<^>^>^^^^<>^<<vv<>><^^>>^v^^^>v><v>v<v<^<^<v>>^<^<>>^<^<<<v<<v^<>>>v>><>>^^vv<<^v>^vv^v^>><v>v<<v><^v<<<<^^<^^<<>>^^v<<<>>v<v^^vv^^><^vvvv^>^^v^^v^>^<>>vvv<vvvv>><^v>v^>^<vv^>v<<>>>^v<v^^<vv>v><>><>vv^vv>><^>^<>^^^><^^<<><^ +><<v^v>v>>^>vv^>^><^>^^^v<<^^^^<v>^v^v^^<^v<><<<v<>v^vvv<v^v^><v>>v>v^<<^^>>^^^v>v^>>^<<^^<<<^^<>>>>^v<>><>>>><v^>>>>^^>v<^<>vv>>vv>v<v^v><>vv>^^v<<<v>>^>vv<v<v>v^v<<^<^<vv<>>><^^>><v<v<v^v>v<v>v>>vv<v<v^^^v>^>>>v^v>^^<vvv<>>v>v<v<<><><><<^<<^>v^><>^v>><>>^v^v^>v>^<^^>>v^>v<^^^>v><<<v^vvv^<v<>v<>>^^v>vv>vv^^><>^<^^v<>>^^<v<^v^<^v>v>^v^<vvv>v>vvv<^v^><<^^v^v>>>^^^<^^^^<^^^<>vv^^^^^>><><>>v<>>vvvv<>>vv<v>v<^>^v<<<^>^>>>>>><<<>>^^>>v><vv<vv^><^>v<^vv>v^>^v><<>>v<vvv^^^><v^>vv<^<^>v>vv<>^>^<vv^>^><v<^^vv>>v<>>v<v^>^><<>^v><<>>vv>^v>v>^^<>>^<vvv><^^<<>v>^vvv<>^>>vv^>><v^v^<><><>^^<^^v<<v<^<^><>>^<^<^^<v<>>>>v<>v^>v<>^v^^<^^><^v^v<^><^^>v<v^>><<<^<<<<^<v>^v<><vv>v>v<<vv>>v<^<^v^>>v>^>>vv^<v^^><^vv<>v>v^^vvv><<vvv<^<>^^vv^<><^>^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>>^>v>>>><>^v>^^^<v^><>v><><>^><^v^v>>vv^>>v<^<^^v>^^v<^vv>v^vv<^>v<<^<^v<<^>^^<>v^<v^^>^><>^^^v^vv^<^>><<^^<^>^^v>>>v^<^<<v<v^^><>v<v<^>v<^v>>vv>^^v<>><>>^<v>>^^v^>v<>^vvv>^ +>v^<<v<>v>><^<v>^<>v>><v^>^v^><><<>^<^<^<^><vvvvvvv>v^<v^<>^>>>>><>><vv>^^vv<v^>>><v><<^<^>>^>>^^<><>^^<<<vv>><^vv>>v^^v^<<>^v>v^^v^>^v>vv><^v<v>vv<>v^v^^^v<<^>>><<<><vvv^<>>>v^v>>^>v^<<^^<^v^<>v^<>>v<<vvv>^^vv<<^vv<<v^vv^^^^v^v^^vv^>v^<^<<v>^v>v>><^>^<>>^v<v^v^^>^v<^>^^><><v<^v>^>>^<<^v^>v>^^<v><vvv^>v^>>>v^><v><>>v<^><^<v<>^<>v^v<>vv>><^<>v<><>>^>^^v^><v>^v^^vvvvvvvv<<^>v<vvvv><^<v^v<>><<<>v>v><><v^>>^>>^<<<<<>^v^<<<^^^v<<v<>>><<>^^>^>>v^^><><>vvv>>vv<><^^v^<>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^^^vv>v^^><v^^^><<<><<^vv<>v<<vvv<<v>v<vv<^^>><<^<v><>>>^^>vv<>v^<^^^><>>>v<^><<>^<><>v>>>><vvv^^>^>^^^><>><^><vv^vvv^<<<><v^^<v^^<^^^><>vvv>>v^v<vvv^<<><<v><<^<<<^^v^>v>^vvvv>^>v^<>>>^>v^>^<>>^>vv<<<^<^v^>><<^<><>v^<^<<^v<^vv>v><<v^><^^vv><^v^<<><<vv^<^^><^>>^<<^<vv<^>v<<>^><<><>>v<^>>^>>v>>^<v<>><<<^vv>>v^>^^<^v>^^^vv>><vv>^<><<^><><<>^^<v>v<vv<<>>^^<^>^<^v<^^^^>^v^<^>>v>vv><vv>^<^>vv>v>^>>^ +v<v>v>v<v<v^>^^v^<<>>>^v^vv>>^^v>^><^v><^vv^^^<>>vv<<<^^vv<^vv>>^v^>^^vv^^<^>^<^>v^^<<<<<vv>^<>>v><><^><>>v<v<^><v><>v><>^<^<<v<<>^^^v<<><><v>^<^<<vv^>>>><^^<^<><^<>v^<v^^>^^^^<v>^vvv>^v<v>v<>>>>^^><v<<<vv>>>>><<<v^>>^<^>^<>>><^><^^^vv<^>v<v<^v^v<>^v>^^vvv<>^><v^<^><<><vv^^^<^v>>v^v<>^<vv<v^<<<>^>v^>v^v<>>^v^<>v^v^v>vvv^>^<><v^vvv<<vv<>^>^>v^><>^<^^vvv>>v^^v^>><^vv>^v<<v>^>v><^v^<v>v<^<v<<>>^>vv^^vvv>vv^>v<vv>>^^<^^^v^><vvvv<<^vv>^^<vv>^^<<<^<v>^<vv<v>>^>>vv<<<>v^<v<^>^>^vv<^vvv<v>^vv>>^^v>v^<v>v>>><>^^>>>^^<v<><v>^>>><v><<vv<<>v^v^v>vvv>>v>>vv<^^<^^<<>>vvv^^^><>><v<<^<v>>^>^<>^v<^^v<<^>>vvv>>><v<^>^^><>v^<^<^>^v>><<<<^vvv<>^vvv>>^<v<^^v>>v<^><<^>><<vv^^^<^^^>^<vv>v>>^>>>^^>v^>v<v>vv><v^<<<vvv^<vvv<>>v<>>v><^^>^<v><v><^><>^^vv^<v^<>v^>vv<^>^<v^^>v<<<^^><<><<<^^^<^^>v>vvv^<>^^v^v<^>^><<><^<v<<^>^^>>v^>v>^<v>>^v><>v^v^^vv^<<<vv>vv>v<v><>>^<vv^<>^vv^v^v><>^^><>><>v><v^^>>>v^^<><<<<v<^^^<^><^>>^>^vvvv^<><<<^<^<^^>>^v<vv>><vv^<>>v<>^^<^v><v>>>vv<<^<<^vv^<vv<<v<>^>^>^vv<vv^<v<<>><^v>v><>>^<v +v^>^^>>v^^^><>^<><<^><>v^v<>vv<v>^^<vvv>^^>v>><vv<>^>v><^<>>>vv<>^>^<>^<v^v<v^^^^><v<v^^<v^v^v<^>>>^><^^v>>^vv^<^<>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^^vv^<v>v^^^^v>>^vv>v<><v>>v^<vv<^v>^><v^<^^vv>^<<vvv>^>vv^v<><^vv^v^<v><v<v<>v^<^><v<<v>^<^>^>v^v>v>^v>>^><^>>vv^^vv<<^vv<^<v<v^<>><^>vv<<>v^^<^^<v<v^<><<<v>><v<><^^v^^v^v><<vv>^^<^v><v>>^^>v<v><v^<>>><^^v^<<^<>^<>v<v^<^<v>^<<^^^>>>^><vvv>>>v>vv^v^^<<^^<v>>>><><>vvv<<^vvv>>v<><>><v<>vv^^<^^vv<v<^>^^^v^^^v^v>><<>^><^v<<v>^<><<>vv^<<v<^>^vv<^<^v>>v>vv^<<v<v<<^v<v^>v<v><>^>^<v<><>>v<>v<vvv^^<v^><vv<><^>><v^<v<vv<<>><^^<><^v<><^^^vv<<>>>>v><<^<<>^^><v>^>vv<v>>>vv>^v^><>v>^>^>>v<vv^>^<<>>v<^^^vv^^^<>v<<>^>v^>vv^^>^v>v<^v>v>^>^vv^>>v>vv^^^<v^^^<^^<^v<>vvvvv^v<^^<v>^<<<v^>>><^vv>>v<v>>v^^^v^<^vv>>^>>>>^><^>>^^v^^^^>><^vv<>v^v^^><v^>^<<>>v<><^v>v>>>^<<^<<^<<vvv^v<^vv<vvv>v^^>>>>v>><^vv<<><^^v^<<>>v>^v^vvv^v^>>^v^^<>v^<><^>><v>>v>> +>><<<v>><<^<v>^<v<>>^><<^<>>><^v<<^^<>^v>v<^^<vvvv^^^v<^<^<vv><^<^<>^vv><<v^><>^><v^>>>v<>^v>^<v><>>v<^>>><>^v>^<v<<^^vv>v^^>^v<v^vv<><v>^<^<>^v>^>^^<v^<^>v^<vvv^<vv^^^^v^<>v>^<v><v>v^<<<<<<>^^^^^^<vvvvv<>>v><<>^v><vv^>^>v>vv><^v<^>v^<<^^v^>^>>v<^^>^<v>v^vv>>><vvvv<^v^v^vv>^<^<^^^>^^<>^^>>>>v>>>v^>><v^v>^^^>^v<>v>>>><^v^>vv>^v<<<^<>v>^>vv>vv^^<><>v<vv<>v<^^^>^^>>v>><<<^v><^<vv>><>v<^<vv<^^>^<^<>>v^<^vv^>>>vvv^v>v^v>^<^<<<^^>>v^vvvvv<vvv^<>><^<v^<<<<>^^><v<^>^v^v>>^>><^^^<<^^<>v<v^^v^v^vv^>>v<>v<>^vv^>^^<^><>^^<vv^>>v^<<<>^>><<v>v>v<^^^<v<<>v^>>>^v^>>v>^^v>^v>^^>v^v^<<<^vv>v<>>v<v^<<^>^^^v>v^^<<^><<^^>v^^^><v>>^<<v<^<vv<vvvv>^<><^<^><v^<vv<^^<^>>^^^vv^>><v><<<^<<^^<<<><<>>^vv>><v^^v^<v^>>^^<^><<>^^v><<>^^vv^vvv<v^vvv^<v^<<v^>v^>><<v^>>v^v>^><vv><>vvv>^>^v<vv^^>^v^<^^v^<<>^<vv>^<^><^vv<vv^>>>>><v>v>^>^><vv^<v<^>>^<^v^^v^>^v<v><v^>><>v><><<^>v<>v>><<v>^vvv^v>v^>>^<<^>^^v><>^vv<>^^><<v>>v>^<<v^<<v>>v^<<<^^^<vv^v^v>^v><<>><>>>^^><<v^>^^v^v<><<vv^>^<^<v>vv^^v^^v<v>^>v><>vvv^vv>>><>^>^^<vv>^< +><>^^>v<<>v><^<<v>^><v<v>>>^>>vvv>^><>>^v^^<^<>>v<v>>>>^>^v>>v<vv><^vvv<<<^v>><<<^>^v^vvv<^v<v^v^^>^>v><v>>^vv<>><>>>^^^>>>>>>v<>^vv><v>>^^<v>^<>^^^vvvv<v<^<^><<<>>><>v><>>^><<vvv^>v^<^^>v><vvv><>>v>v<^^<v^>>>^^>v<^<^^><><vv>^<>^<v>v>^v>v>>vv<vv^<vv<v>v<^v<^^^>^<<><^^v>v>v>>v^>>v>^v^<>^v><^v<^v^<v^<vvvv^>^>^>vv>vv<^>v<<v<<>>^v^v<v<^>>^<>v^>^^v>><v<vv>^^<<^v^<>>^<^<^<v^v><>><v><>v>v><^>^^>><vv<>><<^<^<v^^v<v^v<^><<vv>^><<vv^<^<><vv>v^^>><vv^<vvv<v>>vv^v><^^<^vvv^<<<^^<^v<><^<^<<><<v>^<v^<><^vv^^v^^^v<>^>><^vv<^<>^v><<vv^<^>^^v>^^<^>v<<<^><><<><^<^<><v<^^^^v<^<^^^^>vvvv><^vv>v^>v><vvv<><v^^<^^<^^<^<^<v<^^v>>^<<<^v^vv<>v^^>vv^^^<><>^<<^vvv>>^>v<vv>^<^vv>^>vv>>v<>v^^^<v^>vv^v^<>v^^<>v^v^>><^>v><<<>^^^><vvv>>^v<>><vv<<v<<^v>^^v<>>>vv^>>vv^^v>v><^v<vv^vvv>^^v^v^vv><<<>>^^<<<<><>vv>^^^^>^v^>^^><^vv>v>>^^<^^^v<<<^>^vv<<><v<v^^v^<vv<>><v^>><v<>>><v^<<vv^><^^<^^^>><^v^v>>>><^<><^><^<<^^v><^v>^<^<^>v<<v^^v<<^^v>vv><>>vv>^^<^><><^v^><vv<<^<<v<vv^<v^^<>vvv^<^vv>^<><<^<^^vv^>vv>>v^vv><<v^vv><<>^v^v< +>>v^><^^>vv^^>v>>v<<vv^<<^>><^v<^<>v<vv>>>v<>^>v^vv^^<>^>^>^v<^<^^^^^>vvvv>vv><vv<<>>>^v><v>v<v>^^^^><<>><^<vv^^<>^<v<v<^<<v^<v><^^^><<^>^<^>>><vv^>>^^^><<>>vv^>><^^<<^><v<^v>^^^<>^>>>v<^^^v<<^>><><^>^>v<vv^v>^^vvv^<><>><<<<^^v<>^vv>v<>^><^<^v>^><<v<><^>>^<>v<^^<v>v><v>^>>v^^vvvv^>^>>v^<vv>>^<>v><<v>^<>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^<v<<<<><<vv<v^v<v>^<<v<<<^<v^>^<>v>v>v<<<^^<^^vvv<<<^>v<<^>><><>v<<<<>^^^>^>^<^v>^v<v^>v^>vv^<>>v>^v^vv><<>v^>>><><<vv^<<v>>^>^>v^>^^v>>^v<^>>v<^v^vv<v^^v^<^vv^^v>v>^^>>v><^v^><vv<><v<<>v><v^v>>v<^v>>v<^^^v>^vv>v><v<>^>>vv>>^^<<^^<v<v>>^><<^vv>^v>^^^<v>^<^>v^vv>v><<v<<^<<<^v^<>^<v>>v^<^^><>vv<><>v^v>>^<<>v<<v<<<<v^v^^^>v<<^><><<><>>v<vv<vv^^^v<>v<^vv^^>>vv<^^^v^vv^>vv>v<v^<>v<v^<<<v>^<^>^v^^<<v>v^>^<vv<<><>>^<>v>^>^>v>v><v<>vv<v^v^v<>^<<>vv>^^v^^v<^^vv<<^>>^>^<v<vv^<v<^vvv^^<>><>>><vv>>v<v^v^^v><<<<><><v<v>^<vv^>>vv>^^>>v>>><vv^v><v<>^>><<><vv^>v<^^v^v^^vv<vv>>v<<><> +^^v^vv>>vv<^>^<<^v^<>v^<><><>^>v>^^<>v^v^^^v>^>vv^^>vv<^<>><v><><<>><v^><<v^^^>><v^<<>vvv<^>^^<^<><>^>^><>v>>>v>v<^>^>^vv<v<<>>>v^^<<v>>>^v<<>vv^^<<>^v<vvvv<^^>>><>^<^v<v><><^v>v^<v<^<><^^v<^v<^<<<><<^>^<v^<^><<>><v<v><>v<^^<>vv<v^<vv^v^><vvv^^^>>vv^<^>^<<<<v<<><><<v<>v<>>v>^<^>v<v<vv>^<^<>>vv><v^>>^vvv<^><^>><v^><v<v>^>v>><vv^<<v<^v<^>^><^>v<^^^<^^>^vvvvv<vv>^<>^^v>^^<^v<v>>^^<v><v>^>v<>>vv^v<><<^v<v<v<vvv<vv>vv^v<vv<>v>^<v<>v^<<v^><>^<^^^><><^<vvv^^<<v<<>^^v>^><v>>^>^v><v^<^^^<>v<<v<v<>>>^^><<<^v^v><^>vvv<>vv><^<>>v^>v^>><^>v^<>>v>>><^>^><v^>>^v>>vv<<v>^>><^^>><v^<^><<^><vv>>><vv^><>^>^vv^><^<^><>v<>>^vv>^^v>>><v><vv^>><^v^vv><^vv<>>v>>v<^^^v^v^v<v^<><^<v>>^^<<>^v<^v><vvvv^v<>vv>><vv>>v^v<<>v^v>^<vv<^<^><^^<<><>v<v^<<vv<vv<vvv<v<v^^^^^>><^vv<>vvv<<^vv^<^v^<v<<^v>>>vv^<>v><><<<^>^<<^^<>>v<^v><<^vv<^v>v^v<<v^<<v^v>^>v^>><>>^<v><><>^>><v^v>v^<^^<^v<vv^v>vvv>^^>^^<<<>v><<^v<^><<v<>>v<^>^^^<^><^<v>>vv<>v>>^^v>^^<^<><v>^<v<>^>vvv><<<<>^>^><v^>^v<^v<^<>v<^<>^>^^<^<>>^v^>v<^v^^>>^^>^v^^<>>^< +<vv^>>^vv^^<^^>v^<<<<v^><v<><v^v<vvvv^vv^^^v<<^v>>v<>>><^><^^v><<<<^^vv<v^>v<^<vv>>>>>^^>^v>^^v<vv><<v^^^^^v<^^>>^v><^<v<^<<<v<>>>vv^^<<<v>><><^<^^<><>v>^v<^^v^^v>vv><<<>^^>^v^>>^^>^v>^^>^vv^>^>vv<v>><><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^vv<<v^v^v^^v^v^>^<v><^><<^v^v^>v><^v><<><v>>vv<^vvv^>^<^v<^^>>v<><v<<v^><<^<>>^v<^>><v^v>v>^<vv^<<v<<^^>>^^<^^^vv^vvv>vv<>^^v<v><><<>>>>v^vv<v>>v^<<<^<vv^v<^<>v>^<>v<<^^>><v^>>v<v<v>>^v^<^<>^^^^<>^v<>^>^^v^vv>^<^^>>>v^^<<<>v<vv<<v<^^<>^>>><v>>v<^^^v><v<><>vv>v>^>>>v^<>v>^<<^v^><vv>v>^vvv>>>v^<v^^>^<^>>><v>v<>^^>v>v^^v><<<<vvv<<^^>v^vv^>v<<^<vv^<>>>v<<<^<<<>v^>>>v<v>^^^^^v<>v<v><vv>>>v^><>v>>v>>v<vv^>^>>v>v^^^^vv<vv^v^>v^>^>^>^^^<^v<<^^v>v<^^^^<<<<><v>><><vv^^<v<>><v^v^<>v<<v<<>vv<<<vv>v>vv>><>^<>v<>>^<<v<>v>^><v^>^>^>^^>>^v>^<<<^<<>>^><vv^v><^<^^v<<v>>^<<<v>><>v><^^<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^v +^^<>v^><v>^v<>^><>>><<^v><^><<<vv><v^<v^>>^<vvv<><><^<>v><v^v>^<vvv^v<^<^vvv<>>>^v>vv^>v<v>^^>vv^^v^<vv<<<<v^^><>>><<><vv>v^^v<>^^^v>>>^><^<v>^<<><v<^^>v^^>v>^^><>>v<>^vv<<v^><^<<vv^^v^<^vv>^>^^v<<vv<>>vv<<^v<v>^<^<>>>v<<>vv^^v^<<^^>^^^><v<<^>>>><<>^^vvvvv^><<vv><v^v>vv<>><vv^<vvv^^^<<^><<v^^><v^^<><v^<<v^^<^<v^<^v^<^>v<v>vv>^<<>^^><<v<v>^^^^v<>>>^^>v<<<^<><<<^v^<>>><vv<v^v><><>^v^vvvv>><v<vv^v<<v^v>vv^^>^>v<v>^^v<>v>^v<><<<^^v<^<^^v^vv<v^^v^<<<v<^<<<<>v>^vvv<>vvv<^>>^<v>>^><<v<><^>vv<><v<<^^<v^v<v<<^>vv^v>v^<><v<<>^v^^>><v>>>>^>>v>v>v>>^<vv>vv><>^><<^<v<<^v<><^^>^v<^v<<>>^<>vv><>^<v><>^<^<vv^v<<>><^<<>><^<vv<v>v>vvvvv^<<v<<<<>>v<<^<^^<>>>><>^^<v>v<v><<^vv<^v^<<<v>^vv^v<^<<<<<^v<vv>^>><<>vv>vv<^v<^^><<<vv<vv^>^>v><v^<>>>vv>><v<^><^>^^v^^^<>v<v<v^^>v<^<<>><vv<<^<v<<>>>^vvv^>^vv<><>^^<^^<<<>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>^^<><vv^v<<^><>^^^<^^vv<^<>^^>><^<<><<^^v<v<vv^><^vvv><>>vv<^<<<<^<>^>^vv>> +<>^<v<^<<v^^<vv>^v^<^vv<^<<^<<^^<^vvv>^vvv>v^<>v^v^>><<<<<^^^^<<^<^vv<><v<<^^^<v<>>v^>v^>^vv>>^>^vv>vv^<<>><<vv^<<<>^>v<<^<>>^<^><v<^^>^<v^^>v<v^<>^><v<^^^^^v^>>>>^>v^<>v^^<vv^^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><<>>^^^v<>>v<^>v^v<v^^^^^<^>v>vv<<v^><>vvvv^vv><^>^v^v<v<<^v>v<vv^<v<<<^><vvv><>^>^vv<^v<>vv^v><<<>><^<<<>v<^>vvv<v<^^v^><>v<^v^>v^<vv^>^<<v^^<vvv^<<><v>v><>^>^^<<^<><><v<^^^>v^^>>>>>v<<>><<v<<^<v<>v<><v<>>v>v^^^v>>>^^>v<<v>vvv>>v<>>><<>^<>>>^<^^>^>^^^vv^<^><vv<<v>v><v^^><vv<>^v<^<^<v>v<>v^v>v<^<<>^>^>^>v^>^v^^^>^^><<<v>>>>^^>^<><^v^v^>^vv><>>>^><v^<>^vvvv<<vv^^<<^><v^vvv^<^<^v>><>><v<v>v^v>><<^^<^^>vvv><>^><<^vvvvv<<><v^>^v>v^v>vvv<v<<>v^^^^>^>vvv<v<>^>^^v>^v<<v>>>>v>><>^^>v<>>>vvv^^><^>>>^^>v>^>>>v^<<v>v^vvv><^vv>^^>>><<>>v<v>v^>v<><<>vv>v^<>>v<v^>v^v<>v>>v<^><vv>v^v<><v<^v<<<><^><vv>>>^^v<v^v^>^^^<v<<v^<^<>v>^<v^v^<^<^v<<v^^<>><<<^>>^v>^<>><^><vv^<^<^^^><^v<>v^v^<^v^<^<v^<v<^^^> +v<vv^v>>^^v^v^vvvvvvv^^vv^<>^v^<vv>vvv>^><v>v<^>vv><^<>v>^>^v^^<v<^<><^^>^>vvv^^>><>v<^><v>>v^>v>v^><>>v^>^<>>><>^<vv<^v^v^vv><>>^^<^vv^<<vv^>^vv^^<v<v<vv<^^<^<<^>><<^<v^^^<<<>^^v>^<>v^^>vv<^v<^v<<>v^v^vv<v>>>v><v^v^<v<<>v^<v><v<vv<<^^^><v^^<<<<><>vvv^>^v<<<<^v^>vvv<<>>v^^vv>>v^<v<<>>v<^>><v^<<^>^>vv>>>^^v^^vv<^<^^^<^<v^v^v^v^>v><^<v<>><v>>^<<^<><>><<<^>>^v^v^v<^vvv^vv<>vvv^^^<<>^v<v^><^^>vv<><v><>^<<<>>v<>^vv>^^^v^>v>>^v>>^>vvv<<<^<^<<<v^>v>>^^v^>vvv^<<^>^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<<>v<^>v^v<<>^<vv>>v^v^<<<^v>^^>><<vv>>^v>^>^v><^>^<><>^<vv^<v^<<>^^v<>^<>^^v^><v>v^<vvv>^<^v>>>^><<<^v<v^<v>^<<<<vvv>v<^v><^vv^<>v><>^v>v><>>v<^^vv^>>^>><vv<v<v^>><>v><v<vv<><>^^v>v>>>vvv><vv^>>>>^^<^^<v>^^^v<>^^v><<v<vv<<<^>^><><vv><>v>^v^>^<^v>vvvv<^><>>>v^<>v<^^<>^>^^<<v><<^>vv^vv<^v^><vvv<vv^>v>v^>v^v>v^<v^><<^^^>><<^^<>^>v>^>^<^><> +>^>^^>v<^<^^<>>>^<<vvvvv^><v>^<><<<v>>^<^v^<v<v>>vv>><v<v^^<v<<^><v<v<>>>><><><^<>^v^<v^>v<<<>v<<vv^^^<<<v<^vv^^<><v^><>^vv>>^<><^<>>^<>vv^<<<v^<v>><<>^^>>>>>^vv^v>^^<v^>>>v>vv<<^<^<>>^v^^^>^^<>v^^>^>v<^<>^<^v^>v<v><<<^<v<^<>>^><>><<v<<v<><>^>>v<<vv<v^^<v^><>><><v<><<^v<>^^^<^>vv>>^<^><<>v^^v>v>><<v><<v>^>v>vvv>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<vv^<^<>>v^vvvv<^><<>v><v<vvv^<v>^^^^^<<v>>>><<<>>vv<^v>^v^>^<v>^v><>v^>>><><>><>>>^v^<<v<^v<v>vv<<v>><<<<>>v^>>v>><<>>^<<v>>>>>v^>^^<<><^>vv<<v^<vv^^v><><v>>^>>^^^>>v^>>v>^^^>v^<<>v>^v^<^<^>v^v^>vvvv^^<<>^v>v>><>^^>v>>v^v<^>^<<^vv^<^<vv<><<^>^><<<v<^<>>^>>>^v^<v><^><><v>>^<^>><^^>^^vv>^><^v<>>vvv^><v^v^<v<^v>vv<<><>^>^^^<^^<^v^^^^vv<v<><^<<^>^<^>vv^^<^^>^v^<vv>v^<^<v<v>^v>>v><v^><v^v<><vv>^<><v^^<v^<^<>>>>^^<^<^v<^^v^v<^v^<><v>^^>v<^vvv><<>vvv^v<<v<><^<<<<v<vvv>^>>v>>v><^><v<>>v>v<<<v<^<>>>^<>>>vv<<v<<>><^v^v^<vv^^v<<^>^^<^^vv>^v<<>v>v<^v^v>><<>vv<<>^><v><v<^>^^ +<v>v>^>^<v^vv^v^v<v>>^>vv<>^^v>^>>vv<v>v^<^v<>>>vv><^vv<^^vv^><>>>v<<^<v^<^>>^vv<<>v^v>>>^^>v^>^<<^vv^<<^><^<v^>>vvv^^><>v^<v<v<v<^^>^v><<<^>v<<<<><^^<v<>^^<<v>v^v<vv^^><<^^v>^^^^v^vv^<v^^vv<v><<^<>v^^><v^^v<>^>>v<v^>>v>vv<<^^>^vvvv<<<v<><<>v>>><><>v<<<>vv><>v<^>v<v>v<<^><>^<^^^vvv><v^<>vv<><>vv<>^>^vv<><^v>^^<^<^vvv^<v<><>^<>^vv^<>^^v><>^>v^><>v<>^^>^^^v^>^<><>^^<>>>v^<>v<vv<<^>^>^v^<><^^><<^<^><<<^<>^<v<>vv>v<><vvv<v<><<>^^<<>vvv^v<<v<<^<v<v<<^v><vv><v^><^v>>^<^^^v^<v^>v^>^v<>><^vv>>>v><<>>vv^v<<<><<<<><>^><<<>>v^<<<^^<>>^<^<^><v<v^^<>vv>><><><<>^v<vv>v>v^<<>v<<^<v<<v>v>^v>>^v^<<<^v>v^<v<^v^v^v>><<^v^<>^v<><^><^>vv><^><>>v>^v^>>>v<>><>^vvvvv<>^<^<v>v<^v>><>v><^^v^vv>v^>^v^<<vv>^^^<^>>>v^<vv<^v>v<<v<<<^<<<^^<^<>^vv><>^v>>>v<<v<<^v><^<v<v<<<<<>vvv^<>vv<><^>v<>^vv^^><><v<<^>v^<v^v>>^><^>^<v>^vv<<v^<>^><^vv<^v>>v<v^<<<><<<^vv>>v^>v^v>vvv>v^^^^^<>vv>^<vv<<^^<v^^^v><vv<^<<><^>^^<>v>>^>vv<<><>><^vv<>^>vv<vv<^v>v>>>v>v>^<^v<>v>^^^^^v^^^v^>^^^<v^<<^^^v^vvv>^v<>v^>>^>v<v<v^><^^^>v>v>v>^>>^<<<^ diff --git a/day15_sample.txt b/day15_sample.txt @@ -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/src/main/java/day15_pt1.java b/src/main/java/day15_pt1.java @@ -0,0 +1,126 @@ +import java.nio.file.Files; +import java.nio.file.Path; +import java.io.IOException; +import java.util.*; +import java.util.stream.*; +import java.util.regex.*; + + +class day15_pt1 { + record Point(int x, int y) { + Point add(Vec v) { + return new Point(this.x + v.x, this.y + v.y); + } + } + record Vec(int x, int y) {} + enum Direction{ + North('^'),East('>'),South('v'),West('<'); + char c; + Direction(char c) { this.c = c; } + + Vec unitVec() { + return switch (this) { + case North -> new Vec(0, -1); + case East -> new Vec(1, 0) ; + case South -> new Vec(0, 1); + case West -> new Vec(-1, 0); + }; + } + static Direction from(char c) { + for (var d: Direction.values()) { + if (d.c == c) return d; + } + throw new IllegalArgumentException("unrecognised direction %c".formatted(c)); + } + } + public static void main(String[] args) throws IOException { + var input = Files.readAllLines(Path.of(args[0])); + var spl = input.indexOf(""); + var grid = input.subList(0, spl); + var inst = input.subList(spl+1, input.size()).stream().collect(Collectors.joining("")); + var height = grid.size(); + var width = grid.get(0).length(); + Point robotPos = null; + var boxes = new HashSet<Point>(); + var walls = new HashSet<Point>(); + for (var y=0;y<height;y++) { + for (var x=0;x<width;x++) { + var p = new Point(x, y); + var val = gv(grid, p); + if (val == '@') { + robotPos = p; + } else if (val == 'O') { + boxes.add(p); + } else if (val == '#') { + walls.add(p); + } + } + } + //System.out.printf("RobotPos: %s\n", robotPos); + for (var ch : inst.chars().toArray()) { + var d = Direction.from((char)ch); + var np = robotPos.add(d.unitVec()); + if (walls.contains(np)) { + // do nothing + } else if (boxes.contains(np)) { + moveBox(np, d, boxes, walls); + if (boxes.contains(np)) { + // do nothing + } else { + robotPos = np; + } + } else { + robotPos = np; + } + // Debugging... + // System.out.printf("instruction: %c\n", ch); + // for (var y=0;y<height;y++) { + // for (var x=0;x<width;x++) { + // var p = new Point(x, y); + // if (walls.contains(p)) { + // System.out.print('#'); + // } else if (boxes.contains(p)) { + // System.out.print('O'); + // } else if (p.equals(robotPos)) { + // System.out.print('@'); + // } else { + // System.out.print('.'); + // } + // } + // System.out.print('\n'); + // } + // System.out.print('\n'); + } + + var score = 0; + var res = boxes.stream().mapToInt(b -> 100 * b.y + b.x).sum(); + System.out.printf("Day 15 pt1: %d\n", res); + } + + static void moveBox(Point box, Direction d, HashSet<Point> boxes, HashSet<Point> walls) { + var np = box.add(d.unitVec()); + if (walls.contains(np)) { + return; + } else if (boxes.contains(np)) { + moveBox(np, d, boxes, walls); + if (boxes.contains(np)) { + // didn't move it, + return; + } else { + boxes.remove(box); + boxes.add(np); + } + } else { + boxes.remove(box); + boxes.add(np); + } + } + + static int gv(List<String> grid, Point p) { + var height = grid.size(); + if (p.y < 0 || p.y >= height) return '#'; // treat out of bounds as a wall + var width = grid.get(0).length(); + if (p.x < 0 || p.x >= width) return '#'; + return grid.get(p.y).charAt(p.x); + } +}