Задача: Взлом замка

Условие: даётся замок, состоящий из четырёх вращающихся дисков, на каждом из которых имеется 10 цифр: от 0 до 9. При этом за раз можно перемещать только одно колесо и на одно значение. 

Изначально замок находится на значении «0000». 

На вход подаётся список блокирующих комбинаций, то есть таких четвёрок цифр, при которых открыть механизм не представляешься возможным. 

Помимо этого даётся шифр открывающий замок, необходимо вычислить наименьшее число перемещений дисков механизма для открытия замка.

Пример:

Ввод: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Вывод: 6

Объяснение: последовательность, открывающая замок: "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

Решение задачи на Python:

Наилучший результат для приведенного ниже кода - 284 мс / 14,3 МБ (удары 96% / 100%).

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if target == "0000": return 0
        queue, target = deque([0]), int(target)
        seen, turns = [0] * 10000, 1
        for d in deadends: seen[int(d)] = 1
        if seen[0]: return -1
        while len(queue):
            qlen = len(queue)
            for i in range(qlen):
                curr, j = queue.popleft(), 1
                while j < 10000:
                    mask = curr % (j * 10) // j
                    masked = curr - (mask * j)
                    for k in range(1,10,8):
                        nxt = masked + (mask + k) % 10 * j
                        if seen[nxt]: continue
                        if nxt == target: return turns
                        seen[nxt] = 1
                        queue.append(nxt)
                    j *= 10
            turns += 1
        return -1