Задача с собеседования в eBay

Перед вами замок с 4 вращающимися дисками. Каждый диск имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Диски можно свободно вращать вперёд и назад: например, вы можете превратить '9' в '0' или '0' в '9'. Каждый ход - это поворот одного диска на одну позицию.
Замок начинает с комбинации '0000' (строка, представляющая состояние 4-х дисков).
Вам дан список тупиков - deadends: если на замке отображается какая-либо из запрещённых комбинаций, диски замка перестают вращаться, и вы не можете его открыть.
Вам также дана целевая комбинация target, представляющая значение дисков, при котором замок откроется. Верните минимальное возможное количество вращений, необходимое для открытия замка. Если это невозможно, верните -1.

Пример 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Объяснение: последовательность допустимых ходов может быть такой: "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Обратите внимание, что последовательность типа "0000" -> "0001" -> "0002" -> "0102" -> "0202" будет недопустимой, так как диски замка остановятся после запрещённой комбинации "0102".

Пример 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
Объяснение: мы можем повернуть последний диск в обратном направлении, чтобы перейти от "0000" к "0009".

Пример 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Объяснение: мы не можем достичь цели, не попав в тупик.

Ограничения:
1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target не может присутствовать в списке deadends
target и deadends[i] состоят только из цифр

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Рассмотрим задачу как поиск кратчайшего пути в графе.
Вершины графа - комбинации цифр на 4 дисках, каждый диск - одна позиция в комбинации. Некоторые вершины (deadends) заблокированы, мы не можем посещать их на пути к целевой вершине (target). Граф - невзвешенный, так как все рёбра имеют одинаковый вес (один поворот диска) => используем алгоритм поиска в ширину (BFS).

Начинаем обход с начального состояния '0000' (если оно в списке deadends - до target мы не дойдём, возвращаем -1), добавляем в очередь в виде кортежа (комбинация цифр и количество вращений). Все запрещённые комбинации сразу добавляем во множество visited, чтобы избежать попадания в тупик.

Пока очередь не пуста: извлекаем текущую комбинацию и количество вращений. Если комбинация соответствует target - возвращаем число вращений. Иначе: генерируем 8 следующих комбинаций, увеличивая и уменьшая каждую из 4 цифр (2 направления: 1 поворот диска вперёд и назад). Чтобы реализовать закольцованность дисков: деление по модулю (%10), "9" -> "0" при вращении диска вперёд ((9 + 1) % 10 = 0) и "0" -> "9" при вращении назад ((0 - 1) % 10 = 9).
Проверяем комбинацию: если ещё не посещена - добавляем в visited и помещаем в очередь, увеличивая количество вращений на 1.
Если очередь опустела, а target не достигнута - пути не существует, возвращаем -1.

Сложность
O(V + E) - по времени
O(V) - по памяти

Код
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if "0000" in deadends:
return -1

def new_combinations(node):
result = []
for i in range(4):
next_digit = (int(node[i]) + 1) % 10
result.append(node[:i] + str(next_digit) + node[i + 1:])

prev_digit = (int(node[i]) - 1) % 10
result.append(node[:i] + str(prev_digit) + node[i + 1:])
return result

q = deque([("0000", 0)])
visited = set(deadends)
visited.add("0000")

while q:
node, turns = q.popleft()
if node == target:
return turns
for combination in new_combinations(node):
if combination not in visited:
visited.add(combination)
q.append((combination, turns + 1))
return -1

@algoses