0477MediumHash TableStringBreadth-First SearchBidirectional Search

Retooling the Bottling Line

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 bottling line has eight stations in a row, and each station carries one of four nozzle types, written "A", "C", "G" or "T". A fitting of the whole line is therefore a string of exactly eight of those letters, read from the first station to the last.

The line is currently on the fitting start and the shift plan calls for the fitting target. A single retool takes the line down and swaps the nozzle on exactly one station, leaving the other seven alone.

Safety rules only allow the line to run on a fitting drawn from approved. Every fitting the line comes to rest on, including target, has to be on that list. The fitting the line starts on does not have to be on the list, since it is already running. The list may be empty and may name the same fitting more than once.

Return the fewest retools that take the line from start to target, or -1 when no run of retools does.

Examples

Example 1

Input: start = "AACCGGTT", target = "AACCGAAA", approved = ["AACCGGTA", "AACCGGAA", "AACCGAAA", "TTTTTTTT"]
Output: 3

Swapping station 8, then station 7, then station 6 gets there, and each of the three fittings the line rests on is on the approved list.

Example 2

Input: start = "AACCGGTT", target = "AACCGAAA", approved = ["AACCGGAA", "AACCGAAA"]
Output: -1

Each approved fitting here differs from the current one on two stations, and a retool touches one station, so the line has nowhere legal to rest.

Example 3

Input: start = "AACCGGTT", target = "AACCGGTT", approved = []
Output: 0

The line already carries the fitting the shift plan asks for, so no station is touched.

Constraints

0 <= approved.length <= 10
len(start) == len(target) == len(approved[i]) == 8
start, target and approved[i] consist only of the characters 'A', 'C', 'G' and 'T'.

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_retools(start: str, target: str, approved: list[str]) -> int:

Java

public int fewestRetools(String start, String target, String[] approved)

The intended approach

Time O(B * L^2) for B approved fittings of length LSpace O(B * L) for the approved set, the visited set and the queue

Treat each fitting as a spot the line can rest on and each single-station swap as a hop between spots. Put the approved list into a set so a hop can be tested in constant time, then sweep outward from the starting fitting level by level with a queue, generating the hops by trying each of the four nozzles at each of the eight stations. The level on which the target first turns up is the retool count. Two early exits handle the case where the line is already fitted correctly and the case where the target is not approved at all.

Pythonentry point: fewest_retools

from collections import deque


def fewest_retools(start, target, approved):
    # Sweep outward from the current fitting one retool at a time.
    # time O(B * L^2) for a list of B approved fittings of length L
    # space O(B * L) for the approved set and the queue
    if start == target:
        return 0
    allowed = set(approved)
    if target not in allowed:
        return -1
    seen = {start}
    queue = deque([(start, 0)])
    while queue:
        fitting, steps = queue.popleft()
        for pos in range(len(fitting)):
            for nozzle in "ACGT":
                if nozzle == fitting[pos]:
                    continue
                swapped = fitting[:pos] + nozzle + fitting[pos + 1:]
                if swapped not in allowed or swapped in seen:
                    continue
                if swapped == target:
                    return steps + 1
                seen.add(swapped)
                queue.append((swapped, steps + 1))
    return -1

The obvious version

Number the starting fitting and the approved fittings, then work out which pairs sit one station apart by counting mismatches for every pair. Keep a retool count per fitting and relax the whole table repeatedly until a full sweep improves nothing, then read the count for the target.

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_retools(start, target, approved):
    if start == target:
        return 0
    if target not in approved:
        return -1
    labels = [start]
    for fitting in approved:
        if fitting not in labels:
            labels.append(fitting)
    total = len(labels)
    far = 10 ** 9
    best = [far] * total
    best[0] = 0
    moved = True
    while moved:
        moved = False
        for i in range(total):
            if best[i] == far:
                continue
            for j in range(total):
                if i == j:
                    continue
                apart = 0
                for p in range(len(labels[i])):
                    if labels[i][p] != labels[j][p]:
                        apart += 1
                if apart == 1 and best[j] > best[i] + 1:
                    best[j] = best[i] + 1
                    moved = True
    goal = labels.index(target)
    return -1 if best[goal] == far else best[goal]

How this problem was checked

Reference solution executed against 10 test cases — 10 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