Quick Part 1 with a silly issue for Part 2.
| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 25:56 | 2:11:58 | 2:37:54 |
A "just do it" solution, bruteforcing the way toward the solution. Simple BFS keeps track of visited nodes for each candidate and expands in all directions until the end. After the entire space is searched, the longest visited set is the winner.
from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix
din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0
world = Matrix([len(din), len(din[0])], 0)
start = []
end = []
for i in range(len(din)):
for j in range(len(din[i])):
if i == 0 and din[i][j] == ".":
visited = set()
visited.add(tuple([i, j]))
start = [i, j, visited]
if i == len(din) - 1 and din[i][j] == ".":
end = [i, j]
world.set([i, j], din[i][j])
longpaths = []
queue = [start]
while queue:
curr = queue.pop(0)
pos = [curr[0], curr[1]]
visited = curr[2]
if pos == end:
longpaths.append(len(visited) - 1)
continue
for val, neighbor in world.neighbors(pos):
if tuple(neighbor) in visited:
continue
vcopy = visited.copy()
if val in ".>^v<":
vcopy.add(tuple(neighbor))
if val == ".":
queue.append([neighbor[0], neighbor[1], vcopy])
if val == ">" and tuple([neighbor[0], neighbor[1] + 1]) not in vcopy:
vcopy.add(tuple([neighbor[0], neighbor[1] + 1]))
queue.append([neighbor[0], neighbor[1] + 1, vcopy])
if val == "<" and tuple([neighbor[0], neighbor[1] - 1]) not in vcopy:
vcopy.add(tuple([neighbor[0], neighbor[1] - 1]))
queue.append([neighbor[0], neighbor[1] - 1, vcopy])
if val == "v" and tuple([neighbor[0] + 1, neighbor[1]]) not in vcopy:
vcopy.add(tuple([neighbor[0] + 1, neighbor[1]]))
queue.append([neighbor[0] + 1, neighbor[1], vcopy])
if val == "^" and tuple([neighbor[0] - 1, neighbor[1]]) not in vcopy:
vcopy.add(tuple([neighbor[0] - 1, neighbor[1]]))
queue.append([neighbor[0] - 1, neighbor[1], vcopy])
aocd_submit(max(longpaths))Not so simple for Part 2 since with removing the slopes (which felt weird to remove a restriction) the space to search got significantly bigger.
My first attempt was to keep the code as is (removing the slopes of course) and to just run BFS on it. I started letting it run and without a result in the first minute, I created a new file and started working with the other one in the background. It never finished in time and was making my computer really laggy (high memory consumption), so I ended up quitting it about 10 minutes later.
I searched online for algorithms to find the longest path through a graph, and I found the Bellman-Ford Algorithm which apparently would let you do so if you make all the edge weights negative. Optimizing for the shortest path would give you the longest negative path. So I naively turned the maze into nodes and edges and coded the algorithm. However, the algorithm had no problems visiting the same node twice, and also it got bogged up with negative weight cycles. I tried this angle for a while and it just wasn't working out.
I knew the BFS solution would work out eventually, so I figured I'd just optimize it slight then let it run after going to bed. I compressed the graph into a series of intersections and distances between them, then let it run! But then I looked at the input and saw that it shouldn't be taking that long, so the memory was definitely a bottleneck. I switched it to DFS and then it gave the answer within 20 seconds! 🤦♂️
from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix
from collections import defaultdict
din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0
world = Matrix([len(din), len(din[0])], 0)
start = []
end = []
# Load into matrix, gosh I need to make a helper for this
for i in range(len(din)):
for j in range(len(din[i])):
if i == 0 and din[i][j] == ".":
start = [i, j]
if i == len(din) - 1 and din[i][j] == ".":
end = [i, j]
world.set([i, j], "." if din[i][j] in ".<>^v" else "#")
# Find all intersections
intersections = []
for i in range(len(din)):
for j in range(len(din[i])):
if din[i][j] == ".":
if len([x[0] for x in world.neighbors([i, j]) if x[0] == "."]) != 2:
intersections.append([i, j])
edges = defaultdict(dict)
# Get distance between each intersection and its adjacent intersections
for inter in intersections:
queue = [(0, inter)]
visited = set()
while queue:
dist, curr = queue.pop(0)
if tuple(curr) in visited:
continue
visited.add(tuple(curr))
if curr in intersections and curr != inter:
edges[tuple(inter)][tuple(curr)] = dist
continue
for val, n in world.neighbors(curr):
if val == ".":
queue.append((dist + 1, n))
# Run Part 1 code on this compressed graph
longest_path = 0
queue = [(tuple(start), set(), 0)]
while queue:
curr = queue.pop(-1) # Use DFS instead to limit memory growth bottleneck
pos, visited, dist = curr
# If we reached the end, update the candidate for the longest path
if pos == tuple(end):
longest_path = max(longest_path, dist)
continue
# Check each outgoing node that hasn't been explored yet
for neighbor in edges[pos].keys():
if neighbor in visited:
continue
queue.append([neighbor, visited | {neighbor}, dist + edges[pos][neighbor]])
aocd_submit(longest_path)