diff options
Diffstat (limited to '2024')
| -rw-r--r-- | 2024/day16/input | 141 | ||||
| -rw-r--r-- | 2024/day16/input_test | 15 | ||||
| -rw-r--r-- | 2024/day16/input_test2 | 17 | ||||
| -rw-r--r-- | 2024/day16/solve.py | 75 |
4 files changed, 248 insertions, 0 deletions
diff --git a/2024/day16/input b/2024/day16/input new file mode 100644 index 0000000..3f2737a --- /dev/null +++ b/2024/day16/input @@ -0,0 +1,141 @@ +#############################################################################################################################################
+#.................#.....#.#...#...............#.......#.......#.......#.....#.........#.............#...#.......#.#.......#.........#...#..E#
+#.#.#.#.###.#####.###.#.#.#.#.#.#####.#######.#.###.###.#.###.###.#.#.###.#.###.#.###.#######.#.###.#.#.###.###.#.#.#.#####.#.#####.#.#.###.#
+#...#.#...................#.#...#.....#...#...#...#...............#.#.....#...#.#.#...#.....#.#...#.#.#...#.#...#.#.#.....#.#.....#...#.....#
+#.###.#######.#####.###.###.#####.#####.#.#.###.#.#.#.#####.###.###.#########.###.#.###.###.#####.#.#.###.#.###.#.#.#####.#.###.#.#########.#
+#.#.#.......#.#.............#...#.....#.#.....#.#.#.#.#...#.#.......#.......#.....#.#...#.#.#.....#.#.#...#...#.#.....#.....#...#.#.......#.#
+#.#.#######.#.#.#######.#.###.#######.#####.#.###.###.#.#.#.###########.###.#######.###.#.#.#.#####.#.#.#####.#.#######.###.#.#.#.###.###.#.#
+#.....................#...#.........#.......#.#...#.............................#...#...#.#...#.......#.#.....#.#.....#.......#.#...#...#.#.#
+#.#########.#####.###.#.#.#####.###.#####.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#####.#.###.###.#####.#######.###.###.#.###.#########.###.#####.#.#
+#.#.......#...#...#.#...#.................#...................#.#...#.................#.......#.#...#.......#.#...#.#.....#.....#...#.....#.#
+#.#.#####.#.#.#.#.#.###.#.#.#####.#.#.#.###.#####.###.###.#.#.#.###.#########.#.#.#.#####.#.###.#.#.#########.#####.#####.#######.###.###.#.#
+#.#.#.....#.#.#.#.....#...#.#.#.........................#.#.#.#...#.............#.#...............................#.#...#...#.....#...#...#.#
+###.#####.###.#.#.#.###.###.#.#.#.#.#.###.#.#.#.#.#####.#.#.#.#.#.###.#.#.#.#####.#####.###.#.###.###.#.###.#.#.#.#.#.#.###.#.#######.#####.#
+#...#...#.....#.#...#.....#.#...#.#.#...#.#.#.#...#.....#.....#.#.....#.#...#.................#...#.#...#...#.#.#.#.#.#...#.#.#.......#.....#
+#.###.#.###.###.#.###.#.###.#.###.#.###.#.#.#.#####.#####.#.#######.###.#.###.#.#####.#.#.###.#.###.#####.#####.#.#.#.###.#.#.#.#.###.#.#####
+#...................#.#.#...#.#.#.....#.#.#.#.#.....#.....#...#...#.#...#.#...#.......#.#...#.#.#.......#...#...#...#.#.#...#.#.#...#.#...#.#
+#.#####.###.#.###.#.#.#.#.###.#.#####.#.#.#.#.#.#######.#.###.#.#.###.#####.#########.###.#.###.#.###.#####.#.#####.#.#.#####.###.#.#####.#.#
+#.#...#...#.#.....#...#.....#.#.....#.#.#...#.#...#.....#...#...#...#.....#.#.#.....#...#.#.#...#...#.....#.#.#.....#.....#.#...#.#.........#
+#.#.#####.#.#####.###.#.###.#.#.###.#.#.#####.###.#.#####.#######.#.#.###.#.#.#.###.###.###.#.#####.#####.#.#.#.#########.#.#.#.#.#######.#.#
+#.#.....#.#.#...#...#...#...#.#.#.#...#.....#.......#.......#...#.#.#...#...#.#.#.#.#.......#...#.#...#...#.#.#.#.....#.......#.#...#...#...#
+#.#.#.###.#.#.#.###.###.#.###.#.#.#.#######.#.#.#####.#####.#.#.###.#.#####.#.#.#.#.###########.#.###.#.#.#.#.###.###.#.###.###.#####.#.#.#.#
+#.#.#...#.#.#.#...#.#...#.......#...#.......#.#.#.....#.......#.#...#.#...#...#...#.....#.......#.....#.#.#.#.....#...#...#.#.#.#.........#.#
+#.#####.#.#.#.###.#.###.#.###########.#########.#.#####.#######.#.#####.#.#######.#####.#.#############.###.#.#####.#.###.#.#.#.#.#######.#.#
+#.#.....#.#.#.#...#...#.#.#.....#.....#.........#.......#...#.....#.....#.......#.#...#.#.............#.#...#.....#.#.#...#...#.....#.....#.#
+#.#.#####.#.#.#.#####.#.#.#.###.#.###.#.###########.#.###.#.#####.#.###########.#.###.#.#.#.###.#.###.#.#.#######.#.#.#.###########.#.#.#.###
+#.#.....#.......#.#...#.#.....#.#.#...#.#.........#.#...#.#.......#...#.......#.#...#.#...#.....#.#.#.#.#.....#.#.#.#...#.......#.#.#.#.#...#
+#.#####.#.#####.#.#.#.#########.#.#####.#.#.#####.#.#####.###.#.#####.###.###.#.###.#.###########.#.#.#.#####.#.#.#.#####.#.###.#.#.#.###.#.#
+#.....#.#...#.....#.......#...#.#.#...#.#.#.#...#.#.......#.#.............#...#.....#...........#.#...#.....#.#.#.#.....#...#...#...#.....#.#
+#####.#.###.#####.#######.#.#.#.#.#.#.#.#.#.#.#.###########.#######.###############.#####.#####.#.#.###.###.#.#.#.###.#.###.###.#########.#.#
+#...............#.......#.#.#...#...#.#.#.#...#.....#.......#...#...#.....#.......#...........#...#...#...#.#.#.......#...#...#...#.....#.#.#
+###.#.#.#.#.#.#.#######.#.#.#.#######.#.#########.#.#.#####.###.#.#.#.###.#.#####.#########.#.#######.#.#.#.#.###########.###.###.#.###.#.#.#
+#...#...#.#.#.#.....#.#.#.#.#.#.....#...........#.#...#...#.#...#.#...#.#...#...#...#...#...#.#.......#.#.#.#.......#...#...#...#...#.#.#...#
+#.#######.#.#.#####.#.#.#.#.#.#.###.#.###.#.###.#.#####.#.#.#.###.#####.#####.#####.#.#.#.###.###.#######.#.#######.#.#####.#.#.#####.#.#.#.#
+#.....#...#.....#...#...#.#.#.#.#...#.#.......#.#.....#.#.#.#.#...#.....#.........#...#.#.#.#...#...#.....#...#.....#...#...#.#...#.......#.#
+#.###.#.#####.###.#######.#.#.#.#.###.#.#####.#.#.###.#.#.#.#.#.#####.###.#######.#####.#.#.###.###.#.###.#####.#####.#.#.###.###.#.#####.###
+#...#.#.#.#...#...#.........#.#.#.#...#.....#...#...#.#.#.....#.....#...#.#...#.......#...#...#.#.....#...#.....#.....#...#.....#.#...#.....#
+#####.#.#.#.#.#.###.###########.#.###.#####.#####.#.#.###########.#.###.#.#.#.#.#############.#.###########.#####.###########.#.#.#####.#.#.#
+#...#.#.#...#.#...#.#...........#...#.......#.......#.....#.....#.#.....#...#.#...............#.#...#.......#.#...#.........#.#...#.....#...#
+#.#.#.#.#####.###.#.#.#############.#######.#####.#######.#.###.###.#.#######.#######.#######.#.#.#.#.#######.#.###.#######.#.###.#.#####.#.#
+#.#...#.#.....#.#...#...#.#.......#.......#.....#.....#...#...#.....#.......#.#...#...#.....#.#...#...........#.....#...#...#...#...#.....#.#
+#.###.#.#.###.#.#######.#.#.###.#########.#####.#.#####.#.###.#######.###.#.#.#.#.#.###.#####.###########.#.#.#######.#.#.###.#.#.###.###.#.#
+#...#.#.#...#.....#...#.#.#.#.#.......#...#.....#.#...#.#.....#...#...#...#.#.#.#.#.#.........#.........#.#.#.#...#...#.#...#.#...#...#.....#
+###.#.#.###.#####.###.#.#.#.#.###.#####.###.#####.#.#.#.###.#.###.#.###.###.#.###.#.#######.###.#######.#.#.#.#.###.###.###.#.###.#.#####.###
+#...#.#.....#...#...#.#.#.......#.#.....#.......#.#.#...#...#...#.....#.....#.....#.......#...#.#...#...#.#.#...#...#.....#.#...............#
+#.#####.#####.#.###.#.#.#####.###.#.###########.###.#######.###.#.###.#####.#####.#######.###.#.#.#.#.#####.###.#.###.#.#.#.#.#.#.#######.#.#
+#.........#...#...#...#.....#.#...#.........#.#...#.#.....#.#...#...#...#.#.....#...#...#.#.#.#.#.#.#.......#...#...#.#...#.#...#.#.........#
+#.#.###.#.#.###.#####.#####.###.#####.###.#.#.###.#.#.###.#.#.###.#.###.#.#.#######.#.#.#.#.#.#.#.#.#.#######.#####.#.#.#.#.#####.#.#.#.#.#.#
+#...#...#...#.#.....#.#...#.....#...#.....#.#...#.#.....#.#.#.#...#...#.#.#.......#...#.#.........#.#...#.......#...#.#.#.#.#.......#.#...#.#
+#.###.#.#####.#####.#.#.#######.#.#.#####.#.###.#.#######.#.#.#.#####.#.#.#######.#####.#.#######.#.#.#.###.#####.###.#.#.#.#.###.#######.###
+#...#.......#.....#...#.....#...#.......#.#...#.#.....#...#.#...#...#...#.#.......#.....#.#.....#.#...#...#...#.....#.#...#.#.#.........#...#
+###.###.#####.###.#####.#.###.###.#####.#####.#.#####.#.#####.#.###.#.#.#.#.#######.#####.#.###.#.#######.###.#.#####.#.###.#.#.#.#####.#.#.#
+#.#...#.......#.#.....#.#...#.#...#...#.......#.#.....#.....#.#.....#.....#.........#.#...#.......#.....#.#...#...#...#.#...#.#.#.....#.....#
+#.###.#.#######.###.###.###.#.#.###.#.#########.#.#########.#.#####.###########.#####.#.#####.#######.#.#.###.###.#.###.#.#####.#.#.#.###.#.#
+#.#...#...........#.....#...#.#.#...#...........#...#.....#.#.#.#...#...#.....#.....#.#...#...........#.#...#.#...#.#...#.#.....#...#.#.....#
+#.#.#.#.###########.#####.#.#.#.#############.#.###.#.###.#.#.#.#.###.###.###.#####.#.###.#.###.#.#####.###.#.#.###.#.###.###.###.###.#.#.###
+#.................#.#.....#.#.#.........#...#.#...#.#.#.#...#.#...#...#...#.#.#...#...#...#.....#.#...#.#.#.#.#...#.#.#...#...#...#...#.....#
+#.###.###.#.#####.###.#####.#.#########.#.#.#.#####.#.#.###.#.###.###.#.###.#.#.#####.#.#.###.###.#.#.#.#.#.#####.#.###.###.###.#.#.#######.#
+#.....#.#...#...#.#.....#...#.#...#...#.....#.#...#...#.#...#...#.#...#...#.#.#.....#...#.....#.....#.#.....#.....#.....#...#...#...#.....#.#
+#####.#.#######.#.#.###.#.###.#.###.#.#####.#.#.#.#####.#.#####.#.#.#####.#.#.###.#####.###.###.#####.###.#.#.#.###########.#.###.#####.###.#
+#...............#...#.....#.#.#.#...#.....#.#...#...........#.#.#...#...#.#.#...#.#.....#...#...#.......#.#.#...............#...#.......#...#
+#####.#.###.###.#####.#.###.#.#.#.#####.#.#.#.#.###########.#.#.###.#.#.#.#.###.#.#.#####.#.#.###.#######.#.#################.#.#######.#.###
+#.......#.....#.#...#.#...#.#.#.......#.#.#.#...#.........#.#.#...#.#.#.#.#.#...#.#.....#.#.#.#.#.........#.........#.........#.#.......#...#
+#.###.#.#.#.#.#.#.#.#.###.#.#.###.#####.#.#.#####.#######.#.#.###.###.#.#.#.#.###.###.###.#.#.#.#############.#####.#.###.#####.###########.#
+#.....#.#.#.#.#...#...#...#.#...#.#.....#.#.#...#...#...#.#.....#.....#...#.#...#.#...#...#.#.....#.....#...#.#...#.#...#.....#...........#.#
+#.###.###.#.#.#########.###.###.#.#.#####.#.#.#.###.#.###.###########.#####.###.#.#.###.###.#####.#####.#.#.#.#.#.###.#.#.###############.#.#
+#.#.#.....#.#...............#...#.#...#...#...#.....#...#...#...#...#.......#...#.#...#...#...#.........#.#...#.#.......#...........#.....#.#
+#.#.#.#####.#################.#######.#.###############.#.#.#.#.#.#.#######.#.#.#.###.###.#####.#########.#####.#######.#####.#####.#.#.###.#
+#.#...#.........#...#.........#.......#.#.................#...#.#.#.#...#.....#.#.......#.......#...#.....#.....#...........#.#...#.#.#.....#
+#.#.#.#.###.#.###.#.#.#########.#.#######.#########.#####.#####.#.#.#.#.###.###.#####.#######.###.#.#.#####.#####.#####.###.###.#.#.#.#.#####
+#.#.....#...#.....#.#...#.......#.#...#...#...#...#...........#.#.#...#...#.#...#...#.#.....#...#.#...#.....#...#.....#...#...#.#.#.#...#...#
+#.#.#.#####.#######.###.#######.#.#.#.#.#####.#.#.#######.###.#.#.#######.#.#.#.#.#.###.###.###.#.###.#.#####.#.#########.###.#.#.#.#####.#.#
+#.#...#...#.......#...#.#.....#.#...#.........#.#...#...#.#...#.......#.#.#.#.#.#.#.#.....#.#...#...#.#...#...#...........#.#.#.#.......#.#.#
+#.###.#.#.#.#.###.###.#.#.###.#.###.#########.#.###.#.#.###.#.#########.#.###.###.#.#.#####.#######.#####.#.###############.#.#.#######.###.#
+#.#.....#.....#.#...#.#.#.#.......#...#.....#.#...#...#.....#...#.......#.#...#...#...#.....#.......#...#.#...#.......#.....#...#.....#...#.#
+#.#.#.#########.###.#.#.#.###.###.#.#.#.###.#####.#############.#.#######.#.###.#######.#####.#######.#.#.###.#.#.###.#.###.###.#.#.#.###.#.#
+#.#.#.......#.....#.#.#.#...#...#.#.#...#.........#...........#.#.#.......#.....#...#...#.......#.....#...#...#.#...#.#...#.........#.#...#.#
+#.#.#.#####.#.#####.#.#.#.#.###.#.#.#####.#####.#############.#.#.#.#######.#######.#.#########.#.#########.###.###.#.###.#####.#.###.#.###.#
+#.#...................#.#.#...#.#.#.#.....#...#...............#.#...#.....#.#.......#.....#.....#.#.........#.#...#.#.....#.........#.#.....#
+#.###.#.#####.#.#####.#.#####.#.#.#.#######.#.###.###.#######.#.#####.#.#.#.#.#.###.#.###.#.#####.###.#######.###.#.###.#.#.###.#.#.#.###.#.#
+#.....#.....#...#.....#.......#.#.#.........#.......#.#...#...#...#...#...#.#.#...#.....#.#...........#...#.....#.#.#.......#.......#.#...#.#
+###########.#.###.#############.#.#############.#.#.###.#.#######.###.#.#.#.###.#.#####.#.#.#######.###.#.###.#.#.#.###.#.#####.#.###.###.#.#
+#.......#...#.#.#.#.........#...#...#.........#.#.#.....#...#...#.......#.#...#.#...#.#.#.#...#.....#...#...#.#...#.#...#.....#.#.........#.#
+#.###.###.###.#.#.#.###.###.#.###.###.#######.#.#.#########.#.#.#########.###.#.###.#.#.#.#####.###.#.#####.#.#####.#.#####.#.###.#########.#
+#...#.#...#.....#.....#.#...#...#.#...#.....#...#...#.....#.#.#.....#...#.#.#.#.#...#...#...#.........#.....#...#...#.......#.......#.......#
+#.#.#.#.#############.#.#.#####.#.#.###.#.#########.#####.#.#.#.###.###.#.#.#.#.#.###.#####.#.###.###.#.#########.#####.#########.#.#.#######
+#.#.#.#.#.........#...#.#.....#...#...#.#.........#.#.....#...#.#.....#.#.#.#.#.#...#...#...#.#...#...#.#.......#.....#.#.....#...#.#.......#
+#.#.###.#.#######.#####.#####.#.#.###.###.#####.###.#.###.#####.#####.#.#.#.#.#.###.#####.###.#.###.###.###.#.#.#####.#.###.#.#.#.#.#######.#
+#.#.....#.....#.#.......#.#...#.#.#.#...#.....#...#.#...#.#...#.#.......#...#.#.#...#...#.....#.......#...#...#.......#...#.#...#.#.......#.#
+#.#######.###.#.###.#####.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.###.###.#.#######.#########.#.#############.#.#.###.#########.#
+#.#...#...#...#.....#...#.....#.#.#...#.#.#.#...#.#.#.#.#...#.#...#...#...#.#.....#...#.......#...#...#...#.........#.......#.#...#.....#...#
+#.###.#.###.###.###.#.#.###.#.#.#.#.#.#.###.###.#.#.#.#.#############.#####.#.#####.#########.#####.#.#.#####.#.###.#######.#.#.#.#.###.#.###
+#...#.#.#.#.#...#.....#...#.#...#...#.#.....#...#.#.#.#.............#.......#.......#...#...#.......#...#...#.#.............#...............#
+###.#.#.#.#.#####.#####.#.#.#.###.#######.#.#.###.#.#########.#####.#######.#.#.#####.###.#.#######.#####.#.#.###.#########.#.###.#.#.#.#.#.#
+#...#.....#.........#...#.#.#...#.........#.......#.#.......#.#...#.....#.....#...#.......#.........#.....#.....#.#.......#.#...#.....#.#...#
+#.###.#.#.#.#######.#.#.#.#####.#.#########.#.#####.#.#####.#.#.#.#####.#.#######.###.#####.#######.###.#########.#.#.#####.#.#####.###.###.#
+#.....#...#.......#.#.#...#.....#.#.........#.#...#.#.#.....#...#.....#.#.......#...#.#.....#.....#.....#.......#.#.#.....#...#...#.#...#...#
+#####.#.###.#.###.#.#.#.###.#####.###.###.#.###.#.#.#.#.#####.#########.#####.#####.###.#####.#####.#.###.#####.#.#######.#####.#.###.###.###
+#...#.....#.#.....#.#.#.#...#...........#.#.....#.....#.....#.#...#...#.....#.......#...#...#.......#.#...#.................#...#.#...#...#.#
+#.###.#.#.#.#.#####.#.###.###.###.#####.###.###########.###.###.#.#.#.#.#.###.#.#####.###.###.#.###.#.#.#####.#####.###.#####.###.#.###.###.#
+#.......#...#...#...#...#.#.......#...#...#.#.........#...#.....#...#...#.#...#.#.....#.......#...#...#...........#...#.#.....#.#.#...#...#.#
+#.#.#.#######.#.#######.#.#####.###.#####.#.#.#######.#.#.#####.###.#######.###.###.###########.#.#####.#########.###.###.#.###.#.###.###.#.#
+#.#.....#.....#.#.......#.....#.#.........#.#.#.....#.#.#...#.....#.#.....#...#...#.............#...........#.....#...#...#.............#...#
+#.###.#.#.#.#.#.#.#.#########.#.#.#.#.#######.#.###.#.#.###.#####.#.#.###.###.###.#########.#########.#####.#.#.#.#.#.#.###.#.#######.#####.#
+#.#.#...#.#.#.#.#.#.........#.#.#.#.#.#.......#.#.....#...#.....#...#.#.#.......#.#.......#.......#...#.#.....#.#.....#.....#.#...#...#...#.#
+#.#.#.###.#.#.#.#.#.#####.###.#.#.###.#.#######.#########.#####.#####.#.#########.#.#####.###.#####.###.#.###########.#####.#.#.#.#####.#.#.#
+#...#...#.#.....#.#.#...#.#...#.#...#...#.....#.........#.#...#...#...#.....#...#.#.....#...#.#...#...#.....#.......#.#...#.#.#.#...#...#.#.#
+###.#.#.#.###.###.#.###.#.#.###.###.#########.#####.###.#.#.#.###.#.###.#.###.#.#.#.###.###.###.#.###.#.#####.###.#.#.###.#.###.###.#.###.#.#
+#...#...#.....#.....#...#.#.#.......#...........#.....#.#...#...#.#.....#.#...#...#...#.#.......#...#.#...#...#.#...#.....#.....#.#...#.#...#
+#.###.#.###.#.###.###.#.#.#.#.#####.#.#########.#.###.#.#.#######.###.#####.###########.###########.#.###.#.###.#.#######.#######.#####.#####
+#...#.#.....#...#.....#.#.#.....#...#...#.........#.#.#...#.....#.....#.....#...........#.........#.#...#.#.#...#.......#.#.......#...#.....#
+###.#.#####.#.#.#######.#.#####.#.###.#.#.###.#####.#.#####.###.###.###.#######.#.#######.#######.#.###.#.#.###.#######.#.#.#####.#.#.#.#####
+#.#.#.....#.....#...#...#.#.....#.#...#.....#.#.....#.....#...#...#.#...#.......#.....#...#.#.....#...#.#.#.......#...#.#.......#...#.#.....#
+#.#.#.###.#.#.###.#.#####.#.#.###.###########.#####.###.#.#.#.###.#.#.###.###.###.###.#.###.#.#######.#.#.#######.#.#.#.#####.#.#####.###.#.#
+#...#.#...#.#.....#.#.....#...#.........#.....#...#.......#.#...#.#.#.#.#.#.#...#.#.#...#...#...#...#...#.....#...#.#...#...#.#.....#.......#
+#.###.#.###.#.#####.#.###.###.#########.#.#####.#.#########.###.#.###.#.#.#.###.#.#.#####.#.###.#.#.#.#######.#.###.###.#.#.#.###.#######.#.#
+#...#.#.......#.......#.....#.......#.#.#.#.....#.........#...#.#.....#.#.....#...#.........#.#.#.#...#.....#.#.#.#...#.#.#.....#.....#.....#
+###.#.#####.#.#####################.#.#.#.#.#############.#.#.#.#######.#####.###.###.#.###.#.#.###.###.###.#.#.#.###.#.#####.#.#.#.#.#.#.###
+#.#.#.#...#.#.....#.....#.........#.#...#.#.#.......#...#.....#.#.........#.#...#...#.#.#.#...#.......#...#.#.#.#...#.#.....#...#...#.#.#...#
+#.#.#.#.#.#.#.###.#.###.#.#####.###.#.#.#.#.#.###.#.#.#.#######.#.###.###.#.###.#.#.###.#.###.#######.###.#.###.###.#.#####.#.###.#.###.#.#.#
+#.#...#.#.....#...#.#.#.#...#.#.....#.......#...#.#.....#...........#...#.....#...#.....#...#.#.....#.....#.....#.......#...#.....#.#...#.#.#
+#.###.#.###.###.###.#.#.###.#.#########.###.###.#.#####.#.###.#.###.###.#####.#####.#####.###.#####.#############.#####.#.###.###.#.#.###.###
+#.#...#.#.....#...#...#...#...#...#...#.....#...#.......#...#.....#.#.#.#.....#.....#.....#...#.....#...............#...#.#...#.....#.#.....#
+#.#.###.#.#.#.###.###.#.#####.#.#.#.#.#.#####.#.#.###.###.###.#####.#.#.###.###.###.#.###.#.###.###.#.#.###########.#.###.#.#.###.#.#.###.#.#
+#.#.#.#...#...#.#...#.#.......#.#...#.#.#.....#.#...#.#...#...#...#...#...#.......#.#...#.#...#.#...#.#.#...#...#...#...#...................#
+#.#.#.#####.###.#.#.#.#########.#####.#.#.#####.###.#.#.#.#.###.#.#.#####.#.#.###.#.###.#.###.#.#.###.#.#.#.###.#.#####.#######.#.#.#####.#.#
+#.#.#...#...#...#.#.#.#.........#.....#.#.#...#.#...#...#.#.....#.#.#.....#.#...#.#.#...#...#...#.#...#.#.#.....#.....#...#.....#.#.....#.#.#
+#.#.###.#.###.#.#.###.#######.###.#.#.#.#.#.#.#.#.#.#.#.#.#######.#.#.#####.###.#.#.#######.#####.#.###.#.###.#.#####.###.#.#####.#.#.###.#.#
+#.#.....#.#...#.....................#.#.....#.#.....................#.#.....#...#.#.............#.#...#...#.....#...#...#...#...#...#.....#.#
+#.#####.#.#####.#######.###.#.#.###.#.###.#######.###.###.#.#.#.#####.###.###.#.#.###########.###.#.#.###.#.#.#.#.#.###.#####.#.#.#########.#
+#.#.....#...#.........#.#.....#.#.#...#...#.....#...#.#.#...#.#.....#...#.#...#...#.....#.....#...#.#.....#...#.#.............#.....#.......#
+#.#.#######.#.#######.#.#######.#.#####.#.#.###.###.#.#.#####.#####.###.#.#.###.###.#.###.#####.###.#####.###.#.#.###.#####.#####.#.#.#####.#
+#...#.................#.......#.....#...#...#...#...#.#...#...#...#...#.#.#...#...#.#.......#.#.#...#...#.#...#...#.#.......#...#.#.#...#.#.#
+#.#.#.###.###.#.#######.#####.#####.#.###.###.###.###.#.#.#.###.#.#.#.#.#.###.#.#.#########.#.#.#.###.#.#.#.#.#####.#####.###.#.#.#.###.#.#.#
+#...#...#.#...#.......#...#.#.#.....#.#.....#.#...#...#.#...#...#.#...#.#...#.#.#.......#.....#.#...#.#.#.#.......#.......#...#...#.....#...#
+###.###.#.###.#######.###.#.#.#.#####.#.#.#.#.#.###.###.#######.#.#.#.#.###.#.#.#######.#######.#####.#.#####.###.#####.###.#############.###
+#.#...#.#...#.....#.#...#.#.#.#...#...#.#.#.#.#...#.#.#.....#...#.#...#.#.#.#.....#.....#.....#.#.....#.#...#...#.....#.#.......#.#...#...#.#
+#.#.#.#.###.#####.#.###.#.#.#.###.#.###.#.#.#.#.#.#.#.#####.#.###.#.###.#.#.###.###.#####.###.#.#.#####.#.#.#.###.###.#.#.#####.#.#.#.#.###.#
+#.#...#...#.....#.#.#...#...#.#...#.#.#...#...#.#...#.....#...#.#.#...#.#...........#...#...#.#.#.#.#...#.#.#...................#.#.#.#.#...#
+#.#.###.#.#####.#.#.#.#######.#.###.#.###.#######.###.#.#######.#.#.#.#.#######.#####.#.###.#.#.#.#.#.###.#.#.#####.#.#.###.#.#.#.#.#.#.#.#.#
+#S......#.....#...#...........#.....#.............#...#...............#...............#.....#.....#.......#...#.......#.....#...#...#.....#.#
+#############################################################################################################################################
\ No newline at end of file diff --git a/2024/day16/input_test b/2024/day16/input_test new file mode 100644 index 0000000..94e806c --- /dev/null +++ b/2024/day16/input_test @@ -0,0 +1,15 @@ +###############
+#.......#....E#
+#.#.###.#.###.#
+#.....#.#...#.#
+#.###.#####.#.#
+#.#.#.......#.#
+#.#.#####.###.#
+#...........#.#
+###.#.#####.#.#
+#...#.....#.#.#
+#.#.#.###.#.#.#
+#.....#...#.#.#
+#.###.#.#.#.#.#
+#S..#.....#...#
+###############
\ No newline at end of file diff --git a/2024/day16/input_test2 b/2024/day16/input_test2 new file mode 100644 index 0000000..a98e558 --- /dev/null +++ b/2024/day16/input_test2 @@ -0,0 +1,17 @@ +#################
+#...#...#...#..E#
+#.#.#.#.#.#.#.#.#
+#.#.#.#...#...#.#
+#.#.#.#.###.#.#.#
+#...#.#.#.....#.#
+#.#.#.#.#.#####.#
+#.#...#.#.#.....#
+#.#.#####.#.###.#
+#.#.#.......#...#
+#.#.###.#####.###
+#.#.#...#.....#.#
+#.#.#.#####.###.#
+#.#.#.........#.#
+#.#.#.#########.#
+#S#.............#
+#################
\ No newline at end of file diff --git a/2024/day16/solve.py b/2024/day16/solve.py new file mode 100644 index 0000000..92a24f2 --- /dev/null +++ b/2024/day16/solve.py @@ -0,0 +1,75 @@ +from bisect import insort
+from typing import Optional
+
+
+class Globals:
+ start_position = None
+ end_position = None
+
+
+class Node:
+ def __init__(self, position: tuple[int, int], previous_node: Optional["Node"], cost: int):
+ self.position = position
+ self.previous_node = previous_node
+ self.cost = cost
+
+ self.estimated_total_cost = cost + abs(Globals.end_position[0] - position[0]) + abs(
+ Globals.end_position[1] - position[1])
+
+
+def is_node_in_list(node_list: list[Node], position: tuple[int, int]):
+ for node in node_list:
+ if node.position == position:
+ return True
+ return False
+
+
+data = []
+with open("input") as f:
+ for line in f:
+ data.append(line.strip())
+
+for row_idx, line in enumerate(data):
+ for col_idx, char in enumerate(line):
+ if char == "S":
+ Globals.start_position = (row_idx, col_idx)
+ if Globals.end_position is not None:
+ break
+ elif char == "E":
+ Globals.end_position = (row_idx, col_idx)
+ if Globals.start_position is not None:
+ break
+ else:
+ continue
+ break
+
+row_count = len(data)
+col_count = len(data[0])
+traveled_to_positions = []
+open_nodes = []
+open_nodes.append(Node(Globals.start_position, None, 0))
+while True:
+ current_node = open_nodes.pop()
+ if current_node.position == Globals.end_position:
+ print(current_node.cost)
+ break
+
+ traveled_to_positions.append(current_node.position)
+ if not current_node.previous_node is None:
+ prev_pos = current_node.previous_node.position
+ forward_dir = (current_node.position[0] - prev_pos[0], current_node.position[1] - prev_pos[1])
+ came_from_dir = (forward_dir[0] * -1, forward_dir[1] * -1)
+ else:
+ came_from_dir = None
+ forward_dir = (0, 1)
+ for direct in ((-1, 0), (1, 0), (0, -1), (0, 1)):
+ if direct == came_from_dir:
+ continue
+
+ is_forward_dir = forward_dir == direct
+
+ new_pos = (current_node.position[0] + direct[0], current_node.position[1] + direct[1])
+ if 0 <= new_pos[0] < row_count and 0 <= new_pos[1] < col_count and data[new_pos[0]][new_pos[1]] != "#" and \
+ new_pos not in traveled_to_positions and not is_node_in_list(open_nodes, new_pos):
+ new_node = Node(new_pos, current_node, current_node.cost + (1 if is_forward_dir else 1001))
+ insort(open_nodes, new_node, key=lambda x: -x.estimated_total_cost)
|