задачки про взлом замков

[jayrandom]

Читаю тут про последовательность де Брайна и с каждой строчкой всё отчётливее и отчётливее соображаю, что я это уже изобретал :)

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

Меня интересовал двоичный вариант, и как-то уж так получалось, что последовательность была длины 2^n (если последовательность циклическая, и с хвостиком - если нет). Просто получалось, и всё - поэтому я как-то про себя решил, что это очевидно. А если алфавит не двоичный? "Задумайся, читатель, и тебе станет не по себе" (c).


Кстати, а вот "родственная" задача: дан велосипедный (мне тут подсказывают: "чемоданный" - objection, чемоданный открывают фомкой) замок с 4 крутящимися колёсиками, на которых цифры 0-9. Автосдвига у него, понятное дело, нет. Как его быстрее всего перебрать?

Comments

[faceted-jacinth.livejournal.com]

Я тоже изобретал =)
Когда в Дюк Нюкема играл, там было несколько мест, где есть три или четыре кнопки и дверь или мост, которые открываются на специфическую комбинацию нажатых/ненажатых. Ну и как-то довольно быстро я придумал последовательность нажатий 121 3 121 4 121 3 121, которая проходит все состояния для четырёх кнопок. Почти то же самое, по-моему.

А задачка с велосипедным замком не очень интересная. Если считать за базовую операцию "сдвинуть одно из колёсиков (на любое значение)", то тупой перебор даёт 9 + 99 + 999 дополнительных сдвигов (из 9999) (когда ты за один шаг алгоритма двигаешь больше одного колёсика), а за такую маленькую величину (десять процентов) как-то беспонта бороться. Хотя подумаю ещё, даже интересно как-то.

[jayrandom.livejournal.com]

Комбинация нажатых-ненажатых в Дюке - эта задача скорее похожа на велозамок с бинарными колёсами. И ответ это подтверждает.

То, что я имел в виду - это именно циклическая последовательность. Когда вводится новая цифра, она встаёт в конец числа и "выталкивает" первую из кода. Тут решение другое.

В велозамке за базовую операцию нужно считать "сдвинуть одно колесо по часовой стрелке". Тогда экономическая ценность задачи возрастает :)

[faceted-jacinth.livejournal.com]

Дада, сейчас перечитал и понял, что тупил тогда нипадецки. Конечно, это одинаковые задачи, ответ получается либо рекуррентно (объединяя списки), либо непосредственно: запускаем счётчик в той же системе счисления и двигаем колёсико, соответствующее максимальному изменившемуся разряду счётчика. Наверное, несложно доказать, что так мы переберём всё. Это, в общем, практически очевидно =) Кстати, я даже подозреваю, что оно работает и в системах счисления с переменной базой.

[jayrandom.livejournal.com]

"Дюкозамок" и велозамок - одинаковые задачи.

А "замок с регистром сдвига" - совсем другая задача. Там думать надо :)