Загадка эйнштейна про рыбок

Обновлено: 24.12.2024

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

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

member(Elem, List) — истина, если элемент Elem есть в списке List
nth1(N, List, Elem) — истина, если элемент Elem в списке List стоит на N-й (счет начинается с 1) позиции
nextto(X, Y, List) — истина, если X стоит перед (слева от) Y в списке List

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сек, если скомпилировать то будет еще немного быстрее.

Эти функции входят в стандартную библиотеку. Приведены тут для полноты решения, чтобы показать что даже на «чистом» Прологе решение не сильно больше.

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 ).

Следующая загадка

Была такая компьютерная игра Sherlok. Как раз с такими загадками. Очень много времени я за ней проводил. В итоге наловчился решать такие задачки за минуту, а то и быстрее. :)
Норвежец пьет воду. У японца зебра. :)