Fewest actions or least cost?

S→T costs 8. S→U costs 1. U→T costs 1.

Which route uses the fewest edges? Which costs least?

What assumption makes first FIFO discovery a shortest-path proof?

1 / 7

Word Ladder — predict before coding

Words are vertices; changing one position is an unweighted edge. Wildcard buckets are an adjacency index, not an alternative distance metric. The answer counts words, so the start has distance 1.

Decision: For hit->hot->dot->dog->cog, what is the returned length? Why must cog be in the dictionary even though hit need not be?

Presenter notes

Model answer: The length is 5, not 4. Every changed-to word, including the endpoint, must be allowed. The starting word is supplied as the initial state and need not have appeared in the list.

Correctness argument: FIFO processing ensures all words at distance d are processed before any newly discovered word at distance d+1. Every legal one-letter neighbor shares a wildcard pattern with the current word, and each bucket contains only such neighbors (apart from the current word itself). Thus all shorter paths would have been explored before a word is first enqueued. Clearing a bucket after its first expansion is safe: all its words have then been discovered at distance at most the current distance plus one; a later use cannot improve them. The first dequeue of endWord gives the shortest number of words, and exhaustion proves it unreachable.

Debugging prompt: Separate edge count from word count. Mark on enqueue and clear only a fully expanded wildcard bucket. When begin equals end, preserve the existing membership check: return 1 only if that word is in the list, otherwise 0.

2 / 7

Snakes and Ladders — predict before coding

Choose the state after the mandatory jump, so one BFS edge is exactly one die roll followed by at most one snake or ladder. Board drawing coordinates are only an encoding of labels.

Decision: On a 3x3 board, where are labels 1, 4, 6, and 9? If landing on 2 jumps to 8 and 8 contains a jump, do you chain it?

Presenter notes

Model answer: Using zero-based (row,column), the positions are 1=(2,0), 4=(1,2), 6=(1,0), and 9=(0,2). Apply only the jump from landing square 2; do not chain the jump written at 8 during this roll.

Correctness argument: For a label s, row-from-bottom is (s-1)/n and the within-row offset is (s-1)%n; reversing the offset on odd rows yields the boustrophedon coordinates. From each state, enumerate every legal die result without overshooting, apply exactly one destination lookup, and enqueue unseen resulting states. These transitions are precisely the legal one-roll moves. FIFO distance ordering therefore finds the minimum number of rolls. Visiting the post-jump state prevents duplicate work when different landings jump to the same destination. A destination that itself contains a jump does not trigger another jump in that same roll.

Debugging prompt: Draw labels before placing jumps. Off-by-one errors in (s-1) and reversing the wrong row produce plausible but wrong boards. Mark the destination after the jump, not only the die-landing square.

3 / 7

Minimum Genetic Mutation — predict before coding

Generate neighbors by changing one character to one of the other three bases. The bank is an admissibility filter; being one mutation away is not enough unless the resulting gene is allowed.

Decision: Why is start=end answered with 0 even for an empty bank, while a different absent target is answered with -1?

Presenter notes

Model answer: The unchanged starting state requires no mutation. A different target must be entered through a mutation, and every entered state must be allowed by the bank. These are different preconditions, not inconsistent special cases.

Correctness argument: Every generated candidate differs at exactly one position because the original byte is restored before moving to the next position. Filtering by the bank yields exactly the permitted outgoing neighbors. FIFO exploration with marking on enqueue discovers each gene at its smallest mutation count. The initial gene has distance zero; if it already equals the target, no bank entry is needed. Otherwise reaching the target requires the target to be in the bank. Exhausting all reachable bank genes proves no allowed transformation sequence exists.

Debugging prompt: Restore the modified position before generating changes at another position. Forgetting restoration creates edges that change two or more characters. Test absent targets, cycles, and disconnected bank components.

4 / 7

Rotting Oranges — predict before coding

All initially rotten oranges are simultaneous sources at minute zero. A fresh orange rots at the minimum distance from any source, not after the sum of separate source traversals.

Decision: For row [2,1,1,1,2], when does each fresh orange rot? Why does processing the two sources one after another with separate clocks fail?

Presenter notes

Model answer: The fresh times are 1,2,1, so all rot after 2 minutes. The sources act concurrently; summing or serializing their clocks overstates elapsed time.

Correctness argument: Before each layer is processed, the queue contains cells first rotten at one common minute. Each fresh neighbor becomes rotten at the next minute and is immediately marked, so it cannot be scheduled again by another source. Induction on distance from the nearest source establishes the earliest rotting time for every reachable orange. The fresh counter decreases once per changed cell. If it reaches zero, the last processed layer gives the required elapsed minutes; if reachable layers end with fresh cells remaining, those cells are separated by empty cells and the answer is -1. No initial fresh cells means zero elapsed time.

Debugging prompt: Distinguish empty cells from fresh ones, and count actual state changes only once. Test no fresh oranges, fresh cells without a source, and two waves meeting at the same cell.

5 / 7

Shortest Path in Binary Matrix — predict before coding

The graph uses eight directions, and the path length counts cells. A clear 1x1 board therefore has length 1. These choices differ deliberately from the island and rotting-orange problems.

Decision: For [[0,1],[1,0]], is there a path? What length would four-direction code incorrectly return?

Presenter notes

Model answer: There is an allowed diagonal path of length 2. Four-direction code would incorrectly return -1. This contract does not forbid diagonal movement between two blocked orthogonal neighbors.

Correctness argument: The start is enqueued at distance one only when both endpoints are clear. Every generated move joins adjacent clear cells in one of the eight allowed directions. Marking a cell on enqueue prevents repeated discovery. FIFO ordering means a cell first reached at distance d cannot have an unprocessed shorter path: that path would have arrived from a previously processed layer. Thus the first target state has the minimum cell count. If the queue empties without it, every reachable clear cell has been explored and no legal path exists.

Debugging prompt: Check both endpoints before starting. Keep the eight-direction rule and cell-count distance visible in tests. The visited mark changes 0 to 1, so do not expect the board to remain unchanged.

6 / 7

Add one reversible resource

A grid permits one wall removal. Two routes reach the same cell: one has used the removal and one has not.

Can visited[row][col] safely merge these states? Construct the missing state and describe the transition.

7 / 7