algorithms · intermediate · 8d
Pathfinding Route Engine
Four search algorithms, one shared problem: get from A to B across a weighted grid. You'll build BFS, DFS, Dijkstra, and A* on a single graph model, then run them side by side and watch them disagree — DFS lunges into a dead end, BFS floods evenly, Dijkstra crawls outward by cost, A* leans toward the goal. This is where the algorithms unit stops being trivia and becomes a set of tools you choose between, with reasons.
Deliverable
A CLI that loads a grid (walls and weighted cells), runs any of BFS/DFS/Dijkstra/A* between two points, prints the path plus nodes-expanded and path-cost, and renders the explored frontier as ASCII so you can see how each algorithm searches.
Milestones
0/5 · 0%- 01Model the world as a graph
Before any search, you need something to search. Represent the grid so that every algorithm can ask the same two questions: 'what are my neighbours?' and 'what does it cost to step there?'. Decide deliberately whether you store an explicit adjacency list or compute neighbours on the fly from (row, col) — for a dense grid the implicit form is leaner, but writing the explicit `neighbours(node)` function forces you to handle walls, the four-versus-eight-direction choice, and out-of-bounds edges in one honest place. Weighted cells (think mud costing 3, road costing 1) are what separate a real route engine from a maze toy, so bake cost into the edge from the start rather than bolting it on later.
Definition of done- A `neighbours(node)` function returns only in-bounds, non-wall cells with their step cost.
- A small grid (with at least one wall and one weighted region) loads from a text or array source and round-trips correctly.
- 02BFS and DFS: the uninformed pair
Implement breadth-first and depth-first search and let the data structure be the whole lesson: a queue gives you BFS and the shortest path in number of steps; swap it for a stack and the exact same code becomes DFS, which finds *a* path but rarely the shortest. Track a `visited` set and a `parent` map as you go, because the parent map is how you reconstruct the actual route once the goal is reached — the search only tells you it's reachable. Run both on a grid with a wall in the middle and watch DFS dive deep into one corridor while BFS expands in rings; that contrast is the intuition the rest of the project builds on.
Definition of done- BFS returns a path with the minimum number of steps on an unweighted grid; DFS returns a valid (not necessarily shortest) path.
- Both reconstruct the path from a parent map and report it as an ordered list of cells, or report 'no path' cleanly when the goal is walled off.
- 03Dijkstra: search that respects cost
BFS counts steps, but your grid has weighted cells, so the fewest-steps path and the cheapest path are no longer the same thing. Dijkstra fixes this by always expanding the cheapest-so-far node, which means a plain queue won't do — you need a priority queue keyed by accumulated cost. Implement it carefully: the classic bug is treating a node as final the first time you *see* it instead of the first time you *pop* it, which quietly produces wrong costs on graphs where a longer-hop route is cheaper. Keep a `dist` map and only update a neighbour when you've found a strictly cheaper way in. When it works, a detour through a road should beat a straight line through mud, and your printed path-cost should prove it.
Definition of done- On a weighted grid, Dijkstra returns the minimum-cost path, which differs from the BFS step-count path when weights vary.
- Nodes are finalized on pop, not on first sight, and the reported path-cost equals the sum of the edge weights along the path.
- 04A*: aim with a heuristic
Dijkstra is correct but blind — it expands outward in every direction equally, wasting work on cells pointing away from the goal. A* is Dijkstra plus a hint: at each node it minimizes `g + h`, where `g` is the cost so far and `h` is an estimate of the cost remaining to the goal. On a grid, Manhattan distance is the natural heuristic for four-direction movement. The non-negotiable rule is that `h` must be *admissible* — it may never overestimate the true remaining cost — or A* can return a wrong path; this is the failure mode to test for deliberately, not just to read about. When it works you'll see it expand a narrow cone toward the goal instead of a full disk, and on the same map A* should expand strictly fewer nodes than Dijkstra while returning the identical optimal cost.
Definition of done- A* returns the same optimal-cost path as Dijkstra on weighted grids using an admissible heuristic.
- On at least one map, A* expands measurably fewer nodes than Dijkstra, and a test with an inadmissible heuristic visibly breaks optimality.
- 05One CLI, four searches, honest numbers
Wire the four algorithms behind a single command so the only thing that changes between runs is which search you pick. Each run should print the same three facts — the path, the path-cost, and the number of nodes expanded — plus an ASCII render of the explored frontier so the differences are visible, not just numerical. This is where the project pays off: on one map BFS and Dijkstra agree because the weights are flat, on another they diverge, and A* matches Dijkstra's cost while touching fewer cells. Resist hardcoding the grid — read it from a file so you can craft adversarial maps (a long detour, a deceptive wall) that make each algorithm's character obvious.
Definition of done- `engine <algo> <map> <start> <goal>` runs any of the four and prints path, cost, and nodes-expanded consistently.
- At least two maps exist where the algorithms produce visibly different frontiers or costs, demonstrated in the output.
Starter
- README.md
- src/pathfind.ts
- test/pathfind.test.ts
Unzip, implement the stubs, then run the tests until they pass: bun test
Rubric
| Junior | Mid | Senior | |
|---|---|---|---|
| Priority queue correctness | Uses a built-in sort or a linear scan to find the minimum-cost node each step; Dijkstra and A* produce correct paths on small grids. | Implements or wraps a binary-heap priority queue with O(log n) insert and extract-min; finalises nodes on pop (not on first sight) so costs are correct even when a cheaper path to an already-seen node is discovered later. | Can demonstrate the classic pop-vs-visit bug on a concrete graph: a node seen at cost 10 via one path and cost 8 via a later path — if finalised on visit, the suboptimal cost is locked in. Knows when a decrease-key heap (Fibonacci heap) would reduce asymptotic complexity from O((V+E) log V) to O(E + V log V) and can state why it rarely wins in practice due to constant-factor overhead. |
| Heuristic admissibility | Uses Manhattan distance as the A* heuristic and observes that A* expands fewer nodes than Dijkstra on open maps. | Can state the admissibility requirement (h(n) must never exceed the true remaining cost) and has a test where an inadmissible heuristic (e.g. Manhattan * 1.5) produces a suboptimal path on a specific map where the overestimate causes the wrong node to be expanded first. | Explains consistency (monotone heuristic): h(n) <= cost(n, n') + h(n') for all edges, which guarantees the first time a node is expanded its cost is optimal — enabling lazy duplicate detection instead of a closed set. Can construct a grid where Manhattan is admissible but not consistent (it cannot happen in standard 4-directional grids, but can with variable edge costs) and explain the implication. |
| Graph representation trade-off | Stores the grid as a 2D array and computes neighbours on demand with hardcoded direction deltas. | Separates the grid abstraction from the search algorithm via a `neighbours(node) -> [(node, cost)]` interface, making it possible to plug in a non-grid graph (e.g. a road network adjacency list) without changing any search code. | Can argue when an explicit adjacency list beats implicit on-the-fly neighbour computation: dense grids with constant branching factor (4 or 8) favour implicit (no allocation per node); sparse graphs with variable out-degree or heterogeneous edge metadata favour explicit. Can estimate memory: a 1000x1000 grid with 4-connectivity stores 4M edges implicitly as arithmetic vs 4M explicit pointers (~32 MB at 8 bytes each). |
Reference walkthrough (spoiler)
Why nodes must be finalised on pop, not on visit: in a weighted graph, the first time you encounter a node might be via a longer route. A later path through the priority queue may cost less. If you mark the node done on first sight, you lock in the wrong cost. The invariant that makes Dijkstra correct is: when a node is popped from the min-heap its known cost is the global minimum cost to reach it — this holds because all unvisited costs are >= the popped cost.
A* optimality condition: A* returns the optimal path if and only if the heuristic is admissible (never overestimates). An inadmissible heuristic can cause A* to expand a suboptimal path first, reach the goal via that path, and return a non-minimum-cost solution. The failure is not a crash — the path is valid, just not cheapest — which makes it a silent correctness bug that only appears on maps where the overestimate matters.
Binary heap vs linear scan for the priority queue: a naive implementation that scans all open nodes each step is O(V^2) total; a binary heap makes each insert and extract-min O(log V), giving O((V+E) log V) overall. For a 1000x1000 grid with ~4M edges, the heap approach explores ~1M nodes with ~20 comparisons each (log2(1M) ≈ 20) vs ~1M nodes with ~500K comparisons each for the naive scan — roughly 25000x fewer comparisons.
DFS as the cautionary tale: DFS expands in the deepest direction first, which means on a map with a long corridor next to a short one it will explore the entire long corridor before backtracking. It finds a path but not the shortest, and its nodes-expanded count can be the entire graph even when the goal is adjacent to the start via a short path DFS never tried first. It is not a route-finding algorithm — it is a reachability-check algorithm that happens to return a path.
Make it senior
- Add bidirectional search: grow two frontiers, one from the start and one from the goal, and stop when they meet. The payoff is real — searching to radius r from both ends touches far fewer nodes than searching to radius 2r from one — but the meeting condition and path-stitching are subtle, especially for the weighted and A* variants where 'they met' is not the same as 'the optimal path is found'.
- Build a real benchmark: generate randomized maps at several sizes and obstacle densities, run all algorithms under a timing harness, and report nodes-expanded and wall-clock time as a table. The goal is to make the textbook claims falsifiable — show where A*'s heuristic advantage shrinks (open maps, weak heuristics) and where Dijkstra's extra work is the price of having no hint.
- Make the heuristic pluggable and prove the theory: compare Manhattan, Euclidean, and a deliberately inadmissible (overestimating) heuristic on the same maps, and show how the inadmissible one trades optimality for speed — sometimes acceptably, sometimes not.