2018-12-22 - Mode Maze
(original .ipynb)
target_x = 14
target_y = 796
depth = 5355
extra_x = 50
extra_y = 10
def initialize_geologic_index_lookup():
geo_index = []
for x in range(target_x + extra_x):
new_row = []
for y in range(target_y + extra_y):
if x == 0:
new_row.append(y * 48271)
elif y == 0:
new_row.append(x * 16807)
else:
new_row.append(None)
geo_index.append(new_row)
geo_index[0][0] = 0
geo_index[target_x][target_y] = 0
return geo_index
def geologic_index(geo_index, x, y):
if geo_index[x][y] is None:
geo_index[x][y] = erosion_level(geo_index, x-1, y) * erosion_level(geo_index, x, y-1)
return geo_index[x][y]
# A region's erosion level is its geologic index plus the cave system's depth, all modulo 20183
def erosion_level(geo_lookup, x, y):
return (depth + geologic_index(geo_lookup, x, y)) % 20183
# If the erosion level modulo 3 is 0, the region's type is rocky.
# If the erosion level modulo 3 is 1, the region's type is wet.
# If the erosion level modulo 3 is 2, the region's type is narrow.
def region_type(geo_lookup, x, y):
return erosion_level(geo_lookup, x, y) % 3
def part_one():
risk_level = 0
geo_index = initialize_geologic_index_lookup()
for x in range(target_x + 1):
for y in range(target_y + 1):
risk_level += region_type(geo_index, x, y)
return risk_level
print("part one:", part_one())
part one: 11972
import math
def build_world():
geo_index = initialize_geologic_index_lookup()
world = []
for x in range(target_x + extra_x):
row = []
for y in range(target_y + extra_y):
row.append(region_type(geo_index, x, y))
world.append(row)
return world
def neighbours4(grid, r, c):
max_r = len(grid)
max_c = len(grid[0])
candidates = (
(r-1, c), (r+1, c),
(r, c-1), (r, c+1)
)
for maybe_r, maybe_c in candidates:
if maybe_r == r and maybe_c == c:
continue
if maybe_r >= max_r or maybe_r < 0:
continue
if maybe_c >= max_c or maybe_c < 0:
continue
yield (maybe_r, maybe_c)
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, dsts):
#parent_of = {node: None for node in graph}
processed = set()
cost_of = {node: math.inf for node in graph}
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)
return [ cost_of[dst] for dst in dsts ]
def tools_required(world, r, c):
# You start at 0,0 (the mouth of the cave) with the torch equipped
if r == 0 and c == 0:
return ("t")
tile = world[r][c]
# In rocky regions, you can use the climbing gear or the torch.
if is_rocky(tile):
return ("c", "t")
# In wet regions, you can use the climbing gear or neither tool.
elif is_wet(tile):
return ("c", "n")
# In narrow regions, you can use the torch or neither tool.
elif is_narrow(tile):
return ("t", "n")
def is_rocky(region_type):
return region_type == 0
def is_wet(region_type):
return region_type == 1
def is_narrow(region_type):
return region_type == 2
def part_two():
world = build_world()
graph = {}
for r, row in enumerate(world):
for c, col in enumerate(row):
for t in tools_required(world, r, c):
key = f"{t}{r}-{c}"
neighbours = {}
for nr, nc in neighbours4(world, r, c):
nkey = f"{nr}-{nc}"
for nt in tools_required(world, nr, nc):
time = 1 if t == nt else 8
neighbours[nt+nkey] = time
graph[key] = neighbours
dsts = [ t+f"{target_x}-{target_y}" for t in tools_required(world, target_x, target_y) ]
return 1 + dijkstra(graph, "t0-0", dsts)[0]
print("part two: ", part_two())
part two: 1092