программистская задачка

[avva]

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

По-моему, неинтересно задавать сложные "олимпиадные" задачи, в которых нужно придумать алгоритм или необычный подход, а если не придумать, то ничего не выйдет. Нет, такие задачи тоже, конечно, заслуживают внимания, и если вам хочется таких, то IBM'овская колонка Ponder This - неплохой источник; я их одно время старался делать регулярно, но забросил потом. Мне кажется более интересным предложить что-то, что очень многие могут сделать, но вместе с тем это не совершенно тривиально, и может быть написано многими разными способами.

Поэтому вот моя задача. Напишите код, который решает игру в пятнашки. Конкретно говоря, если ему дать доску 4x4 с неправильно расставленными числами:



ваш код находит последовательность движений (их можно обозначить просто номерами костяшек, которые двигаются, например), после которых получается правильный порядок от 1 до 15. Необязательно находить самое быстрое решение, но обязательно всегда найти решение, если оно существует. Необязательно приводить к разумному порядку, если решения нет (напр. с 13 15 14 в конце), но можно и сделать это.

Мне нравится эта задача тем, что как бы понятно, что мы МОЖЕМ это сделать. Тут нет ничего невозможного. Но когда садишься писать код, начинаешь думать, как именно это организовать, и с точки зрения алгоритма, и с точки зрения организации данных/кода при уже выбранном алгоритме, есть много разных вариантов, и когда в итоге это все работает и выглядит хорошо, то приятно. Ну мне по крайней мере было приятно. Я украл эту задачу у А. Шеня, который предложил ее у себя в фейсбуке с полгода назад. Свой код я написал еще тогда, но сюда кину ссылку на него через 2 дня. Если вы хотите поучаствовать, присылайте код ссылками на https://pastebin.com/ или свой гитхаб или еще как угодно.

P.S. Кстати, если вы не помните, КАК решать игру в пятнашки, или никогда этим не занимались, то вот заодно удобный случай разобраться. Подвигать костяшки можно в куче мест на вебе или в телефоне.


P.P.S. Вот мое решение: https://pastebin.com/yYg302eU, я добавил комментарии по-русски в начале. В сравнении с другими оно очень хлопотное, но всегда быстро находит путь.

Comments

[gegmopo4.livejournal.com]

Кажется в «Науке и жизни» публиковали программу для микрокалькулятора, решающую эту задачу. 105 байт кода, 14 регистров, вот и всё.

[tlkh.livejournal.com]

Писал студентом сто лет назад, больше не хочется. Тогда сделал максимально просто - так, как собирал вручную. Сначала 1 на свое место, 2, потом 3 на место 4, чтобы можно было подогнать 4 и все встало как надо, и т.д.

Писал даже не на полноценном языке программирования, а на чем-то прологоподобном.
Чтобы восстановить, нужен дисковод на 5'' )

[fantaseour.livejournal.com]

Эта задача -- домашнее задание для 4 недели курса Алгоритмы на Курсере: https://www.coursera.org/learn/algorithms-part1

http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html
http://coursera.cs.princeton.edu/algs4/checklists/8puzzle.html

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

[rezdm.livejournal.com]

О! Мы такое на прологе писали. Только в те временя из-за нехватки памяти приъодилось ограничиваться полем 3x3

[alexanderr.livejournal.com]

а почему именно 4х4? почему бы не поиграть 5х5? или 8х8?

[technocrator.livejournal.com]

Хмм... а любопытно, какова асимптотика трудоёмкости задачи в зависимости от размеров поля? надо будет подумать


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

[roman nastenko (from livejournal.com)]

Сто лет не программировал, но интересно, можно ли решить эту задачу на основе простой оценки игрового поля?

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

Выбираем то из 2-4 возможных действий по движению, которое максимально улучшает результат.

Оно так в какой-то бессмысленный цикл впадет или решится?

P. S. А если глубину расчета с одного хода до 2-3 поднять?

[avva.livejournal.com]

Логичный порыв. Попробуйте! :)

[gul-kiev.livejournal.com]

или 3x3x3?

Анализ сложности алгоритмов.

[gaz-v-pol.livejournal.com]

Не совсем то, что Вы просите, но вдруг Вам понравится?

На плоскости отмечены две точки на расстоянии 1. Разрешается, измерив циркулем расстояние между двумя отмеченными точками, провести окружность с центром в любой отмеченной точке с измеренным радиусом. Линейкой разрешается провести прямую через любые две отмеченные точки. При этом отмечаются новые точки – точки пересечения построенных линий. Пусть Ц(n) – наименьшее число линий, проведение которых одним циркулем позволяет получить две отмеченные точки на расстоянии n (n – натуральное). ЛЦ(n) – то же, но циркулем и линейкой. Докажите, что последовательность Ц(n)/ЛЦ(n) неограничена (автор А.Я.Канель, была на Всероссийской олимпиаде школьников в 1995 году)

[gaz-v-pol.livejournal.com]

Не может ли так оказаться, что у указанной Вами функции "близость к правильному расположению" есть локальные минимумы? Т.е. из какой-либо позиции можно за несколько ходов перейти в изначальную, но для этого нужно сделать один или несколько ходов, которые временно ухудшают ситуацию?

[akimka.livejournal.com]

Ну с учетом того, что можно решить через MCTS, то не выглядит слишком сложно, или есть подводные камни?

[(Anonymous)]

Вот стохастическое решение:

https://pastebin.com/HpPUJwSR

На неразрешимость проверки нет, но если решение есть, то оно таки обязательно будет найдено. Когда-нибудь (если генератор случайных чисел хороший)...

Для поля 4x4 этого в большинстве случаев можно не дождаться, но для 3x2 и даже 3x3 работает нормально.

[alexanderr.livejournal.com]

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

[edd-l.livejournal.com]

А разве не доказано, что если поставить на место пустой клетки 0 или 16 в зависимости от того, какая окончательная позиция будет "правильной" - с пустой клеткой в начале первой строчки или с пустой клеткой в конце последней, то, по крайней мере, в 7-окрестности ходов, функция, равная числу инверсий в перестановке 16 чисел, собранных по строчкам, не будет иметь локальных минимумов? Интуитивно кажется, должно быть так, поскольку по опыту игры в детстве, пятнашки приводятся к правильной позиции постепенными улучшениями, затрагивающими только 2 строчки. В этом смысле, пятнашкам не нужен alphazero, достаточно подходящей глубины расчета позиций. И думается, что 7 не трудно заменить на 3, возможно вышеприведённую функцию чуть модифицировав.

[hyperpov.livejournal.com]

Если минимизировать напряжение собственной мысли, то приходит на ум следующее. Переберем все состояния и для каждого запомним ход, приближающий к победе. Правда, состояний многовато. Поэтому разобьем задачу на три. Первая - упорядочить верхний ряд. Для этого все клеточки от 5 до 15 заменим на * и переберем все состояния таких пятнашек. Их чуть больше полмиллиона, это фигня. Потом так же расправимся со вторым рядом (еще меньше), а на третьем этапе - с последними двумя рядами сразу (вообще пустяк, 8!). То есть один раз мы составляем словарь ходов, а потом действуем по алгоритму:
1) смотрим, как расположены 1,2,3,4,_. Если неправильно, заглядываем в словарь и делаем ход. Если правильно, аналогично смотрим на расположение 5,6,7,8,_. Если и они уже стоят на месте, смотрим на перестановку 9,...,15,_ и заглядываем в словарь, если игра еще не закончена.

Это решение требует немного памяти и времени на составление словаря, зато умственного напряжения - ноль, а решаться потом будет близко к оптимальному по числу ходов.

[anton panchenko (from livejournal.com)]

мне кажется, можно вот так сделать.
ставим на свои места сначала 1-ю, потом 2-ю и так далее пятнашку, пока на своем месте не окажутся все.
как ставим? строим дерево из этих досок с пятнашками такое, что для каждого элемента этого дерева его дочерние элементы - это доски с пятнашками с выполненным на них тем или иным ходом. когда дерево построено, выбираем наиболее короткий путь, чтобы пятнашка n оказалась на своем месте.
и так в цикле для всех 15 пятнашек.
дерево можно целиком не строить. можно, например, выпиливать с него заведомо лажовые ветви. можо вообще какой-то топ-N ветвей держать, не сильно большой.
насчет дерева - это я так шахматы делал.

[avva.livejournal.com]

Отличное решение! Написал его на Питоне сейчас, могу выслать код, если вам самому лень :)
Время составления словаря около пол-минуты, из-за перебора 500 тысяч досок на первом этапе. Но при желании его можно убыстрить до тривиальности, разбив первый этап на два: сначала 1,2, потом 3,4.

Стандартные методы

[son-0f-morning.livejournal.com]

Как я понимаю "стандартные методы" (наверняка есть "механистическое" решение 15к, по аналогии с механистическим решением для кубика-рубика) не принимаются?

Интересует именно самостоятельный велосипед?


ПС
У кубика-рубика для стандартного решения просто поочерёдно ставятся на место: верхние рёбра - верхние углы - боковые рёбра - боковые углы (дальше забыл рёбра или углы сначала ставятся для нижней грани).

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

Re: Стандартные методы

[avva.livejournal.com]

Принимается любое решение. У стандартного решения по этапам есть свои пусть не трудности, но интересные моменты.

[ilyakor.livejournal.com]

> По-моему, неинтересно задавать сложные "олимпиадные" задачи, в которых нужно придумать алгоритм или необычный подход, а если не придумать, то ничего не выйдет.

Задача вполне себе олимпиадная, при этом из категории относительно сложных (нужно немало написать технически, и нужны какие-то идеи, чтобы оно быстро работало).

Вот моя версия: https://pastebin.com/4dfizExz

(A* с двух сторон, выводим ответ как только два A* встречаются)

Работает довольно быстро, правда, на сложных тестах "быстро" - порядка 20 секунд. Вот кстати пример нетривиального теста, а то пример в посте - слишком простой:

15 14 13 12
10 11 8 9
2 6 5 1
3 4 7 -1

[occuserpens.livejournal.com]

Все-таки Питон - удивительно прожорливая тварюга :)
https://github.com/MilanPecov/15-Puzzle-Solvers

RE: Анализ сложности алгоритмов.

[(Anonymous)]

Забавно. Я правильно понимаю, что с одной стороны там log n, а с другой log log n?

[(Anonymous)]

Mathematica: https://pastebin.com/gFkYri1U
(текст исходного кода лучше скопировать во фронтенд, так он будет легче читаться).

Я реализовал два алгоритма: относительно быстрый (Solution1) и медленный (Solution2).
Solution2 работает примерно как выше предлагали в комментах (ищет кратчайший способ поместить несколько фишек на свои места; костяшки из двух крайних вертикальных и крайних горизонтальных рядов расставляются парами, но остальные — по одной друг за другом).
Solution1 делает то же, но при поиске кратчайшего способа пользуется геометрией игрового поля, а не рассматривает множество состояний как произвольный граф. Чтобы переместить костяшку на нужное место, для неё ищется кратчайший путь, и дальше она двигается по этому пути клетка за клеткой (чтобы передвинуть её на одну клетку, нужно сначала поставить в эту клетку дыру, для этого используется встроенная функция поиска кратчайшего пути в произвольном графе).

Оба алгоритма переводят произвольную начальную доску в произвольную конечную (т.е. не обязательно приводить доску к стандартному виду), размеры доски произвольны. Если решения нет, выводится ближайшее к нему (с отличием в одну транспозицию).

Для запуска функции Demo на вход передаются две матрицы значений (0 значит пустую клетку) и название функции, имплементирующей решающий алгоритм. Левая кнопка мыши — показать доску на следующем ходе, правая — на предыдущем.

[hyperpov.livejournal.com]

Да, на блоки процесс можно разбивать по-разному, я взял самый топорный способ.

Это на самом деле перепев гораздо более содержательного алгоритма сборки кубика Рубика, который я видел в журнале "Квант" когда-то давным-давно. Множество состояний кубика - это группа. Назовем ее G. В ней, с помощью запрещения некоторых ходов, выделяются три подгруппы A<B<C<G (< означает включение) так, что каждое из фактор-множеств B/A, C/B, G/C, а также группа A, уже обозримы и перебираются на компьютере. Алгоритм состоит из четырех этапов: на первом нужно попасть в C и дальше использовать только ходы, не выводящие из C, потом так же в B, в A и в 1. Вот этот момент, что для выполнения каждого этапа сначала делается тупой перебор и составляется словарь, я тогда не понял и остался ужасно недовлетворен тем, что я не вижу, как использовать этот алгоритм на практике. Суть подхода в том, что он дает хорошую верхнюю оценку на число ходов из любого начального положения. Если правильно помню, всего 23. Но человек им пользоваться, как я понимаю, без машины не может. На ваш код для решения пятнашек я бы взглянул чисто из любопытства, чтобы сравнить детали реализации с тем, как я сам стал бы делать, если бы вдруг понадобилось. Скажем, используете tuple, hex или int для ключей словаря?

[avva.livejournal.com]

>Скажем, используете tuple, hex или int для ключей словаря?

Строки :)

https://pastebin.com/6FfY9jdA

Re: Анализ сложности алгоритмов.

[gaz-v-pol.livejournal.com]

В решении, которое было предъявлено на разборе олимпиады, было доказано, что Ц(2^(2^n)) > 2^n и ЛЦ(2^(2^n)) < 5(n+1).

Это доказательство можно посмотреть в книге "Всероссийские олимпиады школьников по математике 1993-2006." Агаханов Н.Х. и др.
Задача 491 на странице 304

http://www.alleng.ru/d/math/math127.htm

Насколько эти оценки точны? Я не знал тогда, и не знаю сейчас.

Re: Анализ сложности алгоритмов.

[(Anonymous)]

Да, я точно так же рассуждал, как в этом решении. Очевидно, оценка Ц верна с точностью до постоянного множителя, т.к. можно удвоить расстояние, проведя ровно 4 окружности. Про ЛЦ надо подумать, но пока не видно, как ее улучшить.

[hyperpov.livejournal.com]

Спасибо, оказалось и правда познавательно. В паре мест я бы сделал топорнее.

Из улучшаемого: перед 78 просится

print move

а то решить-то решили, но как - никому не сказали.

Еще тело solve() я бы запихнул внутрь try: ... except KeyError: print 'обратитесь в сервисный центр'.

[avva.livejournal.com]

Спасибо, я с большим интересом это поизучаю на днях, потому что как раз установил себе на ноутбук Математику и хочу поиграть с ней. Ваш solution1 звучит как то, что я сделал на питоне (см. ссылку в записи).