Spiiin's blog

Запись из архива.

Играл в James Bond Jr. на NES :

В этой игрушке в первой зоне сын известного спецагента Джеймса Бонда должен деактивировать 5 ракет главзлодея. Чтобы “выключить” ракету, необходимо решить головоломку - заданы исходное поле из разноцветных клеток и целевая позиция, в которую надо перевести поле, сдвигая любую строку или столбец.

В принципе, задача решается не очень сложно, но мне захотелось поупражняться в программировании, и поэтому, под катом, скрипт - помощник суперагента :)

Код

В коде использован алгоритм поиска в ширину.

Работает так :

• Задача представляется в виде графа, в котором вершины - состояния поля, а ребра - допустимые переходы от одного состояния к другому (в коде допустимые фукнции переходов хранятся в массиве fun ) .
• Имеются 2 списка - open , в котором хранятся вершины, которые предстоит просмотреть и closed , в котором хранятся уже просмотренные вершины.
• Помимо собственно вершины в элементах списков open и closed также хранится вершина, из которой был совершен переход в данное состояние. Это делается для того, чтобы по окончании поиска можно было восстановить последовательность переходов (функция extract ).
• Изначально в open кладется стартовое состояние поля. Далее циклически совершается раскрытие вершины. Оно заключается в добавлении к списку открытых вершин всех вершин, в которые можно перейти из данной и перемещении раскрываемой вершины в список closed . Раскрытые вершины добавляются в конец списка open , что обеспечивает обход графа в ширину. Цикл завершается, если текущая раскрываемая вершина является целевой или если заканчиваются раскрываемые вершины (это означает, что перейти в конечное состояние из стартового невозможно).
• Когда целевая вершина найдена, необходимо пройтись по списку closed и восстановить путь от цели к исходной вершине, пользуясь указателями, которые были добавлены при раскрытии. Я для удобства сделал не только извлечение пути из списка, но и вывод ответа в форме “какую линию и в какую сторону двигать”. Для еще большего удобства можно сделать перевод в набор кнопок, которые нужно нажимать на геймпаде для получения результата :)

Описание алгоритма здесь и здесь .

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

Вторая версия тормозила про проверке, входит ли элемент в списки open или close, пришлось еще дополнительно сделать хэш-таблицу open-hash для быстрой проверки вхождения.

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

Таким образом, время решения значительно улучшается, и Джеймс Бонд должен успеет обезвредить вражеские ракеты за отведенные ему 45 минут =) Ну и да, скрипт теперь реализует не поиск в ширину, а какой-то из частных случаев А-алгоритма, у которого эвристическая функция состоит только из прогноза оставшегося пути и не учитывает пройденного расстояния, но это в данной ситуации неважно, главное, быстрее получить ответ.

---

И, собственно, решения:

====== 1 ======
source:[1, 2, 3, 4, 4, 1, 2, 3, 3, 4, 1, 2, 2, 3, 4, 1]
target:[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
[‘left’ , 1] #означает - сдвиг 1-й строки влево. отсчет строк и столбцов ведется с нуля
[‘left’ , 2]
[‘left’ , 2]
[‘right’ , 3]

====== 2 ======
source:[1,1,1,1, 1,2,3,1, 1,3,2,1, 1,1,1,1]
target:[1,1,1,1, 1,3,3,1, 1,2,2,1, 1,1,1,1]
[‘left’ , 1]
[‘up’ , 1]
[‘right’, 1]
[‘down’ , 1]

====== 3 ======
source:[1,2,1,3, 3,2,1,2, 1,1,3,1, 1,2,1,3]
target:[3,1,2,3, 2,1,1,1, 1,1,1,2, 3,2,1,3]
[‘right’, 0]
[‘right’, 2]
[‘down’ , 3]
[‘up’ , 0]
[‘left’ , 1]

====== 4 ======
source:[1,2,2,1, 3,4,4,3, 3,4,4,3, 2,4,4,2]
target:[4,3,4,2, 3,1,2,4, 4,2,4,3, 2,4,3,1]
only difs:
[‘left’ , 2]
[‘up’ , 3]
[‘right’, 1]
[‘down’ , 2]
[‘right’, 0]
[‘down’ , 1]
[‘right’, 0]
[‘left’ , 2]
[‘left’ , 2]

====== 5 ======
source:[1,1,2,2, 1,1,2,2, 3,3,4,4, 3,3,4,4]
target:[1,1,2,2, 1,3,4,2, 3,3,4,4, 1,3,4,2]
[‘left’, 1]
[‘up’ , 0]
[‘left’, 1]
[‘left’, 1]
[‘up’ , 3]
[‘left’, 1]