Публикация Школы траблшутеров

Вариации алгоритма взлома кодового замка

Время чтения: 6 мин
15 февраля 2024 г. Просмотров: 313

Алгоритмы, Траблшутинг | Олег Брагинский, Владислав Иванов

Хорошие головоломки будоражат сложностью, не поддаваясь с первой попытки. Классическими считаются загадки, объединяющие пять условий. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов покажут, как справляться с логическими лабиринтами.

Алгоритмы изменили компьютерные науки: упростили математические операции, прокачали связи между элементами микросхем, дали второе дыхание операционным системам. Некоторые стали основой современных архиваторов, иные лежат в нутре навигаторов и приложений для курьеров.

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

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

  1. 682 – одна цифра верная и находится на своём месте
  2. 614 – одна цифра верная, но находится не на своём месте
  3. 206 – две цифры верные, но находятся не на своих местах
  4. 738 – все цифры в данной тройке неверны
  5. 380 – одна цифра верная, но находится не на своём месте.

Представляем в уме или рисуем на бумаге вектор из десяти цифр:

Обращаем внимание на четвёртое условие и убираем из расчётов «7», «3», «8», как ошибочные. Замечаем отсутствие в подсказках цифр «5» и «9». Вычёркиваем и их. Остаётся суженный набор:

Замечаем: в такой конфигурации пятое условие играет новыми красками – «0» подходит, но надо пододвинуть. Видим, что в третьей подсказке «0» уже стоит на второй позиции. И это ошибка. Следовательно: «0» размещаем в первую ячейку. Возвращаемся к первому и третьему правилам.

В одном случае верная цифра и на своём месте, во втором – две цифры подходят, но не местами. «6» не подходит, поскольку уже определили «0» на первое место, а значит, не о ней намекает первая подсказка. Остаётся «2», которая размещается на третьей позиции. Промежуточный итог:

Остаётся выбрать среднюю цифру между «1» и «4». Единицу использовать не можем – поставив на позицию №2, получим противоречие со второй подсказкой. А вот коллега коллизии не вызывает и даже подтверждает условие. Вводим заветную комбинацию и открываем кодовый замок:

Придадим формальности решению:

  1. Раздадим условиям веса

Построим таблицы для оценивания подсказок. За совпадения будем начислять один положительный балл, за ошибку вычитать единицу. Порядок расположения значения не имеет.

Условие 1. 682 – одна верная цифра на нужном месте:

Распространим подобное на другие условия.

Условие 2. 614 – одна верная цифра не на том месте:

Условие 3. 206 – две верных цифры, не на своих местах:

Условие 4. 738 – все цифры неверны:

Условие 5. 780 – одна верная цифра не на своём месте:

  1. Расставим подсказки по полезности

Сведём полученные суммы баллов для правил в единую таблицу, отсортировав места по возрастанию весов:

Далее будем опираться на полученную последовательность.

  1. Определим алфавит

Зададим альтернативы, которые сможем использовать.

Начальный вектор содержит все возможные цифры:

  1. Пройдём сквозь

Нулевым ходом уберём из алфавита «5» и «9 «как непоявляющиеся значения. Используем правила в соответствии с расположением в иерархии. Первым действием вычеркнем цифры «3», «7» и «8»:

Обратим внимание: есть связанные правила. После применения первого, третье (780) приобретает иной смысл – «0» становится очевидным выбором цифры, а пятое усиливается, говоря: «0» отлично подходит, но не на третью и вторую позиции. Получается, вновь первая позиция за ним:

Вторым действием посмотрим на подсказку 614 – одна верная цифра, не на своём месте. На данном этапе правило подходит для всех цифр. Делаем третий ход. Правила 682 и 206.

Согласно первому, у нас есть нужная цифра на своём месте. Согласно второму, две цифры не на своих местах. Зная о «0» и «8», выбор остаётся между «2» и «6». Предположим, «2» – верный выбор, тогда возникает ли противоречие между подсказками? Нет. Ставим «2» на позицию три:

Четвёртый ход. Возвращаемся к правилу 614. Нам требуется цифра в середину, и знаем: одна цифра верна, но стоит не там. Отбрасываем «1», так как серединная позиция не удовлетворяет подсказке. Выбираем между 062 и 042. Пройдём вновь через все правила.

738 и 780 не влияет на них. 682 говорит не в пользу «6», добавляем +1 балл к цифре «4». Последнее правило 206 сказало: прячу «0» и «2», о цифре «6» речь не идёт. Прибавим ещё +1 балл к «4». Теперь её вес (2) оказывается больше веса «6» (0), поэтому в финал убедительно проходит «4».

  1. Проверяем решение

Заполняем поле ввода кода и замок гостеприимно распахивает дужку перед нашей пытливостью ловкостью: