Grids and graphs

Two things live in this chapter. Grid[T] is the rectangular two-dimensional collection: fixed width and height, one T per cell, indexed grid[x, y]. And the prelude has twelve graph helpers — the bfs, dfs, dijkstra and A* families, plus flood_fill — which take a start state and a closure that answers “what is next to here?”. They are related because most puzzle graphs are a grid, but neither needs the other: a walk never sees a grid, and a grid knows nothing about search.

Coordinates

(x, y), with x increasing rightward and y increasing downward. x is the column and y is the row, so grid[0, 2] is the leftmost cell of the third line of input. Every position a grid method hands back is an (Int, Int) tuple in that order.

Where a grid comes from

From the input parser, in practice. grid(P) reads one cell per character of each line; matrix(P) reads one cell per whitespace-separated token. Both are covered in structural parsers.

And from the program itself. Grid() is the empty 0×0 grid; Grid(w, h, fill) is the working grid an algorithm allocates for itself — an occupancy board, a visited mask, a distance table — with every cell starting as fill. That is the difference between using Grid[T] and reimplementing it: a hand-rolled Vec[Bool] indexed y * w + x has no contains, no neighbors4, and no bounds behaviour at all. There is still no to_vec-style to_grid on any sequence, so a grid is either read or allocated.

When fill is itself a collection, every cell is the same collection — Grid(2, 2, Vec()) is four names for one Vec — because a binding names an object rather than owning it. And a negative extent, or one whose w × h is past 2^28 cells, is a size or extent out of range fault rather than a check-time refusal: the extents are ordinary Ints computed at run time.

// `read grid(char)` makes every character of every line a cell.
var map = read grid(char)
var rock = '#'

out(map.width())
out(map.height())

// `map[x, y]` is column `x` of row `y`: x rightward, y downward.
// `map.get(x, y)` is the same read spelled as a method.
out(map[0, 0])
out(map.get(3, 1))

// Whether a position is inside is a question, not a fault.
out(map.contains(3, 1))
out(map.contains(9, 0))

// A row, a column, and the whole thing flattened in row-major order.
out(map.row(1))
out(map.column(0))
out(map.cells())

// A `for` walks the cells in that same order.
var rocks = 0
for cell in map {
    if cell == rock { rocks = rocks + 1 }
}
out(rocks)

// A grid is mutable in place; `map.set(x, y, v)` is the same store.
map[0, 0] = rock
map.set(0, 2, rock)
out(map.row(0))
out(map.row(2))

// A row prints as a Vec; `to_text()` draws it back as the line it was read as.
for y in 0..map.height() {
    out(map.row(y).to_text())
}

On the input

..#.
#...
.#.#

that prints

4
3
.
.
true
false
[#, ., ., .]
[., #, .]
[., ., #, ., #, ., ., ., ., #, ., #]
4
[#, ., #, .]
[#, #, ., #]
#.#.
#...
##.#

The wall is written '#', a character literal — the spelling for a character the program chose. "#"[0], a one-character Text subscripted at 0, is the same Char and is what a program reaches for when the character came out of text it did not write down. See Text and Char.

Note what a grid does not have. There is no len(): “how many” would have to choose between cells and rows, and the catalog picks neither, so map.len() is a Y110 — no such method on Grid[Char]. A grid is also not one of the ten pipeline receivers, so map.map(f) and map.filter(p) do not resolve either — map.cells() is the bridge, and map.cells().filter(p).count() is one fused loop over a Vec[T]. A bare for over the grid itself works and yields cells in row-major order, which is the case that mattered.

The working grid

The allocated grid above, in use: a visited mask over a maze, sized from the maze’s own extents and marked as the walk goes.

// `Grid(w, h, fill)` is the working grid — the one an algorithm allocates for
// itself rather than reads. Here it is a visited mask over a maze, filled with
// `false` and marked as the walk goes.
var maze = read grid(char)

var seen = Grid(maze.width(), maze.height(), false)
var frontier = Vec()
frontier.push((0, 0))
seen[0, 0] = true

var reached = 0
var at = 0
while at < frontier.len() {
    var cur = frontier[at]
    at = at + 1
    reached = reached + 1
    for n in maze.neighbors4(cur) {
        if maze[n.0, n.1] != '#' && !seen[n.0, n.1] {
            seen[n.0, n.1] = true
            frontier.push(n)
        }
    }
}

out(seen.width())
out(seen.height())
out(reached)
out(seen[0, 0])
out(seen.contains(0, 0))
out(seen.contains(seen.width(), 0))

On the input

....#
.##.#
....#

that prints

5
3
10
true
true
false

The mask is a Grid[Bool] and the maze a Grid[Char]: the two have the same extents and nothing ties them together, which is the usual arrangement. Written out by hand this is bfs — and the whole of the graph helpers below is the case where you would rather not.

Positions and neighbours

var g = read grid(char)
var blank = '.'

// Every position, row-major, as `(x, y)` tuples.
out(g.positions())

// Where a value is: the first one as `Option[(Int, Int)]`, or all of them.
out(g.find(blank))
out(g.find_all(blank))
out(g.find('z'))

// The in-bounds neighbours of a point. Both take one `(Int, Int)` and
// answer a `Vec[(Int, Int)]`, already clipped to the grid.
out(g.neighbors4((0, 0)))
out(g.neighbors8((0, 0)))
out(g.neighbors4((1, 1)))

// A pattern opens a tuple by binding both elements at once.
for (x, y) in g.neighbors4((1, 1)) {
    out(g[x, y])
}

// `p.0` and `p.1` select one element by position.
var p = g.neighbors4((1, 1))[0]
out(p.0)
out(p.1)

On the input

ab.
cde
.fg

that prints

[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
Some((2, 0))
[(2, 0), (0, 2)]
None
[(0, 1), (1, 0)]
[(1, 0), (0, 1), (1, 1)]
[(1, 0), (1, 2), (0, 1), (2, 1)]
b
f
c
e
1
0

The neighbour lists are already clipped, so a corner gets two entries and not four — no bounds test of your own. neighbors4 runs up, down, left, right; neighbors8 runs the 3×3 block row-major with the centre skipped. Which entry was which direction is not in the list; that is what around4 and around8, below, are for. find answers Option[(Int, Int)], so a value that is not there is None rather than a position nobody wrote; find_all needs no Option because an empty Vec already says it.

There are two ways to take a (Int, Int) apart. p.0 and p.1 select an element by position, and an index past the end is a Y019 at check time rather than a run-time surprise. A pattern takes the whole tuple at once — in a for binding as above, or in a match. If you want names, use a record as your position instead; both work everywhere a tuple does.

Naming the directions, and counting them

A clipped Vec drops two facts on the floor: which direction each neighbour was, and — at the edge — that there was a direction at all. around4 and around8 keep both. They answer a record, one field per direction, and every field is an Option[(Int, Int)]: None is the direction that leaves the grid.

The field order is the order the record prints in. around4 is the plus read off the page with the centre skipped — up, left, right, down. around8 is the whole 3×3 block in reading order, again with the centre skipped — up_left, up, up_right, left, right, down_left, down, down_right.

The four counts are the other half. count4(p, v) and count8(p, v) count the neighbouring cells that hold v; count4_where(p, f) and count8_where(p, f) count the ones whose cell a closure accepts. A neighbour off the grid has no cell, so it is not counted, and f is never called for it — there is no cell to hand it, and inventing one would mean choosing a value the cell type may not have.

// `#` is a wall. Which way is which, and how boxed in is a square?
var g = read grid(char)
var wall = '#'

// `around4` answers a record with one field per direction, named: `up`,
// `left`, `right`, `down`, in that order.
var corner = g.around4((0, 0))
out(corner)
out(corner.up)
out(corner.right)

// Every field is an `Option`, because a direction can leave the grid — the one
// thing a clipped `Vec` of neighbours cannot say.
match corner.down {
    Some(p) => out(g[p.0, p.1]),
    None => out("off the grid"),
}
match corner.up {
    Some(p) => out(g[p.0, p.1]),
    None => out("off the grid"),
}

// `around8` names all eight, in reading order with the centre skipped.
out(g.around8((1, 1)))

// The counts answer a number without building a collection first.
out(g.count4((1, 1), wall))
out(g.count8((1, 1), wall))
out(g.count4_where((1, 1), |c| c != wall))
out(g.count8_where((1, 1), |c| c != wall))

// A neighbour off the grid has no cell, so it is not counted and the closure
// is never called for it: the corner has two neighbours, not four.
out(g.count4_where((0, 0), |c| true))

On the input

..#
#..
.#.

that prints

{ up: None, left: None, right: Some((1, 0)), down: Some((0, 1)) }
None
Some((1, 0))
#
off the grid
{ up_left: Some((0, 0)), up: Some((1, 0)), up_right: Some((2, 0)), left: Some((0, 1)), right: Some((2, 1)), down_left: Some((0, 2)), down: Some((1, 2)), down_right: Some((2, 2)) }
2
3
2
5
2

The record’s type is called Around4 — a type error prints that name — but it is not a name you can write: var a: Around4 = ... is an N002. Bind it with a plain var and read its fields.

neighbors4 and neighbors8 are still here, and still answer a Vec. That is not a leftover. The graph helpers below type their neighbour argument as (T) -> Vec[T], so bfs(start, |p| g.neighbors4(p)) is the spelling a walk needs, and a record of four Options is not a Vec of anything. Use neighbors4 to walk and around4 to look; use a count when the answer was going to be a number and the loop only existed to add it up.

Turning a grid

var g = read grid(char)

fn show(name: Text, g: Grid[Char]) -> Unit {
    out(name)
    for y in 0..g.height() {
        out(g.row(y))
    }
}

show("original", g)
show("transpose", g.transpose())
show("rotate_right", g.rotate_right())
show("rotate_left", g.rotate_left())

// Each answers a new grid; the receiver is untouched.
show("still original", g)

On abc / def:

original
[a, b, c]
[d, e, f]
transpose
[a, d]
[b, e]
[c, f]
rotate_right
[d, a]
[e, b]
[f, c]
rotate_left
[c, f]
[b, e]
[a, d]
still original
[a, b, c]
[d, e, f]

out(grid) prints the cells flat, in row-major order, with no row structure — printing grid.row(y) in a loop, as show does, is how you look at the shape.

matrix(P) is a Grid[T]

There is no separate Matrix type. grid and matrix differ only in how each cuts a row into cells, and both answer Grid[T].

// The only difference between the two constructors is how a row is cut up.
// `grid` takes one cell per character; `matrix` takes one per whitespace-
// separated token. Both answer a `Grid[T]`.
var heights = parse("123\n456\n", grid(digit))
var readings = parse("12 3\n45 6\n", matrix(int))

out(heights.width())
out(heights.cells())

out(readings.width())
out(readings.cells())

// Same type, so the same methods.
out(heights.row(1))
out(readings.row(1))

3
[1, 2, 3, 4, 5, 6]
2
[12, 3, 45, 6]
[4, 5, 6]
[45, 6]

Both constructors require every row to have the same cell count; a short row is a parse fault unless you ask for grid(P, ragged, fill: "X"). That is the input parser’s business, not the grid’s.

When an index is off the grid

grid[x, y], get, set, row and column fault when the position is not there. contains is the way to ask first.

var g = read grid(char)
out(g[4, 0])

error: program faulted: index out of bounds

Backtrace:
#0   <entry>

  locals:
    g: Grid[Char] = [a, b, c, d]
  temps:
    <tmp#1> = "abcd\n"
    <tmp#2: Int> = 1
    <tmp#3: Grid[Char]> = [a, b, c, d]
    <tmp#5: Int> @ "4" = 4
    <tmp#6: Int> @ "0" = 0
    <tmp#7: Char> @ "g[4, 0]" = <uninit>
    <tmp#8: Unit> @ "out(g[4, 0])" = <uninit>

The Grid[T] method surface

That is all of it — twenty-four rows, including the two subscript forms.

There is no grid.map(fn): g.map(f) is a Y110. Map over grid.cells() instead, and index back with grid.positions() if you need to know where each cell was.

Drawing the grid back is how a grid puzzle is debugged, and out(grid.row(y)) is not it — that prints [., ., |]. A Vec[Char] has a to_text(), so the line the grid was read from comes back one call later:

for y in 0..grid.height() { out(grid.row(y).to_text()) }

It is a Vec[Char] row and not a Grid one, so a whole grid still prints as its cells; a picture is a sequence of lines, and the loop is where the reader chooses that.

The graph helpers

There is no graph object, no adjacency type and no node type. Every helper takes a start state and then only functions of it: the graph is the closure. A state is any value you can put in a Set, so an Int node id, a Text, an (Int, Int) grid position and a record all work, and the walk never learns where they came from.

There are twelve of them, and the names are a rule rather than a list. The bare name is the whole walk, _distance is the number, and _path is the route. One search, three questions. Learn the rule on one family and you can write the other three from the name: the arguments are the same in the same order, and the only one the bare form does not take is the goal predicate — which it has no use for, because it is not looking for anything.

The argument order is always start, neighbours, then weight, heuristic and goal where they apply. The goal is a predicate, not a value: |p| p == exit for a specific square, |s| s.depth == 26 for a property. A*’s five arguments are the honest count — a start, a graph, a cost, an estimate and a goal, none of which has a default worth guessing.

Two families are short a row, and both gaps say something. A* has no bare a_star: the heuristic estimates the remaining cost to a goal, so a whole-graph A* would be a search steering at nothing — dijkstra is that walk, and it is why the two share a weight function. flood_fill has no _distance and no _path: it is bfs’s unordered twin, and a Set has thrown away the order a route would be made of. Ask bfs_path for that.

What the three forms answer:

• The bare name walks everything reachable. bfs and dfs answer a Vec[T] in the order they reached it, flood_fill a Set[T], dijkstra a Map[T, Int] of least costs. None of them needs an Option, because all of them contain the state you started from.
• _distance answers Option[Int] — the cost of the route the search reaches a goal by, or None when no goal is reachable. For bfs_distance and dfs_distance the cost is the step count, one per edge.
• _path answers Option[Vec[T]] — that same route, start to goal inclusive, so a route holds exactly one more state than the matching _distance counts steps. The Option is the same Option: a found route always holds at least its own start, so an empty Vec could not stand for “no route”.

One honest caveat, and it is the whole of the difference between the two unweighted families: dfs_path answers a route, not the shortest one, and dfs_distance is that route’s length rather than the fewest steps. Depth-first search commits to the first neighbour a state reports and backtracks only when it must, so it finds a goal by wandering to it. bfs_path is the shortest route; dfs_path is a route that exists. Reach for dfs_* when the graph is a tree, when any route will do, or when you want the one depth-first happens to take — never when you meant “shortest”.

A maze

A grid on stdin, a shortest path, an answer.

// A maze on stdin: `#` is a wall, `S` the start, `E` the exit.
// How few steps is the exit?
var maze = read grid(char)
var wall = '#'

// The graph is this function. `bfs_distance` never sees the grid: it only
// ever asks "what is next to here?" and "is this the exit?".
fn open_neighbours(maze: Grid[Char], wall: Char, p: (Int, Int)) -> Vec[(Int, Int)] {
    var open = Vec()
    for (x, y) in maze.neighbors4(p) {
        if maze[x, y] != wall {
            open.push((x, y))
        }
    }
    open
}

fn square(maze: Grid[Char], mark: Char) -> (Int, Int) {
    match maze.find(mark) {
        Some(p) => p,
        None => panic("the maze is missing a marker"),
    }
}

var start = square(maze, 'S')
var exit = square(maze, 'E')

var steps = bfs_distance(
    start,
    |p| open_neighbours(maze, wall, p),
    |p| p == exit,
)

match steps {
    Some(n) => out(n),
    None => out("walled in"),
}

The input is nine columns by five rows, with a sealed pocket on the right edge:

S..#....#
.#.#.#..#
.#...#.#.
.#.#.#..#
...#...E#

11

bfs_distance counts steps, one per edge, and stops at the first state its predicate accepts — which is a shortest one, because breadth-first reaches every state by its shortest path. is_goal is asked about the start first, so a search that begins at its goal answers Some(0). A goal nothing satisfies is None, not -1 and not a fault; see Option.

The same maze, drawn

Change the suffix and the same search hands back the route instead of its length. Nothing else about the call moves — same start, same neighbours, same goal predicate, same three arguments in the same order — which is the whole point of the naming rule.

// The same maze, and the same graph — but the route rather than the number.
var maze = read grid(char)
var wall = '#'

fn square(maze: Grid[Char], mark: Char) -> (Int, Int) {
    match maze.find(mark) {
        Some(p) => p,
        None => panic("the maze is missing a marker"),
    }
}

var start = square(maze, 'S')
var exit = square(maze, 'E')
var step = |p| maze.neighbors4(p).filter(|q| match q { (x, y) => maze[x, y] != wall })
var arrived = |p| p == exit

// The number, then the route: same start, same graph, same goal.
out(bfs_distance(start, step, arrived))

// `dfs_path` answers *a* route, not a shortest one — depth-first commits to
// the first neighbour a state reports and backtracks only when it must.
match dfs_path(start, step, arrived) {
    Some(route) => out(route.len()),
    None => out("walled in"),
}

// A route runs start to goal inclusive, so it holds one more state than the
// matching `_distance` counts steps.
match bfs_path(start, step, arrived) {
    Some(route) => {
        out(route.len())
        for (x, y) in route {
            if maze[x, y] == '.' { maze[x, y] = 'o' }
        }
        for y in 0..maze.height() {
            out(maze.row(y).to_text())
        }
    },
    None => out("walled in"),
}

On the same input, that prints

Some(11)
20
12
Soo#....#
.#o#.#..#
.#ooo#.#.
.#.#o#..#
...#oooE#

Eleven steps and twelve squares: the route is inclusive of both ends. The depth-first route through the same maze is twenty of them — a route that exists, and not the shortest one. The two calls differ by three letters and answer routes of different lengths, which is the caveat above measured on the maze this chapter is built around.

Marking the route back onto the grid is a good part of why _path exists at all. bfs_distance can tell you a puzzle has an answer; only the route can tell you the answer went the way you thought it did.

Traversals

bfs, dfs and flood_fill do not look for anything. They answer everything reachable — the first two in the order they reached it, the third as a Set. All three contain the state you started from, which is why none of them needs an Option.

var maze = read grid(char)
var wall = '#'

// The same graph as the maze, written as one closure: the in-bounds
// neighbours, minus the walls.
var step = |p| maze.neighbors4(p).filter(|q| match q { (x, y) => maze[x, y] != wall })

// `bfs` and `dfs` answer every reachable state, in the order they reached it.
// Both start with the state you gave them.
var breadth = bfs((0, 0), step)
out(breadth.len())
out(breadth[0])
out(breadth[1])
out(breadth[2])

var depth = dfs((0, 0), step)
out(depth[1])
out(depth[2])

// `flood_fill` asks the same reachability question and drops the order.
var filled = flood_fill((0, 0), step)
out(filled.len())

// The pocket at (8, 2) is open but walled off, so no walk reaches it.
out(maze[8, 2] != wall)
out(filled.contains((8, 2)))

On the same maze:

29
(0, 0)
(0, 1)
(1, 0)
(0, 1)
(0, 2)
29
true
false

Thirty squares are open and twenty-nine are reachable; the pocket at (8, 2) is on the right edge with a wall on each of its three neighbours, so it appears in nothing. dfs descends into the first neighbour a state reports, so its second and third states are (0, 1) and (0, 2) — straight down the left edge — while bfs takes (0, 1) then (1, 0).

A closure stored in a variable, as step is here, is an ordinary value and can be handed to as many helpers as you like. So can a top-level fn by name: bfs(0, steps) and bfs(0, |n| steps(n)) are the same walk. The neighbour result is an ordinary Vec, so a pipeline is a fine way to build it, as step does here.

Costs: dijkstra and A*

The weighted families are the same three questions over a cost instead of a step count. dijkstra answers a whole Map[T, Int] — the least cost from the start to every state it reaches; dijkstra_distance and dijkstra_path answer the number and the route for one goal. A* is the same pair with one extra argument, an estimate of the remaining cost to steer with, and no whole-walk form to be the third.

// A cost field: entering a square costs the number written on it.
var cost = read matrix(int)
var goal = (cost.width() - 1, cost.height() - 1)

var step = |p| cost.neighbors4(p)
var price = |a, b| match b { (x, y) => cost[x, y] }

// `dijkstra` answers a table: the least cost from the start to every state it
// reaches. The start is in it at 0, and a state it cannot reach is absent
// rather than infinite — which is why this one needs no `Option`.
var table = dijkstra((0, 0), step, price)
out(table.len())
out(table[(0, 0)])
out(table[(2, 0)])
out(table[goal])
out(table.contains((99, 99)))

// The goal-directed pair over the same weights: `dijkstra_distance` is the
// number the table already holds for one state, `dijkstra_path` the route to
// it, start to goal inclusive.
out(dijkstra_distance((0, 0), step, price, |p| p == goal))
out(dijkstra_path((0, 0), step, price, |p| p == goal))

fn manhattan(a: (Int, Int), b: (Int, Int)) -> Int {
    match a {
        (ax, ay) => match b {
            (bx, by) => abs(ax - bx) + abs(ay - by),
        },
    }
}

// A* takes one more argument than Dijkstra — an estimate that never
// overshoots. Every step here costs at least 1, so Manhattan distance is
// admissible. There is no bare `a_star`: an estimate is an estimate *of the
// remaining cost to a goal*, so a whole-graph A* would be a walk with nothing
// to steer towards.
out(a_star_distance((0, 0), step, price, |p| manhattan(p, goal), |p| p == goal))
out(a_star_path((0, 0), step, price, |p| manhattan(p, goal), |p| p == goal))

// A zero estimate is admissible too; it turns A* back into Dijkstra.
out(a_star_distance((0, 0), step, price, |p| 0, |p| p == goal))

// A goal nothing satisfies is `None`, not a fault and not a sentinel — and a
// `_path` says it the same way, because an empty route would be a route that
// does not even hold its own start.
out(a_star_distance((0, 0), step, price, |p| 0, |p| p == (99, 99)))
out(a_star_path((0, 0), step, price, |p| 0, |p| p == (99, 99)))

On

1 1 9 1
1 9 1 1
1 1 1 9
9 1 1 1

it prints

16
0
10
6
false
Some(6)
Some([(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 3)])
Some(6)
Some([(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 3)])
Some(6)
None
None

The weight function is (T, T) -> Int — the two endpoints of the edge, in that order. Here only the destination matters, because the cost is a property of the square you enter; a graph whose edges carry their own cost would use both.

A*’s contract is that the estimate never exceeds the true remaining cost. |p| 0 always satisfies it, and turns the search into Dijkstra with one goal.

dijkstra_distance and a_star_distance agree here, and so do their _path forms, because both routes cost six: the estimate steers which states get looked at, not which answer comes out. A cost of six over seven squares is the route-is-inclusive rule again — six edges, seven states.

What a state has to be

Every walk keeps the states it has seen in a set, and the weighted ones key a cost table on them, so the state type has to be one that cannot change after it is stored — the same HashStable rule a Map key follows (capabilities).

// Every walk keeps the states it has seen in a set, and the weighted ones key
// a cost table on them. So a state has to be a value that cannot change after
// it is stored — and a `Vec` can.
fn steps(v: Vec[Int]) -> Vec[Vec[Int]] {
    Vec()
}

out(bfs(Vec(), steps).len())

$ praxis check unstable-state.px
error[Y014]: a value of type `Vec[Int]` can change after it is stored, so it cannot be used as a key

  unstable-state.px:8:5
  8 | out(bfs(Vec(), steps).len())
    |     ^^^^^^^^^^^^^^^^^ a value of type `Vec[Int]` can change after it is stored, so it cannot be used as a key

help: use a value that cannot change — a number, `Text`, or a tuple of those

praxis: 1 error(s)

The requirement is reported at the call, not inside the helper. If the state type is still a variable — fn walk(start, step) { bfs(start, step) } — it is deferred onto walk’s own signature and answered at each call to walk.

The neighbour function’s result shape is written into the helper’s signature, so handing it the wrong container is a type error and not a run-time surprise:

// The neighbour function's shape is written into the helper's own signature,
// so a `Set` of neighbours is reported at the call rather than at run time.
fn steps(n: Int) -> Set[Int] {
    Set()
}

out(bfs(0, steps).len())

$ praxis check neighbours-must-be-a-vec.px
error[Y001]: expected (Int, (Int) -> Vec[Int]) -> Vec[Int], found (Int, (Int) -> Set[Int]) -> ?T

  neighbours-must-be-a-vec.px:7:5
  7 | out(bfs(0, steps).len())
    |     ^^^^^^^^^^^^^ expected (Int, (Int) -> Vec[Int]) -> Vec[Int], found (Int, (Int) -> Set[Int]) -> ?T

praxis: 1 error(s)

What stops a walk

An answer the walk cannot compute is a fault, not a wrong number. A negative edge weight is the one to know about: Dijkstra and A* settle a state the first time they pop it and never reconsider, so a negative edge makes the answer quietly too large. It stops instead.

fn steps(n: Int) -> Vec[Int] {
    var v = Vec()
    if n < 3 { v.push(n + 1) }
    v
}

out(dijkstra(0, steps, |a, b| -1).len())

error: program faulted: an argument this algorithm has no answer for

Backtrace:
#0   <entry>

  temps:
    <tmp#1: Int> @ "0" = 0
    <tmp#2: (Int) -> Vec[Int]> @ "steps" = <closure:0>
    <tmp#3: (Int, Int) -> Int> @ "|a, b| -1" = <closure:0>
    <tmp#4: Map[Int, Int]> @ "dijkstra(0, steps, |a, b| -1)" = <uninit>
    <tmp#5: Int> @ "dijkstra(0, steps, |a, b| -1).len()" = <uninit>
    <tmp#6: Unit> @ "out(dijkstra(0, steps, |a, b| -1).len())" = <uninit>

The full list of stops:

The list is per family, not per name: the weight rules bind all five weighted helpers, and a _path form stops where its _distance form does. It is one algorithm answering a different question, not a different algorithm.

The last row is worth stating plainly: a walk calls back into your code, and a division by zero inside a neighbour function stops the walk rather than letting it continue over garbage. See the fault model.

An estimate that merely overshoots is not on that list, and that is the one place in this family where you are on your own: A* cannot detect it without computing the answer first, so an inadmissible heuristic is a wrong number rather than a stop.