Задача Эйнштейна на Прологе

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

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

    Дом мы будем представлять как список из 5 элементов, по одному на каждый атрибут: национальность хозяина, домашний питомец, марка сигарет, напиток и цвет дома, соответственно. Всего домов 5, потому решение будем искать среди списков (списков) длины 5.
    Для этого нам понадобятся стандартные предикаты:
    • member(Elem, List) — истина, если элемент Elem есть в списке List
    • nth1(N, List, Elem) — истина, если элемент Elem в списке List стоит на N-й (счет начинается с 1) позиции
    • nextto(X, Y, List) — истина, если X стоит перед (слева от) Y в списке List
    Также, нам нужно уметь сказать что 2 дома стоят рядом друг с другом. Это можно реализовать вот таким простым предикатом:
    neighbors(X, Y, List) :- nextto(X, Y, List).
    neighbors(X, Y, List) :- nextto(Y, X, List) .
    Т.е., либо X слева от Y, либо наоборот.

    А вот, собственно, и решение:
    einstein :-
       /* 0. Всего 5 домов */
        Houses = [_,_,_,_,_],
       /* 1. Норвежец живёт в первом доме. */
        nth1(1, Houses, [norwegian,_,_,_,_]),
       /* 2. Англичанин живёт в красном доме. */
        member([englishman,_,_,_,red], Houses),
       /* 3. Зелёный дом находится слева от белого, рядом с ним. */
        nextto([_,_,_,_,green], [_,_,_,_,white], Houses),
       /* 4. Датчанин пьёт чай. */
        member([dane,_,_,tea,_], Houses),
       /* 5. Тот, кто курит Marlboro, живёт рядом с тем, кто выращивает кошек. */
        neighbors([_,_,marlboro,_,_], [_,cat,_,_,_], Houses),
       /* 6. Тот, кто живёт в жёлтом доме, курит Dunhill. */
        member([_,_,dunhill,_,yellow], Houses),
       /* 7. Немец курит Rothmans. */
        member([german,_,rothmans,_,_], Houses),
       /* 8. Тот, кто живёт в центре, пьёт молоко. */
        nth1(3, Houses, [_,_,_,milk,_]),
       /* 9. Сосед того, кто курит Marlboro, пьёт воду. */
        neighbors([_,_,marlboro,_,_], [_,_,_,water,_], Houses),
       /* 10. Тот, кто курит Pall Mall, выращивает птиц. */
        member([_,bird,pallmall,_,_], Houses),
       /* 11. Швед выращивает собак. */
        member([swede,dog,_,_,_], Houses),
       /* 12. Норвежец живёт рядом с синим домом. */
        neighbors([norwegian,_,_,_,_], [_,_,_,_,blue], Houses),
       /* 13. Тот, кто выращивает лошадей, живёт в синем доме. */
        member([_,horse,_,_,blue], Houses),
       /* 14. Тот, кто курит Winfield, пьет пиво. */
        member([_,_,winfield,beer,_], Houses),
       /* 15. В зелёном доме пьют кофе. */
        member([_,_,_,coffee,green], Houses),

       /* Внимание, вопрос: у кого рыба? */
        member([Owner,fish,_,_,_], Houses),

        /* Печатаем решение */
        print('Owner of the fish: '), print(Owner), nl,
        print('Full Solution: '), print(Houses), nl.


    Как видим, суммарное количество строк в программе практически совпадает с количеством условий в оригинальной задаче.
    Да и сами строчки читаются почти как оригинальные условия. Пролог — очень декларативный язык, нам лишь нужно описать что мы от него хотим.
    Интерпретатор выполняет за нас всю грязную работу, причем достаточно быстро. На моей машине скрипт выполняется за 0.08сек, если скомпилировать то будет еще немного быстрее.

    Чтоб запустить программку нужно установить себе SWI-Prolog, скопировать текст в файл и добавить вот такой-вот хеш-бэнг:
    #!/usr/bin/pl -q -t einstein -s
    (ну или берем код вот отсюда)

    Эти функции входят в стандартную библиотеку. Приведены тут для полноты решения, чтобы показать что даже на «чистом» Прологе решение не сильно больше.
    member(X, [X | _]).
    member(X, [_ | Rest]) :- member(X, Rest).

    nth1(1, [Elem | _], Elem).
    nth1(N, [_ | Rest], Elem) :- N > 1, K is N-1, nth1(K, Rest, Elem).

    nextto(L, R, [L, R | _]).
    nextto(L, R, [_ | Rest]) :- nextto(L, R, Rest).

    Также, условия 0, 1 и 8 можно упростить до одного:
    Houses = [[norwegian,_,_,_,_],_,[_,_,_,milk,_],_,_]
    тогда не нужен предикат nth1, но мне хотелось быть как можно ближе к оригиналу.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 23
    • +1
      В «Программирование», вестимо.
      • 0
        перенес, спасибо
        • +1
          Так и знал что на прологе будет так локанично, только поленился проверить, спасибо :)
          • +2
            Это гениально, сделать две ошибки в слове «лаконично», получилось слово с другим смыслом :) Извините, не удержался.
            • +1
              Наоборот, спасибо за замечание :)
        • +4
          Жажду «Задача Эйнштейна на Brainfuck».
          • 0
            на асме тоже былобы любопытно взглянуть…
            • +2
              На асме есть стек, поэтому поиск с бэктрекингом реализовать будет достаточно легко.
              А вот на брейнфаке, нужно будет хорошо так «потрахать мозг».
              • 0
                Скомпилируйте любое, из представленных решений, затем загрузите его в дизассемблер.
            • +1
              День задач Эйнштейна! Даешь решение на калькуляторе!
              • +1
                На таком пойдёт?
                image
                • 0
                  Пойдет!
                  • +2
                    Назвался груздем — пиши программу. Друг сейчас пишет похожий калькулятор под iOS, если и вправду напишите такую программу, можно будет добавить ее в список предустановленных. У меня сохранился до сих пор живой МК-61, отличный аппарат, хоть и работает медленно.
                    • +1
                      К сожалению пять переездов — приравнивается к двум пожарам, а я за последее десятилетие переезжал раз двадцать и один из них в другую страну.
                      Если можете порекомендовать хороший эмулятор — попробую размять мозги, но не обещаю.

                      P.S. А девайс такой был. Жаль, не сохранился…
                      • 0
                        Я пошутил же, но если действительно хочется размять мозги, то это можно сделать в эмуляторе множества калькуляторов (под виндовс) www.emulator3000.org/rus-c3.htm
                        Там же есть различные сканы журналов с программами.
                • +8
                  хорошая все же штука пролог.
                  В который раз убеждаюсь.
                  • +1
                    на какой реализации пролога пишете?
                    • +2
                      а, пардон, SWI-Prolog не увидел
                      • +2
                        Я не использовал ничего нестандартного и в конце привел реализации всех функций, чтобы код был как можно более портативным. Код должен работать на любом интерпретаторе с Эдинбургским синтаксисом (я не уверен что в природе остались живые диалекты с другим). Если убрать вывод так точно будет :)
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +1
                        хорошее решение. я приблизительно то же самое начеркал на листочке, но до конца не довел :) однозначно в избранное!
                      • +1
                        Теперь задача Энштейна — это хабровский HelloWorld?)
                        • НЛО прилетело и опубликовало эту надпись здесь

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.