Minimum Turns Lock Problem | Dataford Interview Questions

The Current app uses a four-wheel security lock for a protected flow. The lock starts at "0000". Each turn increments or decrements exactly one wheel, with digits wrapping from 9 to 0 and from 0 to 9.

Given a list of forbidden lock combinations and a target combination, return the minimum number of turns needed to reach the target from "0000". Return -1 if the target cannot be reached. A forbidden combination cannot be entered, including the starting combination.

Formal Specification

Implement open_lock(deadends, target).

deadends is a list of unique four-character strings containing digits 0 through 9.
target is a four-character string containing digits 0 through 9.
Return an integer representing the minimum number of turns, or -1 when no valid sequence exists.
A move changes one digit by exactly +1 or -1, with wraparound.

Constraints

0 <= len(deadends) <= 10,000
Every deadend is a unique four-character string of digits.
target is a four-character string of digits.
The state space contains exactly 10,000 possible combinations.

Function Signature

def open_lock(deadends, target):

Your question is Minimum Turns Lock Problem. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem