| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 23:58:57 | >24h | >24h |
This is YET another day that I didn't stay up until midnight to do the problem when it came out. I started at 10PM on 12/24 and finished around
I first precompute the blizzard patterns, which turns out to be marginally helpful as my paths are only a little longer than the blizzard cycle (300 for me). Then I just bruteforce simulate with BFS and use position and blizzard state as caching. It takes pretty long to run (multiple tens of minutes), perhaps I will come back to it later and optimize because some of the r/adventofcode solutions run in milliseconds.
from helpers.datagetter import data_in, submit
from collections import defaultdict
ans = 0
din = data_in(split=True, numbers=False)
grid = defaultdict(list)
bounds = [len(din[0])-2, len(din)-2]
print(bounds)
for i in range(len(din)):
for j in range(len(din[0])):
if din[i][j] not in ["#", "."]:
grid[(j-1, i-1)].append(din[i][j])
goal = [len(din[0]) - 3, len(din) - 2]
print(goal)
stored_grid = [grid]
def move(grid):
new_grid = defaultdict(list)
for key, val in grid.items():
for bliz in val:
if bliz == ">":
new_grid[((key[0] + 1) % bounds[0], (key[1]) % bounds[1])].append(bliz)
if bliz == "<":
new_grid[((key[0] - 1) % bounds[0], (key[1]) % bounds[1])].append(bliz)
if bliz == "^":
new_grid[((key[0]) % bounds[0], (key[1] - 1) % bounds[1])].append(bliz)
if bliz == "v":
new_grid[((key[0]) % bounds[0], (key[1] + 1) % bounds[1])].append(bliz)
found = new_grid in stored_grid
if not found:
stored_grid.append(new_grid)
return found
while not move(stored_grid[-1]):
None
start = [0, -1, 1]
new_queue = [[start]]
visited = []
while True:
queue = new_queue.copy()
print("QUEUE", len(queue), "PATH", len(queue[0]), "VISITED", len(visited))
new_queue = []
while queue:
path = queue.pop(0)
node = path[-1]
grid = stored_grid[node[2] % len(stored_grid)]
for i in range(-1, 2):
for j in range(-1, 2):
if abs(i + j) == 1 or (i == 0 and j == 0):
if [node[0] + i, node[1] + j] == goal:
print(path + [[node[0] + i, node[1] + j]])
print(len(path))
exit()
if (node[0] + i < 0 or node[0] + i >= bounds[0] or node[1] + j < 0 or node[1] + j >= bounds[1]) and [node[0] + i, node[1] + j] != start[0:2]:
continue
if grid[(node[0] + i, node[1] + j)] == [] and [node[0] + i, node[1] + j, (node[2] + 1) % len(stored_grid)] not in visited:
new_queue.append(path + [[node[0] + i, node[1] + j, (node[2] + 1) % len(stored_grid)]])
visited.append([node[0] + i, node[1] + j, (node[2] + 1) % len(stored_grid)])
print(ans)
submit(ans)I turned the search into a function and ran it 3 times, making sure to start at the correct blizzard pattern. It's still running as I type this, but I'm confident it'll produce the correct result. Edit: It did. I skipped doing the first Start to End because we already know the answer. Finished around 1:02 AM on 12/25.
from helpers.datagetter import data_in, submit
from collections import defaultdict
ans = 0
din = data_in(split=True, numbers=False)
grid = defaultdict(list)
bounds = [len(din[0])-2, len(din)-2]
print(bounds)
for i in range(len(din)):
for j in range(len(din[0])):
if din[i][j] not in ["#", "."]:
grid[(j-1, i-1)].append(din[i][j])
goal = [len(din[0]) - 3, len(din) - 2]
print(goal)
stored_grid = [grid]
def move(grid):
new_grid = defaultdict(list)
for key, val in grid.items():
for bliz in val:
if bliz == ">":
new_grid[((key[0] + 1) % bounds[0], (key[1]) % bounds[1])].append(bliz)
if bliz == "<":
new_grid[((key[0] - 1) % bounds[0], (key[1]) % bounds[1])].append(bliz)
if bliz == "^":
new_grid[((key[0]) % bounds[0], (key[1] - 1) % bounds[1])].append(bliz)
if bliz == "v":
new_grid[((key[0]) % bounds[0], (key[1] + 1) % bounds[1])].append(bliz)
found = new_grid in stored_grid
if not found:
stored_grid.append(new_grid)
return found
while not move(stored_grid[-1]):
None
def bfs(name, start, goal):
new_queue = [[start]]
visited = []
while True:
queue = new_queue.copy()
print(name, "QUEUE", len(queue), "PATH", len(queue[0]), "VISITED", len(visited))
new_queue = []
while queue:
path = queue.pop(0)
node = path[-1]
grid = stored_grid[node[2] % len(stored_grid)]
for i in range(-1, 2):
for j in range(-1, 2):
if abs(i + j) == 1 or (i == 0 and j == 0):
if [node[0] + i, node[1] + j] == goal:
return len(path)
if (node[0] + i < 0 or node[0] + i >= bounds[0] or node[1] + j < 0 or node[1] + j >= bounds[1]) and [node[0] + i, node[1] + j] != start[0:2]:
continue
if grid[(node[0] + i, node[1] + j)] == [] and [node[0] + i, node[1] + j, (node[2] + 1) % len(stored_grid)] not in visited:
new_queue.append(path + [[node[0] + i, node[1] + j, (node[2] + 1) % len(stored_grid)]])
visited.append([node[0] + i, node[1] + j, (node[2] + 1) % len(stored_grid)])
ans += bfs("First", [0, -1, 1], goal)
ans += bfs("Second", goal + [ans + 1], [0, -1])
ans += bfs("Third", [0, -1, ans + 1], goal)
print(ans)
submit(ans)