- commit
- f2c82a8ae57c7a051eed87cde809dd6d66f5b340
- parent
- 0e4eb86b03c05b4ec8569d78acfeb5d36dda14b3
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2024-12-15 08:35
2024-12-15
Diffstat
| A | 2024/15/input.txt | 71 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/15/solution.rs | 220 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/15/test1.txt | 10 | ++++++++++ |
| A | 2024/15/test2.txt | 21 | +++++++++++++++++++++ |
4 files changed, 322 insertions, 0 deletions
diff --git a/2024/15/input.txt b/2024/15/input.txt
@@ -0,0 +1,71 @@ -1 1 ################################################## -1 2 #...##...OOO.#.O.OOO......O###...O.#..O.......O..# -1 3 #....O...O.....O..O#O#O.O....O...OO#OOOO....OOO..# -1 4 #..O.O..O.#..#...O...O.O....#....O..OO.#O#..O....# -1 5 #..........OO....O..#OO...O.O.O....#..O.......#.## -1 6 #OO.......O.....OO.....O.....O.O.#...O..O..O#.#..# -1 7 #....#..O.#.....OOO.O......O....OO.O#OO.O...O.#.O# -1 8 #.O#.OO....O#...OO...O.O..........O.........OO..O# -1 9 #OO.O#.O...O.O..O.....O#O.O..O...OOO...O....#OOOO# -1 10 #..OO.O........O..#....OOOOO..OO...O#..OO##....OO# -1 11 #....O.O...#.O....OO...#..#...O...O...O.#..O.O...# -1 12 ##.....OO#O..O.....O##.OOO....OO..OOOO.O........O# -1 13 #.#.#..O...#.OOO.O.......O.OO.O...O#....OO....#OO# -1 14 #..##.O.#..#..O..O...OOO...O..O.OOOO...O.OO.#...O# -1 15 #....O..O#.O.OO.O.........O.O.O.OO#.O.#O#..OO#.O.# -1 16 #.....O.............#...O..O..O#.O.OO..O.OO..O...# -1 17 #.#..O..#O...O....#..O.#.....O.....O.........O...# -1 18 #..O..O..O#O.....O....#.O...#OO....O.....#.......# -1 19 #O..O#......OO...OO.O..O#OOOO........O.OOO..O..OO# -1 20 #OO...O.#...O#O..#.O.#.#....O.OO....OO.O..O.O..O.# -1 21 #.#...#.O..O..O.......#.........#.O.O.....O..O...# -1 22 #O.O..O...O...O..O.O.O.#..#O..OOO....O....#..#...# -1 23 #...OO#O......O.O..OOOO#.O#........OO..#O.#OO...O# -1 24 #O#....OO...O#..OO.#.OO....O...OO....#..O...O.O..# -1 25 ##...#........#..O....O#@O#O........O.OO..O#.O.O.# -1 26 #OO.#....OO.O...OO...OO..O....O.O.O...O#...O.OO..# -1 27 #.OO#..#..#O.O#..OO.#O.O#.OO..OO.#..O......#.....# -1 28 #.#..O.O..#O..O....O....#...OO......O......O#..O.# -1 29 #O...#.O#....OO....O...O.#.......#O....O.O#.O....# -1 30 #....#.O...O...O........OO.#.O..O......#..#..#.O.# -1 31 #..OO....O..O.#........O..#......O..O....#OO...#.# -1 32 #..OO.OO#...#..#.....#..O#.#O..O.O...O.O..O.O....# -1 33 #O.OO....O..OO.#..OOO..OO##....#.O...OOO...#....O# -1 34 #.OOO#..#........O...O.O.#.......OO..O.O......O.O# -1 35 #.......OO..O.O........O...OO.....O.....#.O.OOO#.# -1 36 #OO.......OOOO.....O....O.....#.#...OO........O.O# -1 37 #..O.OOOO...O..O.O#.OO.OO.#...OO#.OO......O..O.O.# -1 38 #.O.O.#.O#..O.O.O...#O...O...O...O.O.O...O.#O#O..# -1 39 #OO#........O........OO..O#O.......O..#...O......# -1 40 #.#.#..OO.OO..O....#OO....O.OO...O#.#....#.......# -1 41 ##.#.O#O..OO.O......O..O#.......#OO#.......O.OO..# -1 42 #.....O..O...O...#OOO.O.O...O...O..O..#...O...#.O# -1 43 #O.##O....#.O...O.OO.......O.....O..O.O..O....O..# -1 44 #.O...O.O..#O.#.....O..OO.....#O....O.O..O..O.O.O# -1 45 #....#O..OO.OO#.OO...O...#.OO#...OO....O.O.......# -1 46 #.O..O....#OOO..O......##..#O.O.......O...#O..O..# -1 47 ##O..O...O.O.......O#.......#.O#.O.O.O#..O...O.O.# -1 48 #O.#...O.O....#.#.....O.....OO.#.O.#...#.....OO..# -1 49 #.O.OO.O........#...#.......OO#....#..O#.O.......# -1 50 ################################################## -1 51 -1 52 ^^vv><<><><^v^v^v<^vvv><v>v>v>^v<<v>^^^><v><v^<v^v^^^<>>>>>><vv<^>v>>>^>^<^v^^^>^<^^v<<v<>>^<>>>v^<>v>>v^<vvvv<v<>>^>v>^<v^^>^<^>^<vv><v<<vv^>^>><<^^>^vv>v^^<^>v^><>>^<<^v<^<<vvv<^v<^>^>^>v>^<>v>>vvv<<v<^>>v>^v<^>>^<^vv><v<v><<>>v<^>^^^<><vvv^<>^<^^v>^><^vv<<>^^^<>v^>v^>v<^>^v<v^v><>><<^^^^><^<><>^vvvv>v>v<vv>v^v^>>vv^^v><>^^>>>>v^v>v>>v>v<<<>vvv>^v<^v^>^>v<vvv^^><^><^>>>v><v>><vv^<v^><v>^<^^^>^<v>^>vv<^>><><v^<>>>^>^^vv^<v<<<vv^>v>^><>^>^<>^>^><<^<<<>v><v>v<<<v<v^^^^<>>>^vv<<<<v<^v^>>>^^v>vv^^<<v>>^>^v>^^<<^><v<<vv^^>v>vv^v<>>^>>^<>>>^>v^^<<^v<>^<>><<<^v><<>>>><^^>>^>>><^vvv<v><<>v<v^v<^^v^^<>>>v^>^^^>v<vv<>vv><<>vv^<^v^v<^vvv>^v>>^^^<>><vv>^^>^v<>v>v<>><vvv><v^<^>^<<v>v<<v><v<<>>>v>^><<><<>^v<<v<>^>^^><^<^><>>v>^>v^v>vv^^<<vv<^>^<v>><>vvv^v>><>v<<>^<>vv<^v<v^<v>^v^<>^>>>vv>>^<><vv^<<><v>v<^vv<^>>v<v>^^^><^vvvv>^vv<vv^^<v><v<>^^<<v<^><><^^v>>^<^><v>^v>v^><<vv^>^<^^^>>>^^>>v^>v^^><><vv<^>^<>^v^<vvv<>v<>v<<^>v><v>^<>^^v^^v^<>v^vv^v^>^v><v>>v>^>^v><v<^>><<>>v^>>^<vvv^^<<<^^<v^>vv<<v^<<>^ -1 53 ^>>v^<>v>>>v>v<<^<><v<v>>>v^<<>><vvv<><<v>>v^><^vvv<v<vv>^^^<^><<v><^<>>>^>>vv^^<^v<<<<>v>vv><v<v^<^^^<^v^vvv^<><>>^>^>>vv>vv<^^vv<v<v>><<vvv><^<<^<>><vvv^^<<><^v>^^^><><>>v>><^^v>^>v<<^>v>v>v<>v<^<^>vv>vv^vv<>v>^v^v<^^^<^^^^<vv^vvv^vv^v><vv<v>^v<<v<<<<<vv<^^><^v><<>v<^^^^>^<<v>vv<^<<>>v>v<><>^v>>v>><vv>>^>><>^<vv^vv^^<^>>>v><<^<>^^^>^<v^>v^><<v>^^v>>^>^<vv^^<>>>^><<>^^<^<v^v^<<^<^vv><v<>v>><<<<^^vv^^>v^v^v^>^<vvv<^<v^>^>>v<v^>v<>^v<^vv>^<v^^<^>>v<v<>v<v<<>^v<>>^>v<<v^><<v><<><v>v^<v>><v<<v^v>^^^><<^^^>v<v^><>^>^>^<<>v>>vv<<<^<>><<^<v>^v><vv><^<v<v^v<>v<vv>v>vvv>^<><>vv<<>vv><^>>><<><<v^v><>v>^v><<<v<^v<v<vv<^^vv^^vvv>^<><vv^v>>>^>>^v>^v>v<^>v^^><^><v>v^<v^^vv<^v>^>><^><v^vvv>^<^^v^v>>^v>>^^<^<>^<>>v<>>^>^^>^>v<v<<><^<^vv>^>vvvv>^>v^<<vv>^v^><>>v^v<<^<v^<^v><<^<<<>^<<>v^<^v<>>vv^vvvv^^>v<><^^>v<vv<<>v^v<<<<v>vv>v^v>>^<<<v>>^v>^<^^v>^^>v<^v<><>>><v^<<vv>^><<<^^>><^^<>>>^<<^<<^^<^^>^>vv>>v>>>v<><v^<>^><<<^^^<>^<<<<<^<v<v<^>vv<vv><^v><<^v^v<vv<<^v^<^<v>><<>^<<<>v^<^>v>v^vv<<>v<><<>^^^<<^v -1 54 ^>^<v^<<v>v>^v<<>^^^v<v<^>>^>^^v^<<^v>^^v<<vv<>v>^>^v^<v^>v^><v<<>^<^^v<v^>v>v><<v>v<^v>>vv^>^^<<v<vvvvvv>^^v^>v<>^^v^<v>^>>^vv^v<><>><v>><vv^><<vv><v^^v<v<^^v<v^v>vvvv^<>^>v^>v^^>vv^><<vv^>^^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^vvv<<>v<<<<^<^v>v>vv>v<vv<><v<^>^v^vvv>v>^>^>>>>vv>><v^v^^>>v>v<^<^<>><v^vv>^<v^>v<v<<>v><^^^<><<>>v><v<v^^><>v^>>^>><vv^>>v^^<>v^^^>^^v^vv^v^<>vvv><><><<>><>^>>v<>^^v^v^vvv<v<v<^v^vv^vv<^>^v>>^>>^^>v<^^>>^>^^><><^^>^<^<><v>v>><<vv^<>^<>>>>v<><^^v>v>^^v>^<v<>v<^>v>^>vv<<^><^v^vv<^^<v<v^v^v><<^^v<^>^<>><v^><<^v>><><v>^<<v<^>^^^^^<^<><^^^v>v><>vvv>>^<v><^<^><<^^^^v>^<<>v^^^<<<<<^v>^v^<^<v>v>v^v^^<^^<><v^<v<>^^vv>v<vv^^<^><<>^^^>vv^^v<<vv^<^<^<<<^^^v><^^^<>vv>v^v>v<<>><v^>^>>><><<^vv>^^<^<v^<vvv^<v><<>^^>^^>>v<^v>>v^>>^vv^<>v<<v^v<<^v^v>>^><^^<v^^v<><<^^>^<^>v>vv>>>>v>>>v^^^>vv>>>v<><^>>>^<v^<<v<>v<v<<vvvvvvvvv^^<>>^^<<<<vv<><^^vv<vv<^^<<>v^v^>v<<v<^>>^^^<<^v> -1 55 <>>^<<vv>><v<vv<>>^><>>>v^^^>v>v>^v>vvvv><^v>^<^>^^vvv>vv><<v^>>>><^v<^v^>v>vvv^v<<v^<^v>><<^<<^<<^^v>vv^^><>v<^><<<>>vv>vvv<^v<>vv<v>>^<<>^>v^v<v<<>vvv^^v>^v<^<>^<>^><>v<><<^>^<v<^^^<>^<v><vvv>^<^v<vv^^>^^^>>>v<^v<<v^v<v>v^>>v>v<vv<>vv><>v><^^^^v>>v>v<^v>^v^>^vvvvv^<v^v^vv>v^<<^^><v<^v^v>>>>^v<<^^vvv<v>><v^>^^v^>>^v<v<<<^v^<^^<vv^>v<<>>v<v<<><v><v<^<>v>v>^<><^^v^^>vv^<vv^<>^^>v^><<>><<<^<v^v<>>^^^<^^>^^<v^v<<>v^^><^<>v>vv^><>^>^^^^<>>v^^v>><<>^<^v><v^v>>>vv<v><vvv>^<<<<v>v^>v>^v<^>v<><>>^v^^><^vv>^^<^^><^>vv><v^>>>^>^>v><^><vv<<<^<v<>>v><>^><v<><^^v<>vvv<<>v<^>>v<>>^^<^><<^><v^<<^^<>v^<^^^>^^<>v^>^v>>v^^^>>vv<vv^^^v>^><<>^>>><<<v^<^v<^v^v^>v^^v>^><>^^<<v<><>^vvvv>v<^<^>^vv>>^v^><vvvv^^<^>>vv<v<^>v<^>^>>^^<vv^<^<^<v<><^<<<^<v<<^^<<v><>^v<^^<>>vv<^^>^<>>v><>>><>^^v^>v><>>v>^vv^<^v^><>>v^><>^><^<<<v^^>>>^><vv<>>^<^>>>vv<>vv>v<>^><<^<^^<v><^^^^^<^>>>>><v<^>><><^^>^^<><v<<<^^<v^>^>^^>^>>><^>^><>v<<>><^<><>><v>>^v>^<<vvv^<>^vv>v<>^><v^><^^>>>^<<^v^v>v^<>v>>><^^>vv^^^>>^^>^^<<>><^><><v^v><^> -1 56 ^v<<^><><^>>>v<><<<<v<v>>v<>v<vv><^vvv^<^v>vv<v<^^vv^vvv><<^v<^^vv^v^><<><^><^>^v<>^v<^^v><><>v^<<<>v^>^>><vv^>^^>><>^>v^><>^<>^><<^^>>>v<><v><vvv<^>v>^<<vv>^^v><vv<<><>vv>^v^vv><><^^v^<v>vvv>>^<><^v>^>v>>vv>v^>>^v^^^<v>^^v<<>>v<><>v>^v<vv<v^>vv<<><<^v<>>^<<<^v^^<v<><^<^>^<vv<<>v<>^^v^><<><^<vv<^>v^>^>^<<<<<vv^v><vvv<^^<<<^^^^>^v><>>^^>>^v<<v><>><^<<>v<<^v<v^>^v<><^^>v^^^v^^<^<^^><vv^<>>v>v^<v^<>><<^^<^^>>^^^^^vv^<>^><<<><<><>><v>^<>v^^<><^<v<vv<vv<^<v^><vvvv<^<vv^^>^>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><>><>^>v^^^<>>^v^<^v>v<^<<<<^v^v>v><v<<v^<><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<>vv<^<^^<<>>>><v^><^>v^<>^<v><>^<>><<<<>>^vv<<v>>>vv^vv<><<^<vv^^v<<^<^<>^>vv^^><^><<v<vv<<><v<<^>vv^>v^>v><>vv>^v>>>v>v<>><^^<^v<><>>>^vv>^>v^vv^v>^v>v><><<^^^><>><>>>^>vv^<v<<<^^<>vv>^><>><v^v^^^^v^vv>><^<<vv<<<^<<<v><>v>> -1 57 ^^v^>^v^>>>><^<^<<<<^^v<<>^v>><<v>^v>^>><<<v<<<v^<<^>><vv^>>^>vv^<>v>>^^>><><^^<>^vv><>v^><v<vv>><^>v^^^^^v<<<v^^vv>><<^v<^<^^vv<^>>v>><^v><>v^^^<v^^<><^>^v^>vvvv><<>v><^<v^^>^<<><>v<v<<v^^vv<v<v^><<^>>^<<>^<^v>v^v^v^^<>^<>><^<^>>^^<>><vv<v^v><^<^^vvv>^v<<^v<v^^><>><^<vv<v^>^v><^v^vv<^v>^<>><^^<><v>^>^^<><^v>^^^^^>><v>^^<v^<<<><<^^<>><<>^>vv<v<>>>^v<v<v<>v<^^v^>v>v>^><v^<^v>>v^v<>^<^<>><^^>>v^><v<>>^>^^^^>>><<^<^^vv^^<<vv^>^v>^vv<^v><<vv^^^><^<<v^^^^><v>>v<v>^<^<<^v^<<^vvv^v><<^<>^<^^^v<<v^>vv<<<^<<vv>^^>^>>v>^v>>v>v>^^<v>^<^>v^vv><^^<^>^v^vv>v<v>^^v^vvv><v^^>v<^^^<v^^>v<v>v><vvv<><<^><<^<>^^^v>^<v<^>><vv<<vv><>^v>>vv<vv<<<><><^v^v<>v^>vv><>v<<>v<v>^>>v<vvv>^>^^^<><v>^>^^>^v<v^^v>vvv<v^>>><v^<<^^vv^^^<>^v<^^><^><^^<^>v^^>><><<<^><^^v<<^>^<^>^vvv>>^v^<v<^v^<vv>>>>v><>>^<^><><>^^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<>vv>^vv<<v<^>^<>><<v>v^^vv<v>vv>vvvv<v<v^<><<^>v<v<<^^vvv<v^>^>^v^>^<>v<><><>> -1 58 ^>>>><<<vv^^^>^>^<<>>>^><<v^<>>v>^><>><vv<^>v<>^^^<>v^^v><^vv<^v^<^v>>^>^v<v^v^^v>^v^<<v<<vv^^^vvv^<v^>>><vv^vvv>^v<^>><^^^^vv<>vv^v>vv<v<<vv<^<<vv<<>>vvv<<>v<>vv<vv^^<^^v<<<>>v><^vv^<>v>^<^v>^<<<v<vv>^v^>>vvvv^^<>v<v<<v^<v<<><^v<^^<<<>>v>>>v>v>>vv<>vv<v^^^v>>>^v<^^>v<^v><<^<<<<^>^v<^^v>v^^<^^^<vv><>^^<vv<^vv^<^^>><>>><><v^^>>^^<^<^v<^>v^v><^vvv^<v>v<>^<^vv<><v^>>^vv>^v>^^^<<>>^><^>^^<^>v^v>>v^v>>^^<>>>>>>>vvv<^><^>^v^>>v<^^v>^v<^<>v<^^v^^v>>^^v^<v>v><v^>^<v<<v^vvv><v^>>^>v^>vv^>>^^<<>v>v^<^v>>>^<>^^^><><v^>^^^v^>v>^><<<^^^^^<>>^<<vv^>>><v>^^<^><vv><<^v>v<>vvv><>^<^^>><v><v<^v><^v^<^>^><^v<vv<^<>vvvv>>>vvv^<><><>^v>v<^v>vv^^v>v>>vvv^^v^<vvvvv^^<<<<v^<><<><^<>^>^>>>v<>v^>><v>v>v<v^^<vv<<v<>^<^vv<^^<<<^v^v><<v>^<>v>>v^v^^vv<^>^>^vv^>^<vvv>v>>>v<^>>v><<^>v^vv<<>>^^v><vv<^<<v^^^^v><<>vv><v^<><vvv>vv<vv^><^^^<v<v<^<<v>>><<v^v>>v^<vvv<v<>^<v^^<<<><<v>><>^>^<^<v><<<>v^^vvv^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>v^<^><^^^^^<>^<v><>^<>> -1 59 vv>^<vvv^vv^^<vv^<<>>^<<^^<<v><>^^^v^<^<^^v<><v>^<^><<<^v><v><^>^v<v>>^vv^vvv<>^v<<>>^>v^v><>^^v^>>>^><><<><v>^>>v<<v<v^^^>v><<<<<v<<<^><vv^vv>><<^^>v<<^>^^><v^v<^<^<^^^^<^^<v^^<^v<^>>^v<vv<^><>v^<v>vvv^v^^v^^vv><>>>>^^>v<v>^<<v^^><>>v<^<<<^v^>><v>>^v>^<>>>^^^>>v^>v^<^<v>^v^<>>><v^<>>^v<<vv^>v<<v<>^<^^<v><vv^vv<>>^v<<^^>><v>v<<>>>^><^v^v>><v^<^>vv<<^v<<v^^vv><>>>v^v<<^<>v<<vv^<^^<<>v>>v<v<^>>v^^<^>v^^<><<>>>^v<>vv^<>>>^<^^^^>^v>vv<<>^<<v>^<><v^<>^<<<^>vv<<v^^<^^^><vv<>^<^>>><>><vv^^^v^vvv<v^>v<v<v^>><^vv^v>^^><vv>^^^^vv<<^>>^>^^v>vv^><>>^><>>><^>><^>v^^<><>vv^<><<>^<>^v<><^><^v^>vv><<^v>^v<>>^^v^<^^^<^v><>^^^^^>>^^<>>>vvvvv>v^v<<<>>>vv^<^<vv^><>><^^<^<^^<<^>>^^^<>>><>^^vv^<^v>vv<<<v<v<vv<<>>vv>v^^vv^>^<^vv^v^v>v><vvv>>v^vv>>^vv><^v<<^>>^^^<<<<^<^v<><<v^v>>^v^v<v^>>^^v<^^^<^^<<<<^<>>^<>^>v>^v><^<^>^><^v<^^^^^vv<>^^<v>><v<<^vvv>v^>^<^><^vv<<<><>^>><v<v<<<v<<<>^^<>^><>v><><<>v><<>vv^><><>v<vvv>vv^<>^v^<^vv>><<^<<^v<<<>vv^v<v<vv^^^>>>^>>^>^v^^<v<<<>v>>v^^vv<^>>>vv^>^^<v>>v<^><v^^<>v^^<^v^> -1 60 ^<>v>vvvv>^><v<^<<v><<<v<<^^<<>^v<>v>>v>vv^>v<v<>^><>v<<v<<<>vvv^><^>^><><^v<>>>v<<><vv^vv<<^<^v<^>^>><<^^^<>vv^^^>^<v<^<<<>>><>>>v<>>v>>^^v^<>^<>v^>vv^>><<vv>^v^v><^>>v^vv<^vv<>v<vv>^<>>>^>>>><v>>^^<<>>>v<<>v<^<^^>^<<^><>v<<^v^^^v<><^v><<>^^v^^^^>v><^^v><^<^v^>>v<^>^v<<v^^^>>^v^<><>^>v>v>>>vv^>>vv><>>^>v<^^>^<>^v^v>>^vvv>><<^<>^><<>^^<^v^^^v>v^v<v^^^<v^v^^^vv>>vv<><v^v>^<><<>>>>v>v^<v<<<v^<<<<vv>^^vv><^^>^^^<<<v^^<^<^v^<^<>><>^v^v><<v<<><<>v<>^^>^^>vv<v^v<^vv>^>>^^v<<<>^v^>v>>^<<v^><><<<<v<>^<^<<v^^>>^>>v<>v<^<<>>><v^^^<v^>v<^v^>^^><vvv>v^^^>^^vv>><<v^^><<<^v<^^v^<v>v^^<<>v>vv<>><>v>v<^v^<<<^>>^^^<^v^v^><^>^<<^v^v^v<>v>^^><v<<><><vvv^v>^<v><><<v<<<^<><>>><>>v><v^^^v>^v<^v<<<^^>>v>^<<^>^^v>>^^<vvv<<<<v>^^><vvvv<>^v^vv<<^<<<<>^^>v<v<^v><>v>v<<>^<<v^v<v<>v>>^<>v><<>vvvv^<>><>v><>v^v<>vv>v>v^v>>^<^v>^>v>><v>^<vv^vv^v^^><>>>^>><>^^><<>v><v^<<<^v<<<v<v^<v>^<>^>>><<v>vv<vv<<^v>v^v<vv^v<vvvv^v>>><<<>^^^<^>>^<vv>^^^>v<vvv>vv^v<<><v<^^<<><^<<^vvv^<^v^v^^<v<>^v^^vv><vvvv><v<<v<v<^^<^v><>>v<<<>v> -1 61 <<^^<^>^v<v<^><v^<><vv^vv^<v<>v><vv^<^v^^>^>>^vvvv>v>^v^>^><^^^^v><<<v>^vv<^<^^^v<^^<><>v<v^<<^^<>><>vv>^v><>v^>^<v<<v<<>>^^^>><<>^<v>>>v>^>>^v>>vvv^^>><^v^v^v<v<<><^<<<vv^<v<<<^v<v<<v><>^v<vvv>^><>>>>>^vv>v><>^<>^^>>>v><>>><<<>>^>><v^v<<^vv^>^>><<^<><vvvv<^<vvv^<>>^<^>>>>^v<<^^^^><><><<<<^^<^v><><<<><^<>>><>>^<<^<^>^<^^<^>^>^><<^<vv^>v^vv<^<vv^^vv<<>>v^<^<vv<><vv^v<>><^>>v<vv^^<^>v><^vv^^<^<<v>^<<v>v>v<v>>v<^>^>^^><<v<>^vvv^><<<>^><^vv><^<<>^><<^^vv<v<^^v^^^^>^v<^v<<^^^<^^v<>><><^^><v<<>^^v>v^v<>vv<v^>>^<v><>>vv><v^v>>vv>v>v<v><><>>>>v><vv>>>^><><^v<>v>>>^^^>^v^v>^<<>^>><vv<v^v>^<^<^^<vv>v^^v>^><>>v^>v>>^v<>v>v^^<<><^><vv<>>v<<^>>^v^>>>><^<<<<^<v><v>v<<v^>^v>>v<>v<><<vv>v^><<^<^v<^<^>^>^vv<<vvv<v><vv>vv>^v><>^<<vvv><^^<<v<>^v<<^<<^v^>v^vvv^v>>>v<^v>^v<v>v><<^<vvv^v<^<vv^v^^>^<v<^>>v^<<<^<^v>^v^v^<v>>^^<^v^^v^<<^<><^>^^<>^>vv^v<<^v<^vv>v><>^^^>>v^>^<^v^<^v<><v^^>>>^v><>>^v^>^><>>><v<<v<^^^><vv^>vvv><^>vv>^^^<^^<^v<v^vv^<^^<>vv^v<<>vv<<>>^^v><<v>^v<<<><v^^>^<v>><^v<vvv<v>^^^>><<<<^<^>v< -1 62 <><<<>^^>^^v^^>^^^vv>^>>^>v^^^v<^<^>v<<><v>^>^v>^<^<<^vv<<>^><<vv^v<v>^>^^<<^^<^<^><><^vvv><<>>>>>^>><>vvvv>^v^<^<^^>v^^v^><>v<v^>><>>^<>>^<v<<<v^><vv><v<v<<v^^>^^v<v<v^<<v^vv<<<v^>^v<>>v<v>^><^<>>>vv>vv>^v^^<<<vv<^>^^<^v>>>>v^><^><<^><>>><^^^v^^>>>>^>>v^^>><vvv>v^<<>>^>v<<<v^^<^v><v^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<>>vvvv<v>v^^><^<<^^<vv<<v^<>^<<^<v<^>^v^v^<v^<^<><^v^<^^><>><^><^<^<<><vv<^><^<<v<^^v<v^vv<<v^^v>>v>v<<<^>><^^<<>^v^v<v>>^>v>v^>^v^^v>>>^>v>v^<^v>>^^>><v<v><<>^^>v^^^><v^<>>v>>>^vv^v>><><>><>^vvv^^><>vv><<v<v^vv^<v<v<^>>>v^>>>^>v>vv^^^vv<<^<>><v<^^^^<^v>>v^^^^^>^>vv<^^><>><v><^^<>><^<>^v<>vv>>>^v>>^<<<>^v>>^vv<<<<v<>v<v>>^^^v^><^^>>vv<>^<>v^<>>v^vv<<^v<vv<<<>>v>vv><><<v<<^^>^^<vv^^<v>>v^>v^<<<^>^^^v>v>>v<>>^^^vv<>^<v^^^^vv><^v<v^v<>>^>^vvv^^^<v<<<v>>>>v<>^<^vv>^v<>v^v^>v>^^<^^v>^>>v^vv^^v^^<^<<<v^^>^>v^><<<<><v>>vvvv>vvv^<><<^v^v<<><>v><<><>^>>><<<v^<>v^v^v<v<^<>v>^<v><v<<>>^<v<< -1 63 vv><>v<><^><>>^><><^>v><>v<<^^^^v>^<>>^<^^^^<^<>^<>>>v<vv<>>^><<vvv^><<>>>>^vv^><>^>^>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^>vv<<>>^v>v>^v<<<>^v>>v<>>^>^v>^<>vv<v^<><>v>^^>v>v<><<^^^<v>^<<vv^><<vvv^<>vvv>>><vv^^v^<<v>^v>>>>><><^v<^<<<<<v<v^v^>v^vv^><vv>><<>v><>vv^<>^<>>v<<<><<vvvv><><>^>v^v<v<v><vvv>>^><>>^<>^vvvv>v<<<vv<><v><v^>^^v<<>vv^>>>>>>v^^<v><^v^^<^v<<^><<><^^^v>vv>>><>v^<>>vv>^<vv^<<<<v<>vv>v<v<<^<^v<><>^>>^v^v><v^<^<>>>v<<^<^>vvvv^<>><<>v>><>^>^<><v^^>v><v^>^<^vv><v>>^v^^^><<^<v<><^^^^<vv>>v<><<<>>^vv^<v^><^<v<>><>>^v><v^^>v>v^<vvv^^v>>^<>>><>v<>^v<^^^v><<v>^<>>^><><>v^^>><^<^^^>v^v<>v^v>^><v^<^<v>^>vv<>v<^^<v>>vvv>^^vv^><v^^>v<v<^>v<v<<<^v>><>^<>vv<vv^<<vv<^v^^><>><<<v^<<^>v>^>v^><^<<v>><v<^^v^v>v>>><>vv^v>><<v>^>><^^^<<<v^v<vvv><<<<^v^>>v^>><^>>^<<><v>>^><>^>>^<>vv<^>^>v>^>v>v^<<<vv^v<^^vvv<<>^v>^><v<v^vv^<^^<<>>>^<vv^<v^>^v>>^^^<>^v^>^^^^><<vv^^<^^vv<><>>>v<^^><v<>>^ -1 64 ^^>^^v><^><^vv<<<<^>>><v<v>^>vv^<>vv^vvv^<>>v<<v<><^<v^^>^v^^^vv>>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<vvv>>v<vvv<^v>vvvv^<<^<^vv><<>^^^^v<<>vv<><vvv<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<<^>vvvv<v<<<<vv>>^^^<>v>vvvvv^v>>^<<^>^>v^<^>^v^^><^>v^<^>><^^^vvv>^<>v>v^^^>^>><<<><><<<^<vvv>^v^^<<^<^v<<<^<>>>>vv^><><v^>^v<^^>v<<v^<>>v>^<^vv<<vv><><><^v<<<>^>v^v<>v^^^^>^^>^<<>^><<^>^^^>^<^^<>><<^>^<<<v^^>^^<>^v<^><>^v>v^<>>^<<vv^^>>^^^^v<v^v>vvvv<<>v>^<<<>>v>^^>v><>>^<v^v^v><><<vv<><<<^^<<vv^<v^v^v>^vv^><vv>^v<^v<v>>^^<<<><<<v<^>><><<<<v>>^v^v<>>>v<><^^vv^v><>^<>vvvv>>>>>^>><<^>vvv^^v^>^>><<<^>^<>><vvv^>><v^<vv<^v>>>>v<^<<><^<^^>v<>>v^^^<^<vvvv<<^>>^^<^v>v>v^^v^^>v<^^<>><>>vv>^^>vv>v>vv<><v>^v^^v<^<^^>vvvv>v<<<<<^^<<v^><^>>^^v><<^>^^<v<<v<>^v^>>>^><vvv^^v><>vv>^^v>vv>v^v<<^>><<^^>^^><^<^>^>^>v>^<<><^>^^<^< -1 65 vv>>^<v>><<<v>>^>><>><<<<^<^<<^>^>vv^v^<v^^^v>v><^<^>v^>>^v^<><<<^v^><v^vv>>>>v<><>vv<><vv><><<^<^<>><<^>^v><<vv^vv<^^<>v<>v>^>^<^<^>><>^^><vvv>v^<^<^<>v^><<<>>v<<<v^>^<>>>^v>v>v^vv><vv^>^v^<v><v^v^<>>^vv>^>>v<><>v>><^vv<<<<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>^v><<v^<><v><v^><^<vv^><^<<v>><><^><>>v^<^<^>^^<^>^^<>>^<vv>vv<<>^<vv>>^>^<v<>v^<v><^<<v<^^<^>>^vv>^>vv^<vv<^v>v^v<vvvv^^>^^v>>>><>vv>^vv<>v^><><v>^v<<^>v<>^><v<<^vvv^>v^<<v^^>>>^^><^<<v^v>vv>v<^<<^v<>>^^<^>^^vv^^^^<^^<v<^v>><^<>^vv^><>>^v<vvv>v^^^vv<^<>>^><<>v^^^<>>^^<v^<vvv<^<<v^v<v><<v<<^>^v^><>><>^^^<><>>>v>>><vv><vvvv>^^^<^<><^^^>^v<^<^<>^^<vv>^>^v^><>>v<^<^>^><v><>vv>^v^>v^^v<><<v<><^<<>>^>^>>>v^><<vv<>^<^^v>v<<v^>>v>>^<vv>>v<v^v><<^><<><^^>v>v>>v^<><^>^<^v<>^^v<<<v<>v>>vv^><><>>^v<v>>>>^v^vvvv>><v<v<>^v<<^<v^<<v^>^<>v><<<^^^>^<^^^v>^<^^vv><>v^><<<>>^v^><<>>^<v<^^v>^>v<<<><><v^vv^v<vvv<>v>^^^^v<v><v>v>>^>^^> -1 66 >^^v>><vvv<vv<>>vvv><>>^>>v>^v<^^vv^<>>v^^v^>>v<>^>v<^v>^^>^><><vv^>v>^vvv<<v>^v^<<>v>><^v^v>^>v^<v<^v>vv^>>v><<<<<^<vv^<>^>^<>v>v>>^^^><<^vv<<>v<><^<v<><vvv^v<^v^><<<v>vv<vvv>v>^^^<>><<v>><<>^^<><vv<^<<vv>^<<><>><vvv^>^v^vv>^^<v^<>v<>^^^>^v<^^>v^^<v>^<<v^vvv<<v<^><<v^<<>^^<><>^<><v^vv>>^^v>>v^><<<<vv<^<<vvv>^<<><<^>><>>><^v<<^^^<v^^vv><>^<>><>>v<^><<^^^><>v<<>v<><<^^v>^>>>v<>vv<>v<>^><v^^><v<>^v><><>><<^><v>>^>^><<v^>>v<v<<<><vvvvvvv><>vv>v<>>^><v<>vv^<><v><v^v>^^^^v<>>v>><<><v<v^<v^><^>>>>^<<vvv>^>v^>v^<v<>vv>v^<<<>>v<^<vvv^v^<><><<vv>v^<v<^v^>><v^>^^vvv^<><^^>^^<>v>^><>><v><>>vv<vv<^^<>v^v^v<<v<<v>><<<>>^^^vvvv>><<<v<>v>^^>^^<vv>^<<vv>v>v<><<^><<<v^<v^<vv^>>v>><>>><^v><<^<>^>v<<<vv^v^>^^^>><<^vv^<v<>^^>>>v<<^^^v>^^vv>v<<^><<vv^^>><<^<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^vv^<^>^<<v<<^^<v^v<><v<v<vv<vv<v^^v<^>>^^v^v^^<>>>>vv^>^><v<<v<^vv^>>^^^>v^<>^^<<v<^v^>^^^^<>^<vv^<>^<<^>>^><v^v<v<<^<><^vvvv^v<><>v> -1 67 ^<<vvv><<<<^<<<v>v^v^^<>>v<v^^v<>^<^v><>><>^<^><^vv>vv>^<^>>v^^>v>><^>v><>>^^^<<v<^<>^>^>v>^v>^<>>>>>vv^v^^v<<>^^<vv>^v<v>>^<<v<<<>^<<<^vvv<v<^<><^v<^<><<^^^<v<<vvvv<^>v<<^^^v>^><v<>^<^<><<<>^<^v<^^<><<<<v>^<<vv<^<^<v<<<>>^>v>>>>v^<<<^<^v>>v>><<vv^>v^<^v<v<vvv<><v<v>^^vv><>><^<<<<^^<^^<>><<v>>v>v^v^>^^<vv><>>>^>^^>^vvv<vvv^<vv<v<v^v^>v>^^vv^<v<^<<^v>vv<<^^v><v^>^^^>v><<v^vv^<>v><^^>>>>>^<^>>>v<<<>^v^<^^^v>v^><<>><>>v>><^><v<<<>vv<><>><>><^v^v>v^<>vv^<vv<v><vv^<vvv^^^>v^^^vv>vv^vvv<<^><v><>vv>>v><<>v<>>v>><v>vv<><>>^vv^>>v<v<vv><^>v^v>^<^>^vv>v^^<^<<v><v><<^^<^<<^>v<^>v^><v>><^><^<<<<^vvv<^><<^<^vvv>v^^<^v^^><><^vv>^vv^<<^<<v>v<<<vv<^<v^>v>^<<><>vv<v^>v^^v<^^<>v>v^^>v>v<vv<>v<<<<v>>v^^v^>^v>^>v<><v^v^vv<<vvv^<>>>v^^>^><v^^<v>^^^>^<^^v<><>>^v<><vv^^v<><>>v>>>v^^vv^v<<><v^vv<v^<>>^<>v<v^^v^>>^<<^^<<<^v^^>^v^>>><v^vv<^^><v><<<<^<>v^<^^>^v^^v<<>v<<vv^<^<^>^v^<^v^>v^<<vv><^^>>^><v<<vvv^^<>v^<v>^v<^>^^<v^<^>v><vv><<><vvvv<>>>^<^<<^^v<>v^v^<^^^^^>>>><v^v<v^^^><<v^vv^v<>^v^v>>>^<^^>vv>^vv><<v^v -1 68 vvv>vv><<<^>^<>^^^v<v>^<<<^v<v>v<^v>^<>v^>>vv<>>><>><^^v^v><^><><<>v><<v><v<<>^v^^><^^<v^v>^v^>v<>v^vv>^^>><v>^v<^vv>>><<>^^>vv<><>v>^>^>><v<^v<^v^>^<vv<v<^>^^>><<v<^^>v<v><^v^<v>><>^<>^>>vv<>>^^<v<><v>^<v<<<<^<><vv^v<>><^<<^><<v^^>v>v<>v^^^<<v^<>><^v>>><<vvv>^v<vv<>><^<^^v><^^>><^^^<><v<^^>^^>v<v><^<^^>v<<^<>>v<^v<^<^<v>>^^>><^<^^<>v><<vv>^>^^><><^^^<v>>v^^>v^^<^^><^^v><v<<>>>><><>vv^>^><^><v<^<>^><v<^^^^><>>>^v<vv^v^>v<v<<v^<<<<^>v<v>><>^<>><>>v<^<^><vvv><>^><v<<vv^<v<^v>><<<<<><^>^<<^>>vv>v>^<<>>>v<v^^><>vvv^^>>^>^vv^^v^v^v^v^<>^<^^<<<>v<>^^^>><<>v^v^>v^v>>>^<^>v<v<^^^><<v>vv<^v<v<v^^<^v^vv^>v<^vv<vv<<>^v><^>vv<^><<^v>^><<<v>^>vv>^^^>v^<<vvv<^v>>^^<<<<^^^><v>v^v^^^>^vvv^><v^<^>v^v^vv>^><^<^>>v>>><^<<>^<^>v>vvv<^><<>><^^>v>^^v^vv^>v^<^v>v^>^^^<<<^^<^v^>>^^<^>^<^>v>>v<v>>v^<<vv>v^v^>^<v><><<^<^^v<^><^<^>v>^<>vv><<><^v^<v<v>v>>^><v>^>^^>v<^^^>vvv<v><>^^<<vv>^<^^^^v<<v<<^v<v>v^^vvvv<>>v><><v><^^v^>>^^>v><>v>^^><v>^vvv>v<<<^>v^^>>^v^^><^vv>v^v>>v^^^v<^>v<>><>>^vv<<^<>^<^<>><^<^<>>^>^^^v< -1 69 ^^>v^<^<v<<<v^<v<vvv>>v><vvv^v>v<vv^><>>>^>v^><<^^<^v^^<^<^^^v<^v><<v>>^^v<^<>v<<vv<><>>v^><>^<v<<^vv^>vv<<^^^>v^^>^vvv^v^^^v<^<>vv^v<>v^>vvvv<^<<vv>>v>><><^>vv<^>><><<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<v<^vv>vv><v>><<^vv>^>vv>^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><<<>>><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^^^>^<^vv>>>^^v>vvv^<^v^vvvv<vv<<><v>v^^v^>^v^v^<v><>^v^vv><vvv<>><<vv<vv>v^vv<^v^v>^^<v>v^<>v^<>>vvvv<^>v^><^v<v>>>>v<<^<vv>^<<^^^^>^>>v>^vv>v^>v>^^^<^v^vv<<>v^v<><vv>>^^><<>^<<v<^>vv>v>>>v<vv>v>v<^<<<>v^<vvv<<<v>v>>v<<>><<^v<^v<^<>^><^<>v<>v<<^<<<v><^^<><^v><<^<^v<>v^>^>><>v>vv^<<v^<<vv<v^<v>v^^<>><^><><>>^^><^^vv>^<>^^>v<>vvv^>v^>v^>^<><v<<<vv<<^v^v>^<<^<^<<^v><^>^><>^><v<<>>>^^>v>><>><>^^<>>>^^>^v^<v>>>^^> -1 70 ^<<<><>>>^>^<<vv^<>v><^v<>^<^><^><v<vv^>vv><<>^><><><^v^<>^<>vv^^<>v>><^>>>><>>^^v^<^^^>><^v^v^<v<<<<^<>><v^^>^v<>vv<>><<^^^^v>^<vv<<^>>>>vv>>v>^v^<<^><v>^>vv><<<<^>^^>>^<<>^>>^<<>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<>^vvv>^<><v^>v^<v^<><v>vv^v^<^<>><<v^><^>^<^><v^>^^^>><^v^<<^<^vv<v><^^v^<v<>v^^>>^^>vvv>^^v>><vv>^vv>vv<<vv<<>^<>>>v^v>>^vvv^v^v<^>v^v^<<v><>v<<<>v<<vv<>v<>v<>v<<v<v<>><^^^>v^>v>>^><><>^>^^>^<>>^>>v><<<<^^<v<><>>>^<v<<^^v^>^><^^vvvv<<>vv>^>^><^v>v>>vv<>^>>^>^<vv<>^<<^^v<^<>vv>vv<v>^v>v<<>v<^vv><^>v>>^><^vvvvv<<>^>>>^<<<<^><<><v<><<<^<<<>>v^vv>v<<^>^v^<^>vv^>>>^<>^v^v^vv>v>v><<v<>><v^v>^<v>^>^v^^<<v^v<><v<v^vv>v>v<v<v>>v<^v<<vvv><^<<<><^v^>v^>v<><^v>>^<^v>^><><>><>^<^<<<<^>^><^vv>v^^<^v^v>>^vv<<<^>>v^>^>>><<v>^>>><<v>^>v<><>v<v<>>vvv>^><>^>vv^^>v><>>^v^<<^v^v>>>>>vv^<<^>^>^^v>vv<<v>>^^^vv^<v<>>v^>v<v><v^v^^<^<<>^>v<^>v<<>>^><>v^>><^v>^>>v>^><vv<vv>><^><><<><>>v><><^>>vv<^>>^>v<<^<>v>^>v<^ -1 71 ><^<<vvv^^>>^^>v<^<v<>v<vvvvv><^v>>>^<^^>^>>><vv<>v<^vv<<vv<<v^<^><<>^^v^<v<<>^><v^>^>vv<>>>v>^><vv^<><<>v^v><v^v<v>^^<<<>^^>v<><^^>^<>v>vv<vv<^<>^<>^>v><>^^v>v<v<<^<^v<>v<^^vv^<>v><^>vvv<>><<^>v^<<v<<^^v<^v<<^>v><>^vv<>^<<vv^^<^v<^<vv>>^>v<^<v<>><><>^<v^^^^>^>^v<>^v>v><<^^<v>^>>><v^>>^^<^v><<v>>>>v<<>>>^><>v>>v<^^vv>^^v^<vv>^<v>><v<^^>v^^><^<^^<<>>v>>v<<<v>><>v<<vv>v><vv^<^<vvv^>><vv>^^>>v^<^<<<<<<<<<>^>>vv<^^^>>vv^><>^>><^^v<^<v^v^>^<<^>vv>^^>vv>^<<v<<v<^^<vv>v<<<v^>^^>^><^<<>^v^>^>v^<v^vv>>>^<vv<<>>^>>^^^<^>v^^>v^<v>^<^<v<^vvvvvvvvv^><^>^>><vv<<^v<>^>^v><>>^^<^>v<^<>^>>^>v><^v^<<>>vv^<v>v<v><v^^>^><^v^>^<v^^vv>>v^vv^v<<v<vv<^v><>^>vvv>^vvvv<<^vv^<<^^v^>v<^^^<^^v^v<^v><>>><^vv<><^>^^vv>>>v>>^<vvv^><^^vvvv^vv^>^>^><^>v^^<<^v^><vv^^v^<v>>>v^><^v><><<v^>>><v<^<^<><<>><<^v>>^^^v<>><>>v<^vv<v>><v<<^^<^><><^^>vv<v><v><vvvv<<><>><^><v<^>>>v^<>vv>^>v<<>vv>>^v^<<v^<v^^><v><^^^>v^<v>v<><><>^>>>v^<<>>v>^v<<>^>^>^<><^^v^^<>vv<<<vv^<^v^>^<>v<<^v>><^>v<v^^<^v>^<><^<<^<^<v^^<>>vv<><v<^v>^^<^<^<<>^>
diff --git a/2024/15/solution.rs b/2024/15/solution.rs
@@ -0,0 +1,220 @@
-1 1 #[path = "../lib.rs"]
-1 2 mod lib;
-1 3
-1 4 #[derive(Debug, Copy, Clone, PartialEq)]
-1 5 enum Tile {
-1 6 Wall,
-1 7 Floor,
-1 8 Box,
-1 9 DoubleBoxLeft,
-1 10 DoubleBoxRight,
-1 11 }
-1 12
-1 13 #[derive(Debug, PartialEq, Copy, Clone)]
-1 14 enum Dir {
-1 15 Up,
-1 16 Right,
-1 17 Down,
-1 18 Left,
-1 19 }
-1 20
-1 21 impl Dir {
-1 22 fn apply(self: &Self, x: usize, y: usize) -> (usize, usize) {
-1 23 return match self {
-1 24 Self::Up => (x, y - 1),
-1 25 Self::Right => (x + 1, y),
-1 26 Self::Down => (x, y + 1),
-1 27 Self::Left => (x - 1, y),
-1 28 };
-1 29 }
-1 30 }
-1 31
-1 32 fn parse_input() -> (usize, usize, Vec<Vec<Tile>>, Vec<Dir>) {
-1 33 let mut x0 = 0;
-1 34 let mut y0 = 0;
-1 35 let mut map = vec![];
-1 36 let mut mov = vec![];
-1 37 let mut map_done = false;
-1 38
-1 39 for (y, line) in lib::iter_input().enumerate() {
-1 40 if line == "" {
-1 41 map_done = true;
-1 42 } else if map_done {
-1 43 for b in line.bytes() {
-1 44 mov.push(match b {
-1 45 b'^' => Dir::Up,
-1 46 b'>' => Dir::Right,
-1 47 b'v' => Dir::Down,
-1 48 b'<' => Dir::Left,
-1 49 v => {
-1 50 println!("{}", v);
-1 51 unreachable!();
-1 52 }
-1 53 // _ => unreachable!(),
-1 54 });
-1 55 }
-1 56 } else {
-1 57 map.push(
-1 58 line.bytes()
-1 59 .enumerate()
-1 60 .map(|(x, b)| match b {
-1 61 b'#' => Tile::Wall,
-1 62 b'.' => Tile::Floor,
-1 63 b'O' => Tile::Box,
-1 64 b'@' => {
-1 65 x0 = x;
-1 66 y0 = y;
-1 67 Tile::Floor
-1 68 }
-1 69 _ => unreachable!(),
-1 70 })
-1 71 .collect(),
-1 72 );
-1 73 }
-1 74 }
-1 75
-1 76 return (x0, y0, map, mov);
-1 77 }
-1 78
-1 79 fn stretch(x: usize, y: usize, map1: &Vec<Vec<Tile>>) -> (usize, usize, Vec<Vec<Tile>>) {
-1 80 let map2 = map1
-1 81 .iter()
-1 82 .map(|row1| {
-1 83 let mut row2 = vec![];
-1 84 for tile in row1.iter() {
-1 85 match tile {
-1 86 Tile::Box => {
-1 87 row2.push(Tile::DoubleBoxLeft);
-1 88 row2.push(Tile::DoubleBoxRight);
-1 89 }
-1 90 _ => {
-1 91 row2.push(*tile);
-1 92 row2.push(*tile);
-1 93 }
-1 94 };
-1 95 }
-1 96 return row2;
-1 97 })
-1 98 .collect();
-1 99 return (x * 2, y, map2);
-1 100 }
-1 101
-1 102 fn can_move(x: usize, y: usize, dir: &Dir, map: &mut Vec<Vec<Tile>>) -> bool {
-1 103 // only used for up/down on double boxes
-1 104
-1 105 // PERF: I expected that this explodes because of the recursion.
-1 106 //
-1 107 // For example, if two double boxes are directly on top of each other,
-1 108 // everything is checked twice (for each side).
-1 109 //
-1 110 // However, in practice this doesn't seem to be an issue. The tweaks I tried
-1 111 // had no noticable impact. Probably the chains are too short.
-1 112
-1 113 let (x2, y2) = dir.apply(x, y);
-1 114
-1 115 return match map[y2][x2] {
-1 116 Tile::Wall => false,
-1 117 Tile::Floor => true,
-1 118 Tile::Box => unreachable!(),
-1 119 Tile::DoubleBoxLeft => can_move(x2 + 1, y2, dir, map) && can_move(x2, y2, dir, map),
-1 120 Tile::DoubleBoxRight => can_move(x2 - 1, y2, dir, map) && can_move(x2, y2, dir, map),
-1 121 };
-1 122 }
-1 123
-1 124 fn do_move_double(x: usize, y: usize, dir: &Dir, map: &mut Vec<Vec<Tile>>) {
-1 125 let (_, x2, y2) = do_move(x, y, dir, map);
-1 126 match dir {
-1 127 Dir::Up | Dir::Down => {
-1 128 do_move(x + 1, y, dir, map);
-1 129 }
-1 130 _ => {}
-1 131 }
-1 132 // important: if moving left/right, it is important to place the
-1 133 // box parts at the end so they do not get replaced by floors.
-1 134 map[y][x] = Tile::Floor;
-1 135 map[y][x + 1] = Tile::Floor;
-1 136 map[y2][x2] = Tile::DoubleBoxLeft;
-1 137 map[y2][x2 + 1] = Tile::DoubleBoxRight;
-1 138 }
-1 139
-1 140 fn do_move(x: usize, y: usize, dir: &Dir, map: &mut Vec<Vec<Tile>>) -> (bool, usize, usize) {
-1 141 let (x2, y2) = dir.apply(x, y);
-1 142
-1 143 return match (map[y2][x2], dir) {
-1 144 (Tile::Wall, _) => (false, x, y),
-1 145 (Tile::Floor, _) => (true, x2, y2),
-1 146 (Tile::Box, _) | (Tile::DoubleBoxLeft | Tile::DoubleBoxRight, Dir::Left | Dir::Right) => {
-1 147 let (free, x3, y3) = do_move(x2, y2, dir, map);
-1 148 if free {
-1 149 map[y3][x3] = map[y2][x2];
-1 150 map[y2][x2] = Tile::Floor;
-1 151 return (true, x2, y2);
-1 152 } else {
-1 153 return (false, x, y);
-1 154 }
-1 155 }
-1 156 (Tile::DoubleBoxLeft, Dir::Up | Dir::Down) => {
-1 157 if can_move(x, y, dir, map) {
-1 158 do_move_double(x2, y2, dir, map);
-1 159 return (true, x2, y2);
-1 160 } else {
-1 161 return (false, x, y);
-1 162 }
-1 163 }
-1 164 (Tile::DoubleBoxRight, Dir::Up | Dir::Down) => {
-1 165 if can_move(x, y, dir, map) {
-1 166 do_move_double(x2 - 1, y2, dir, map);
-1 167 return (true, x2, y2);
-1 168 } else {
-1 169 return (false, x, y);
-1 170 }
-1 171 }
-1 172 };
-1 173 }
-1 174
-1 175 fn score(map: &Vec<Vec<Tile>>) -> usize {
-1 176 let mut score = 0;
-1 177 for (y, row) in map.iter().enumerate() {
-1 178 for (x, tile) in row.iter().enumerate() {
-1 179 match tile {
-1 180 Tile::Box | Tile::DoubleBoxLeft => {
-1 181 score += x + 100 * y;
-1 182 }
-1 183 _ => {}
-1 184 }
-1 185 }
-1 186 }
-1 187 return score;
-1 188 }
-1 189
-1 190 fn print(px: usize, py: usize, map: &Vec<Vec<Tile>>) {
-1 191 for (y, row) in map.iter().enumerate() {
-1 192 for (x, tile) in row.iter().enumerate() {
-1 193 match tile {
-1 194 Tile::Wall => print!("#"),
-1 195 Tile::Floor => print!("{}", if (x, y) == (px, py) { "@" } else { "." }),
-1 196 Tile::Box => print!("O"),
-1 197 Tile::DoubleBoxLeft => print!("["),
-1 198 Tile::DoubleBoxRight => print!("]"),
-1 199 }
-1 200 }
-1 201 println!("");
-1 202 }
-1 203 println!("");
-1 204 }
-1 205
-1 206 fn main() {
-1 207 let (mut x1, mut y1, mut map1, mov) = parse_input();
-1 208 let (mut x2, mut y2, mut map2) = stretch(x1, y1, &map1);
-1 209
-1 210 for dir in mov.iter() {
-1 211 (_, x1, y1) = do_move(x1, y1, dir, &mut map1);
-1 212 (_, x2, y2) = do_move(x2, y2, dir, &mut map2);
-1 213 }
-1 214
-1 215 print(x1, y1, &map1);
-1 216 print(x2, y2, &map2);
-1 217
-1 218 println!("part1: {}", score(&map1));
-1 219 println!("part2: {}", score(&map2));
-1 220 }
diff --git a/2024/15/test1.txt b/2024/15/test1.txt
@@ -0,0 +1,10 @@ -1 1 ######## -1 2 #..O.O.# -1 3 ##@.O..# -1 4 #...O..# -1 5 #.#.O..# -1 6 #...O..# -1 7 #......# -1 8 ######## -1 9 -1 10 <^^>>>vv<v>>v<<
diff --git a/2024/15/test2.txt b/2024/15/test2.txt
@@ -0,0 +1,21 @@ -1 1 ########## -1 2 #..O..O.O# -1 3 #......O.# -1 4 #.OO..O.O# -1 5 #..O@..O.# -1 6 #O#..O...# -1 7 #O..O..O.# -1 8 #.OO.O.OO# -1 9 #....O...# -1 10 ########## -1 11 -1 12 <vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^ -1 13 vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v -1 14 ><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv< -1 15 <<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^ -1 16 ^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^>< -1 17 ^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^ -1 18 >^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^ -1 19 <><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<> -1 20 ^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v> -1 21 v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^