Due to real-life scheduling constraints, I didn’t start working on Day 17 until this morning, and I just finished both parts this evening. It was tricky enough that I took a break to solve Day 18 before I finished even part 1 of Day 17.
Discussion of Day 17 solution
A problem like this might have been more effectively solved with specific path finding algorithms. However, I’m not familiar with the nuances of those, so I approached it with general dynamic programming concepts. There are some similar, but simpler, Project Euler problems which I had solved with similar DP approaches, and I’ve discussed those problems and shared my code in earlier posts: Project Euler / programming problems - #185 by yebellz and Project Euler / programming problems - #244 by yebellz.
The Day 17 AoC problem is made significantly trickier by constraints on the shape of paths allowed. Thus, rather than just tracking the minimum cost (heat loss) needed to reach each intermediate point, one also needs to be aware of the movement constraints imposed by the corresponding paths. I handled this by tracking a list of the “best” paths for each intermediate point in the map, where the concept of “best” means keeping the dominant paths with pareto efficient combinations of cost and movement restrictions.
With this algorithm, tackling the entire 13x13 test case at once worked very quickly. However, it became way too slow when scaling it up to the 141x141 problem input. So, I modified the code by adding an outer loop that progressively grows the area under consideration. It starts with the 21x21 top-left region and very quickly figures out the best paths to the bottom and right edges of that region. Then, the region is expanded by 5 more rows and columns and the optimization is started again, but just from those leading edges. Using this divide-and-conquer approach, the part 1 code runs in about 6.3 seconds on my machine. This could probably be sped up much further by applying some better heuristics to more aggressively prune bad paths, and maybe even tuning the divide-and-conquer expansion schedule.
Part 1 Code
import numpy as np
map = []
for line in open("17input", 'r').readlines():
#for line in open("17test", 'r').readlines():
map.append([int(c) for c in line.strip()])
map = np.asarray(map)
max_h, max_w = map.shape
print(max_h, max_w)
worst = np.sum(np.diagonal(map)) + np.sum(np.diagonal(map, 1))
print(worst)
paths = [[ [] for i in range(max_w) ] for j in range(max_h)]
def tail(path):
last = path[-1]
if path.endswith(last * 3):
return 3
if path.endswith(last * 2):
return 2
return 1
def dominates(cost_a, path_a, cost_b, path_b, strict=False):
if path_a[-1] != path_b[-1]:
return False
if strict and tail(path_a) == tail(path_b) and cost_a == cost_b:
return False
if tail(path_a) <= tail(path_b) and cost_a <= cost_b:
return True
def update(new_cost, new_path, position):
if position == (0, 0):
return
new_cost += map[position[0], position[1]]
current_paths = paths[position[0]][position[1]]
for cost, path in current_paths:
if dominates(cost, path, new_cost, new_path):
return
current_paths[:] = [(cost, path) for cost, path in current_paths if not dominates(new_cost, new_path, cost, path)]
current_paths.append((new_cost, new_path))
queue.append((position, new_cost, new_path))
queue = [((0, 0), 0, "")]
steps = 0
h = w = 21
while h < max_h:
h += 5
w += 5
while queue:
position, cost, path = queue[0]
queue = queue[1:]
if position == (h - 1, w - 1):
continue
if (not path.endswith('RRR')) and (not path.endswith('L')) and position[1] < (w - 1):
new_path = path + "R"
next_position = (position[0], position[1] + 1)
update(cost, new_path, next_position)
if (not path.endswith('DDD')) and (not path.endswith('U')) and position[0] < (h - 1):
new_path = path + "D"
next_position = (position[0] + 1, position[1])
update(cost, new_path, next_position)
if (not path.endswith('LLL')) and (not path.endswith('R')) and position[1] > 0 and position[0] > 0 and position[0] < (h - 1):
new_path = path + "L"
next_position = (position[0], position[1] - 1)
update(cost, new_path, next_position)
if (not path.endswith('UUU')) and (not path.endswith('D')) and position[0] > 0 and position[1] > 0 and position[1] < (w - 1):
new_path = path + "U"
next_position = (position[0] - 1, position[1])
update(cost, new_path, next_position)
steps += 1
if steps % 10000 == 0:
print(h, steps, len(queue))
for i in range(h):
for cost, path in paths[h-1][i]:
queue.append(( (h-1, i), cost, path))
for cost, path in paths[i][h-1]:
queue.append(( (i, h-1), cost, path))
print(paths[h-1][w-1])
lowest = 5000
for cost, path in paths[h-1][w-1]:
lowest = min(lowest, cost)
print(lowest)
The part 2 code is not too substantially different in approach, as the main change is to just capture the differences in movement constraints. One wrinkle is that minimum movement constraint leads to the potential paths overshooting outside of the limiting region. As a consequence of these difference, this part 2 code runs noticeably slower (taking about 100 seconds), even after changing the divide-and-conquer schedule. It could probably benefit significantly from further tweaks and application of heuristics.
Part 2 Code
import numpy as np
map = []
for line in open("17input", 'r').readlines():
#for line in open("17test", 'r').readlines():
map.append([int(c) for c in line.strip()])
map = np.asarray(map)
max_h, max_w = map.shape
print(max_h, max_w)
worst = np.sum(np.diagonal(map)) + np.sum(np.diagonal(map, 1))
print(worst)
paths = [[ [] for i in range(max_w) ] for j in range(max_h)]
def tail(path):
if len(path) == 0:
return 0
last = path[-1]
i = 0
while path.endswith(last):
i += 1
path = path[:-1]
return i
def dominates(cost_a, path_a, cost_b, path_b,):
if path_a[-1] != path_b[-1]:
return False
if tail(path_a) != tail(path_b):
return False
if cost_a <= cost_b:
return True
def update(new_cost, new_path, position):
if position == (0, 0):
return
if position[0] < 0 or position[0] >= max_h or position[1] < 0 or position[1] >= max_w:
return
if position[0] == max_h - 1 and new_path[-1] == "D" and tail(new_path) < 4:
return
if position[1] == max_w - 1 and new_path[-1] == "R" and tail(new_path) < 4:
return
new_cost += map[position[0], position[1]]
current_paths = paths[position[0]][position[1]]
for cost, path in current_paths:
if dominates(cost, path, new_cost, new_path):
return
current_paths[:] = [(cost, path) for cost, path in current_paths if not dominates(new_cost, new_path, cost, path)]
current_paths.append((new_cost, new_path))
queue.append((position, new_cost, new_path))
queue = [((0, 0), 0, "")]
steps = 0
h = w = 21
while h < max_h:
h += 2
w += 2
while queue:
position, cost, path = queue[0]
queue = queue[1:]
if position == (max_h - 1, max_w - 1):
continue
if tail(path) > 0 and tail(path) < 4:
new_path = path + path[-1]
if new_path[-1] == "R":
next_position = (position[0], position[1] + 1)
if new_path[-1] == "D":
next_position = (position[0] + 1, position[1])
if new_path[-1] == "L":
next_position = (position[0], position[1] - 1)
if new_path[-1] == "U":
next_position = (position[0] - 1, position[1])
update(cost, new_path, next_position)
else:
if (not path.endswith('R' * 10)) and (not path.endswith('L')) and position[1] < (w - 1):
new_path = path + "R"
next_position = (position[0], position[1] + 1)
update(cost, new_path, next_position)
if (not path.endswith('D' * 10)) and (not path.endswith('U')) and position[0] < (h - 1):
new_path = path + "D"
next_position = (position[0] + 1, position[1])
update(cost, new_path, next_position)
if (not path.endswith('L' * 10)) and (not path.endswith('R')) and position[1] > 0 and position[0] > 0 and position[0] < (h - 1):
new_path = path + "L"
next_position = (position[0], position[1] - 1)
update(cost, new_path, next_position)
if (not path.endswith('U' * 10)) and (not path.endswith('D')) and position[0] > 0 and position[1] > 0 and position[1] < (w - 1):
new_path = path + "U"
next_position = (position[0] - 1, position[1])
update(cost, new_path, next_position)
steps += 1
if steps % 10000 == 0:
print(h, steps, len(queue))
for i in range(max_h):
for j in range(max_w):
if i >= h - 1 or j >= h - 1:
for cost, path in paths[i][j]:
queue.append(( (i, j), cost, path))
print(paths[h-1][w-1])
lowest = 5000
for cost, path in paths[h-1][w-1]:
lowest = min(lowest, cost)
print(lowest)
