Pull to refresh
48
0
Артём Гапченко @artemgapchenko

Android Dev

Send message
(не)переведена фраза «Personally I find the latter example simpler, clearer, and easier to understand».

Вы точно нашли эту фразу именно в той статье, с которой я делал перевод? Потому что я сейчас проверил оригинал и ее там не нашел.
В total нет внутреннего for цикла, там применяется свертка, т.е. конструкция вида foldl1 (+) list. Сложение происходит не итеративно, а рекурсивно.
Нет, дамп я не выводил.
Haskell работает со списками лениво. Думаю, что столь медленная скорость работы связана именно с ленивостью вычислений (в совокупности с не самым лучшим выбором структуры данных).
Окей, запишем количество путей следующим образом: n^12, n из промежутка [2,5].

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

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

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

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

Программу можно, написанную на нем, можно запустить через интерпретатор runhaskell. А можно получить исполняемый файл через ghc.
Пример: на левом берегу три миссионера и ноль каннибалов.
Ваш вариант проверки дает (3 >= 0) && (0 >= 3) == False. Получается, что состояние небезопасно, хотя это не так.
Все четыре решения находит за 1.2 секунды. Как запустить функцию solve так, чтобы она вернула результат после нахождения первого же решения, я пока не сообразил — монады для меня дремучий лес.:) Но результат получится явно быстрее, чем мое решение, не основанное на этом фреймворке.
Можно конечно, отчего б не написать.:)
Вот и решение.
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 []
12 ...
7

Information

Rating
Does not participate
Date of birth
Registered
Activity