Minimum Lock Turns
## description
## Minimum Lock Turns
Given a starting lock combination (e.g. 0000) find the minimum number of turns required for each wheel to get to a target (e.g. 0202) in the presence of potentially blocked states.
Example 1:
1Input: start = "0000", target = "0202", blocked = ["0201","0101","0102","1212","2002"]
2Output: 6Example 2:
1Input: start = "1234", target = "1236", blocked = []
2Output: 2Example 3:
1Input: start = "5555", target = "5559", blocked = ["5556", "5557", "5558"]
2Output: 6## notes
### Intuition
Each lock combination is a graph node with 8 neighbors (4 wheels × 2 directions). BFS from start to target finds the minimum number of turns, avoiding blocked combinations.
### Implementation
Generate neighbors by turning each wheel up or down (using mod 10 for wraparound). Start BFS with (start_combo, 0) in the queue and a visited set. For each state, try all neighbors—skip if visited or blocked. If a neighbor is the target, return turns + 1. Otherwise, add to queue and visited.
### Edge-cases
Check if start equals target (return 0) or if start is blocked (return -1) before starting BFS.
- –Time: O(10⁴) — at most 10,000 possible states
- –Space: O(10⁴) — visited set and queue
### Complexity
## solution
1from typing import List
2from collections import deque
3
4class Solution:
5 def neighbours(self, combo: str) -> List[str]:
6 result = []
7 for i in range(len(combo)):
8 up_n = [int(c) for c in combo]
9 down_n = [int(c) for c in combo]
10 up_n[i] = (up_n[i] + 1) % 10
11 down_n[i] = (down_n[i] - 1) % 10
12 result.append("".join([str(n) for n in up_n]))
13 result.append("".join([str(n) for n in down_n]))
14 return result
15
16 def minLockTurns(self, start: str, target: str, blocked: List[str]) -> int:
17 block = set(blocked)
18 if start in block:
19 return -1
20 if start == target:
21 return 0
22
23 q = deque([(start, 0)])
24 visited = { start }
25 while q:
26 curr, turns = q.popleft()
27 for n in self.neighbours(curr):
28 if n in visited or n in block:
29 continue
30 if n == target:
31 return turns + 1
32 visited.add(n)
33 q.append((n, turns + 1))
34 return -1
35
36if __name__ == "__main__":
37 # Include one-off tests here or debugging logic that can be run by running this file
38 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
39 solution = Solution()
40