artemgapchenko Mar 17 2012 at 17:13

Решение задачи о миссионерах и каннибалах на языке Haskell

4 min

6.5K

Haskell*Algorithms*

From sandbox

+17

Comments 18

UFO landed and left these words here

artemgapchenko Mar 18 2012 at 11:25

Можно конечно, отчего б не написать.:)
Вот и решение.

import RCFramework
prn_M3C3 = (take 6 . cycle) [Actor "Missionaire" 1 True, Actor "Cannibal" 1 True]
rst_M3C3 side = not $ or [3 == f "Cannibal" side && 2 == f "Missionaire" side,
						  3 == f "Cannibal" side && 1 == f "Missionaire" side,
						  2 == f "Cannibal" side && 1 == f "Missionaire" side]
  where
    f nm = (length . filter (\actor -> name actor == nm))
tsk_M3C3 = Crossing
				2
				prn_M3C3
				rst_M3C3
				(Here prn_M3C3 [])
				(There [] prn_M3C3)
main = do
	mapM_ print $ solve tsk_M3C3 []

kastigar Mar 18 2012 at 11:29

И как результаты? Как по времени?

artemgapchenko Mar 18 2012 at 11:41

Все четыре решения находит за 1.2 секунды. Как запустить функцию solve так, чтобы она вернула результат после нахождения первого же решения, я пока не сообразил — монады для меня дремучий лес.:) Но результат получится явно быстрее, чем мое решение, не основанное на этом фреймворке.

UFO landed and left these words here

artemgapchenko Mar 18 2012 at 22:47

Давайте. :)

afiskon Mar 19 2012 at 13:16

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

Эту проверку точно нельзя было сделать проще?

(число_миссионеров >= число_каннибалов) && ((3 — число_миссионеров) >= (3 — число_каннибалов))

Как-то так.

artemgapchenko Mar 19 2012 at 18:12

Пример: на левом берегу три миссионера и ноль каннибалов.
Ваш вариант проверки дает (3 >= 0) && (0 >= 3) == False. Получается, что состояние небезопасно, хотя это не так.

B08AH Mar 19 2012 at 16:34

не совсем понятно почему так медленно, целая секунда.
хаскель это интерпретируемый язык?

на с# тож самое сделал ради интереса — время в нулях, в пределах погрешности.
решения в виде дерева получились, так показалось легче делать. точнее обратного дерева(или как это называется, когда только у детей ссылка на родителя, а не наоборот)
и в любом случае, в каждом узле этого дерева оказывается хэшсет со всеми состояниями до этого момента,
считай тот же набор списков, только не в списке списков, а раскиданные по дереву
<habracut text =">
time 00:00:00.0080000
Solution 1:
Bank: L C:3 M:3 Transfer:
Bank: R C:2 M:0 Transfer: CC
Bank: L C:2 M:3 Transfer: C
Bank: R C:3 M:0 Transfer: CC
Bank: L C:1 M:3 Transfer: C
Bank: R C:2 M:2 Transfer: MM
Bank: L C:2 M:2 Transfer: MC
Bank: R C:1 M:3 Transfer: MM
Bank: L C:3 M:0 Transfer: C
Bank: R C:2 M:3 Transfer: CC
Bank: L C:2 M:0 Transfer: C
Bank: R C:3 M:3 Transfer: CC
Solution 2:
Bank: L C:3 M:3 Transfer:
Bank: R C:2 M:0 Transfer: CC
Bank: L C:2 M:3 Transfer: C
Bank: R C:3 M:0 Transfer: CC
Bank: L C:1 M:3 Transfer: C
Bank: R C:2 M:2 Transfer: MM
Bank: L C:2 M:2 Transfer: MC
Bank: R C:1 M:3 Transfer: MM
Bank: L C:3 M:0 Transfer: C
Bank: R C:2 M:3 Transfer: CC
Bank: L C:1 M:1 Transfer: M
Bank: R C:3 M:3 Transfer: MC
Solution 3:
Bank: L C:3 M:3 Transfer:
Bank: R C:1 M:1 Transfer: MC
Bank: L C:2 M:3 Transfer: M
Bank: R C:3 M:0 Transfer: CC
Bank: L C:1 M:3 Transfer: C
Bank: R C:2 M:2 Transfer: MM
Bank: L C:2 M:2 Transfer: MC
Bank: R C:1 M:3 Transfer: MM
Bank: L C:3 M:0 Transfer: C
Bank: R C:2 M:3 Transfer: CC
Bank: L C:2 M:0 Transfer: C
Bank: R C:3 M:3 Transfer: CC
Solution 4:
Bank: L C:3 M:3 Transfer:
Bank: R C:1 M:1 Transfer: MC
Bank: L C:2 M:3 Transfer: M
Bank: R C:3 M:0 Transfer: CC
Bank: L C:1 M:3 Transfer: C
Bank: R C:2 M:2 Transfer: MM
Bank: L C:2 M:2 Transfer: MC
Bank: R C:1 M:3 Transfer: MM
Bank: L C:3 M:0 Transfer: C
Bank: R C:2 M:3 Transfer: CC
Bank: L C:1 M:1 Transfer: M
Bank: R C:3 M:3 Transfer: MC

B08AH Mar 19 2012 at 16:36

что то с хабракатом не срослось…

artemgapchenko Mar 19 2012 at 18:36

не совсем понятно почему так медленно, целая секунда.

Ну, на самом деле это не так уж сложно. Моя программа сделана на списках, а Haskell работает со списками своеобразным образом — для того, скажем, чтобы произвести какую-либо операцию с концом списка (взять последний элемент, или сконкатенировать список с другим списком), он последовательно обойдет каждый элемент. В процессе построения дерева решений мой список списков разрастается неимоверно — после нахождения первых одиннадцати состояний он состоит из (примерно) 5*4^9 путей.
А теперь представьте себе процесс нахождения двенадцатого, финального состояния. Берем первый путь из списка, строим дополнения. Ни одно из них не привело к финальному состоянию -> кладем их в конец списка (последовательно проходим 5*4^9 элементов, и кладем новые построенные пути в конец). Затем берем второй путь. Затем третий. И всякий раз, меняя дерево решений, мы последовательно проходим его полностью. :) Отсюда и медлительность.
C# же, я уверен, хранит в списках указатель на последний элемент — раз. Вы строили список, состоящий из объектов-состояний, ссылающихся на своего родителя (я, кстати, писал эту задачу на python точно так же), а не список путей — два. Потому ваше решение так шустро и отработало.
Тут проблема не в языке, а в том, что я выбрал не самое (самое не) оптимальное решение.

хаскель это интерпретируемый язык?

Программу можно, написанную на нем, можно запустить через интерпретатор runhaskell. А можно получить исполняемый файл через ghc.

B08AH Mar 19 2012 at 18:59

после нахождения первых одиннадцати состояний он состоит из (примерно) 5*4^9 путей.

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

Тут проблема не в языке, а в том, что я выбрал не самое (самое не) оптимальное решение.

как то не подумал, что так было задумано.

ЗЫ еще не совсем понятно, что именно делается за 45 секунд. если отключить проверку на то, что следующее состояние уже было ранее, то лодка по кругу будет бесконечно возить одно и то же.

artemgapchenko Mar 19 2012 at 20:42

Окей, запишем количество путей следующим образом: n^12, n из промежутка [2,5].

если отключить проверку на то, что следующее состояние уже было ранее, то лодка по кругу будет бесконечно возить одно и то же.

В том то и дело, что бесконечно возить она не будет. Вернее, так: будет возить бесконечно, но решение (хотя бы одно) все-таки найдет.
Смотрите: у нас есть изначальное состояние, с глубиной 0. Из него мы строим три продолжения. Берем первое состояние с глубиной 1, и пробуем продолжить его — получаем состояния с глубиной 2. После получения первых состояний с глубиной 2, мы не пытаемся сразу же продолжить их. Мы должны сначала посетить все состояния с глубиной 1, и попытаться достроить их. В этом смысл поиска в ширину.
Насчет дубликатов — обязательно посмотрю на днях на код еще раз.

kastigar Mar 20 2012 at 12:30

ЗЫ еще не совсем понятно, что именно делается за 45 секунд. если отключить проверку на то, что следующее состояние уже было ранее, то лодка по кругу будет бесконечно возить одно и то же.

Не совсем так. Это поиск в ширину (как уже написали). Если проверку не делать, то на следующий уровень добавляется больше потенциальных решений, которые на свой следующий уровень добавят ещё больше потенциальных зацикленых решений, и программе придётся тоже их обрабатывать, пока не найдётся решение. С проверкой, очередь вырастает до 4-х элементов максимум (вот тут дамп моего решения), а так вообще держится на 2х-3х элементах. Без проверки, там безумные цифры.

B08AH Mar 20 2012 at 14:27

пока не найдётся решение.

это если ставить так задачу, что надо найти одно решение.

но у задачи 4 решения. все из них находятся на 11ой глубине. И если заранее этого не знать, то есть не ставить искусственный триггер окончания вычислений, когда решение(я) найдено, то этот поиск станет бесконечным. посему и возник вопрос, что именно программа делает 45 секунд.

kastigar Mar 20 2012 at 20:07

Верно, но в алгоритме и задано «найти первое решение». Вот он эти 45 секунд и обрабатывает все «зацикленные решения». Вот размеры уровней:

Level 1: 1
Level 2: 3
Level 3: 5
Level 4: 15
Level 5: 27
Level 6: 79
Level 7: 145
Level 8: 417
Level 9: 771
Level 10: 2193
Level 11: 4071

Хотя после запуска я понял ваше недоумение: программа выполнилась за 1 сек, вместо 0 (у sbt таймер с округлениями). Это никак не 45 сек. До этого я пускал с дампом этих уровней, выполнялось долго, но похоже тут проблема в выводе огромных данных в консоль. Могу лишь предположить, что либо в хаскелле всё плохо со списками, либо автор тоже выводил какой-то дамп.

artemgapchenko Mar 21 2012 at 16:12

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