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

[artemgapchenko]

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

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]

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

[artemgapchenko]

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

[artemgapchenko]

Давайте. :)

[afiskon]

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

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

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

Как-то так.

[artemgapchenko]

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

[B08AH]

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

на с# тож самое сделал ради интереса — время в нулях, в пределах погрешности.
решения в виде дерева получились, так показалось легче делать. точнее обратного дерева(или как это называется, когда только у детей ссылка на родителя, а не наоборот)
и в любом случае, в каждом узле этого дерева оказывается хэшсет со всеми состояниями до этого момента,
считай тот же набор списков, только не в списке списков, а раскиданные по дереву
<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]

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

[artemgapchenko]

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

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

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

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

[B08AH]

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

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

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

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

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

[artemgapchenko]

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

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

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

[kastigar]

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

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

[B08AH]

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

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

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

[kastigar]

Верно, но в алгоритме и задано «найти первое решение». Вот он эти 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]

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