summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-16 02:08:12 -0700
committerJack Sangdahl <[email protected]>2024-12-16 02:08:12 -0700
commit5c91260838a45f4a422fae26aa040420a2770c62 (patch)
treec33510fe97bbfe48bccdc27d7990c303cc187d75
parent0ca91e0da2793b481c55bb2367e1549ec37f693d (diff)
downloadaoc-5c91260838a45f4a422fae26aa040420a2770c62.tar.gz
aoc-5c91260838a45f4a422fae26aa040420a2770c62.zip
Day 16 2024
-rw-r--r--16_2024.py79
-rw-r--r--data/16_2024.txt142
2 files changed, 221 insertions, 0 deletions
diff --git a/16_2024.py b/16_2024.py
new file mode 100644
index 0000000..2ae5fbe
--- /dev/null
+++ b/16_2024.py
@@ -0,0 +1,79 @@
+import heapq
+
+input = "data/16_2024.txt"
+data = open(input).read().strip()
+lines = data.split("\n")
+rows = len(lines)
+cols = len(lines[0])
+lines = [[lines[r][c] for c in range(cols)] for r in range(rows)]
+dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
+
+
+for r in range(rows):
+ for c in range(cols):
+ if lines[r][c] == "S":
+ sr, sc = r, c
+ if lines[r][c] == "E":
+ er, ec = r, c
+
+
+q = []
+vis = set()
+heapq.heappush(q, (0, sr, sc, 1))
+dist = {}
+best = None
+while q:
+ d, r, c, dir = heapq.heappop(q)
+ if (r, c, dir) not in dist:
+ dist[(r, c, dir)] = d
+ if r == er and c == ec and best is None:
+ best = d
+ if (r, c, dir) in vis:
+ continue
+ vis.add((r, c, dir))
+ dr, dc = dirs[dir]
+ rr, cc = r + dr, c + dc
+ if 0 <= cc < cols and 0 <= rr < rows and lines[rr][cc] != "#":
+ heapq.heappush(q, (d + 1, rr, cc, dir))
+ heapq.heappush(q, (d + 1000, r, c, (dir + 1) % 4))
+ heapq.heappush(q, (d + 1000, r, c, (dir + 3) % 4))
+
+
+print(best)
+
+
+q = []
+vis = set()
+dist2 = {}
+for dir in range(4):
+ heapq.heappush(q, (0, er, ec, dir))
+
+
+while q:
+ d, r, c, dir = heapq.heappop(q)
+ if (r, c, dir) not in dist2:
+ dist2[(r, c, dir)] = d
+ if (r, c, dir) in vis:
+ continue
+ vis.add((r, c, dir))
+ dr, dc = dirs[(dir + 2) % 4]
+ rr, cc = r + dr, c + dc
+ if 0 <= cc < cols and 0 <= rr < rows and lines[rr][cc] != "#":
+ heapq.heappush(q, (d + 1, rr, cc, dir))
+ heapq.heappush(q, (d + 1000, r, c, (dir + 1) % 4))
+ heapq.heappush(q, (d + 1000, r, c, (dir + 3) % 4))
+
+
+valid = set()
+for r in range(rows):
+ for c in range(cols):
+ for dir in range(4):
+ if (
+ (r, c, dir) in dist
+ and (r, c, dir) in dist2
+ and dist[(r, c, dir)] + dist2[(r, c, dir)] == best
+ ):
+ valid.add((r, c))
+
+
+print(len(valid))
diff --git a/data/16_2024.txt b/data/16_2024.txt
new file mode 100644
index 0000000..c894de8
--- /dev/null
+++ b/data/16_2024.txt
@@ -0,0 +1,142 @@
+#############################################################################################################################################
+#.........#.........#...........#.....#.............#.........................#.........#.............#...#.#.........#...................#E#
+#.#.#####.#.###.###.###.###.#.#.#.#.###.#########.#.#.###.#######.#.#########.#.#####.#.#.#####.#####.#.#.#.#.###.#.#.#.#######.#########.#.#
+#.#.....#.......#.#.....#.......#.#.#...#...#.#...#.#...#.#.#...#.#.#.....#.#.#.#.....#.#.#...#.....#...#.#.....#...#.#.#.#...#.....#...#.#.#
+#.#####.###.#####.#.#######.#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.###.#.#.###.###.#.#.###.#####.#####.###.###.#####.#.#.#.#####.#.#.#.#.#
+#.....#.....#...#...#.......#.#...#.#...#.#...#...#...#.#.#...#...#...#...#.......#.#...#.#.....#...#...#...#.#...#.......#.#.....#.#.#...#.#
+#########.#.#.###.###.#####.###.###.###.#.#.#####.###.#.#.#.###########.#####.#####.#.#.#.#.###.#.###.#.###.###.#.#.#######.#####.#.###.###.#
+#...........#.....#...#...#.......#...#.#.#.#...#...#...#.#...#.#.....#...#...........#.#...#.#.....................#.#...#.#.#...#...#.....#
+#.#########.#.#####.###.#.#.#######.###.#.###.#.###.#.###.###.#.#.#.#.###.#.#.#.###.###.#####.#.#########.#######.###.#.#.#.#.#.#####.#####.#
+#...#...#...#.....#...#.#.#...#.....#...#.#...#.....#...#...#.#...#.#.....#.#.#.#...#...#.......#...#...#.#...#...#...#.#...#.........#...#.#
+###.#.#.#.#.#######.#.#.#.#.#.#.#####.#.#.#.#.#####.#.#.###.#.#####.#####.#.#.#.#.#####.#.#######.#.#.###.#.#.#.#.###.#.###############.#.#.#
+#...#.#...#.....#...#.#.#...................#.#...#...#...#.#...........................#.#.....#.#.#...#.#.#...#.....#.#...............#.#.#
+#.###.#########.#.#.#.#.#.#####.#.#.#.#.#.#.###.#.###.###.#.#########.#.###.#.#.###.###.#.#.#.#.#.#.#.#.#.#.#####.###.#.#.###.###########.#.#
+#.#...#.....#.#.#.#...#.#.#...#...#.#...#.#.....#...#.#...#...#...#...#.....#.#.#...#...#.#.#.#...#.#.#.#.#.#.....#...#.........#...#.....#.#
+#.#.###.###.#.#.#.#####.###.#.#####.#####.#########.#.#.#####.#.#.#.#########.#.###.#.#.#.###.#####.###.#.#.###.#.#.#########.#.#.#.#.#######
+#.#...#...#...#.#...#.....#.#...#.......#...#.....#.....#...#...#.#.....#...........#...#.#...#...#.....#.#.....#...#.....#...#...#.#.......#
+#.###.###.###.#.###.#.###.#.###.#.#####.###.#.###.#########.#####.#####.#.###########.###.#.#####.#####.#.#######.###.###.#.#######.#######.#
+#...#...#.#...#.....#.....#.#.....#.........#.#...#.........#...#.......#.#.....#.....#...#.....#.#.....#...#.....#...#.#.#.........#.......#
+###.###.#.#.###.#.#.#.#####.#####.#.#########.#.#######.###.###.###.###.#.#.###.#.#####.#######.#.#.#######.#.#####.###.#.#########.#.#####.#
+#.........#...#.#.#.#...........#.#.....#.#...#...#.....#.#...#...#.....#.....#.....#...#.......#...#.....#...#.....#...........#.....#.....#
+#.###.#####.#.#.###.#####.#####.#.#.#.#.#.#.#.###.#.#####.###.###.#.###.###.#.#####.#.###.#######.###.###.###.###.#.#.#########.#.#.###.#####
+#.............#...#.........#...#.#...#.#.....#.#...#.........#...#.#.#.....#.....#.#.#...#.....#.#.#.#.#...#.....#.#...#.#...#...#...#...#.#
+#.###.#.#.#.#####.#########.#.###.#####.#####.#.#.#####.#######.#.#.#.#####.#####.#.#.#.#####.#.#.#.#.#.###.#####.#.###.#.#.#.#####.#.###.#.#
+#.#.#.#.#...#.....#...#.....#.#.......#.......#...#...#.........#.#.#.....#...#...#.#.#...#...#.#...#.#...#.....#.#.#.....#.............#...#
+#.#.#.###.#.#.###.#.###.#####.#.#####.#.#.###.#####.#.###########.#.###.#.###.#.###.#.###.#.#####.###.#.#######.###.#######.###.#####.#.###.#
+#.#.#.....#...#.#...#.....#...#.#.#.....#.#.#.#.....#.#.........#.#...#.#...#.#.#...#.....#.......#...#.....#.#.....#.......#...#...#.#...#.#
+#.#.#.#####.###.###.#.#####.###.#.#.#####.#.#.#.#####.#.#########.###.#####.#.#.###########.#######.###.#.#.#.###.#.#.#######.###.#.###.###.#
+#.........#.#.....#.#.#.#...#.#...#.....#.#.#.#...#...#...#.....#.#.#.#...#.#.#...#.....#...#.....#.#...#.#...#...#.#.#.....#.#...#.#...#...#
+#.###.#####.#.#.###.#.#.#.###.###.#####.#.#.#.###.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#.###.###.#.#####.###.###.#.#.#.###.#.#.###.#.###.###
+#.#.........#.#.#...#.#.#.#...#...#.....#.#.#.#...#.#...#...#.#...#.#.#.#...#...#...#...#.....#...#.#.....#.......#.#.....#.#.#.#.....#...#.#
+###.#.#########.#.###.#.#.#.###.###.#.###.#.#.#.###.###.#####.#####.#.#.#####.#.#####.###.#####.###.#.###########.#.#######.#.#.#####.#.###.#
+#...#...........#.#.....#.#.......#...#...#...#...#...#.#.....#...#.#.#.......#.#...#.....#...#.#...#.#.....#...#.#...#...#.#.#.....#.#...#.#
+#.#########.#####.#.#####.#####.#####.#.#####.###.###.#.###.#.#.#.#.#.#.#.#.###.###.#######.#.#.#.###.#.###.#.#.#.###.#.#.#.#.#.###.#####.#.#
+#...#.....#.......#...#...#...#.#.....#.............#.#.....#...#.....#.#.....#.........#.#.#...#.#.#...#...#.#.#.#...#.#.#.#.#...#.........#
+###.#.###.###########.#.###.#.###.###################.#############.#.#######.#########.#.#.#.###.#.#.###.#.###.#.#.###.#.#.#.###.#####.###.#
+#...#.#.#.............#...#.#.#...............#...#...#...#.....#...#.....#.#...#.....#...#.#.............#...#...#.#.#.#...#.#.#.....#...#.#
+#.###.#.#################.#.#.#.#############.#.#.#.###.#.#.###.#.#####.#.#.###.#.#######.#.#######.#######.#.#####.#.#.#####.#.#.#.###.#.#.#
+#.#...#.....#...........#...#.....#.....#.......#...#...#.#.#.#.#.#...#.#.#.#...#.....#...#.#...#...#.....#.#.....#...#...#...#.....#...#.#.#
+#.#.###.###.#.###############.#.#.#.###.#########.#.#.###.#.#.#.###.#.#.#.#.#.###.###.#.###.#.#.#####.###.#.#####.###.###.#.#####.###.#.#.###
+#...#...#...#.........#.....#.....#.#.#.#.......#...#.#.....#.#...#.#.#.....#...#...#...#...#.#.#.......#...#...#.......#.#.#...#.....#.#...#
+#.###.#.#.#######.#.#.#.###.#####.#.#.#.#.#####.###.#.#######.###.#.#.###.#.###.#########.###.#.#.#######.#.###.#########.#.#.#.#.#####.###.#
+#...#.#.#.......#.#.#...#...#...#.#.#.#...#...#.#...#...#...#.....#.#.....#...#.........#.....#.#.#.......#...#.....#...#.#...#...#.....#...#
+###.#.#.#####.#.#.#.#####.###.###.#.#.#####.#.#.#######.#.#.#.#####.#######.#########.#.#.#####.#.#.#########.#.###.#.#.#.#.#####.#.#.###.#.#
+#...#.#...#.......#...#.....#.#...#.#.......#.#.......#.#.#.#.......#.#.................#.#...#...#.....#.....#...#.#.#...#.#...#...#.#...#.#
+#.#######.#.#.#######.#.###.#.#.###.#######.#.#######.#.#.#.###.#####.#.#####.#.###.#######.#.#####.###.#.#.#######.#.#####.#.#.#.#.###.###.#
+#.........#.#.#...#...#...#.#.#.....#.......#.#.....#...#.......#.....#.#.....#...#.........#.#...#.#...#.........#.#.....#.#.#...#.#...#...#
+#######.###.#.#.#.#.###.###.#.#.#.###.#######.#.#.#######.###.###.###.#.#.###.###.###########.#.#.###.###########.#.#####.###.###.#.#.###.#.#
+#...#.....#...#.#.#.#.#...#.#...#.#.#.....#.......#.....#.#.#.....#.#.#.#...#...#.......#...#...#.....#...#.............#.....#.............#
+#.#.#.###.###.#.#.#.#.#.#.#.#####.#.#.###.#.#######.#.#.#.#.#####.#.#.#.###.###.#.###.#.#.#.#######.###.#.###.#####.###########.#.#.#####.#.#
+#.............#.#.#.....#.#.#.....#...#...#...#.....#.#.#.#.#...#...#.#...#.#.......#.#.#.#.......#.#...#...#.#...#.#.....#.....#.#.#...#.#.#
+#.###.#.#.###.#.#.#.#.###.#.#.#####.###.#######.#####.###.#.#.#.#####.###.###.#.#####.#.#.#.#######.#.#####.###.#.###.###.#.#####.#.#.#.###.#
+#.#...#.....#...#...#...#.#.#.#...#...#.......#...#.#...#...#.#...#.....#.....#.#...#.#.....#.......#.#.........#.....#.#.#...#...#.#.#...#.#
+#.#.###.#.#.#.#.#######.#.#.#.#.#####.###.###.###.#.###.###.#.###.#.#.###.#####.#.#.#.#####.#.###.#.#.#################.#.#.#.###.#.#.###.#.#
+#...#...............#...#...#.#.....#...#.#...........#...#.#...#...#.#...#...#.#.#...#.....#.......#.#.....#.....#.....#.#.#.#...#.#.#.....#
+#.###.#.#.#.#.###.#.#.###.#.#.###.#.###.#.#.#.#.#######.#.#.###.#####.#.###.#.#.#.#######.###.#.#####.#.###.#.#.###.###.#.###.#.#.#.#.#####.#
+#.#.......#.#...#.#.#...#...#...#.#.....#.#.#.#.#.........#...#.#...#.#...#.#.#.#...#...#.#.#...#...#.....#.#.#.....#.....#...#.....#.....#.#
+#.#######.#.#.#.#.#.###.#.#.###.###.#####.#.###.#.###.#######.#.#.#.#.###.#.#.#####.#.#.#.#.###.#.#.#######.#########.#.#.#.###.###.#####.###
+#.#.......#...#...#.#...#.#...#...#.#.....#.....#.#...#.....#.....#.#.#...#.#.....#...#.#.....#...#...#.....#.........#.#.#.......#.....#...#
+#.#.#####.#.#.#####.#.###.###.###.#.###.#.#######.#.#.#.#.###.#####.###.###.###.#.#.###.#####.#####.###.#####.#.#######.#.#####.#.#####.###.#
+#.#.....#...#...#...#.#.#...#.....#.....#.#.......#.#.........#.#...#...#...#.#...#...#.#...#.......#...#.#...#.........#.............#...#.#
+#.#.###.#.###.###.###.#.###.#############.#.#######.#.#######.#.#.###.###.#.#.#.#######.#.#.###.#####.###.#.#.###.#############.#.#.#####.#.#
+#.#...#.....#.#...#.#...#.#.....#.......#.#.#...#.#.#.#.....#...#.......#.......#.......#.#.........#.#.....#...#.....#...#...#...#.......#.#
+#.#.#.###.#.#.#.###.###.#.#####.#.#.###.#.#.#.#.#.#.#.#.#.#.###############.#.###.#.#####.###########.#.#######.#.#.###.#.#.#.#.###.#####.#.#
+#.#.....#.#.#.#.#.....#...#...#...#...#.#.#...#.#...#...#.#.....#.........#.#...#.#.........#...#.....#.#.......#...#...#...#...#...#.....#.#
+#.#.###.#.#.#.#.###.#.###.#.###.#####.###.#####.###.###.#.#####.#.#######.#.###.#.###########.#.#.#####.###.#.#.#####.#######.#.#.###.###.#.#
+#.#...#...#.#.#...#.#...#.#.........#.....#...#...#...#.#.......#...#.......#.#.#.....#.......#.#.....#.....#.#.........#.....#...#...#.....#
+#.#.#.###.#.#####.#.#.#.#.#######.#.#######.#####.#####.#####.#.###.#.#####.#.#.#####.#.#######.#####.#################.#.###.#.#####.###.#.#
+#...............#.#.#.#.#.......#.#...#.....#...#.....#.#.....#.....#...#...#.#...#.#.#...#...#.....#.........#.........#...#.#.....#...#.#.#
+#####.#.#.###.###.###.#.#######.#.###.#.###.#.#.#####.#.#.###.###.#.#####.#.#.###.#.#.###.#.#######.#.#######.#.#######.###.#.#.###.#.#.#.#.#
+#...#.#...#...#...#...#...#.....#...#.#...#.#.#.....#...#.#.........#.....#.#.....#.....#.#.........#.#...#...#.#...#.....#.#.#.....#.#.#.#.#
+#.###.###.#.#.#.###.#######.#######.#.#.#.#.#.###.#######.#.#########.#####.#.#######.###.#.#########.###.#.###.#.#.#.###.#.#.#.#####.#.#.#.#
+#...#.#...#.#.#.#...........#.......#.#...#...#...#.......#...#.......#...#.#.......#.#...#.#.......#.....#.#.....#.#...#...#.#.....#.#.#.#.#
+#.#.#.#.#.#.#.#.#.###########.#######.###.#####.#.#.#.#####.#.#.#########.#.#######.###.###.#.###########.#.#######.#.#.###########.###.#.#.#
+#.#...#.....#.#.#.#.........#...#...#.#...#.#...#.#.#.#.....#.#.........#.#...#...#.#...#...#...........#.#.......#...#.#.........#.....#.#.#
+#.#####.#.#.###.#.#########.#.#.#.#.###.#.#.#.###.#.###.###.#.#########.#.###.#.#.#.#.###.#########.#.###.#######.#####.#.###.###########.#.#
+#.......#...#...#.........#...#...#.#...#...#...#.#.....#.#.#.....#...#.#.....#.#.#...#.#.#.......#.#...#...#...#...#...#.#.#...#.......#...#
+#########.###.###.#.#####.#.#######.#.###.#.###.#########.#.#####.#.#.#.#########.#.###.#.#.#####.#####.###.#.#.###.#.###.#.###.#.#####.#.###
+#.......#...#...#.#...#.#.#.....#...#...#.#...#...#.......#.#...#.#.#.#.#...........#...#...#...#...#.....#.#.#.#.#.#...#.....#.......#...#.#
+#.###.###.#.###.###.#.#.#.#####.#.#.###.#####.###.#.#.#####.#.#.#.###.#.#.###.#.#.###.#.#####.#####.#.#.###.#.#.#.#.#.#.#####.#####.#.#####.#
+#.#.#.......#.#.....#.#...#.....#.#...#.........#...#.#...#...#.#.....#...#...#...#...#...#...#.....#.#.#...#.#...#.#.#.....#...#...#.#.....#
+#.#.#########.#######.#.#######.#.###.#.#######.#####.#.#.#####.#########.#.#######.###.#.#.#.#.#####.###.###.###.#.#.#####.###.#####.#.###.#
+#.#.#.........#.......#.......#.#...#...#...#.#...#.#...#...#...#.....#...#.....#...#...#.....#.....#.#...#...#.#.#.#.#...#...#.....#.....#.#
+#.#.#.#####.#.#.#############.#.#.#.#####.#.#.###.#.#####.#.#.###.###.#.#.###.#.#.###.#############.#.#.#####.#.#.#.#.#.###.#.#####.#######.#
+#...............#.....#.......#.#.#.#.....#.#.....#.#.....#.#.#...#.#.#.....#.#.#.#.#...............#...#.....#...#.#.#.#.......#.#.........#
+#.#.#.#.#######.###.#.#.#.#.#.#.#.#.#.#####.###.#.#.#.#####.#.#.###.#.#####.###.#.#.#####.###########.#####.###.###.#.#.#.#####.#.#########.#
+#.#.............#...#.....#.#.#...#.....#.#...#.....#...#...#.#...#.#.......#...#.#...#.....................#.#.#.#.#...#.#.#...#...#...#...#
+#.#.#.#######.#.#.#.###.#.###.#########.#.###.#####.###.#####.###.#.###.#####.#.#.#.###.###########.#########.#.#.#.#.#.#.#.#.###.#.#.###.###
+#.#...#.......#.#.#.....#.....#.........#...#...#...#...#...............#.....#.#.#.....#...#.....#.#.....#.......#.#...#.#...#...#...#...#.#
+#.###.#.#######.#.#####.#.#.###.###########.###.#####.###.###.###.#.###.#####.#.#.#.#.###.###.###.###.###.#.#######.#.###.#.###.#.#####.###.#
+#...#...#.......#.#...#.#.......#.........#...#.....#...#...#.#...#...#.#...#.#.#...#.#.....#.#.....#.#.#.#...#.....#.#...#...#.#.....#.....#
+###.#.###.#######.###.#.#.#######.#.#####.###.#####.###.###.#.#.###.#.#.#.#.#.#.###.#.#####.#.#####.#.#.#.#####.###.###.#####.#.#.###.#####.#
+#.............#...#...#...#.......#.#...#.....#.....#...#...#.#...#.#.#...#...#.#...#.....#.#...#.....#.........#.#.....#.....#.#...#.......#
+#.#.#.#.#####.#.#.#.#.###.#.#########.#.#.###.#.#####.###.###.###.#.#.#.#########.#######.#.###.#.#####.#########.#.#.#######.#.#.#.#########
+#.......#.....#.....#.#...#.#.........#.#...#.#...#...#...#.#...#.#.#.#.#...#.........#...#.....#.#...#.#.......#...#.......#.....#.#.......#
+#.#.#.#.#.###.#######.#.###.#.#########.#.#.#####.#.###.###.#.#.#.###.#.#.#.#.#######.#.###.#.#####.#.###.###.#.#.#########.#####.#.#.#####.#
+#.........#.....#.....#.#.......#.....#...#.......#.#...#.......#...#.#...#...#.....#...#...#.......#.....#.....#.#.......#.........#.....#.#
+#.###.#.#.#######.#####.#######.#####.#####.#####.#.#.###.#########.#.#.#.#######.#.###.#.#########.#.#####.#####.#.#.###.#######.###.###.#.#
+#...#...#...#.....#.....#...#.............#.#...#...#.#...#.#.......#.#.#.#.....#.#...#...#.........#.....#.....#...#.#...#...............#.#
+#.#.#.#.#.#.#.#####.#####.#.###.#########.#.#.#.#####.#.###.#.#######.#.#.###.#.#.###.#####.#######.#####.#####.#####.#.###.#.###.#.#.#.###.#
+#.#.#.....#.......#.......#...#...#.....#.#.#.#.....#.#.....#...#.....#.#.....#...#.#.......#...#...#.#...#.#...#.....#...#.#.#...#...#.#...#
+#.###.###.###################.#.#.#####.#.#.#.#####.#.#########.#.###.#############.#########.###.###.#.###.#.###.###.###.#.#.#.#.#####.#####
+#.....#.........#...........#.#.#.......#...#.....#...#...#.....#.#...#.......................#...#.....#...#.#.#.#.#...#.#.#.#...#.....#...#
+#.#####.#.#####.#.#########.#.#.###########.#####.#.###.#.#.#######.###.#.#.#############.#####.###.#####.#.#.#.#.#.#.###.###.###.#.#####.#.#
+#.....#.......#...#.....#.....#.#.................#.....#...#.......#...#.#.#.......#...#.#.....#.#.#.....#.#.#.#...#...#.#...#...#...#...#.#
+#####.###.###.#####.#.#.#.###.#.#.###############.#.#.#######.#####.#.###.###.###.#.#.#.###.#####.#.###.###.#.#.###.###.#.#.###.###.#.#.###.#
+#...#.#.......#.......#.#.....#.#.#...#.....#.....#.#...#.#...#...#.#...#...#.#...#.........#.....#...#.#...#.#.#.....#.#.#...#...#.#.....#.#
+#.#.###.#.#####.#####.#.#.#.###.#.#.#.#.###.#.#.###.###.#.#.#.#.#.#####.###.#.#.#.#############.#####.###.#.#.#.#.#####.#.###.###.#####.###.#
+#.#.....#.......#...#.#.....#...#.#.#.......#.....#.#...#...#...#.#.......#.....#...#.........#.#...#.....#.#.#...#.....#.....#...#...#.#...#
+#.#######.#.###.#.#.#########.#.#.#.###.###.#####.###.###.#######.#.###############.#######.#.#.#.#.#####.###.#.###.###.#######.###.#.###.#.#
+#.#...........#.#.#.....#.....#...#...#.....#...#...#...#.#.....#.#.#...........#.#.........#.#.#.#.#.....#...#.#...#.#.#.....#...#.#...#.#.#
+#.#.#####.#.#.#.#.#####.#.###########.#.###.#.#.###.###.#.#.#####.#.#.#########.#.###########.#.#.#.#.#####.#####.###.#.#.###.###.#.###.#.#.#
+#...#.......#.#.#.#...#.#.....#...#...#...#.#.#...#...#.#...#...#...#.#.......#.#.#.....#.....#...#...#...#.#.....#.....#.#...#...#...#...#.#
+#.#######.#.#.###.#.#.#.#####.#.#.#####.#.#.#.#####.#.#.#####.#.#.#.#.#.###.#.#.#.#.#.###.#############.#.#.#.#.###.#####.#.###.###.#.###.#.#
+#.........#.#.#...#.#.#...#.#...#.....#.#.#...#.....#.#.......#.#.#...#...#.#.#.#...#...#.#.........#...#...#.....#...#.......#.............#
+#####.###.#.#.#.###.#.###.#.#########.###.#.###.#####.#########.###.#####.#.###.#.#.###.#.#####.###.#.###########.###.###.###.###.###.#.#.###
+#...#.#.....#.#.#...#...#.#.........#.....#.#...#.............#...#.#.....#...#.#.....#.#.......#.#...#.......#...#.#.........#.#.#...#.#...#
+#.#.#.#.#.#.#.#.#.###.###.#.#.#####.#####.###.#####.#########.###.#.#.#######.#.#######.#########.#########.#.#.###.#######.###.#.#.###.#.###
+#.#...#...#...#.#.#...#.....#.#...#.....#.#...#.........#...#...#...#.#.....#.#.#...........#...............#...#.........#...#.#...#...#...#
+#.#######.#.###.#.#.###.###.###.#.#######.#.###.#######.#.#.#.#########.###.#.#.#.#####.#.#.#.#.#############.###.###.#######.#.#####.###.#.#
+#.#...#...#.....#.#...#...#.....#.........#.#...#.....#...#.#.#.......#.#.....#.#...#...#.#...#.....#.........#...#...#.....#.....#.#.#...#.#
+#.#.#.#.###.#####.###.###.#.#############.#.#.###.#########.###.###.#.#.#######.###.#####.#########.#.#######.###.#.#.#.#.#######.#.#.###.#.#
+#...#.#.#...#.....#.....#.#...#...#.....#.#...#...........#.....#.#.#.....#...#...#.#.....#.#.....#.........#...#.#.#.#.#.#.....#...#.#.....#
+#######.#.#.#.#####.#####.###.###.#.###.#########.#####.#.#######.#.#.###.#.#.###.#.#.#####.#.#.#####.#.###.###.#.#.###.#.#.###.###.#.#.#.###
+#.....#.#.#...#...#...#...#...#...#...#.........#.#.....#.#.......#.#.....#.#.....#...#...#...#.....#...#...#...#.#.....#.#.#.......#.#.....#
+#.###.#.#.#.#####.###.#.###.###.#.###.###.#####.###.#####.#.#####.#.#####.#.#######.#####.#.#####.#.#####.#.#.###.#######.#.#.#######.###.#.#
+#...#...#.#.#.......#.#...#.#...#...#...#...#.#...#...#...#.#...#.#.....#.#.#.....#.#.....#.....#.#...#...#.#...#.......#...#...#...#.......#
+#.#.#.###.#.#.###.###.###.#.###.#.#####.###.#.###.#.#.###.#.###.#.#####.###.#.###.#.#.#.###.#####.###.#.###.#.#.#######.#######.#.#.#######.#
+#.#.#.#...#...#...#.....#.#.....#.#.....#.#.#.....#.#.....#...#.#.....#.....#...#.#.#.......#.....#.#...#.#.#.#.#.....................#...#.#
+###.#.#.###.###.###.#####.#####.###.#####.#.###.###.#####.###.#.#.###.#######.#.#.#.#.#.###.#.#####.###.#.#.#.#.#.#.###.#.#######.#.#.#.###.#
+#...#.#.....#.....#.....#.....#.#...#.....#...#.#...#.......................#.#.#.#.#.#.#...#...#.#.......#.#.#.#.#...#...#...#...#.#...#...#
+#.#########.#.#####.###.#####.#.#.#####.#.###.#.#####.###.#.###.#.#.#.###.###.#.###.#.#.#.#.###.#.#.###.###.#.#.#.###.#.###.#.#.###.#####.###
+#...........#.#...#...#.....#.#...#.....#.#...#.......#...#.#...#...................#...#.#.....#...#.#...#...#.#...#.......#.#.#...#...#...#
+#.#######.#####.#.#####.#####.#.###.#####.#.#.#########.#.#.###.#.#.#.#.#.#.###########.#.#.#####.###.#.#.###.#.###.###.#####.#.#.###.#.###.#
+#.......#.......#.....#.#...#.............................#.....#.#.#.#...#.#.............#.#.....#.....#.#...#...#.#...#.....#.#...#.#.....#
+#######.#.#.#########.#.#.#.#######.#.###.#.#######.#####.#######.#.#.#####.###.#######.###.#.#####.###.#.#.###.#.#.###.#.#####.###.#.#######
+#.....#.....#.....#...#...#.......#.#...#.#.......#.#.............#.#.#...#...#.....#...#...#.....#.....................#.................#.#
+#####.###.###.###.#.###.###.#####.#.#.#.#.#######.###.###.#.#######.#.#.#.###.#####.###.#.#.#####.#.#.#.#.#.#.#.#######.###.#.#####.#####.#.#
+#.....#...#...#.#.#.#.....#...#.#.#.#.#...#...#.............#.................#...#...#.#.#.......#.#.#...#...#.......#...#...#.......#...#.#
+#.#####.#.#.###.#.#.#########.#.#.#.#.#####.#.#.#######.#####.###########.#.###.#.###.#.#.#.#######.#.#.#####.#######.#.#.#####.#######.###.#
+#S......#.......#.............#.....#...................................#.......#.....#.............#...............#.........#.............#
+#############################################################################################################################################
+