0253MediumArrayHash TableStringBreadth-First SearchBidirectional Search

Four-Drum Seal Dial

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A freight container is closed with a numeric seal built from four drums standing side by side, each showing one digit from 0 to 9. A reading of the seal is written as a four-character string of digits, leftmost drum first.

Turning one drum one notch, in either direction, counts as one move. A drum showing 9 turned upward comes round to 0, and a drum showing 0 turned downward comes round to 9. Only one drum moves at a time.

Certain readings seize the mechanism: the moment the seal shows a reading listed in jammed, the drums lock for good. A reading in jammed therefore cannot be shown at any point, not even in passing on the way somewhere else.

A fresh seal reads 0000. Return the fewest moves needed to bring the seal to target, or -1 if target cannot be shown at all. target is never listed in jammed, and jammed may list the same reading more than once.

Examples

Example 1

Input: jammed = ["0810", "0090"], target = "0091"
Output: 2

Turning the last drum up once shows 0001, then turning the third drum down once brings it round to 9 and shows 0091. Neither reading is listed in jammed.

Example 2

Input: jammed = ["0001"], target = "0002"
Output: 4

The seal can show 1000, then 1001, then 1002, then 0002, four moves in all, and none of those four readings is listed in jammed.

Example 3

Input: jammed = ["0000"], target = "0210"
Output: -1

The fresh seal already shows a jammed reading, so the drums are locked before any move is made.

Constraints

1 <= jammed.length <= 500
jammed[i].length == 4
target.length == 4
target and every jammed[i] consist of digits only
target does not appear in jammed

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_seal_moves(jammed: list[str], target: str) -> int:

Java

public int fewestSealMoves(String[] jammed, String target)

The intended approach

Time O(10^4 * 4 * 2 + d) where d is the length of jammed: every reading leaves the queue at most once and offers eight turnsSpace O(10^4 + d) for the flag array, the queue and the jammed set

There are only 10000 readings, so treat each one as a node and each single notch as an edge of weight one, then sweep outward from 0000 with a queue. Readings are held as the integers 0 to 9999 and a drum is turned by adding or subtracting its place value, folding 9 to 0 and 0 to 9 by hand. A flag array keeps each reading out of the queue more than once, and the jammed set is consulted before a reading is ever entered, so no route passes through one. Because the queue empties one move-count at a time, the first sighting of the target carries the fewest moves.

Pythonentry point: fewest_seal_moves

def fewest_seal_moves(jammed, target):
    from collections import deque

    blocked = set()
    for reading in jammed:
        blocked.add(int(reading))
    if 0 in blocked:
        return -1
    goal = int(target)
    if goal == 0:
        return 0
    seen = bytearray(10000)
    seen[0] = 1
    frontier = deque()
    frontier.append((0, 0))
    while frontier:
        code, moves = frontier.popleft()
        place = 1
        for _ in range(4):
            digit = (code // place) % 10
            for step in (1, -1):
                if step == 1:
                    nxt = code - 9 * place if digit == 9 else code + place
                else:
                    nxt = code + 9 * place if digit == 0 else code - place
                if seen[nxt] or nxt in blocked:
                    continue
                if nxt == goal:
                    return moves + 1
                seen[nxt] = 1
                frontier.append((nxt, moves + 1))
            place *= 10
    return -1

The obvious version

Run a priority-queue shortest-path search over readings kept as four-character strings, settling the cheapest unsettled reading each round and rebuilding neighbours by string surgery.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_seal_moves(jammed, target):
    import heapq

    blocked = set(jammed)
    if "0000" in blocked:
        return -1
    best = {"0000": 0}
    heap = [(0, "0000")]
    settled = set()
    while heap:
        moves, reading = heapq.heappop(heap)
        if reading in settled:
            continue
        settled.add(reading)
        if reading == target:
            return moves
        for i in range(4):
            for delta in (1, 9):
                turned = str((int(reading[i]) + delta) % 10)
                nxt = reading[:i] + turned + reading[i + 1:]
                if nxt in blocked:
                    continue
                if moves + 1 < best.get(nxt, 10 ** 9):
                    best[nxt] = moves + 1
                    heapq.heappush(heap, (moves + 1, nxt))
    return -1

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in