- Computational model
- One state transition cleans the current cell or moves one edge in a 4-neighbour grid.
- Abstraction
- The floor is an unweighted graph; reachable cells are vertices and legal moves are edges.
- Data structures
- Matrix, coordinate pair, queue, predecessor matrix, and a set of dirty cells.
- Algorithm
- Repeated breadth-first search chooses a shortest route to the nearest dirt.
- Correctness idea
- BFS explores by distance layers; the first reached dirt has minimum path length.
- Extensions
- Weighted terrain, battery limits, graph cleaning, competing robots, or a shared task queue.
Predict → step → explain → improve
Algorithms should move.
These small worlds expose state one transition at a time. Predict the next frame, take one step, name the invariant, and only then press Run.
ApproachModelRepresentChooseVerifyImprove
Simulation + graph search
01 · Cleaning robot
Ready. Predict the first action.
robot dirt wall visited
Search made visible
02 · Shortest path
Frontier contains the start.
start frontier explored shortest path
- Computational model
- Each step removes one frontier vertex and discovers its unvisited neighbours.
- Abstraction
- A maze becomes a graph; geometry matters only when generating neighbours.
- Data structures
- FIFO queue, visited matrix, distance matrix, and one parent per discovered cell.
- Algorithm
- Breadth-first search followed by predecessor-chain reconstruction.
- Correctness idea
- When a vertex leaves the queue, its recorded distance is the fewest possible edges from start.
- Extensions
- Dijkstra for costs, A* for a heuristic, graph adjacency lists, or multi-source evacuation.
State + linked sequence
03 · Playable Snake
Use arrow keys or direction buttons.
head body food
- Computational model
- One tick chooses a direction, creates a new head, and removes the tail unless food is eaten.
- Abstraction
- The snake is an ordered path embedded in a bounded grid.
- Data structures
- Ordered coordinate chain plus occupancy set; the C++ version uses linked nodes.
- Algorithm
- Real-time simulation with collision detection and deterministic food placement.
- Correctness idea
- After each legal tick, coordinates are in bounds, unique, and consecutive neighbours.
- Extensions
- AI search, replay strings, obstacles, two snakes, terminal ANSI animation, or a graphical renderer.
One algorithm, many views
Never confuse the model with its picture.
Lowest setup cost; ideal for tracing exact states and remote systems.
Accessible cells, controls, colour, and interaction without changing the underlying algorithm.
Useful for graphs, paths, geometry, and animation at larger scale.
A renderer can consume the same model through a clean interface.