Unweighted shortest path
# grade this stage (from your course directory)
npx theinference test --stage shortest-path --watchFind a shortest path (fewest hops) between two nodes — the Bacon-number primitive. BFS with a predecessor map, then backtrack from the target to reconstruct the interleaved node + relationship sequence. Return null when the target is unreachable.
Implement shortestPath
Run BFS over neighborEdges (which yields {rel, node} pairs so you can record both predecessors). The moment you reach the target, stop and reconstruct. The fixture asks for Kevin Bacon (id 0) → Keanu Reeves (id 16) over ACTED_IN BOTH — a 6-hop path through Apollo 13, Tom Hanks, Cloud Atlas, Hugo Weaving, and The Matrix.
export function shortestPath(store, fromId, toId, type, dir) {
if (fromId === toId) return { nodes: [fromId], rels: [] };
const predNode = new Map(), predRel = new Map(), visited = new Set([fromId]);
let frontier = [fromId];
while (frontier.length) {
const next = [];
for (const cur of frontier)
for (const { rel, node } of store.neighborEdges(cur, type, dir))
if (!visited.has(node)) {
visited.add(node); predNode.set(node, cur); predRel.set(node, rel);
if (node === toId) return reconstruct(fromId, toId, predNode, predRel);
next.push(node);
}
frontier = next;
}
return null;
}
your_program.sh shortest {fixture}/fixtures/data/nodes.json {fixture}/fixtures/data/relationships.json 0 16 ACTED_IN BOTH
# -> {"nodes":[0,65,10,80,19,66,16],"rels":[46,45,94,95,54,51]}
Process mode, stdout_json_match. When several shortest paths exist, the deterministic one is fixed by expanding neighbors in id order (neighborEdges sorts by (node, rel)), so the predecessor set first under that order wins. An unreachable pair returns null.