7. Open the Lock

«Если сомневаетесь, используйте грубую силу. Но используйте её с умом: математика и плоские массивы превращают слепой перебор в мгновенное вычисление».
— Кен Томпсон

LeetCode 752. Open the Lock. Имеется кодовый замок с 4 круглыми колесиками. На каждом колесике нанесены 10 цифр от '0' до '9'. Колесики могут вращаться циклически: после '9' идет '0', а перед '0' идет '9'. За один ход можно повернуть любое одно колесико на одно деление вперед или назад. Замок начинает работу в состоянии "0000".

Вам дан список тупиковых комбинаций deadends и целевая комбинация target. Если замок оказывается в комбинации из deadends, его колесики блокируются и дальнейшее вращение невозможно. Требуется найти минимальное количество поворотов, необходимое для достижения target, либо вернуть -1, если открыть замок невозможно.

Эта задача — визитная карточка поиска кратчайшего пути в неявном дискретном пространстве состояний (State Space Search). В бэкенд-инженерии она моделирует обход графов переходов конечных автоматов (State Machines), проверку безопасности протоколов аутентификации и оценку устойчивости систем к атакам полного перебора (Brute Force).

1. Архитектурная ловушка: строковые манипуляции убивают производительность

Первый порыв большинства инженеров — хранить текущее состояние как строку "0123", генерировать соседей через срез байтов []byte и проверять посещённость в хеш-таблице map[string]bool.

// АНТИПАТТЕРН: Десятки тысяч аллокаций в горячем цикле!
curr := "0123"
b := []byte(curr)
b[0] = (b[0]-'0'+1)%10 + '0'
next := string(b) // АЛЛОКАЦИЯ В КУЧЕ НА КАЖДЫЙ ПОВОРОТ!

2. Механическая симпатия: Целочисленные состояния и массив на стеке

Посмотрим на задачу глазами «механического сочувствия» к процессору и рантайму Go:

1. Состояние — это просто число от $0$ до $9999$:
   Комбинация "0000" — это число $0$, а "9999" — это число $9999$. Пространство состояний замка строго ограничено $10^4$ вершинами.
2. Множество visited — плоский массив [10000]bool:
   Вместо динамической хеш-таблицы мы выделяем фиксированный булев массив ровно на $10\,000$ элементов.
   Его размер составляет ровно 10 КБ. Он полностью помещается в кэш данных L1d современного процессора (размер которого обычно равен 32–48 КБ)! Доступ visited[state] компилируется в одну инструкцию чтения памяти по базовому смещению за 1 такт CPU.
3. Безветвенный поворот колесика (Branchless math):
   • Поворот вперед: (digit + 1) % 10.
   • Поворот назад: (digit + 9) % 10. Добавление $9$ по модулю $10$ полностью избавляет от ветвления if digit == 0 { digit = 9 } и устраняет сбои конвейера предсказания переходов (Branch Misprediction).

3. Идиоматическая реализация на Go

package main

// openLock находит минимальное число поворотов дисков замка от "0000" до target.
// Временная сложность: O(10000 * 8 + D) = O(1) — константное число состояний.
// Пространственная сложность: O(10000) — массив visited занимает 10 КБ памяти.
func openLock(deadends []string, target string) int {
    const maxStates = 10000
    var visited [maxStates]bool

    // 1. Помечаем запрещенные тупиковые комбинации как уже посещенные
    for _, d := range deadends {
        visited[parseState(d)] = true
    }

    targetState := parseState(target)

    // Если начальная точка заблокирована тупиком
    if visited[0] {
        return -1
    }
    // Если цель уже достигнута на старте
    if targetState == 0 {
        return 0
    }

    // 2. Очередь на непрерывном целочисленном срезе
    queue := make([]int, 0, 1024)
    queue = append(queue, 0)
    visited[0] = true
    head := 0
    steps := 0

    // Степени 10 для быстрого извлечения цифр: 1, 10, 100, 1000
    pow10 := [4]int{1, 10, 100, 1000}

    for head < len(queue) {
        levelSize := len(queue) - head

        for i := 0; i < levelSize; i++ {
            curr := queue[head]
            head++

            // Проверяем 4 колесика
            for pos := 0; pos < 4; pos++ {
                p := pow10[pos]
                digit := (curr / p) % 10
                base := curr - digit*p // Обнуляем текущую позицию

                // Поворот вперед: +1
                upState := base + ((digit+1)%10)*p
                if !visited[upState] {
                    if upState == targetState {
                        return steps + 1
                    }
                    visited[upState] = true
                    queue = append(queue, upState)
                }

                // Поворот назад: -1 эквивалентно +9 (по модулю 10)
                downState := base + ((digit+9)%10)*p
                if !visited[downState] {
                    if downState == targetState {
                        return steps + 1
                    }
                    visited[downState] = true
                    queue = append(queue, downState)
                }
            }
        }

        steps++
    }

    return -1
}

// parseState быстро преобразует 4-значную строку в целое число без strconv.
func parseState(s string) int {
    return int(s[0]-'0')*1000 + int(s[1]-'0')*100 + int(s[2]-'0')*10 + int(s[3]-'0')
}

4. Визуализация генерации состояний

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    Start["Состояние: 0000 (число 0)"]:::entry --> GenNeighbours["Генерация 8 переходов"]:::process

    GenNeighbours --> D1["Колесо 1: 1000 и 9000"]:::process
    GenNeighbours --> D2["Колесо 2: 0100 и 0900"]:::process
    GenNeighbours --> D3["Колесо 3: 0010 и 0090"]:::process
    GenNeighbours --> D4["Колесо 4: 0001 и 0009"]:::process

    D1 & D2 & D3 & D4 --> CheckVisited{"visited[state] == false?"}:::warning

    CheckVisited -- "Да, не посещено" --> CheckTarget{"state == target?"}:::warning
    CheckTarget -- "Да: Цель достигнута!" --> Found["return steps + 1"]:::success
    CheckTarget -- "Нет" --> Enqueue["visited[state] = true<br>queue.append(state)"]:::accent
    CheckVisited -- "Нет (тупик или посещено)" --> Skip["Игнорировать переход"]:::error
  

5. Сравнение производительности: Строки против Целых чисел

Резюме для интервью

• Компактные пространства состояний: Если мощность множества состояний не превышает сотен тысяч, всегда проецируйте их на плоские целочисленные массивы.
• Трюк модульной арифметики: Выражение (digit + 9) % 10 элегантно реализует декремент с циклическим переходом 0 -> 9 без использования условных операторов if.
• Ранняя проверка цели: Проверка if nextState == targetState прямо в момент генерации соседа экономит целый слой обхода очереди.

В следующей задаче — 8. Shortest Path in Binary Matrix — мы перейдём к поиску пути на двумерной сетке, где разрешены диагональные перемещения (ход короля).