A padlock has between 1 and 4 dials, each showing a digit 0-9. Its state is a string of digits such as "0472". One turn rotates a single dial one step up or down, and the digits wrap around: turning 9 up gives 0, and turning 0 down gives 9.
Some codes are jammed: if the lock ever shows one of them, it seizes up. Write min_turns(start, target, jammed) -> int that returns the fewest turns taking the lock from start to target without ever showing a jammed code, or -1 if that's impossible (including when start or target is itself jammed).
min_turns("0000", "0011", ["0010", "0001", "0009"]) # 4 (0000 -> 0100 -> 0110 -> 0111 -> 0011)
min_turns("0000", "0009", []) # 1 (turn the last dial down)
min_turns("00", "55", ["01", "10", "09", "90"]) # -1 (every first move is jammed)
min_turns("7", "7", []) # 0
Constraints: start and target have the same length L (1 to 4); jammed holds up to 10,000 codes of length L, possibly repeated. The tests make many calls with thousands of jammed codes: aim for O(10^L · L + |jammed|) per call, which rules out scanning a list to check whether a code is jammed or already reached.
Show hint
Every code is a node with 2L neighbours; the question is how few edges separate two nodes. Explore outward from start one turn at a time, keeping jammed and already-reached codes in sets.