Open the Lock

Open the lock turns a four-wheel combination lock from "0000" to a target, avoiding a set of deadends, using the fewest single-wheel turns. The word fewest is the signal. Each lock state is a node, and turning one wheel one notch is an edge to another state. All turns cost the same, so this is a shortest path on an unweighted graph, which is BFS: - Every state has exactly eight neighbours — four wheels, each turned up or down one notch. The state space is bounded: 10⁴ = 10,000 combinations, small enough to explore exhaustively. Wheels wrap, so the digit after 9 is 0 and before 0 is 9. Modular arithmetic handles both — (d + 1) % 10 and (d + 9) % 10. Forgetting the wrap silently removes valid moves and can make a reachable target look unreachable. Deadends are simply states that may not be entered. The cleanest handling is to load them into the visited set before the search starts, so the traversal treats them as already-seen and never expands them. Checking them separately inside the loop works too but adds a branch on every neighbour. One case is easy to miss: if "0000" is itself a deadend, the answer is −1 even when the target is "0000". Seeding the visited set first handles this automatically, since the start is then never enqueued. Bidirectional BFS — searching from both start and target — cuts the explored frontier substantially and is worth knowing, though plain BFS is fast enough at this size.

BFS over lock states, with deadends folded into the visited set at initialisation. That single trick means the expansion loop needs no separate deadend test — an unreachable state and an already-seen state are handled identically.