Код Давинчи

[frankenstein]

Привет! Задача такая:
У вас есть устройство чтото вроде этого:

но вместо латинских букв там находятся цифры 0-9.
За один ход можно:
Повернуть непрерывных сегмент колес в одном направлении, вверх или вниз.
Это что у вас есть.

Входные данные:
Вам дано текущее состояние устройства, вектор цифр.
И еще один вектор цифр - то состояние которые вы должны получить минимальным количеством ходов.

На выходе вы должны дать число, минимальное количество ходов.

[Утундрий]

frankenstein в сообщении #822698 писал(а):

За один ход можно:
Повернуть непрерывных сегмент колес в одном направлении, вверх или вниз.
Это что у вас есть.

Как это будет сказать по-русски?

[svv]

Непрерывных сегмент колес — это подмножество $S$ множества всех колес устройства, такое, что если колеса $a$ и $b$ принадлежат $S$, а колесо $c$ расположено между $a$ и $b$, то и $c$ принадлежит $S$.

-- Чт фев 13, 2014 00:47:08 --

Да, и таких сегмент колес за один ход не просто поворачивается в одном направлении, а еще и все его колеса поворачиваются на равное количество щелчков.

[arseniiv]

Добавлю очевидное: если все цифры написаны на колёсах в одном и том же порядке, как буквы на картинке, то задача свести $a_i$ к $b_i$ сводится к задаче сведения $a_i-b_i$ к $0$. Таким образом, кстати, ещё и количество колёс во входе присутствует только один раз.

[svv]

Точно! Приятное упрощение.

[arseniiv]

Следующий естественный шаг — хотя не знаю, насколько полезный для ответа — рассмотреть группу преобразований этой солонки. У неё $n$ колёс и $n-1$ делений на непрерывных сегмент колёс и два способа — вращать левый или вращать правый. Получаем базовые вращения $1_L,\ldots,(n-1)_L,1_R,\ldots,(n-1)_R$ на одну цифру, скажем, вверх, и остальные базовые вращения как их степени. Может, разложение на вращения отдельных колёс $\hat1,\ldots,\hat n$ что-то дадут?

Стоит заметить, что все эти элементы коммутируют из-за особенностей этого разложения и вращений отдельных колёс.

[svv]

Я тоже добавлю очевидное. В формулировке arseniiv (а, следовательно, и в оригинальной) для $n$ колёс достаточно $n$ ходов. Поворачиваем первое колесо, пока оно не совпадет со вторым. Дальше вращаем первые два колеса, пока не совпадут с третьим. На последнем шаге крутим все колёса вместе, устанавливая нули.

Но если кто-то хочет $o(n)$...

[Утундрий]

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

[svv]

... и не перемежаемых (или -ющихся?) не поворачивающимися вместе с ними.

[Утундрий]

Вообще-то, поскольку устройство так и просится в лапы (выгодно отличаясь тем от своеобычных в олимпиадном разделе хроносинкластических семнадцатимерных летающих пингвинов), то возникает сильное желание ограничить допустимые движения до проворота левой и правой части относительно одной плоскости. Плоскость, понятно, можно выбирать произвольно.

[svv]

(Оффтоп)

В Гугле (или другом поисковике) в разделе Картинки наберите Cryptex. Так эта штука называется. Увидите много вкусных картинок.

[Утундрий]

(Оффтоп)

А, так это что-то известное! Нет, смотреть не буду. Меньше сил потрачу на забывание.

[frankenstein]

arseniiv в сообщении #825869 писал(а):

Добавлю очевидное: если все цифры написаны на колёсах в одном и том же порядке, как буквы на картинке, то задача свести $a_i$ к $b_i$ сводится к задаче сведения $a_i-b_i$ к $0$. Таким образом, кстати, ещё и количество колёс во входе присутствует только один раз.

Да, упрощение очевидное. Но что делать после того как вы вычислили $a_i-b_i$. Будут ли гарантировать все описанные методы что, полученное решение будет минимальным из множества всех решений.

[arseniiv]

Вообще-то, был описан один метод:

svv в сообщении #825890 писал(а):

Поворачиваем первое колесо, пока оно не совпадет со вторым. Дальше вращаем первые два колеса, пока не совпадут с третьим. На последнем шаге крутим все колёса вместе, устанавливая нули.

и он не гарантирует минимальность числа ходов, что тоже написано.

[svv]

Ну, а второй очевидный метод — это просто отдельное вращение по одному всех $n$ колес.