> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Open the Lock Python Solution with Tests

> Tested Python solution for LeetCode 752 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 752, Medium. Topics: Array, Hash Table, String, Breadth-First Search. [View on LeetCode](https://leetcode.com/problems/open-the-lock/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 752   # by problem number
lcpy gen -s open_the_lock   # by problem name
```

## Problem

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: `'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`. The wheels can rotate freely and wrap around: for example we can turn `'9'` to be `'0'`, or `'0'` to be `'9'`. Each move consists of turning one wheel one slot.

The lock initially starts at `'0000'`, a string representing the state of the 4 wheels.

You are given a list of `deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a `target` representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or `-1` if it is impossible.

### Examples

```
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
```

```
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".
```

```
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.
```

### Constraints

* 1 \<= deadends.length \<= 500
* deadends\[i].length == 4
* target.length == 4
* target will not be in the list `deadends`.
* `target` and `deadends[i]` consist of digits only.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/open_the_lock/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/open_the_lock/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(10^4)
    # Space: O(10^4)
    def open_lock(self, deadends: list[str], target: str) -> int:
        dead = set(deadends)
        if "0000" in dead:
            return -1
        if target == "0000":
            return 0

        queue: deque[tuple[str, int]] = deque([("0000", 0)])
        visited: set[str] = {"0000"}

        while queue:
            state, turns = queue.popleft()
            for i in range(4):
                digit = int(state[i])
                for delta in (1, -1):
                    new_digit = (digit + delta) % 10
                    neighbor = state[:i] + str(new_digit) + state[i + 1 :]
                    if neighbor == target:
                        return turns + 1
                    if neighbor in dead or neighbor in visited:
                        continue
                    visited.add(neighbor)
                    queue.append((neighbor, turns + 1))

        return -1
```

## Complexity

| Time    | Space   |
| ------- | ------- |
| O(10^4) | O(10^4) |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).