- commit
- 8e8988fd784454fafd20813f40c4c685491b4613
- parent
- f2c82a8ae57c7a051eed87cde809dd6d66f5b340
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2024-12-16 13:40
2024-12-16
Diffstat
| A | 2024/16/input.txt | 141 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/16/solution.rs | 168 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/16/test1_7036_45.txt | 15 | +++++++++++++++ |
| A | 2024/16/test2_11048_64.txt | 17 | +++++++++++++++++ |
4 files changed, 341 insertions, 0 deletions
diff --git a/2024/16/input.txt b/2024/16/input.txt
@@ -0,0 +1,141 @@ -1 1 ############################################################################################################################################# -1 2 #...........#...........#.....#.......#.......#...#.......#.................#...............................#.........#.......#...#...#...#E# -1 3 #.#.#######.#.#####.#####.#.#.#.#####.###.###.#.#.#.#####.#.#######.#####.###.#######.#########.###########.#.#######.#.#####.#.#.#.#.#.#.#.# -1 4 #.#.......#.#...#...#.....#.#...#.........#.....#...................................#.....#...#.....#.......#.......#...#...#.#.#...#...#.#.# -1 5 #.#.#.#.###.#.###.#.#.#.###.#####.#################.###.###.#.#.#.#####.#.#.###.###.#####.#.#.#.###.#.#.#.###.#####.#####.#.#.#.#####.#.#.#.# -1 6 #.#...#.#...#.#...#.#...#.#.#.....#...#.......#.........#...#...#.................#.....#.#.#.......#.......................#...#...#.#.#...# -1 7 #.#.#.#.#.#.#.#.#.#.###.#.#.#######.#.#.#####.#####.#.###.#####.#.#.#.#######.###.#####.###.###.#####.#.#.#.#####.###.#.#.#######.###.#.###.# -1 8 #...#...#.................#.........#...#...#.#.....#.#...................#...#.#...#...#...#.....#.#.#.#.#.#...#.....#.#.............#...#.# -1 9 ###.#.#.#.###.#.###.#.#.#.###############.#.#.#.###.#.#.###.#.###.###.#.#.#.###.###.#.###.###.#.#.#.#.#.#.###.#.###.#.#.#.#######.#####.#.### -1 10 #...#.#.#.#...#.............................#...#.................#...#.#...#...#...#.........#.#.#...#.#.#...#.....#.#.#.#.....#.......#...# -1 11 #.#.#.#.#.#.###########.#.#.###.#.#.#.#.###.#####.#.#.#########.#.#.###.#####.#.#.#########.###.#.#####.#.#.#######.#.#.#.###.#.#.#########.# -1 12 #.....#.#.#.....#...............................#...#.....#...#.#.#.#...#.....#.......................#.#...#.....#.....#...#.#.#...#.#.....# -1 13 #.#.#.###.#####.###.###.#.###########.###.#########.#####.###.#.#.#.#.###.#####.#.#.#####.#.#########.#.#.###.###.###.#####.###.#.#.#.#.#.#.# -1 14 #...........#.#.....#...............#...#.#.........#...#...#.#.#.#...#...#.....#.#.#...#...#.......#.#.......#...#.....................#.#.# -1 15 #.#.#.#.#.#.#.#######.#.#.#########.###.#.#.#########.#####.#.#.#.#########.###.#.#.#.#####.#.#####.#.#######.#.###.#.#######.###.#.###.#.#.# -1 16 #.#.#.....#...#...#.......#.........#.......#.#.......#...#.#.#.#.........#...#.#...#.#...#.#.#.#...#.....#...#...#.....#...#.....#.........# -1 17 ###.#.#########.#.#.#####.###.#######.#####.#.#.#.###.#.#.#.#.#.#####.###.###.#######.#.#.###.#.#.#######.#.#####.#####.#.#.#####.#.#.###.### -1 18 #...#...........#.#.........#.#...#.....#...#.#.#...#.#.#.#.#.#.....#...#...#.#.....#.#.#.....#.#.#.......#.#.......#.....#.#...#...#.#...#.# -1 19 #.#.#.###########.###.#.###.#.#.#.#.###.#.###.#.###.###.#.#.#.#####.###.###.#.#.#.#.#.#.###.#.#.#.#.#######.#.#.###.#.###.#.#.#.#.###.###.#.# -1 20 #.#...#.......#.....#.#.....#.#.#...#...#...#.#...#.....#...#.....#.#...#.#.#...#.#...#.#.....#...#.#.#...#...#...#.#.....#...#.#.#.#...#...# -1 21 #.#.#.###.###.#.###.#.#.###.###.#####.#.###.#.#.#.###############.#.#.###.#.###.#.###.#.#######.###.#.#.#.#.#####.#############.#.#.###.#.#.# -1 22 #.#.........#.#...#.#.#.#...#...#.....#...#.#.................#...#...#...#...#.#.#...#...#.....#...#...#...#...#.#.......#...#.#.....#.....# -1 23 #.#.#.#.###.#####.###.#.#####.###########.#.###.#####.#######.#.#######.#####.#.#.###.###.#.#####.###.#########.#.#.###.###.#.#.#.###.###.#.# -1 24 #.....#...#...#...#...#.......#...#.......#...#.#...#.#.....#.#...........#.....#...#...#.#.#.....#.#.....#...#.#...#...#...#...........#.#.# -1 25 #.#######.#.#.#.###.###########.#.#.#####.###.###.#.###.###.#.###########.#.#######.#####.#.#.#####.#####.#.#.#.#####.###.###.###.###.#.#.### -1 26 #.......#.....#...........#.....#.#.#.....#...#...#...#...#...............#.#.......#.....#...#.........#.....#.#...#.....#.#.......#...#...# -1 27 #.#####.#####.###########.#.#####.#.#.#####.###.#####.#.###.###.#########.#.#.#####.#.###.###.#######.#######.#.#.#.#######.#.###.###.###.#.# -1 28 #...#.#.................#.#.#.#.....#.#...#...#.#...#...#.......#.......#.#.#...#.#.#.#...#.....#...#.......#.#.#.#.....#...#.......#.#.....# -1 29 ###.#.#########.#######.#.#.#.#.#######.#.#.#.#.###.#####.###.###.#.###.#.#.#.#.#.#.#.#.#.#.###.#.#.#####.#.#.#.#.###.#.#.#######.#.#.###.#.# -1 30 #...#.....#...#.#.#.....#.#.#...#.#.....#...#.#.....#.#...#.....#.....#.#.#.#.#.#...#...#.#...#...#.#.....#.#.#.....#.#.#.....#.....#...#.#.# -1 31 #.###.###.#.#.#.#.#.#####.#.#.###.#.#####.###.#####.#.#.#####.###.#####.###.###.#####.#.#.###.#.###.#.#######.#######.#.#####.#.###.#.#.#.#.# -1 32 #.#...#.#.#.#...#.......#...#.....#.#...#.....#.....#.#.....#.#...#.....#...#...#.......#.#...#...#.#...#...#.........#.....#.#...#...#...#.# -1 33 #.#.###.#.#.#.#########.#####.#####.#.#.#.#####.#####.#####.#.#.#.#.###.#.###.###.#######.#.###.#.#.#.#.#.#.#######.#######.#.###.###.###.#.# -1 34 #...#...#.#.#.#...#...#...#...#...#.#.#...#.....#.#.......#.#.#...#.#...#...#...#.#.#.........#.#.#.#.#...#.#.......#.....#.#...............# -1 35 #######.#.#.###.#.#.###.#.#####.#.#.#######.#####.#.###.#.#.#.#.###.#######.###.#.#.#.#######.#.###.#.#####.#.#.#.###.#.###.#.#.###.#.#.##### -1 36 #.......#.#...#.#.#.....#.#...#.#...#.....#.#.......#.#.#.#.#.#.#...#.....#.....#.#...#.......#.#...#.#...#...#.#.....#...#...#...#.#.#.#...# -1 37 #.#####.#.#.#.#.#.#####.#.#.#.#.#.###.###.#.#.#.#####.#.###.###.#.#.#.#.#####.#.#.#####.#######.#.#.###.#.###.#.#########.###.###.#.#.#.###.# -1 38 #.#.....#.#.#...#.#.....#.......#.#...#.#.#.#.#.#.....#...#...#.#.#.#.#.....#.#.#.....#.#.......#.#.#...#...#...#...#...#.......#.#...#.....# -1 39 #.###.###.#.#####.#.#########.#.###.###.#.#.#.#.###.#.###.###.#.#.#.#.#####.#.#.#####.#.#.#####.#.###.#####.###.#.#.#.#.#####.###.#.#######.# -1 40 #...#.#.#...#.#...#...#.........#...#...#...#.#...#.#...#...#.#.#.#.#...#...#.....#.#...#.#.....#.....#.....#...#...#.#...#.......#.......#.# -1 41 ###.#.#.###.#.#.###.#.#.#######.#.###.#.#####.###.#.#######.#.#.#.###.###.#.#####.#.#####.#.###########.#####.###.###.#.###.#####.#######.#.# -1 42 #...#...#.#.#.#...#.#.#.#.....#.#.....#.#.#.....#.#.......#.#...#...#.#...#.#...#.....#...#.#.........#...#.#...#.....#...#.#...#...#.....#.# -1 43 #.#####.#.#.#.###.#.#.#.#.###.#########.#.#.###.#.#####.###.#######.#.#.###.#.#######.#.#.###.###.###.###.#.###.#####.###.#.#.###.#.#.###.#.# -1 44 #...#.....#...#...#.#...#.#.#.#.........#...#...#.....#.#.....#...#.#.#.#.....#.....#.#.#.#.....#...#...#.#...#.....#.#...#.#.....#.....#...# -1 45 ###.#########.#.#####.###.#.#.#.#############.#.#####.#.#.###.#.#.#.#.#.#######.###.#.#.###.#######.#####.#.#######.#.#.###.#.###.#######.### -1 46 #...#.........#.........#...#...#.............#...#...#.#.#...#.#.#...#.........#.#...#.....#.....#.......#...#...#...#.#...#...#...#.....#.# -1 47 #.###.#################.###.#####.#####.#.#.#######.###.#.###.#.###.###.#.#######.#########.#.###.#.#.#####.#.#.#.###.#.#.#####.#.###.###.#.# -1 48 #.#...#.....#...#.......#...#...#...#...#...#.....#.#...#...#.........#...#...#...#.......#.#...#...#.#.....#.#.#...#...#.....#.#...#...#...# -1 49 #.#.###.###.#.#.#.#####.#.###.#####.#.#.#####.#.#.#.###.###.#####.###.#####.#.#.#.#.#.###.#####.###.#.#####.#.#.###.###.#####.#.#.#.###.#.#.# -1 50 #.#...#...#.#.#.......#.#.#.....#...#.#.#.....#...........#.#.....#...#.....#...#.#.#...#.....#...#.#.......#.....#.........#.#.#.#...#...#.# -1 51 #.###.###.#.#.#.#####.#.#.#####.#.###.#.#.#.###.#####.#####.#.#####.###.#.#######.#####.#####.###.#.#######.#####.#########.#.#.#.###.###.#.# -1 52 #...#...#.#.#.#.#...#...#...#...#.#...#.#.#.....#...#.#.....#...#.#.....#.......#.....#...#.......#.#...........#.#.....#...#.#.....#...#...# -1 53 #.#.###.#.#.#.###.#.#######.#.###.#.#.#.#.###.#.#.#.###.#.#####.#.#############.#####.###.#########.#.#.#######.#.#.#.#.#.###.###.#.###.#.### -1 54 #.#...#.#.#.#...#.#...#.....#.....#.#...#.#...#.#.#...#.#.#.....#.......#.....#...#.#...#...#.......#.#.......#.#.#.#.#.#...#...#.......#.#.# -1 55 #.#####.#.#.###.#.###.#.#####.#####.#.###.#.#.#.#.###.#.###.#######.#.#.#.#.#.###.#.###.#.#.#.#########.#.#####.###.#.#.###.###.#.#####.#.#.# -1 56 #...#...#.#.#.#...#.#...#...#.......#...#...#...#...#.#...#.#.......#.#.......#.#.#.....#.#.#.#.......#.#.#...#.#.....#.#.#...#.#.....#.#.#.# -1 57 #.#.#.#.#.#.#.#####.#######.#.#.#########.#########.#.#.#.#.###.#####.#######.#.#.#.###.###.#.#.#####.#.#.#.#.#.#.#####.#.###.#.#.###.#.#.#.# -1 58 #.#.#...#.#.....#.....#.....#.#...#.......#.....#...#.#.#.#...#.#...#.......#...#.#.........#...#...#.#.#...#.#.#.#.#...#.#...#...#.#.#.#...# -1 59 #.#.###.#.#####.#.#####.#.###.###.#.#######.###.#.###.###.#.#.#.#.#.#.#####.#.###.#.#.#.###########.#.#.#####.#.#.#.#.###.#.#######.#.###.#.# -1 60 #.#.#...#.#...#.#.......#.#...#.#.#.#...#.#.#.#.#.#.#...#...#.#...#.#.......#.#...#.#.#.#...#.......#.#.#.#...#...#.#...#.#.....#...#.......# -1 61 #.#.#.#.#.###.#.#######.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#.#.#.###.#.#.###.###.#.###.#.###.#.#.###.###.#.#.#.#######.###.#.#####.#.#######.### -1 62 #.#.#.....#...#.......#.#.#.....#.....#...#.#.#...#.#...#.#.#...#.#.#...#.....#.....#...#.#.#...#.....#...#...........#.#.............#...#.# -1 63 #.#.#.#.###.#########.#.#.#####.###########.#.#####.#.###.#.###.#.#.#####.#############.#.#.###.###.#########.###.###.#.#####.#.###.#.#.#.#.# -1 64 #.#.......#.........#.#.#...#.....#.........#.......#.....#.#...#.#.....#...#.....#.....#.#.#.#...#.........#.......#.#.#...#.......#...#...# -1 65 #.#####.###.###.#####.###.#.#.#####.#####.#.#.#####.#.#######.#########.###.#.###.#.###.#.#.#.#.#.###.#####.#######.#.#.#.#.###############.# -1 66 #...#.#...#...#.#.....#...#.#.#.....#...#.#.#.#.....#.#.........#...#...#...#...#...#...#.#.#.........#...#.#...#...#.#...#...#.....#.#.....# -1 67 ###.#.#.#.###.#.#.#####.###.#.#.#####.#.#.#.#.#######.#.#######.#.#.#.#.#####.#.#.###.#.#.#.###########.###.#.#.#.###.#######.#.###.#.#.##### -1 68 #.#.#...#...#.#.#...#...#...#.#.#...#.#.....#...........#.....#.#.#...#.#...#.#.........#.#.....#.....#.......#.....#.......#.#...#.#.#...#.# -1 69 #.#.###.#.###.#.###.#.#.#.###.#.###.#.#####.###.###.###.#.###.#.#.#######.#.#########.#.#.#####.#.###.#.###########.###.#####.###.#.#.###.#.# -1 70 #.#...#.#.....#.....#.#.#.#.#.#...#...#...#.#.....#.#...#.#...#...#.......#...........#.#...#.#...#...#...#...#.........#.....#...#.#.#.....# -1 71 #.###.#.#############.#.#.#.#.###.#####.#.###.###.#.#.###.#.#######.#.###############.#####.#.#####.#######.#.###########.#####.###.#.#.##### -1 72 #...#...#.....#.....#...#...#...#.#.....#.#...#.#.#.#.#.#.#.........#.#.#.....#.......#.....#.#.....#.......#...........#.......#...#...#...# -1 73 #.#####.#.###.#.#.#.###.#######.#.#.#####.#.###.#.###.#.#.###########.#.#.#####.#######.#####.#.#######.###############.#.#####.#.#######.#.# -1 74 #...#...#...#...#.#.....#.....#.#...#...#.#...#.......#.#.#.....#...#.#.#.............#...#...#...#.....#.............#.#.#.....#...........# -1 75 #.#.#.#####.#####.#######.###.#.#####.#.#.###.#.#######.#.###.###.#.#.#.#########.#####.#.###.###.###.###.#######.###.#.#.#.#.#.#####.#.###.# -1 76 #.#.#...........#.#...#.....#.#.#.....#.#.....#.#.......#...#.#...#...#...#.....#.#...#.#.#...#.#.....#.........#...#.#.#...#.#.#...#...#...# -1 77 #.#.#####.#######.#.#.#.#####.#.#.#####.#######.#.#.#######.#.#.#########.#.###.###.#.###.#.#.#.###############.###.###.###.#.#.#.#######.#.# -1 78 #.#.....#.......#...#...#.#...#.#.#...#.#...#...#.........#.#.............#...#.......#...#.#...#...#.......#.....#.#...#.#...#...#.....#.#.# -1 79 #.#####.#######.#.#######.#.#.#.#.#.#.#.#.#.#.###.#######.#.#########.#.###.#.#######.#.###.###.#.#.#.#####.#######.#.###.###.#.###.###.#.#.# -1 80 #.#...#.....#...#.#...#...#.#.#...#.#.....#.#...#.......#.#...#...#...#...#...#.#.....#.#.....#...#...#...#.....#...#.#.....#.....#...#...#.# -1 81 #.###.#.#####.###.#.#.#.###.#.#######.#####.#.#.#.#######.###.#.#.#.#####.#.###.#.#####.#####.###.#####.#.#####.#.#.#.#.###.#.#.#.###.#####.# -1 82 #...#.#.#.....#.....#.#...#.#.#...........#.#.#.#.#...#...#.#...#.#.#...#...#.....#.........#.#.........#...#.#...#.#.........#.....#.#.#...# -1 83 ###.#.#.#.###########.###.#.###.#.#########.#.#.#.#.#.#.#.#.#####.#.###.#####.#.#.#####.###.#.#.###########.#.###.###.#####.###.###.#.#.#.### -1 84 #.....#.#...#...#.#.......#...#.#.....#.....#.#...#.#...#...#.....#.....#.....#.#.....#...#.#.#.#...#.......#.....#...#...#.#...#.....#.#...# -1 85 #.#####.###.#.#.#.#.###.#.###.#.#####.#.#####.#####.#######.#.###.#######.#####.#####.#####.#.#.###.#.#######.#####.#.#.#.###.#.#######.###.# -1 86 #.#.....#.#...#.#.#.#...#.#.#.#.#.#...#.#...#.....#.#.....#.#...#...#.....#.#...#...#...#...#...#...#...#...#...#...#...#.....#.#...#.....#.# -1 87 #.#.###.#.#####.#.#.#.###.#.#.#.#.#.###.#.#.###.###.#.###.#.###.###.#.#####.#.###.#.###.#.###.#.#.#.###.#.#.###.#.###.#.#######.#.#.#.#.###.# -1 88 #.#...#...#...#.#.....#.....#...#.#.....#.#.....#.......#.#.....#...#.....#.#.....#...#.#.....#.#.#.#.#.#.#.#...#.#...#...........#.#.#.....# -1 89 #.###.###.###.#.###.#########.#.#.#######.#####.#.###.#.#####.#.#.#######.#.#########.#.###.#.#.#.#.#.#.#.#.#####.#########.#.#####.#.####### -1 90 #.#...#.#...#.#...#.#.......#.#.....#.....#.......#...#.#.....#.#.......#...#.......#.#...#.#.#.#.#.#.#...#.......#.....#...#.#...#.#.......# -1 91 ###.###.###.#.###.###.#####.#.#####.###.###.#######.###.#.#####.#######.###.#.###.###.###.###.#.#.#.#.#####.#.#####.###.#.#.#.###.#.######### -1 92 #.........#.....#.....#...#.#.........#.#.#...#...#.#...#.......#.#...#...#...#...#.....#.....#.#.#.....#.#...#.....#.#...#.#.....#...#.....# -1 93 #.#####.#######.#######.#.#.#.#.#####.#.#.###.#.#.###.#.#####.#.#.#.#.#.###.#######.###########.#.#####.#.#########.#.#####.#########.#.###.# -1 94 #.#.....#.....#...#...#.#.#.#.#...#...#...#...#.#.....#...#...#.#...#.#...#.#.....#.........#...#.#...#...#.........#.....#.#...#.....#.#.#.# -1 95 #.#.#####.###.###.#.#.#.#.#.#.#.#.#.###.###.###.#########.###.#.#####.###.#.#.###.#.#####.#.#.#.#.#.#.###.#.#.#########.###.#.#.#.#.###.#.#.# -1 96 #.#.#...#...#.....#.#...#.#...#.#...#...#...............#.....#.#.......#...#...#.#.....#.#.#.#.....#...#.......#.....#.....#.#...#.#.....#.# -1 97 #.#.#.#.###.###.#######.#.###.#.#####.###.###.#########.#####.#.#.#############.#.#######.###.#.#######.###.###.#.###.#.#####.#######.#####.# -1 98 #.#...#.........#.....#.#...#.#.....#.#...#.#.........#.#...#.#.#...#.........#.#.........#...#.....#.#.....#.#.....#.#...#...#.......#.#...# -1 99 #.###.#####.###.#.#.#.###.#.#.#####.#.#.###.#####.#####.#.#.#.#.###.#.#######.#.#######.###.#######.#.#######.#######.###.###.#.#######.#.### -1 100 #...#...#.....#...#...#...#.#.#.....#.#...#.......#...#.#.#...#.....#.#.#.......#...#...#...#.....#...#...........#...#.......#...#.....#...# -1 101 #.#.###.#.#.#.#####.###.#.#.#.#.#####.#.#.#.#######.#.#.#.#######.###.#.#.#########.#.###.#####.#.###.#.#.#########.#.###########.#.#.#####.# -1 102 #.#...#.#.#.#.#.....#...#...#.#.#.....#.#.#...#.....#...#...#...#.#...#...#...#...#...#...#.....#...#...#.#.......#.#.#.........#...#.#.....# -1 103 #.###.###.#.#.###.#.###.#####.#.#.###.###.###.#.###########.#.#.#.#.###.###.#.#.#.#####.#####.#####.#######.#####.#.###.#######.#####.#.###.# -1 104 #.#.#.......#...#.#...#.#.....#...#.......#.#.#...#.......#.#.#.#.#...#...#.#...#.....#.#.....#.....#.....#.#...#.#.......#.#...#...#.#.#.#.# -1 105 #.#.#######.###.#.###.#.#.###########.#####.#.###.###.#.#.#.###.#.###.#####.#########.#.#.#####.#####.###.#.#.#.#.#######.#.#.###.#.#.#.#.#.# -1 106 #.#...#...#.....#...#...#.#...........#.......#.#...#...#.#.......#...#...#...#.......#...#.#...#.....#...#.#.#.........#.#.#.....#...#.#...# -1 107 #.#.#.###.#.#####.#.#.#.#.###.#######.#.#######.###.###.#.#####.#.#.###.#.###.#.#.#########.#.#######.#.###.###########.#.#.#######.###.#.### -1 108 #...#...#.#.....#.#.....#...#.#.......#...#...........#.....#...#.#...#.#...#.#.#...........#.........#.#...#.....#...#.#.....#...#.#...#.#.# -1 109 #######.#.#.###.#.#########.#.#.#########.#.#####.###.#.#.###.###.###.#.###.#.#.###.#####.#.###########.#.#.#.###.#.#.#.#.#####.#.###.###.#.# -1 110 #.....#.....#...#.#.......#...#.#.......#...#.......#.#.#.......#.....#...#...#.....#.....#.......#.....#.#.#...#.#.....#.#.....#...#.#.#...# -1 111 #.#.#.#####.#.###.#####.#.#####.#.###########.#######.#############.#.###.###########.#.#.#######.#.#####.#####.#.#####.#.#.#.#####.#.#.###.# -1 112 #.#.#.#.....#.#.#.....#.#...#...#...........#...#.....#.............#.....#.....#...#.#.#...#...#.#...#...#.....#.....#.#...#...............# -1 113 ###.#.#.###.#.#.#####.#####.#.###.#####.#.###.###.#####.#####.#.###########.#.#.#.#.#.#.###.#.###.###.#.#.#.#########.#.#.###.#########.##### -1 114 #...#...#...#.#.......#...#.....#.#...#.#.#...#...#...#.....#.#.#.........#.#.....#...#.#...#.#...#...#.#.#.#.......#.#...#...........#.#...# -1 115 #.###.#####.#.#####.###.#.#.###.#.###.#.###.###.#.#.#.#.###.#.#.#.#######.#.###########.#.#.#.#.#.#.###.###.#####.#.#.#####.#####.#####.#.#.# -1 116 #.....#.....#.....#.....#...#...#.....#.......#.#.#.#.......#.#.#.......#.#...#...#...#.#.....#.#.#...#...#.#...#.#.#.#.....#...#.#.....#.#.# -1 117 #.###.#.###.#####.#########.#.#######.#########.#.#.#########.#.###.###.#.###.#.#.#.#.#.#.#####.#.###.#.#.#.#.#.#.#.#.#.#####.#.#.#.#####.### -1 118 #.#.......#.#...#.........#.#.....#.#...#.#...#.....#.#.....#.#.......#.#.#...#.#.#.#...#.#.#.......#.#.#.#.#.#...#.#.#.......#.#...#.......# -1 119 #.###.###.#.#.#.#########.#######.#.###.#.#.#.#.#####.#.###.#.###.###.#.###.#####.#.#####.#.#.#.#####.###.#.#.#.###.#.#.###.###.#######.#.#.# -1 120 #.#.......#...#.#.#...#...........#...#.#.#.#.#.#.....#.#.#.#.......#.#.........#.#...#.....#.#.#.....#...#.#...#.#.#.#.#...#.......#...#.#.# -1 121 #.#.#.#########.#.#.#.#.#.#.###.#.###.#.#.#.#.#.###.###.#.#.#######.#.#########.#.###.#####.#.###.#####.###.###.#.#.#.###.#.#######.#.#.###.# -1 122 #.#...#.......#.#...#.#.#.#...#.#.#...#...#.#.#.....#.....#.....#...#.#...#...#.....#...#...#...#...#...#.......#...#.#...#...#...#...#...#.# -1 123 #.###.#.#.#####.#.###.#.###.###.#.#.#####.#.#.#######.###.#####.#.#.###.#.#.#.#####.###.###.###.###.#.###.#########.#.#.#####.#.#.#####.#.#.# -1 124 #.....#.#...#...#...#.#.....#...#.#.......#.#.#.....#.....#.....#.#.....#...#.....#...#.#...#.....#.#.......#.....#.#.#.#...#.#.#.#...#.#...# -1 125 #####.#.###.#.#######.#######.###.#########.#.#.###.###.#.#.#####.###############.###.#.#.#.#.#####.#########.###.#.#.#.#.#.#.#.#.#.#.#.###.# -1 126 #.......#...#.......#.#.....#.....#.........#...#...#...#.#.....#.#.....#.........#...#...#.#.....#...........#.#.#.#.....#.#.#.#...#.#.#...# -1 127 #.###.###.#########.#.#.###.#######.#######.#####.#.#.###.#.#.#.#.#.###.#.#################.#####.#########.#.#.#.#########.#.#.#####.#.#.### -1 128 #.................#.#.#.#...#.....#.....#.........#...#.#...#.#...#...#.........................#.........#.#.#...........#.#.#...#...#.#.#.# -1 129 #.#.#.#.###.#####.#.#.#.#.#.#.###.#.###.###.#.#########.#.###.#####.#.###.###.#.#.###################.#.###.#.###########.###.###.#.###.#.#.# -1 130 #.#.#...#.....#...#.#...#.#...#.#.#...#.#...#...#.......#...#.#.....#...#...#.#...#...#...#.....#...#.#.#...#...#.......#...#...#.#...#.#...# -1 131 #.###.#.#.###.#.###.#.###.#####.#.#####.#.#.###.#.#####.###.#.#.###.###.#.#.#.###.#.#.#.#.#.###.#.#.###.#.#####.#.###.#####.#.#.#.###.#.###.# -1 132 #.....#.#.#...#...#.#...#.#.....#.....#...#.#...#.....#...#.....#...#.#.#.#...#...#.#...#...#.#.............................#.#.#...#.....#.# -1 133 #.#####.#.###.###.#.#.#.#.#.#########.#.###.#.###.#####.###.#.#.#.#.#.#.#.#####.###.#########.#########.#########.#.###.#####.#.###.#.#.###.# -1 134 #.#.....#...#.#...#.#...#.#.......#...#.#...#.#...#...#...#...#.#.#...#...#.....#.....................#.#.......#.#.....#...#.#.#...#.#.....# -1 135 ###.###.###.#.#.###.#.###.#.#####.#.###.#.###.#.###.#.###.###.#.#.#####.#.#####.#.#####.#.#####.#.#.###.#.#####.#.#.###.#.###.#.#.#####.##### -1 136 #...#.#.....#...#...#.#...#.#...#...................#.....#...#.#.......#.....#.......#.#.....#...#.#...#.....#...#...#.#.#...#.#.....#.....# -1 137 #.###.#.#######.#.###.#.###.#.###########.#.#.###.###.#####.#.###########.###.#######.#.###.#.###.###.#######.#######.#.#.#.###.#####.#.###.# -1 138 #.#...................#.#.#.#.............................#.............#.#...#.....#.#...#.#.#...#...#.....#...#.....#.#.....#.#.....#...#.# -1 139 #.#####.#########.#.#.#.#.#.#########.#.#.#.#.#.###.###.#.###.#########.#.#.###.###.#####.#.#.#####.#####.#.#.#.#.#####.#######.#.#####.#.#.# -1 140 #S..................#...#.............#...#.......#.....#.......................#.........#.#.............#...#...#.............#.......#...# -1 141 #############################################################################################################################################
diff --git a/2024/16/solution.rs b/2024/16/solution.rs
@@ -0,0 +1,168 @@
-1 1 use std::collections::HashMap;
-1 2 use std::collections::HashSet;
-1 3
-1 4 #[path = "../lib.rs"]
-1 5 mod lib;
-1 6
-1 7 #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash)]
-1 8 enum Dir {
-1 9 Up,
-1 10 Right,
-1 11 Down,
-1 12 Left,
-1 13 }
-1 14
-1 15 impl Dir {
-1 16 fn apply(self: &Self, x: usize, y: usize) -> (usize, usize) {
-1 17 return match self {
-1 18 Self::Up => (x, y - 1),
-1 19 Self::Right => (x + 1, y),
-1 20 Self::Down => (x, y + 1),
-1 21 Self::Left => (x - 1, y),
-1 22 };
-1 23 }
-1 24
-1 25 fn unapply(self: &Self, x: usize, y: usize) -> (usize, usize) {
-1 26 return match self {
-1 27 Self::Up => (x, y + 1),
-1 28 Self::Right => (x - 1, y),
-1 29 Self::Down => (x, y - 1),
-1 30 Self::Left => (x + 1, y),
-1 31 };
-1 32 }
-1 33 }
-1 34
-1 35 type Pos = (usize, usize, Dir);
-1 36
-1 37 fn parse_input() -> (Pos, (usize, usize), Vec<Vec<bool>>) {
-1 38 let mut start_x = 0;
-1 39 let mut start_y = 0;
-1 40 let mut end_x = 0;
-1 41 let mut end_y = 0;
-1 42 let mut map = vec![];
-1 43
-1 44 for (y, line) in lib::iter_input().enumerate() {
-1 45 map.push(
-1 46 line.bytes()
-1 47 .enumerate()
-1 48 .map(|(x, b)| match b {
-1 49 b'#' => false,
-1 50 b'.' => true,
-1 51 b'S' => {
-1 52 start_x = x;
-1 53 start_y = y;
-1 54 true
-1 55 }
-1 56 b'E' => {
-1 57 end_x = x;
-1 58 end_y = y;
-1 59 true
-1 60 }
-1 61 _ => unreachable!(),
-1 62 })
-1 63 .collect(),
-1 64 );
-1 65 }
-1 66
-1 67 return ((start_x, start_y, Dir::Right), (end_x, end_y), map);
-1 68 }
-1 69
-1 70 fn push1(pos: Pos, score: usize, cache: &mut HashMap<Pos, usize>, queue: &mut Vec<Pos>) {
-1 71 if score < *cache.get(&pos).unwrap_or(&usize::MAX) {
-1 72 cache.insert(pos, score);
-1 73 queue.push(pos);
-1 74 }
-1 75 }
-1 76
-1 77 fn part1(
-1 78 start: Pos,
-1 79 end: (usize, usize),
-1 80 map: &Vec<Vec<bool>>,
-1 81 cache: &mut HashMap<Pos, usize>,
-1 82 ) -> usize {
-1 83 let mut queue = vec![];
-1 84 let mut best_score = usize::MAX;
-1 85
-1 86 push1(start, 0, cache, &mut queue);
-1 87
-1 88 while let Some((x, y, dir)) = queue.pop() {
-1 89 let score = *cache.get(&(x, y, dir)).unwrap();
-1 90
-1 91 if (x, y) == end {
-1 92 if score < best_score {
-1 93 best_score = score;
-1 94 }
-1 95 continue;
-1 96 }
-1 97
-1 98 let (x2, y2) = dir.apply(x, y);
-1 99 if map[y2][x2] {
-1 100 push1((x2, y2, dir), score + 1, cache, &mut queue);
-1 101 }
-1 102
-1 103 match dir {
-1 104 Dir::Up | Dir::Down => {
-1 105 push1((x, y, Dir::Right), score + 1000, cache, &mut queue);
-1 106 push1((x, y, Dir::Left), score + 1000, cache, &mut queue);
-1 107 }
-1 108 Dir::Right | Dir::Left => {
-1 109 push1((x, y, Dir::Up), score + 1000, cache, &mut queue);
-1 110 push1((x, y, Dir::Down), score + 1000, cache, &mut queue);
-1 111 }
-1 112 }
-1 113
-1 114 // PERF: makes a major difference, probably because preliminary
-1 115 // results are not propagated
-1 116 queue.sort_by_key(|(xx, yy, _)| xx.abs_diff(end.0) + yy.abs_diff(end.1));
-1 117 }
-1 118
-1 119 return best_score;
-1 120 }
-1 121
-1 122 fn push2(pos: Pos, score: usize, cache: &HashMap<Pos, usize>, queue: &mut Vec<Pos>) {
-1 123 if score == *cache.get(&pos).unwrap_or(&usize::MAX) {
-1 124 queue.push(pos);
-1 125 }
-1 126 }
-1 127
-1 128 fn part2(end: (usize, usize), best_score: usize, cache: &mut HashMap<Pos, usize>) -> usize {
-1 129 let mut queue = vec![];
-1 130 let mut paths = HashSet::new();
-1 131
-1 132 for dir in [Dir::Up, Dir::Right, Dir::Down, Dir::Left] {
-1 133 push2((end.0, end.1, dir), best_score, cache, &mut queue);
-1 134 }
-1 135
-1 136 while let Some((x, y, dir)) = queue.pop() {
-1 137 if let Some(score) = cache.remove(&(x, y, dir)) {
-1 138 paths.insert((x, y));
-1 139
-1 140 let (x2, y2) = dir.unapply(x, y);
-1 141 push2((x2, y2, dir), score - 1, &cache, &mut queue);
-1 142
-1 143 match dir {
-1 144 Dir::Up | Dir::Down => {
-1 145 push2((x, y, Dir::Right), score - 1000, cache, &mut queue);
-1 146 push2((x, y, Dir::Left), score - 1000, cache, &mut queue);
-1 147 }
-1 148 Dir::Right | Dir::Left => {
-1 149 push2((x, y, Dir::Up), score - 1000, cache, &mut queue);
-1 150 push2((x, y, Dir::Down), score - 1000, cache, &mut queue);
-1 151 }
-1 152 }
-1 153 }
-1 154 }
-1 155
-1 156 return paths.len();
-1 157 }
-1 158
-1 159 fn main() {
-1 160 let (start, end, map) = parse_input();
-1 161 let mut cache = HashMap::new();
-1 162
-1 163 let best_score = part1(start, end, &map, &mut cache);
-1 164 let paths = part2(end, best_score, &mut cache);
-1 165
-1 166 println!("part1: {}", best_score);
-1 167 println!("part2: {}", paths);
-1 168 }
diff --git a/2024/16/test1_7036_45.txt b/2024/16/test1_7036_45.txt
@@ -0,0 +1,15 @@ -1 1 ############### -1 2 #.......#....E# -1 3 #.#.###.#.###.# -1 4 #.....#.#...#.# -1 5 #.###.#####.#.# -1 6 #.#.#.......#.# -1 7 #.#.#####.###.# -1 8 #...........#.# -1 9 ###.#.#####.#.# -1 10 #...#.....#.#.# -1 11 #.#.#.###.#.#.# -1 12 #.....#...#.#.# -1 13 #.###.#.#.#.#.# -1 14 #S..#.....#...# -1 15 ###############
diff --git a/2024/16/test2_11048_64.txt b/2024/16/test2_11048_64.txt
@@ -0,0 +1,17 @@ -1 1 ################# -1 2 #...#...#...#..E# -1 3 #.#.#.#.#.#.#.#.# -1 4 #.#.#.#...#...#.# -1 5 #.#.#.#.###.#.#.# -1 6 #...#.#.#.....#.# -1 7 #.#.#.#.#.#####.# -1 8 #.#...#.#.#.....# -1 9 #.#.#####.#.###.# -1 10 #.#.#.......#...# -1 11 #.#.###.#####.### -1 12 #.#.#...#.....#.# -1 13 #.#.#.#####.###.# -1 14 #.#.#.........#.# -1 15 #.#.#.#########.# -1 16 #S#.............# -1 17 #################