Dijkstra not required in Adevent of Code 2024 Day 20, BFS is sufficient

[vismit2000]

Thanks for really good concise solutions again this year. Maybe @norvig and Karpathy are the two people who know the expressive power of python the best. I come back to these solutions every year to not only check alternate approaches but to also learn writing better Python.

https://github.com/norvig/pytudes/blob/main/ipynb/Advent-2024.ipynb

Since the distances are same throughout (1 unit) in Race Condition problem (Day 20), Dijkstra is overkill here although it obviously works perfectly fine. So BFS can asymptotically improve the running time.

with open("input.txt", "r") as file:
    lines = file.read().strip().split("\n")
    graph = {i + j * 1j: c for i, r in enumerate(lines) for j, c in enumerate(r)}
    start = next(p for p in graph if graph[p] == "S")
    end = next(p for p in graph if graph[p] == "E")


def bfs(point, graph):
    dist = {}
    q = [(point, 0)]
    visited = {point}
    while q:
        p, d = q.pop(0)
        dist[p] = d
        for dir in (-1, 1j, 1, -1j):
            np = p + dir
            if graph.get(np, "#") != "#" and np not in visited:
                q.append((np, d + 1))
                visited.add(np)
    return dist


def neighborhood(point, radius):
    """All points within `radius` of `point` (using taxi distance)."""
    return [
        point + dx + dy * 1j
        for dx in range(-radius, radius + 1)
        for dy in range(-(radius - abs(dx)), radius - abs(dx) + 1)
    ]


def taxi_distance(p1, p2):
    return abs(p1.real - p2.real) + abs(p1.imag - p2.imag)


def cheats(racetrack, lower_bound=1, radius=20):
    """All ways of cheating by taking up to `radius` steps through walls and back to the track."""
    D = bfs(end, racetrack)
    return [
        (p1, p2, t)
        for p1 in D
        for p2 in neighborhood(p1, radius)
        if p2 in D and (t := D[p1] - D[p2] - taxi_distance(p1, p2)) >= lower_bound
    ]


print(len(cheats(graph, 100, 2)))
print(len(cheats(graph, 100, 20)))

[norvig]

Thanks for the kind note! You are absolutely right about the BFS. But I don't think there is an asymptotically improvement to be had (although certainly there could be constant factor improvements, say by using numpy arrays rather than dicts. I said that "This is an all-paths-to-the-goal puzzle, which should make you think *Dijkstra's algorithm* <https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm>.", and I stand by that. But I also said "Since we are told the grid is single-path, we don't have to worry about updating entries in distance_from for a second path to a point." I should have also said "we don't have to worry about the order of the points in the queue, as long as we're appending to the end." And, I should have said "with these two simplifications, my Dijkstra becomes a breadth-first search." But I stand by the point that when you notice it is all-paths, you should start thinking Dijkstra, and then think of optimizations/requirements. Thanks again for the note!

…

On Fri, Dec 27, 2024 at 10:35 PM Vishal Mittal ***@***.***> wrote: Thanks for really good concise solutions again this year. Maybe @norvig <https://github.com/norvig> and Karpathy are the two people who know the expressive power of python the best. I come back to these solutions every year to not only check alternate approaches but to also learn writing better Python. https://github.com/norvig/pytudes/blob/main/ipynb/Advent-2024.ipynb Since the distances are same throughout (1 unit) in Race Condition problem (Day 20), Dijkstra is overkill here although it obviously works perfectly fine. So BFS can asymptotically improve the running time. — Reply to this email directly, view it on GitHub <#138>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABBK6LCLTIHGKI6EZ6DCAW32HZBABAVCNFSM6AAAAABUJQXA4KVHI2DSMVQWIX3LMV43ASLTON2WKOZSG43DCNJVGA3DQMY> . You are receiving this because you were mentioned.Message ID: ***@***.***>