Open The Lock

MEDIUM✓ CHIP-TIMEDLC #752 — FULL STATEMENT ↗

The drill: A 4-wheel combination lock starts at 0000. Each move turns one wheel one notch either way. Find the fewest moves to reach a target combination, given a list of combinations the lock jams on and refuses to pass through.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This drill models a 4-wheel combination lock, each wheel holding a digit 0 through 9 that wraps around. A single move turns exactly one wheel one notch in either direction, and the lock starts sitting at 0000.

A list of forbidden combinations acts as deadends — the lock simply cannot land on one of those combinations at any point, including as the very first move from the start. A deadend list that includes the start itself, or that walls off the target completely, blocks the lock for good.

The task is the fewest moves needed to dial in a given target combination, starting from 0000, or −1 if no sequence of legal moves ever reaches it without passing through a deadend.

EX 01

deadends = [] · target = "0000"

→ 0

ALREADY AT TARGET

EX 02

deadends = [] · target = "0007"

→ 3

SHORTER TO TURN ONE WHEEL DOWN THAN UP

EX 03

deadends = [] · target = "9999"

→ 4

EVERY WHEEL ONE NOTCH BACKWARD

deadends list can include the start itself, blocking everything immediately
each wheel wraps: turning past 9 lands on 0, and past 0 lands on 9
at most a few thousand deadend combinations
answer is the minimum move count, or −1 if the target is unreachable

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every combination is a node, and one wheel-turn is an edge to a neighbor. Fewest moves to a target, in an unweighted graph, is a shortest-path question — what search explores layer by layer?

HINT 2 THE STRUCTURE

BFS from 0000, skipping deadends and anything already visited, finds the shortest path — but it explores the whole radius of the search outward from a single start.

HINT 3 ONE STEP FROM THE ANSWER

Grow two frontiers at once — one from 0000, one from the target — and stop the instant they touch. Each side only needs to cover half the distance.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE TWO-SIDED DIALPATTERN · BIDIRECTIONAL BFSstart 0000 → target 0009 · deadend 8888 (unrelated)

STEP 1

Lock at 0000, target 0009 — deadend 8888 isn't even near this path. Bidirectional BFS grows a frontier from each side at once.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/open-the-lock.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        start = "0000"
        if start in dead or target in dead:
            return -1
        if start == target:
            return 0

        def neighbors(state):
            for i in range(4):
                d = int(state[i])
                for delta in (1, -1):
                    nd = (d + delta) % 10
                    yield state[:i] + str(nd) + state[i + 1:]

        front = {start}
        back = {target}
        seen = {start, target}
        steps = 0
        while front and back:
            if len(front) > len(back):
                front, back = back, front
            nxt_front = set()
            for state in front:
                for nxt in neighbors(state):
                    if nxt in dead:
                        continue
                    if nxt in back:
                        return steps + 1
                    if nxt not in seen:
                        seen.add(nxt)
                        nxt_front.add(nxt)
            front = nxt_front
            steps += 1
        return -1

TIME O(10^4) STATES, ROUGHLY HALF EXPLOREDSPACE O(10^4)PYTHON · RACE PACE · 36 LN

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        start = "0000"
        if start in dead:
            return -1
        if start == target:
            return 0

        def neighbors(state):
            for i in range(4):
                d = int(state[i])
                for delta in (1, -1):
                    nd = (d + delta) % 10
                    yield state[:i] + str(nd) + state[i + 1:]

        visited = {start}
        queue = collections.deque([(start, 0)])
        while queue:
            state, steps = queue.popleft()
            for nxt in neighbors(state):
                if nxt in dead or nxt in visited:
                    continue
                if nxt == target:
                    return steps + 1
                visited.add(nxt)
                queue.append((nxt, steps + 1))
        return -1

TIME O(10^4) STATES, 8 MOVES EACHSPACE O(10^4)PYTHON · TRAINING PACE · 28 LN

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if (dead.contains(start) || dead.contains(target)) return -1;
        if (start.equals(target)) return 0;

        Set<String> front = new HashSet<>(Set.of(start));
        Set<String> back = new HashSet<>(Set.of(target));
        Set<String> seen = new HashSet<>(Set.of(start, target));
        int steps = 0;

        while (!front.isEmpty() && !back.isEmpty()) {
            if (front.size() > back.size()) {
                Set<String> tmp = front;
                front = back;
                back = tmp;
            }
            Set<String> nextFront = new HashSet<>();
            for (String state : front) {
                for (String nxt : neighbors(state)) {
                    if (dead.contains(nxt)) continue;
                    if (back.contains(nxt)) return steps + 1;
                    if (seen.add(nxt)) nextFront.add(nxt);
                }
            }
            front = nextFront;
            steps++;
        }
        return -1;
    }

    private List<String> neighbors(String state) {
        List<String> out = new ArrayList<>();
        char[] chars = state.toCharArray();
        for (int i = 0; i < 4; i++) {
            char orig = chars[i];
            int d = orig - '0';
            chars[i] = (char) ('0' + (d + 1) % 10);
            out.add(new String(chars));
            chars[i] = (char) ('0' + (d + 9) % 10);
            out.add(new String(chars));
            chars[i] = orig;
        }
        return out;
    }
}

TIME O(10^4) STATES, ROUGHLY HALF EXPLOREDSPACE O(10^4)JAVA · RACE PACE · 47 LN

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if (dead.contains(start)) return -1;
        if (start.equals(target)) return 0;

        Set<String> visited = new HashSet<>();
        visited.add(start);
        Deque<String> queue = new ArrayDeque<>();
        queue.add(start);
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                String state = queue.poll();
                for (String nxt : neighbors(state)) {
                    if (dead.contains(nxt) || visited.contains(nxt)) continue;
                    if (nxt.equals(target)) return steps + 1;
                    visited.add(nxt);
                    queue.add(nxt);
                }
            }
            steps++;
        }
        return -1;
    }

    private List<String> neighbors(String state) {
        List<String> out = new ArrayList<>();
        char[] chars = state.toCharArray();
        for (int i = 0; i < 4; i++) {
            char orig = chars[i];
            int d = orig - '0';
            chars[i] = (char) ('0' + (d + 1) % 10);
            out.add(new String(chars));
            chars[i] = (char) ('0' + (d + 9) % 10);
            out.add(new String(chars));
            chars[i] = orig;
        }
        return out;
    }
}

TIME O(10^4) STATES, 8 MOVES EACHSPACE O(10^4)JAVA · TRAINING PACE · 43 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED