expectancyViolation · December 18, 2024 13:00
diff --git a/day_18_part2_single_dfs.py b/day_18_part2_single_dfs.py
 from collections import deque


 with open("input.txt", "r") as bb:
    coords = [tuple([int(x) for x in line.strip().split(",")]) for line in bb]

 # old solution did not work reliably. this one should
 # dijkstra exploring paths in order of their "earliest closure" i.e. the time at which they get blocked
 def part2(coords: list[tuple[int, int]]):
    latenesses = defaultdict(lambda: -inf,
                             {(x, y): -i for i, (x, y) in enumerate(coords)})
    curr = []
    heappush(curr, (-inf, (0, 0)))
    visited = dict()
    while curr:
        lateness, (x, y) = heappop(curr)
        if (x, y) in visited:
            continue
        visited[(x, y)] = lateness
        for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):
            nx, ny = x + dx, y + dy
            if 0 <= nx < 71 and 0 <= ny < 71:
                nc = latenesses[(nx, ny)]
                heappush(curr, (max(nc, lateness), (nx, ny)))

    return coords[-visited[(70, 70)]]

 ## single dfs
 #def part2(coords: list[tuple[int, int]]):
 #    # this does not work reliably :/
 #    # the first "random" point after the maze is done might happen to not fall onto such a coordinate, 
 #    # so we might already have gone too far
 #    maze_done = next(
 #        i for i, (x, y) in enumerate(coords) if x % 2 == 0 and y % 2 == 0) - 1
 #
 #    blocked = {*coords[:maze_done]}
 #    curr = deque([(0, 0)])
 #    visited = {(0, 0)}
 #    preds = {}
 #    while curr:
 #        (x, y) = curr.popleft()
 #        for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):
 #            nx, ny = x + dx, y + dy
 #            if 0 <= nx < 71 and 0 <= ny < 71:
 #                if (nx, ny) not in visited and (nx, ny) not in blocked:
 #                    curr.append((nx, ny))
 #                    visited.add((nx, ny))
 #                    preds[(nx, ny)] = (x, y)
 #
 #    path = []
 #    p = (70, 70)
 #    while p in preds:
 #        p = preds[p]
 #        path.append(p)
 #
 #    return next((x, y) for (x, y) in coords if (x, y) in path)

 print(part2(coords))
	from collections import deque


	with open("input.txt", "r") as bb:
	coords = [tuple([int(x) for x in line.strip().split(",")]) for line in bb]

	# old solution did not work reliably. this one should
	# dijkstra exploring paths in order of their "earliest closure" i.e. the time at which they get blocked
	def part2(coords: list[tuple[int, int]]):
	latenesses = defaultdict(lambda: -inf,
	{(x, y): -i for i, (x, y) in enumerate(coords)})
	curr = []
	heappush(curr, (-inf, (0, 0)))
	visited = dict()
	while curr:
	lateness, (x, y) = heappop(curr)
	if (x, y) in visited:
	continue
	visited[(x, y)] = lateness
	for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):
	nx, ny = x + dx, y + dy
	if 0 <= nx < 71 and 0 <= ny < 71:
	nc = latenesses[(nx, ny)]
	heappush(curr, (max(nc, lateness), (nx, ny)))

	return coords[-visited[(70, 70)]]

	## single dfs
	#def part2(coords: list[tuple[int, int]]):
	# # this does not work reliably :/
	# # the first "random" point after the maze is done might happen to not fall onto such a coordinate,
	# # so we might already have gone too far
	# maze_done = next(
	# i for i, (x, y) in enumerate(coords) if x % 2 == 0 and y % 2 == 0) - 1
	#
	# blocked = {*coords[:maze_done]}
	# curr = deque([(0, 0)])
	# visited = {(0, 0)}
	# preds = {}
	# while curr:
	# (x, y) = curr.popleft()
	# for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):
	# nx, ny = x + dx, y + dy
	# if 0 <= nx < 71 and 0 <= ny < 71:
	# if (nx, ny) not in visited and (nx, ny) not in blocked:
	# curr.append((nx, ny))
	# visited.add((nx, ny))
	# preds[(nx, ny)] = (x, y)
	#
	# path = []
	# p = (70, 70)
	# while p in preds:
	# p = preds[p]
	# path.append(p)
	#
	# return next((x, y) for (x, y) in coords if (x, y) in path)

	print(part2(coords))
No results found