?

Log in

No account? Create an account
программистская задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

программистская задачка [мар. 27, 2018|08:16 pm]
Anatoly Vorobey
[Tags|, ]

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

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

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



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

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

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


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

Comments:
[User Picture]From: gegmopo4
2018-03-27 05:40 pm
Кажется в «Науке и жизни» публиковали программу для микрокалькулятора, решающую эту задачу. 105 байт кода, 14 регистров, вот и всё.
(Ответить) (Thread)
[User Picture]From: tlkh
2018-03-27 05:52 pm
Писал студентом сто лет назад, больше не хочется. Тогда сделал максимально просто - так, как собирал вручную. Сначала 1 на свое место, 2, потом 3 на место 4, чтобы можно было подогнать 4 и все встало как надо, и т.д.

Писал даже не на полноценном языке программирования, а на чем-то прологоподобном.
Чтобы восстановить, нужен дисковод на 5'' )
(Ответить) (Thread)
[User Picture]From: fantaseour
2018-03-27 06:03 pm
Эта задача -- домашнее задание для 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

В чеклисте много оптимизаций и ссылки на статьи. Задачка глубокая и интересная, хоть и кажется простой
(Ответить) (Thread)
[User Picture]From: rezdm
2018-03-27 06:09 pm
О! Мы такое на прологе писали. Только в те временя из-за нехватки памяти приъодилось ограничиваться полем 3x3
(Ответить) (Thread)
[User Picture]From: alexanderr
2018-03-27 06:28 pm
а почему именно 4х4? почему бы не поиграть 5х5? или 8х8?
(Ответить) (Thread)
[User Picture]From: gul_kiev
2018-03-27 09:02 pm
или 3x3x3?
(Ответить) (Parent) (Thread) (Развернуть)
From: technocrator
2018-03-27 06:50 pm
Хмм... а любопытно, какова асимптотика трудоёмкости задачи в зависимости от размеров поля? надо будет подумать


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

(Ответить) (Thread)
[User Picture]From: gaz_v_pol
2018-03-27 10:45 pm

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

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

На плоскости отмечены две точки на расстоянии 1. Разрешается, измерив циркулем расстояние между двумя отмеченными точками, провести окружность с центром в любой отмеченной точке с измеренным радиусом. Линейкой разрешается провести прямую через любые две отмеченные точки. При этом отмечаются новые точки – точки пересечения построенных линий. Пусть Ц(n) – наименьшее число линий, проведение которых одним циркулем позволяет получить две отмеченные точки на расстоянии n (n – натуральное). ЛЦ(n) – то же, но циркулем и линейкой. Докажите, что последовательность Ц(n)/ЛЦ(n) неограничена (автор А.Я.Канель, была на Всероссийской олимпиаде школьников в 1995 году)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: Roman Nastenko
2018-03-27 08:47 pm
Сто лет не программировал, но интересно, можно ли решить эту задачу на основе простой оценки игрового поля?

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

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

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

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

Edited at 2018-03-27 20:51 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2018-03-27 09:01 pm
Логичный порыв. Попробуйте! :)
(Ответить) (Parent) (Thread)
[User Picture]From: akimka
2018-03-27 11:54 pm
Ну с учетом того, что можно решить через MCTS, то не выглядит слишком сложно, или есть подводные камни?
(Ответить) (Thread)
From: (Anonymous)
2018-03-28 01:12 am
Вот стохастическое решение:

https://pastebin.com/HpPUJwSR

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

Для поля 4x4 этого в большинстве случаев можно не дождаться, но для 3x2 и даже 3x3 работает нормально.
(Ответить) (Thread)
[User Picture]From: hyperpov
2018-03-28 06:16 am
Если минимизировать напряжение собственной мысли, то приходит на ум следующее. Переберем все состояния и для каждого запомним ход, приближающий к победе. Правда, состояний многовато. Поэтому разобьем задачу на три. Первая - упорядочить верхний ряд. Для этого все клеточки от 5 до 15 заменим на * и переберем все состояния таких пятнашек. Их чуть больше полмиллиона, это фигня. Потом так же расправимся со вторым рядом (еще меньше), а на третьем этапе - с последними двумя рядами сразу (вообще пустяк, 8!). То есть один раз мы составляем словарь ходов, а потом действуем по алгоритму:
1) смотрим, как расположены 1,2,3,4,_. Если неправильно, заглядываем в словарь и делаем ход. Если правильно, аналогично смотрим на расположение 5,6,7,8,_. Если и они уже стоят на месте, смотрим на перестановку 9,...,15,_ и заглядываем в словарь, если игра еще не закончена.

Это решение требует немного памяти и времени на составление словаря, зато умственного напряжения - ноль, а решаться потом будет близко к оптимальному по числу ходов.
(Ответить) (Thread)
[User Picture]From: avva
2018-03-28 10:32 am
Отличное решение! Написал его на Питоне сейчас, могу выслать код, если вам самому лень :)
Время составления словаря около пол-минуты, из-за перебора 500 тысяч досок на первом этапе. Но при желании его можно убыстрить до тривиальности, разбив первый этап на два: сначала 1,2, потом 3,4.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: Anton Panchenko
2018-03-28 10:01 am
мне кажется, можно вот так сделать.
ставим на свои места сначала 1-ю, потом 2-ю и так далее пятнашку, пока на своем месте не окажутся все.
как ставим? строим дерево из этих досок с пятнашками такое, что для каждого элемента этого дерева его дочерние элементы - это доски с пятнашками с выполненным на них тем или иным ходом. когда дерево построено, выбираем наиболее короткий путь, чтобы пятнашка n оказалась на своем месте.
и так в цикле для всех 15 пятнашек.
дерево можно целиком не строить. можно, например, выпиливать с него заведомо лажовые ветви. можо вообще какой-то топ-N ветвей держать, не сильно большой.
насчет дерева - это я так шахматы делал.
(Ответить) (Thread)
[User Picture]From: son_0f_morning
2018-03-28 12:02 pm

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

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

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


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

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

Edited at 2018-03-28 12:04 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2018-03-28 12:19 pm

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

Принимается любое решение. У стандартного решения по этапам есть свои пусть не трудности, но интересные моменты.
(Ответить) (Parent) (Thread)
From: ilyakor
2018-03-28 01:35 pm
> По-моему, неинтересно задавать сложные "олимпиадные" задачи, в которых нужно придумать алгоритм или необычный подход, а если не придумать, то ничего не выйдет.

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

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

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

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

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

Edited at 2018-03-28 13:36 (UTC)
(Ответить) (Thread)
[User Picture]From: occuserpens
2018-03-29 01:49 am
Все-таки Питон - удивительно прожорливая тварюга :)
https://github.com/MilanPecov/15-Puzzle-Solvers


Edited at 2018-03-29 01:51 (UTC)
(Ответить) (Thread)
From: (Anonymous)
2018-03-29 06:58 am
Mathematica: https://pastebin.com/gFkYri1U
(текст исходного кода лучше скопировать во фронтенд, так он будет легче читаться).

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

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

Для запуска функции Demo на вход передаются две матрицы значений (0 значит пустую клетку) и название функции, имплементирующей решающий алгоритм. Левая кнопка мыши — показать доску на следующем ходе, правая — на предыдущем.
(Ответить) (Thread)
[User Picture]From: avva
2018-03-30 10:13 am
Спасибо, я с большим интересом это поизучаю на днях, потому что как раз установил себе на ноутбук Математику и хочу поиграть с ней. Ваш solution1 звучит как то, что я сделал на питоне (см. ссылку в записи).
(Ответить) (Parent) (Thread)