Advent of Code 2024 - Day 18: RAM Run

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
from advent import parse, ints, nx, binary_search

blocks = [ complex(x,y) for x, y in parse(18, ints) ]
dim    = 71
goal   = 70+70j

def create_graph(blocks):
    def gen_edges(blocks):
        for x in range(dim):
            for y in range(dim):
                if (pos := complex(x, y)) not in blocks:
                    if (x + 1) < dim and (east := pos + 1) not in blocks:
                        yield (pos, east)
                    if (y + 1) < dim and (south := pos + 1j) not in blocks:
                        yield (pos, south)

    G = nx.Graph()
    G.add_edges_from(gen_edges(blocks))
    return G

def part1():
    return nx.shortest_path_length(create_graph(set(blocks[:1024])), 0, goal)

def part2():
    def predicate(n):
        G = create_graph(set(blocks[:n+1]))
        return not(goal in G and nx.has_path(G, 0, goal))

    return blocks[binary_search(predicate, 1024, len(blocks))]

# ---------------------------------------------------------------------------------------------

assert part1() == 344
assert part2() == complex(46, 18)

Parsing

We’re given input of the form representing x, y coordinates:

40,65
17,1
34,45
31,51
29,43
...

I’d like a dict of coordinates (as complex numbers), so I can easily check to see if a “byte” has fallen onto the coordinate:

1
 
blocks = [ complex(x,y) for x, y in parse(18, ints) ]

Generating the graph

Both parts will need a graph to search. To generate the edges (and thereby the nodes also), we loop over the x and y coordinates of our space creating east and south edges if both the source and destination nodes are not blocked. We’ll use an undirected graph, so we only need to create the east & south edges, since the edges can be navigated in either direction:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
def create_graph(blocks):
    def gen_edges(blocks):
        for x in range(dim):
            for y in range(dim):
                if (pos := complex(x, y)) not in blocks:
                    if (x + 1) < dim and (east := pos + 1) not in blocks:
                        yield (pos, east)
                    if (y + 1) < dim and (south := pos + 1j) not in blocks:
                        yield (pos, south)

    G = nx.Graph()
    G.add_edges_from(gen_edges(blocks))
    return G

Part 1

For part 1, we simply drop the first 1,024 bytes onto the grid to form obstacles, and then search for the shortest path:

1
2
 
def part1():
    return nx.shortest_path_length(create_graph(set(blocks[:1024])), 0, goal)

Part 2

For part 2, we need to determine how many bytes must fall to completely block the path from start to goal. Maybe there are more clever ways to do this, but I simply took a brute force approach, and did a binary search to find the right number.

NOTE: I’ve updated this post after being inspired by Todd G., from our local Discord, to factor out the binary search code. Here’s the binary search function from my advent.py file:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
def binary_search(predicate, low, high):
    """Return the minimum index, n, for which predicate(n) is
    True. Return None if not found"""
    found = False

    while high - low > 1:
        n = int((low + high) / 2)

        if predicate(n):
            found = True
            high = n
        else:
            low = n

    return high if found else None

With that in place, the new part2() is even simpler:

1
2
3
4
5
6
 
def part2():
    def predicate(n):
        G = create_graph(set(blocks[:n+1]))
        return not(goal in G and nx.has_path(G, 0, goal))

    return blocks[binary_search(predicate, 1024, len(blocks))]

New Python Concepts

  • Graph.add_edges_from()

Conclusion

It was nice to have an easy day after yesterday!

Postscript

I’d forgotten another idea I had, until I spotted a similar solution from a fellow Racket programmer. The idea is simply to start with the graph from part 1 i.e. w/ the first 1,024 bytes dropped, and then remove nodes from the graph one at a time using the remaining bytes in the input. After each additional byte “drops”, see if there is a path from start to goal, if not, that’s the answer. This is conceptually simpler, and it’s shorter than my solution; however, it’s about 50 times slower since we lose the advantage of the binary search efficiency:

1
2
3
4
5
6
7
 
def part2_alternate():
    G = create_graph(set(blocks[:1024]))

    for pos in blocks[1024:]:
        G.remove_node(pos)
        if not nx.has_path(G, 0, goal):
            return pos

Postscript 2

I’ve been using the networkx library for these maze searches, because that’s what I’d do for “real world” graph searching; however, I thought I should probably get familiar with breadth first searching in Python manually, in case I need to create a custom search due to some limitation in networkx. I’m not sure what that limitation might be, but here’s the manual bfs for part 1 anyway :) Python made this trivial!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
from advent import parse, ints, heappop, heappush

blocks = { (x,y) for x, y in parse(18, ints)[:1024] }

def part1(goal):
    pq      = []
    visited = set()
    heappush(pq, (0, (0,0)))

    while pq:
        length, pos = heappop(pq)

        if pos == goal:
            return length
        elif pos in visited:
            continue

        visited.add(pos)
        x, y = pos

        for dx, dy in ((1,0), (0,1), (-1,0), (0,-1)):
            nxt = (nx, ny) = x + dx, y + dy

            if 0 <= nx <= goal[0] and 0 <= ny <= goal[1] and nxt not in visited and nxt not in blocks:
                heappush(pq, (length + 1, nxt))

# ---------------------------------------------------------------------------------------------

assert part1((70,70)) == 344