2019-12-20 - Donut Maze
(original .ipynb)
Day 20 puzzle input is a donut-shaped maze (mine is here) with numerous entrances both on the inside and outside of the maze. Part 1 involves finding the shortest path from node "AA" to "ZZ". Part 2 involves assuming the maze has some weird recursion (going into the inside exit "AA" results in you appearing in entrance "ZZ" ... but in another "dimension". You have to find the shortest path from AA to ZZ in the same dimension, but you can traverse different dimensions.
Need to dust off my maze parsing and solving code from Day 18 - this problem seems a little more solvable with than that one. Maybe.
from itertools import combinations
def create_node_namer():
n = 0
while True:
yield f"_{n}"
n += 1
def is_space(s):
return s == "."
def is_wall(s):
return s == "#" or s == " "
def is_connecting(s):
return s[0] == "_"
def graph_delete(graph, node, ignore_error=False):
if not node in graph:
if ignore_error:
return
raise Exception(f"Node {node} was not found in graph, can't delete")
neighbours = graph[node]
new_edges = list(combinations([n for n in neighbours], 2))
for edge in new_edges:
node_1, node_2 = edge
new_distance = neighbours[node_1] + neighbours[node_2]
# we can add this edge if:
# 1. the nodes weren't already connected
# 2. the nodes were connected, but this edge is cheaper
if (not node_2 in graph[node_1]) or graph[node_1][node_2] > new_distance:
graph[node_1][node_2] = new_distance
graph[node_2][node_1] = new_distance
# finally clean up all references to our old node
for neighbour in neighbours:
del graph[neighbour][node]
del graph[node]
# def cheapest_next_key(graph, from_node):
# neighbours = graph[from_node]
# neighbouring_keys = [ n for n in neighbours if is_key(n) ]
# sorted_neighbouring_keys = sorted(neighbouring_keys, key=lambda n: neighbours[n])
# return sorted_neighbouring_keys[0]
# def shake_graph(graph):
# should_delete_door = lambda node: is_door(node) and len(graph[node]) == 1
# should_delete_connector = lambda node: is_connecting(node) and len(graph[node]) < 3
# nodes_to_delete = [ node for node in graph if should_delete_door(node) or should_delete_connector(node) ]
# while nodes_to_delete:
# for node in nodes_to_delete:
# graph_delete(graph, node)
# nodes_to_delete = [ node for node in graph if should_delete_door(node) or should_delete_connector(node) ]
def is_processed_portal(s):
return len(s) > 1
def is_portal_char(s):
return ord(s) >= ord("A") and ord(s) <= ord("Z")
def get_portal_name(portals, portal_name):
if portal_name in portals:
portal_name += "'"
portals.add(portal_name)
return portal_name
def process_portals(maze_lines):
all_portals = set()
positions = []
for r, row in enumerate(maze_lines):
for c, col in enumerate(row):
if is_processed_portal(col):
continue
if is_portal_char(col):
# look down
if (2 + r) < len(maze_lines) and is_portal_char(maze_lines[r+1][c]) and is_space(maze_lines[r+2][c]):
portal_name = get_portal_name(all_portals, col + maze_lines[r+1][c])
positions.append((r+2,c))
maze_lines[r+2][c] = portal_name
maze_lines[r+1][c] = "."
maze_lines[r][c] = "."
# look up
elif is_space(maze_lines[r-1][c]) and is_portal_char(maze_lines[r+1][c]):
portal_name = get_portal_name(all_portals, col + maze_lines[r+1][c])
positions.append((r-1,c))
maze_lines[r-1][c] = portal_name
maze_lines[r][c] = "."
maze_lines[r+1][c] = "."
# look right
elif is_portal_char(row[c+1]) and is_space(row[c+2]):
portal_name = get_portal_name(all_portals, col + maze_lines[r][c+1])
positions.append((r,c+2))
maze_lines[r][c+2] = portal_name
maze_lines[r][c] = "."
maze_lines[r][c+1] = "."
# look left
elif is_space(row[c-1]) and is_portal_char(row[c+1]):
portal_name = get_portal_name(all_portals, col + maze_lines[r][c+1])
positions.append((r,c-1))
maze_lines[r][c-1] = portal_name
maze_lines[r][c] = "."
maze_lines[r][c+1] = "."
pprint(positions)
return maze_lines
def parse_maze(maze_str):
# 1. split into lines, and then lines into list of strings: ("a...b" => [ "a", ".", ".", ".", "c"])
maze_lines = []
for line_str in maze_str.split("\n"):
maze_lines.append([c for c in line_str])
# 1.5 - identify
maze_lines = process_portals(maze_lines)
# 2. find the spaces that connect two levels vertically, and swap in a string with a name that
# doesn't clash like "_1"
connecting_tiles = []
for line_idx, line in enumerate(maze_lines):
for tile_idx, tile in enumerate(line):
# we don't want to replace if it's a wall or non-space
if is_wall(tile) or (not is_space(tile)):
continue
should_replace = False
if line_idx > 0:
tile_above = maze_lines[line_idx - 1][tile_idx]
if not is_wall(tile_above):
should_replace = True
if (1 + line_idx) < len(maze_lines):
tile_below = maze_lines[line_idx + 1][tile_idx]
if not is_wall(tile_below):
should_replace = True
if should_replace:
connecting_tiles.append((line_idx, tile_idx))
namer = create_node_namer()
for (line_idx, tile_idx) in connecting_tiles:
maze_lines[line_idx][tile_idx] = next(namer)
# 3. start creating the graph by finding horizontal edges
# so for "a...b" we'll add {"a": {"b": 4}, "b": {"a": 4}}
from collections import defaultdict
graph = defaultdict(dict)
for line_idx, line in enumerate(maze_lines):
current_node = None
current_count = 0
for tile_idx, tile in enumerate(line):
current_count += 1
# if we hit a wall, we need to reset current_node/count
if is_wall(tile):
current_node = None
current_count = 0
continue
if not is_space(tile):
if current_node:
graph[current_node][tile] = current_count
graph[tile][current_node] = current_count
current_node = tile
current_count = 0
# 4. add the vertical edges (they'll reach DOWN until they find a non-space node)
for line_idx, line in enumerate(maze_lines):
for tile_idx, tile in enumerate(line):
if is_wall(tile) or is_space(tile):
continue
count = 0
next_line_idx = line_idx + 1
while next_line_idx < len(maze_lines):
count += 1
next_tile = maze_lines[next_line_idx][tile_idx]
if is_space(next_tile):
next_line_idx += 1
continue
if is_wall(next_tile):
break
graph[tile][next_tile] = count
graph[next_tile][tile] = count
break
# 5. finally we'll make a pass to remove:
# - doors that have only one neighbour (dead end)
# - connectors unless they're a real choice (>2 neighbours)
# and update graph accordingly. we'll need to do this until we return no nodes to delete
# should_delete_door = lambda node: is_door(node) and len(graph[node]) == 1
should_delete_door = lambda node: False
# should_delete_connector = lambda node: is_connecting(node) and len(graph[node]) < 3
should_delete_connector = lambda node: is_connecting(node)
nodes_to_delete = [ node for node in graph if should_delete_door(node) or should_delete_connector(node) ]
while nodes_to_delete:
for node in nodes_to_delete:
graph_delete(graph, node)
nodes_to_delete = [ node for node in graph if should_delete_door(node) or should_delete_connector(node) ]
# connect up the warp portals
root_nodes = [node for node in graph.keys() if not ("'" in node)]
for node in root_nodes:
warp_node = node + "'"
graph[node][warp_node] = 1
graph[warp_node][node] = 1
return graph
import math
from pprint import pprint
def cheapest_node(cost_of, src, processed):
cheapest_cost = math.inf
cheapest_node = None
for node in cost_of:
cost = cost_of[node]
if cost < cheapest_cost and node not in processed:
cheapest_cost = cost
cheapest_node = node
return cheapest_node
def dijkstra(graph, src, dst, debug=False):
cost_of = {node:math.inf for node in graph} # if node != src}
parent_of = {node:None for node in graph} # if node != src}
processed = set()
for node in graph[src]:
cost_of[node] = graph[src][node]
node = cheapest_node(cost_of, src, processed)
while node is not None:
cost = cost_of[node]
neighbours = graph[node]
for neighbour in neighbours.keys():
new_cost = cost + neighbours[neighbour]
if cost_of[neighbour] > new_cost:
cost_of[neighbour] = new_cost
parent_of[neighbour] = node
processed.add(node)
node = cheapest_node(cost_of, src, processed)
if debug:
route = []
node = dst
while node != None:
route.append(node)
node = parent_of[node]
print(route[::-1])
return cost_of[dst]
def solve(maze_str, src, dst, debug=False):
maze = parse_maze(maze_str)
pprint(maze)
return dijkstra(maze, src, dst, debug)
test_input = """ A
A
#######.#########
#######.........#
#######.#######.#
#######.#######.#
#######.#######.#
##### B ###.#
BC...## C ###.#
##.## ###.#
##...DE F ###.#
##### G ###.#
#########.#####.#
DE..#######...###.#
#.#########.###.#
FG..#########.....#
###########.#####
Z
Z """
print(solve(test_input, "AA", "ZZ"))
[(2, 9), (6, 9), (8, 2), (10, 6), (12, 11), (13, 2), (15, 2), (16, 13)] defaultdict(, {'AA': {"AA'": 1, 'BC': 4, 'FG': 30, 'ZZ': 26}, "AA'": {'AA': 1}, 'BC': {'AA': 4, "BC'": 1, 'FG': 32, 'ZZ': 28}, "BC'": {'BC': 1, 'DE': 6}, 'DE': {"BC'": 6, "DE'": 1}, "DE'": {'DE': 1, "FG'": 4}, 'FG': {'AA': 30, 'BC': 32, "FG'": 1, 'ZZ': 6}, "FG'": {"DE'": 4, 'FG': 1}, 'ZZ': {'AA': 26, 'BC': 28, 'FG': 6, "ZZ'": 1}, "ZZ'": {'ZZ': 1}}) 23
bigger_test_input = """ A
A
#################.#############
#.#...#...................#.#.#
#.#.#.###.###.###.#########.#.#
#.#.#.......#...#.....#.#.#...#
#.#########.###.#####.#.#.###.#
#.............#.#.....#.......#
###.###########.###.#####.#.#.#
#.....# A C #.#.#.#
####### S P #####.#
#.#...# #......VT
#.#.#.# #.#####
#...#.# YN....#.#
#.###.# #####.#
DI....#.# #.....#
#####.# #.###.#
ZZ......# QG....#..AS
###.### #######
JO..#.#.# #.....#
#.#.#.# ###.#.#
#...#..DI BU....#..LF
#####.# #.#####
YN......# VT..#....QG
#.###.# #.###.#
#.#...# #.....#
###.### J L J #.#.###
#.....# O F P #.#...#
#.###.#####.#.#####.#####.###.#
#...#.#.#...#.....#.....#.#...#
#.#####.###.###.#.#.#########.#
#...#.#.....#...#.#.#.#.....#.#
#.###.#####.###.###.#.#.#######
#.#.........#...#.............#
#########.###.###.#############
B J C
U P P """
print(solve(bigger_test_input, "AA", "ZZ", True))
[(2, 21), (8, 19), (8, 23), (11, 34), (13, 28), (15, 4), (17, 4), (17, 28), (17, 34), (19, 4), (21, 10), (21, 28), (21, 34), (23, 4), (23, 28), (23, 34), (28, 15), (28, 17), (28, 23), (34, 13), (34, 17), (34, 21)] defaultdict(, {'AA': {"AA'": 1, 'AS': 12, 'CP': 12}, "AA'": {'AA': 1}, 'AS': {'AA': 12, "AS'": 1, 'CP': 22}, "AS'": {'AS': 1, 'QG': 10}, 'BU': {"BU'": 1, 'LF': 10, "QG'": 12, "VT'": 4}, "BU'": {'BU': 1, "JO'": 8}, 'CP': {'AA': 12, 'AS': 22, "CP'": 1}, "CP'": {'CP': 1, 'JP': 8}, 'DI': {"DI'": 1, 'JO': 26, 'ZZ': 20}, "DI'": {'DI': 1, "YN'": 8}, 'JO': {'DI': 26, "JO'": 1, 'ZZ': 12}, "JO'": {"BU'": 8, 'JO': 1}, 'JP': {"CP'": 8, "JP'": 1}, "JP'": {'JP': 1, "LF'": 10}, 'LF': {'BU': 10, "LF'": 1, "QG'": 20, "VT'": 12}, "LF'": {"JP'": 10, 'LF': 1}, 'QG': {"AS'": 10, "QG'": 1}, "QG'": {'BU': 12, 'LF': 20, 'QG': 1, "VT'": 10}, 'VT': {"VT'": 1, 'YN': 8}, "VT'": {'BU': 4, 'LF': 12, "QG'": 10, 'VT': 1}, 'YN': {'VT': 8, "YN'": 1}, "YN'": {"DI'": 8, 'YN': 1}, 'ZZ': {'DI': 20, 'JO': 12, "ZZ'": 1}, "ZZ'": {'ZZ': 1}}) ['AS', "AS'", 'QG', "QG'", 'BU', "BU'", "JO'", 'JO', 'ZZ'] 58
puzzle_input_str = open("puzzle_input/day20.txt", "r").read()
print(solve(puzzle_input_str, "AA", "ZZ", True))
[(2, 43), (2, 51), (2, 63), (2, 69), (2, 73), (2, 85), (2, 91), (36, 43), (36, 53), (36, 59), (36, 65), (36, 77), (36, 81), (36, 95), (39, 134), (41, 4), (41, 38), (41, 134), (43, 100), (49, 38), (51, 100), (53, 4), (53, 134), (55, 4), (55, 134), (57, 100), (61, 38), (63, 4), (63, 100), (63, 134), (65, 4), (71, 38), (73, 4), (75, 38), (75, 100), (75, 134), (79, 100), (79, 134), (81, 38), (83, 4), (83, 38), (85, 4), (90, 45), (90, 57), (90, 63), (90, 67), (90, 75), (90, 85), (90, 93), (124, 45), (124, 53), (124, 65), (124, 73), (124, 77), (124, 83), (124, 97)] defaultdict(, {'AA': {"AA'": 1, 'UT': 4, "ZV'": 74}, "AA'": {'AA': 1}, 'EK': {"EK'": 1, "YL'": 54}, "EK'": {'EK': 1, 'QP': 56}, 'FV': {"FV'": 1, 'RP': 48}, "FV'": {'FV': 1, 'ZP': 76}, 'HK': {"HK'": 1, 'IB': 66}, "HK'": {'HK': 1, "NU'": 68}, 'IB': {'HK': 66, "IB'": 1}, "IB'": {'IB': 1, 'QR': 64}, 'JB': {"JB'": 1, 'YS': 50, 'ZZ': 4}, "JB'": {'JB': 1, "LS'": 68}, 'JN': {"JN'": 1, 'JQ': 54}, "JN'": {'JN': 1, 'RX': 62}, 'JQ': {'JN': 54, "JQ'": 1}, "JQ'": {'JQ': 1, "NZ'": 52}, 'LP': {"LP'": 1, 'ZV': 70}, "LP'": {'LP': 1, "OF'": 82}, 'LS': {"LS'": 1, 'XP': 58}, "LS'": {"JB'": 68, 'LS': 1}, 'MP': {"MP'": 1, 'TV': 84}, "MP'": {'MP': 1, 'NZ': 4, 'OF': 80, "QP'": 78}, 'NU': {"NU'": 1, "RP'": 74}, "NU'": {"HK'": 68, 'NU': 1}, 'NZ': {"MP'": 4, "NZ'": 1, 'OF': 82, "QP'": 80}, "NZ'": {"JQ'": 52, 'NZ': 1}, 'OF': {"MP'": 80, 'NZ': 82, "OF'": 1, "QP'": 4}, "OF'": {"LP'": 82, 'OF': 1}, 'QP': {"EK'": 56, "QP'": 1}, "QP'": {"MP'": 78, 'NZ': 80, 'OF': 4, 'QP': 1}, 'QR': {"IB'": 64, "QR'": 1}, "QR'": {'QR': 1, "SK'": 50}, 'RP': {'FV': 48, "RP'": 1}, "RP'": {'NU': 74, 'RP': 1}, 'RX': {"JN'": 62, "RX'": 1}, "RX'": {'RX': 1, "UT'": 66}, 'SK': {"SK'": 1, 'YL': 58}, "SK'": {"QR'": 50, 'SK': 1}, 'TD': {"TD'": 1, "XP'": 70}, "TD'": {'TD': 1, 'ZJ': 70}, 'TV': {'MP': 84, "TV'": 1}, "TV'": {'TV': 1, "ZJ'": 68}, 'UT': {'AA': 4, "UT'": 1, "ZV'": 72}, "UT'": {"RX'": 66, 'UT': 1}, 'XP': {'LS': 58, "XP'": 1}, "XP'": {'TD': 70, 'XP': 1}, 'YL': {'SK': 58, "YL'": 1}, "YL'": {'EK': 54, 'YL': 1}, 'YS': {'JB': 50, "YS'": 1, 'ZZ': 48}, "YS'": {'YS': 1, "ZP'": 76}, 'ZJ': {"TD'": 70, "ZJ'": 1}, "ZJ'": {"TV'": 68, 'ZJ': 1}, 'ZP': {"FV'": 76, "ZP'": 1}, "ZP'": {"YS'": 76, 'ZP': 1}, 'ZV': {'LP': 70, "ZV'": 1}, "ZV'": {'AA': 74, 'UT': 72, 'ZV': 1}, 'ZZ': {'JB': 4, 'YS': 48, "ZZ'": 1}, "ZZ'": {'ZZ': 1}}) ['UT', "UT'", "RX'", 'RX', "JN'", 'JN', 'JQ', "JQ'", "NZ'", 'NZ', "MP'", 'MP', 'TV', "TV'", "ZJ'", 'ZJ', "TD'", 'TD', "XP'", 'XP', 'LS', "LS'", "JB'", 'JB', 'ZZ'] 676