Open the lock

A combination lock has four wheels, each showing a digit 0–9. One move turns a single wheel one step up or down, and the wheels wrap (9 to 0, 0 to 9). Given a start, a target and a list of blocked combinations the lock must never show, return the fewest moves from start to target, or -1 if it can't be done.

Interface

Unless you agree on a different interface with the interviewer, assume:

• open_lock(start: str, target: str, blocked: list[str]) -> int — combinations are 4-character digit strings.

Example

open_lock("0000", "0302", [])                                ->  5
open_lock("0000", "0302", ["0100", "0201", "0202", "0301"])  ->  7    # the direct routes are blocked
open_lock("0000", "0019", [])                                ->  2    # 0000 -> 0009 -> 0019, using the wrap
open_lock("1234", "1234", [])                                ->  0
open_lock("0000", "9999", ["0001", "0009", "0010", "0090",
                           "0100", "0900", "1000", "9000"])  ->  -1   # every first move is blocked

Constraints

• 0 <= len(blocked) <= 10^4; blocked combinations are distinct.

Clarifying questions

• If the start is blocked, is the answer -1?
• Can the target be blocked?
• Are there always four wheels, or should the number of wheels be a parameter?

What a strong answer covers

• The states form an unweighted graph of 10^4 nodes with 8 neighbours each, so BFS from the start finds the fewest moves; blocked states go into the visited set up front.
• Generating neighbours with (d + 1) % 10 and (d + 9) % 10.
• O(10^4 * 8) time and O(10^4) space; bidirectional BFS as a constant-factor improvement.
• Edge cases: start equals target, start blocked, target blocked, every neighbour of the start blocked.

Follow-ups

• Return the sequence of combinations, not just the count.
• Generalize to w wheels with b symbols each.
• Turning a wheel by more than one step counts as one move.