Код Давинчи

[Утундрий]

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

[svv]

Утундрий, погодите... мне вдруг показалось, что от состояния 12345678901234567890... (и многих других, конечно) можно перейти к нулевому только за $n$ ходов (ну, чуть меньше, учитывая, что некоторые колеса уже нули; это фигня).

[Утундрий]

Нельзя ли по-конкретнее? Если найдётся хоть одно состояние, которое не перевести в заказанное менее чем за $n$ ходов, то это уже результат. Впрочем, сильно зависящий от соотношения количества символов и количества колёс.

[_Ivana]

svv, напишите исходное состояние без нулей, длиннее 9 цифр, и я перейду меньше, чем за $n$ ходов, оставаясь в рамках условий задачи.

[svv]

Так я сильно не настаиваю.

[_Ivana]

Алгоритм навскидку (не факт, что минимизирующий число вращений):
1) рассматриваем массив цифр, ищем каких больше всего, допустим, их $k$. Вычитаем из $n$ $k-1$ - получаем нужное число вращений.
2) рассматриваем отдельно каждый интервал между позициями тех цифр, количество которых максимально - по логике пункта 1. До тех пор, пока в интервалах не останется максимум по одной цифре каждого вида.
ЗЫ если у нас получилось на определенном шаге равное количество разных цифр - пробежать оба варианта до самого конца (как граф) и из всех веток выбрать с минимумом вращений.

[frankenstein]

Что-то подсказывает, что это задача динамического программирования.

[_Ivana]

Мой алгоритм не дает минимальное количество вращений - например, на последовательности $23332$ он даст $3$ вращения (крайние двойки до троек и хором все тройки до нулей), а минимум - $2$ (тройки до двоек и двойки до нулей). Но если искать не максимум, а просто перебирать все варианты, тогда конечно будет достигнут минимум. Правда, по первому впечетлению, это будет не быстро и не оптимально.

[Утундрий]

_Ivana в сообщении #826857 писал(а):

на последовательности 23332 он даст 3 вращения

На практике их и будет три.

_Ivana в сообщении #826857 писал(а):

тройки до двоек и двойки до нулей

Для осуществления этого движения надо мутантом быть...

[_Ivana]

Не знаю насчет мутантом, а условию задачи эти два движения вполне удовлетворяют. Так что на практике при таких исходных данных их и будет два.

[svv]

Мутанты — это хорошо. Собственно, мы здесь все мутанты.

[Утундрий]

Погодите, а он "переламывается" или по нему просто пояски крутятся?

[sup]

Любопытная задача. Можно свести к динамическому программированию. Получится полиномиальный алгоритм. Степень, правда, не очень ...
Прежде всего, отметим, что все эти повороты коммутируют, посему можно сначала провести все повороты, в которых самым левым будет 1 колесо. Потом второе и т.д. Далее, замечаем, что если у двух "вложенных" поворотов общее граничное колесо, то их можно заменить на два "непересекающихся" по колесам поворота . Например, два поворота колес 1-2-3-4-5 и 3-4-5 можно заменить на 1-2 и 3-4-5. Отсюда вытекает, что каждое конкретное колесо может быть граничным не более двух раз, причем если два раза - то один раз левым и один раз правым. Отсюда вытекает, что определяющим является набор не столько чисел в начальной расстановке, сколько разностей между соседними колесами (по модулю 10 или чего-там-надо). Ну и, наконец, надо заметить, что порядок в этих разностях несущественный. Важна лишь "брутто-формула": сколько разностей равны 1, сколько 2 и т.д. А это прямая дорога к ДП.
Пример. Пусть исходная позиция на колесах 25341. Надо привести ее к 00000. Для определенности будем брать разности с левым колесом. Тогда добавляем фиктивное "самое левое колесо" с 0. Получим 025341. После этого последовательность разностей получится 2 3 -2 1 -3
Между прочим, отсюда видно, что потребуется 3 поворота. Каждый поворот одну разность увеличивает, а другую уменьшает на одно и то же число. Поэтому выгодно искать пары разностей отличающихся знаком. Таких тут 2. Итак сначала крутим первые два колеса. Получим 03341. Потом крутим колеса 2-3-4. Получим 00011. Ну и наконец последние пару колес.
Проверим, что ничего не изменится, если разности переставить как угодно. Например
1 -3 - 2 2 3. Это соответствует начальной позиции 1 8 6 8 1. Тут уж ясно что делать. И тоже 3 поворота.