Dijkstra when you are not allowed to go straight

Every Dijkstra implementation I had written before this puzzle shared one line, more or less: if new_cost < best[cell]: best[cell] = new_cost. It is such a load-bearing line that it is easy to stop seeing it as an assumption at all. It says: the cheapest way anyone has found so far to reach this cell is all I need to remember about this cell. Every future decision (which neighbour to relax next, whether this path is worth continuing) gets made from that one number.

Advent of Code 2023, day 17 hands you a grid of single-digit heat-loss costs and asks for the cheapest route from the top-left corner to the bottom-right, with one rule that breaks the assumption outright: the crucible carrying the heat cannot travel more than three blocks in a straight line before it must turn, and it can never reverse. Suddenly the cheapest way to reach a cell is not enough information: whether you are allowed to leave it depends on which direction you arrived from and how long you had already been going that way. Two paths can reach the same cell for the same cost and be in completely different states, because one of them has one more turn available than the other.

The fix people reach for is usually “a new algorithm”: A*, or some bespoke constraint-tracking wrapper around the frontier. It doesn’t need one. Dijkstra is still exactly the right tool. What was wrong was the graph: the node was never the cell, it was (cell, direction, run-length). Once you search that space instead, plain unmodified Dijkstra solves it.

I solved this in aoc/a2023/d17/main.py in the libaoc repo, the same scratch-notebook style as the rest of that season (a #%%-delimited script, no functions where a script would do), and (a running joke by now) TLS verification disabled globally so the input downloader could get past a work proxy (http.pool_manager.connection_pool_kw["cert_reqs"] = 'CERT_NONE', line 6). None of that is the point of this post. The state-space idea is.

A path the naive version accepts

The sample grid (thirteen rows, transcribed from the string literal at aoc/a2023/d17/main.py L28–40) is small enough to check a claim like that by hand:

2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533

Look at just the top row: 2 4 1 3 4 3 2 3 1 1 3 2 3. Advent of Code’s rule is that you don’t pay for the cell you start on, so walking right from (0,0) to (0,4), four straight moves, costs 4 + 1 + 3 + 4 = 12. That is a straight run of four. The puzzle caps a straight run at three, so that path is illegal.

Feed a cell-only Dijkstra this grid (if new_cost < best[cell] and nothing else) and it has no way to know that. It will discover (0,4) first via whatever cheap route it finds, and if the run of four happens to be cheaper than anything a legal, forced-turn route can manage, it records 12 as the best cost to (0,4), marks the cell settled, and never looks at it again: Dijkstra’s whole efficiency argument rests on never revisiting a settled node. I checked what the legal minimum actually is, by running the real (cell, direction, run) search restricted to just this corner of the grid: it’s 14, two higher, because the cheapest three-straight-then-turn route has to spend more getting back to the same cell. A cell-only Dijkstra would report 12 and be wrong, not slightly wrong: wrong in a way that would silently under-report the answer, because it never even considers that a run of four is a different, illegal kind of arrival at (0,4) than a run of three followed by a turn.

That is the whole argument in one paragraph: the state a shortest-path search needs to remember is not always “which node,” it’s “which node, and what condition are you in.” Day 17 needs the direction and the run-length. A router with a fuel budget would need remaining fuel. A puzzle with a key you must collect before a door would need “have I got the key.” Same algorithm, bigger node.

The blow-up, and why it’s fine

Expanding the node from cell to (cell, direction, run-length) multiplies the state count by (number of directions) × (max run length): four directions, up to three values of run-length for part 1. For the 13×13 sample that’s a genuinely small number:

Node definition	State count
cell only	169 (13 × 13)
(cell, direction, run), part 1 rules	2,028 (13 × 13 × 4 × 3)
(cell, direction, run), part 2 rules	6,760 (13 × 13 × 4 × 10)

An order of magnitude more states, and Dijkstra doesn’t even visit all of them: running the search below settles 1,561 of the 2,028 possible part-1 states and 1,450 of the 6,760 possible part-2 states on this sample (the widget’s readout shows the same two numbers live, for whatever grid and rules you have loaded). A real puzzle input is around 141×141, which puts the state count in the hundreds of thousands, still nothing a binary heap on a laptop notices. The blow-up is real, but it is the boring kind: more memory, not a different order of growth, and small enough here that it’s barely worth calling a cost.

The Python: direction and run-length packed into one complex number

Here is the part-1 relaxation loop, aoc/a2023/d17/main.py L46–92 (trimmed to the setup and the loop body):

up = -1j
down = 1j
left = -1
right = 1
directions = [up, down, left, right]
def complex_dot(c1:complex,c2:complex):
    return c1.real*c2.real + c1.imag*c2.imag
def mag(c1:complex):
    return c1.real + c1.imag

while len(to_explore):
    item = heapq.heappop(to_explore)
    prev_cost, pos, last_dir = item.cost, item.pos, item.last_dir
    ...
    pos_cost = world[int(pos.imag)][int(pos.real)] + prev_cost
    if seen[pos][last_dir] > pos_cost:
        seen[pos][last_dir] = pos_cost
    else:
        continue # Dont bother exploring node

    if pos == end:
        break

    for d in directions:
        dot_product = complex_dot(last_dir, d)
        if dot_product < 0: continue # Going backwards
        # Store the new length
        next_dir = d*dot_product+d
        if mag(next_dir) > 3: continue
        new_pos = pos+d
        heapq.heappush(to_explore, PrioritizedItem(pos_cost,new_pos,next_dir))

pos is a cell, encoded the same way a companion post about this repo’s complex-as-a- grid-point trick covers in more depth: a complex number, up is -1j because a grid’s row axis increases downward. seen is a dict of dicts: cost to reach a cell, per direction key, which is the (cell, direction, run-length) state made concrete. seen[pos][last_dir] is exactly best[(cell, direction, run)], just with direction and run-length still packed together in last_dir. That packing is the clever part. next_dir = d*dot_product+d builds a new direction key whose value encodes the run: dot the previous direction against the candidate d (1 if continuing straight, 0 if turning, filtered out if negative, going backwards), then d*dot_product scales d by how many blocks you’ve already gone. Three straight moves right leave last_dir = 3 (not 1); one move right after a turn leaves last_dir = 1. mag() (not a true complex magnitude, just real + imag) reads the run-length back out of that one number, because a direction vector only ever has one nonzero component.

That caveat is also the argument for the next section. The complex-number trick is genuinely clever: one field carries both a direction and a run-length of up to ten, packed into a single Python built-in, and it is also exactly the kind of cleverness that hid a sign bug from me for years. I don’t think it’s the right choice if anyone besides me is ever going to read this code. A plain tuple, (direction_index, run_length), with the run-length always a non-negative integer, cannot have this bug: there is no sign to get backwards, because direction and magnitude were never the same variable. The widget below uses exactly that, see “What the widget does differently,” further down.

Part 2: the ultracrucible, and the rule that’s easy to miss

Part 2 swaps in an “ultracrucible”: it must move at least four blocks before it’s allowed to turn or stop, and it may run up to ten before it’s forced to turn. The whole diff against part 1’s loop is three lines, aoc/a2023/d17/main.py L184–193 against L85–92:

        if abs(mag(next_dir)) > 10: continue
        if last_dir != 0 and abs(mag(next_dir)) == 1 and abs(mag(last_dir))<4: continue
        new_pos = pos+d
        if new_pos == end and mag(next_dir)<4: continue

against part 1’s

        if mag(next_dir) > 3: continue

One line changed (3 → 10, and abs() added, which is why part 2 doesn’t have the sign bug above: it bounds both directions correctly), and two lines added. The second new line is the minimum-run rule: abs(mag(next_dir)) == 1 means “this move is a turn” (a fresh run of length 1), and it’s only legal if the previous run (abs(mag(last_dir))) was already at least 4. The third is the rule I’d have missed cold: you cannot stop on the goal mid-run. An ultracrucible that has only gone straight for two blocks isn’t allowed to turn or stop until it hits four: arriving at the goal doesn’t except it from that rule. if new_pos == end and mag(next_dir)<4: continue throws away exactly that transition. Miss it and you’ll under-count: a two-block dash into the goal along a cheap corridor would score, and shouldn’t.

main.py also grows a second embedded grid for part 2 (L135–139) that exists specifically to catch that mistake: a 12-wide corridor of 1s with a wall of 9s beneath it for four rows:

111111111111
999999999991
999999999991
999999999991
999999999991

With a max-3 crucible this is trivial: hug the top row. With a min-4 ultracrucible, the cheap top row is also the only row you can afford to be in for long enough to satisfy the minimum run, so the answer is forced to be almost the whole corridor: 71, one turn short of dead straight. It’s a good adversarial case precisely because “the constraint only matters near the goal” is the bug the previous paragraph describes, and this grid is small enough that the bug is either obviously present or obviously absent.

Reconstructing the path

The search only ever stores costs, not parent pointers, so recovering the actual route from seen means reasoning backwards from end using the same packed direction values, aoc/a2023/d17/main.py L96–113:

def get_smallest_dir(pos:complex):
    return min((v,k) for k,v in seen[pos].items())[1]
def get_path():
    start = complex(width-1,height-1)
    nodes = [start]
    d = get_smallest_dir(nodes[-1])
    abs_dir = d/mag(d)
    nodes_dir = [abs_dir]
    while nodes[-1] != 0:
        d = get_smallest_dir(nodes[-1])
        abs_dir = d/mag(d)
        while mag(d) != 0:
            nodes.append(nodes[-1]-abs_dir)
            nodes_dir.append(abs_dir)
            test_d = get_smallest_dir(nodes[-1])
            d -= abs_dir
            assert mag(d) == 0 or test_d == d
    return nodes, nodes_dir

(start here is a leftover variable name from an earlier draft: it’s actually the goal; the walk runs backwards until nodes[-1] != 0, i.e. until it reaches the true start at the origin.) At each node it looks up the cheapest (direction, run) key in seen[pos], takes the unit direction out of it (d/mag(d)), and then walks straight backwards for the whole encoded run (mag(d) steps), decrementing d by one unit each time and re-querying seen at each intermediate cell as a consistency check (assert mag(d) == 0 or test_d == d: either you’ve used up the whole run, or the direction you’d independently look up at this intermediate cell matches the one you’re walking with). It’s a nice self-check, and it only works because the packed encoding makes “how far is left in this run” a single subtraction rather than a separate lookup.

The crucible router

With JavaScript enabled this becomes a live (cell, direction, run) Dijkstra: drag the two sliders to change the minimum and maximum straight-line run and watch the optimal path and its heat loss update, paint the grid, or paste your own.

Two sliders (minimum run before a turn, maximum straight run) re-solve the loaded grid on every drag and redraw both the optimal path and its total heat loss. Part 1 (0 / 3) and Part 2 (4 / 10) jump straight to the puzzle’s own settings; everything between and around them (a crucible that must run at least 2 but can go up to 6, say) is just another point in the same state space, which is the fastest way I know to convince yourself the constraint logic generalises rather than being two special cases bolted together. “Show explored states” reveals every (cell, direction, run) state Dijkstra actually settled: as a static overlay, or animated as a wavefront with the Animate button, so you can watch the frontier spread out from the corner and stop expanding the moment it turns the goal cell into a dead end for anything more expensive. The state-count readout below the grid is the live version of the table two sections up.

You can edit the grid three ways: drag on it to raise a cell’s cost (shift-drag to lower it), use the keyboard (arrow keys move the selection, +/- change its value, for anyone who can’t or doesn’t want to use a pointer), or paste a grid of your own digits into the box underneath. Whatever you paste stays in your browser tab: it is parsed locally and never sent anywhere, which matters if you’re tempted to paste your actual puzzle input in to check your answer (I’d rather you didn’t need to trust me on that, but there’s also nothing here that could ship it even if I wanted to: everything runs client-side, there’s no server this page talks to). Grids are capped at 60×60 for the widget’s own sake, not the algorithm’s: real AoC inputs for this puzzle run around 141×141, which the plain JS solver here handles in well under a second, but re-solving on every pixel of a slider drag at that size is the kind of thing that wants a debounced Web Worker so the drag doesn’t feel laggy. I didn’t build one; the site’s convention is to reach for that only when a post actually needs it, and this one’s argument is about the state space, not the engineering to make it instant at puzzle-input scale.

The transferable part

Most Dijkstra tutorials stop at “shortest path in a weighted graph” and never get to the question this puzzle forces: what is a node, actually? The algorithm doesn’t care: Dijkstra only needs a set of states, a cost to move between them, and a way to expand a state into its neighbours. Nothing about it says a state has to be a place. The moment a decision depends on more than “where am I,” the fix is never a different search algorithm, it’s a bigger node: fold whatever the decision depends on (direction and run-length here, remaining fuel, a collected key, a colour you’re not allowed to repeat) into the state, and the exact same relax-the-cheapest-frontier-node loop you already trust is still correct. The three-line diff between this puzzle’s two parts is honestly the best illustration I’ve found of how cheap that fix is, once you’ve seen it: the algorithm didn’t change at all.