2019-12-18 - Many-Worlds Interpretation
(original .ipynb)
NOTE: Incomplete!!!
Day 18 puzzle input is a maze (mine is here) where capital letters represent doors, that require keys (lower case letters) to open (i.e. you need to collect "a" if you want to traverse through door "A"). Part 1 involves finding the fastest route through this maze to collect all keys. Part 2 involves splitting the maze into quadrants and having four different things moving through the maze. Ugh.
I kind of hated this one too - it's like travelling salesman if after visiting a node the graph changed :-/
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 == "#"
def is_connecting(s):
return s[0] == "_"
def is_key(s):
if (len(s) > 1):
return False
return ord(s) >= ord("a") and ord(s) <= ord("z")
def is_door(s):
if (len(s) > 1):
return False
return ord(s) >= ord("A") and ord(s) <= ord("Z")
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 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])
# 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 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_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) ]
return graph
from copy import deepcopy
import math
class SearchState:
def __init__(self, graph, current, visited, route, steps=0):
self.graph = graph
self.current = current
self.visited = visited
self.route = route
self.steps = steps
def move(self, node):
neighbours = self.graph[self.current]
if not (node in neighbours):
raise Exception(f"cannot move from {self.current} to {node}. valid moves: {neighbours.keys}")
visited = self.visited.union(set([node]))
route = self.route + [node]
steps = self.steps + neighbours[node]
new_graph = deepcopy(self.graph)
graph_delete(new_graph, self.current)
if is_key(node):
# ignore_error=True, in case there's no door for the key
graph_delete(new_graph, node.upper(), True)
# if all_keys.issubset(visited):
# solutions.append(steps)
# return None
should_delete_door = lambda node: is_door(node) and len(new_graph[node]) == 1
should_delete_connector = lambda node: is_connecting(node) and len(new_graph[node]) < 3
nodes_to_delete = [ node for node in new_graph if should_delete_door(node) or should_delete_connector(node) ]
while nodes_to_delete:
for node in nodes_to_delete:
graph_delete(new_graph, node)
nodes_to_delete = [ node for node in new_graph if should_delete_door(node) or should_delete_connector(node) ]
return SearchState(new_graph, node, visited, route, steps)
def __repr__(self):
return "->".join(self.route)
def __str__(self):
return "->".join(self.route)
def step(state):
to_visit = [ node for node in state.graph[state.current] if not is_door(node) ]
new_states = [ state.move(node) for node in to_visit ]
return [ s for s in new_states if s ]
def step_all(states):
new_states = []
for state in states:
new_states += step(state)
# assume that anything outside the quickest 2048 so far are probably not the fastest solutions
return sorted(new_states, key=lambda state: state.steps)[:10000]
def solve2(graph):
global solutions
global all_keys
solutions = []
all_keys = set([ node for node in graph if is_key(node) ])
states = [
SearchState(graph, "@", set(), [])
]
while len(solutions) < 1:
pprint(states)
states = step_all(states)
print(sorted(solutions)[0])
print("----------------------------")
def solve_inner(state, indent=""):
global all_keys
global total
global best
# if we're already more than the limit, give up
if best < state.steps:
return math.inf
# print(f"{indent}{state.current}")
if all_keys.issubset(state.visited):
total += 1
if state.steps < best:
best = state.steps
print(f"new best: {best}")
if total % 100 == 0:
print(f"found {total} solutions")
# print(f"new solution: {state.steps} (best is {best})")
return state.steps
neighbours = [ n for n in state.graph[state.current] if not is_door(n) ]
if not neighbours:
return math.inf
return min([ solve_inner(state.move(n), indent+" ") for n in neighbours])
best = math.inf
total = 0
def solve(graph):
global all_keys
global best
global total
pprint(graph)
total = 0
all_keys = set([ node for node in graph if is_key(node) ])
best = math.inf
ans = solve_inner(SearchState(graph, "@", set(), []))
print(ans)
print("------------------------")
return ans
from pprint import pprint solutions = [] all_keys = None maze_str_0 = """######### #b.A.@.a# #########""" graph_0 = parse_maze(maze_str_0) maze_str_1 = """######################## #f.D.E.e.C.b.A.@.a.B.c.# ######################.# #d.....................# ########################""" graph_1 = parse_maze(maze_str_1) maze_str_2 = """######################## #...............b.C.D.f# #.###################### #.....@.a.B.c.d.A.e.F.g# ########################""" graph_2 = parse_maze(maze_str_2) maze_str_3 = """################# #i.G..c...e..H.p# ########.######## #j.A..b...f..D.o# ########@######## #k.E..a...g..B.n# ########.######## #l.F..d...h..C.m# #################""" graph_3 = parse_maze(maze_str_3) maze_str_4 = """######################## #@..............ac.GI.b# ###d#e#f################ ###A#B#C################ ###g#h#i################ ########################""" graph_4 = parse_maze(maze_str_4) solve(graph_0) solve(graph_1) solve(graph_2) solve(graph_3) solve(graph_4)
defaultdict(, {'@': {'A': 2, 'a': 2}, 'A': {'@': 2, 'b': 2}, 'a': {'@': 2}, 'b': {'A': 2}}) new best: 8 8 ------------------------ defaultdict( , {'@': {'A': 2, 'a': 2}, 'A': {'@': 2, 'b': 2}, 'B': {'a': 2, 'c': 2}, 'C': {'b': 2, 'e': 2}, 'D': {'E': 2, 'f': 2}, 'E': {'D': 2, 'e': 2}, 'a': {'@': 2, 'B': 2}, 'b': {'A': 2, 'C': 2}, 'c': {'B': 2, 'd': 24}, 'd': {'c': 24}, 'e': {'C': 2, 'E': 2}, 'f': {'D': 2}}) new best: 86 86 ------------------------ defaultdict( , {'@': {'a': 2, 'b': 22}, 'A': {'d': 2, 'e': 2}, 'B': {'a': 2, 'c': 2}, 'C': {'D': 2, 'b': 2}, 'D': {'C': 2, 'f': 2}, 'F': {'e': 2, 'g': 2}, 'a': {'@': 2, 'B': 2}, 'b': {'@': 22, 'C': 2}, 'c': {'B': 2, 'd': 2}, 'd': {'A': 2, 'c': 2}, 'e': {'A': 2, 'F': 2}, 'f': {'D': 2}, 'g': {'F': 2}}) new best: 144 new best: 136 new best: 132 132 ------------------------ defaultdict( , {'@': {'a': 3, 'b': 3, 'c': 5, 'd': 5, 'e': 5, 'f': 3, 'g': 3, 'h': 5}, 'A': {'b': 3, 'j': 2}, 'B': {'g': 3, 'n': 2}, 'C': {'h': 3, 'm': 2}, 'D': {'f': 3, 'o': 2}, 'E': {'a': 3, 'k': 2}, 'F': {'d': 3, 'l': 2}, 'G': {'c': 3, 'i': 2}, 'H': {'e': 3, 'p': 2}, 'a': {'@': 3, 'E': 3, 'd': 6, 'g': 4, 'h': 6}, 'b': {'@': 3, 'A': 3, 'c': 6, 'e': 6, 'f': 4}, 'c': {'@': 5, 'G': 3, 'b': 6, 'e': 4, 'f': 6}, 'd': {'@': 5, 'F': 3, 'a': 6, 'g': 6, 'h': 4}, 'e': {'@': 5, 'H': 3, 'b': 6, 'c': 4, 'f': 6}, 'f': {'@': 3, 'D': 3, 'b': 4, 'c': 6, 'e': 6}, 'g': {'@': 3, 'B': 3, 'a': 4, 'd': 6, 'h': 6}, 'h': {'@': 5, 'C': 3, 'a': 6, 'd': 4, 'g': 6}, 'i': {'G': 2}, 'j': {'A': 2}, 'k': {'E': 2}, 'l': {'F': 2}, 'm': {'C': 2}, 'n': {'B': 2}, 'o': {'D': 2}, 'p': {'H': 2}}) new best: 168 new best: 166 new best: 164 new best: 162 new best: 158 new best: 156 new best: 154 new best: 152 new best: 150 new best: 148 found 100 solutions new best: 146 new best: 144 new best: 142 new best: 140 new best: 138 new best: 136 found 200 solutions
puzzle_input_str = open("puzzle_input/day18.txt", "r").read()
puzzle_input = parse_maze(puzzle_input_str)
# doors = [ n for n in puzzle_input if is_door(n) ]
# door_neighbours = [ (d,len(puzzle_input[d])) for d in doors ]
# print(doors)
# print(len(puzzle_input.keys()))
# pprint(puzzle_input)
solve(puzzle_input)
defaultdict(, {'@': {'B': 131, 'E': 63, 'S': 27, 'T': 259, 'W': 239, 'Y': 275, 'e': 52, 'n': 194, 'o': 68, 's': 14, 'u': 32}, 'A': {'J': 26, 'a': 11, 'j': 7}, 'B': {'@': 131, 'E': 192, 'S': 156, 'T': 130, 'W': 370, 'Y': 146, 'e': 83, 'n': 65, 'o': 197, 's': 145, 'u': 161}, 'C': {'G': 90, 'K': 48, 'R': 72, 'Y': 26, 'a': 95, 'z': 3}, 'E': {'@': 63, 'B': 192, 'O': 18, 'S': 86, 'T': 320, 'W': 300, 'X': 34, 'Y': 336, 'e': 113, 'n': 255, 'o': 131, 's': 75, 'u': 95}, 'F': {'N': 36, 'Q': 54, 'm': 57}, 'G': {'C': 90, 'K': 44, 'R': 20, 'Y': 98, 'a': 11}, 'H': {'h': 9, 'l': 11}, 'J': {'A': 26, 'a': 27, 'h': 7}, 'K': {'C': 48, 'G': 44, 'R': 26, 'Y': 56, 'a': 49, 'r': 9}, 'N': {'F': 36, 'i': 11}, 'O': {'E': 18, 'X': 42}, 'P': {'p': 9, 'v': 9}, 'Q': {'F': 54, 'm': 61, 'o': 49, 'x': 29}, 'R': {'C': 72, 'G': 20, 'K': 26, 'Y': 80, 'a': 25, 'g': 9}, 'S': {'@': 27, 'B': 156, 'E': 86, 'T': 284, 'W': 264, 'Y': 300, 'e': 77, 'n': 219, 'o': 95, 's': 39, 'u': 59}, 'T': {'@': 259, 'B': 130, 'E': 320, 'S': 284, 'W': 498, 'Y': 30, 'e': 211, 'n': 73, 'o': 325, 's': 273, 'u': 289}, 'W': {'@': 239, 'B': 370, 'E': 300, 'S': 264, 'T': 498, 'Y': 514, 'e': 291, 'n': 433, 'o': 305, 's': 229, 't': 11, 'u': 269}, 'X': {'E': 34, 'O': 42, 'q': 9}, 'Y': {'@': 275, 'B': 146, 'C': 26, 'E': 336, 'G': 98, 'K': 56, 'R': 80, 'S': 300, 'T': 30, 'W': 514, 'a': 103, 'e': 227, 'n': 89, 'o': 341, 's': 289, 'u': 305}, 'a': {'A': 11, 'C': 95, 'G': 11, 'J': 27, 'K': 49, 'R': 25, 'Y': 103}, 'b': {'f': 52, 'q': 18}, 'c': {'i': 70, 'k': 32, 'w': 76}, 'd': {'s': 126}, 'e': {'@': 52, 'B': 83, 'E': 113, 'S': 77, 'T': 211, 'W': 291, 'Y': 227, 'n': 146, 'o': 118, 's': 66, 'u': 82}, 'f': {'b': 52, 'q': 54}, 'g': {'R': 9}, 'h': {'H': 9, 'J': 7}, 'i': {'N': 11, 'c': 70, 'w': 18}, 'j': {'A': 7}, 'k': {'c': 32}, 'l': {'H': 11, 'p': 16}, 'm': {'F': 57, 'Q': 61}, 'n': {'@': 194, 'B': 65, 'E': 255, 'S': 219, 'T': 73, 'W': 433, 'Y': 89, 'e': 146, 'o': 260, 's': 208, 'u': 224}, 'o': {'@': 68, 'B': 197, 'E': 131, 'Q': 49, 'S': 95, 'T': 325, 'W': 305, 'Y': 341, 'e': 118, 'n': 260, 's': 80, 'u': 92, 'x': 24}, 'p': {'P': 9, 'l': 16}, 'q': {'X': 9, 'b': 18, 'f': 54}, 'r': {'K': 9}, 's': {'@': 14, 'B': 145, 'E': 75, 'S': 39, 'T': 273, 'W': 229, 'Y': 289, 'd': 126, 'e': 66, 'n': 208, 'o': 80, 'u': 44}, 't': {'W': 11, 'y': 24}, 'u': {'@': 32, 'B': 161, 'E': 95, 'S': 59, 'T': 289, 'W': 269, 'Y': 305, 'e': 82, 'n': 224, 'o': 92, 's': 44}, 'v': {'P': 9}, 'w': {'c': 76, 'i': 18}, 'x': {'Q': 29, 'o': 24}, 'y': {'t': 24}, 'z': {'C': 3}}) new best: 3334 new best: 3274 new best: 3258 new best: 3198 new best: 3150 new best: 3102 new best: 3082 new best: 3078 new best: 3070 new best: 3050 found 100 solutions
My algorithm is extremely suboptimal so I just kept this running for 10 minutes or so before coming back and trying the latest "new best" value (which was 3048). This clearly won't work for Part 2 but I cannot motivate myself to revisit this and rewrite it from scratch.