Retrace — workshop

The LC 79 Word Search grid DFS drawn one event at a time — the live path lit through the letters, every neighbour it turns away flagged with why — with the visited mark's lifetime and the outer scan each switchable to their bug, so a cell that stays marked after its branch is abandoned is a thing you watch turn a true into a false.

Word Search (LC 79): a grid of letters, a word, and the question of whether the word can be spelled along a path of side-adjacent cells that uses no cell twice. The search is a depth-first walk from every cell whose letter matches the first one, and the piece draws that walk as it happens, one event per step: pick a start, enter a cell that matches, reject a neighbour (off the board, wrong letter, already used), spell the word, pop back out. The path the recursion is standing on is lit blue with its depth in the corner; the cell this step is about wears a white ring; the word on the right fills in as far as the path spells it.

Two controls, one per classic failure.

Visited mark is the whole problem. “May not be used more than once” makes the visited set a property of the current path, not of the grid, so the mark a cell gets on the way in has to come off on the way back out. Cleared on return is that. Never cleared is a global visited set: abandoned branches leave their cells hatched amber, nobody standing on them, and a later path that needs one is turned away as if something were — the AAB preset goes from true to false and the readout says false negative. No marks is the other direction: the brief’s ABCB comes out true along a path that steps on B twice, and the badge in that cell reads 2·4.

Start cells is the scan bug. Try every match keeps going when a search fails. Return from the first match is if board[r][c] == word[0]: return dfs(r, c, 0) — it returns whatever the first matching cell says, and SEE on the brief’s board fails from the first S without ever trying the second.

Type your own board (rows separated by spaces, up to 6 × 6) and word (up to 15 letters, capped so the page stays responsive — a search past 4 000 events is truncated and says so), step through, or let it run.

Reuse

src/retrace.js is a framework-free ES module:

parseBoard(text, { maxRows, maxCols }) — rows of letters out of free text, every row cut or padded to the first one’s width.
cleanWord(text, { max }) — letters only, capped.
exist(board, word) — the plain answer, as you would write it in an interview.
simulate(board, word, { visited, starts, maxFrames }) — runs the search once and returns frames, one per event (start, enter, reject with its reason, found, leave, giveup, done), each carrying the working path, one mark per cell, and the running counters; plus the run’s result, the correct truth, and a verdict (ok, false-negative, false-positive). visited is 'unmark', 'never' or 'none'; starts is 'all' or 'first'. Same trace-per-tick shape as prune, ledger, window and astar-grid.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

Neighbours are tried right, down, left, up — the order changes which path is found and how many cells are entered, never whether one exists.
Under no marks the path can revisit a cell; the corner badge lists every depth it is standing at.
The demo bundles its own copy of retrace.js (self-contained by contract); re-copy after editing src/.