10 июня 2011 в 16:16

Кто разводит рыбок? Или решение загадки Эйнштейна регулярным языком

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



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


Идея


Сама идея не моя, услышал ее в одной видеолекции. Однако, там ее решали слишком уж изощренно. Я попытался решить ее более просто и прямолинейно.

Для удобства приведу здесь текст загадки:
  1. Норвежец живёт в первом доме.
  2. Англичанин живёт в красном доме.
  3. Зелёный дом находится слева от белого, рядом с ним.
  4. Датчанин пьёт чай
  5. Тот, кто курит Marlboro, живёт рядом с тем, кто выращивает кошек.
  6. Тот, кто живёт в жёлтом доме, курит Dunhill.
  7. Немец курит Rothmans.
  8. Тот, кто живёт в центре, пьёт молоко.
  9. Сосед того, кто курит Marlboro, пьёт воду.
  10. Тот, кто курит Pall Mall, выращивает птиц.
  11. Швед выращивает собак.
  12. Норвежец живёт рядом с синим домом.
  13. Тот, кто выращивает лошадей, живёт в синем доме.
  14. Тот, кто курит Winfield, пьет пиво.
  15. В зелёном доме пьют кофе.

Вопрос: кто разводит рыбок?

Чтобы решить задачу нужно найти такую последовательность домов, цветов, национальностей, напитков и сигарет, чтобы они удовлетворяли правилам выше

И так, что и где мы будем искать. Для начала нужно каким-то образом формализовать правила. У нас пять домов, цветов, национальностей, напитков, животных и сигарет. Произвольный вариант дома с «жильцами» может выглядеть так:

german white cat beer malboro


Но этого недостаточно, так как у нас есть правила, которые учитывают взаимное расположение домов и предметов в них (к примеру, правила: 1, 3, 5...). Учтем это, расположив в строке пять домов последовательно:

german white cat beer malboro      englishman red dog water pallmall    norwegian green fish milk winfield   dane blue bird tea dunhill      swede horse yellow coffee rothmans


Строка выше — один из вариантов расположения предметов. В данном случае, неверный. Если же мы составим все возможные варианты, и поместим это в один текст, получится следующее:

n c a d s   n c a d s   n c a d s   n c a d s   n c a d s
n c a d s   n c a d s   n c a d s   n c a d s   n c a d s
n c a d s   n c a d s   n c a d s   n c a d s   n c a d s
...


Где n — nation, c — color, a — animal, d — drink, s — cigarettes. И каждая из этих букв может принимать одно из пяти своих значений.

Замечательно. То, что остается сделать — перевести правила на язык регулярных выражений:
  1. ^norwegian \w+
  2. \w+ englishman red \w+
  3. \w+ dane \w \w tea \w+
  4. ...

И если строка подойдет ко всем правилам, то мы нашли решение! Останется только посмотреть национальность в доме с рыбой. Это и является главной идеей поиска: построить текст и пройтись по нему регулярными выражениями.

Но есть плохая новость. Текст, по которому будет проходить поиск может быть ОЧЕНЬ большим. Если точнее, он будет размером (5!)^5 строк (~24 миллиардов). Его не то чтобы проверить, его будет сложно даже сгенерировать. Но есть и хорошая новость. Мы можем не генерировать весь этот текст, а воспользоваться операцией пересечения регулярных выражений. То есть найдем все общие строки регулярного выражения * (все возможные строки), с теми строками, которые дают регулярные выражения правил задачи. Та строка (а может и строки) что останется после пересечения и будет решением задачи.

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

Реализация


Конечные автоматы буду строить с помощью библиотечки openfst. Она дает все что мне необходимо для построения автоматов, плюс удобный способ работы из шелла. Чтобы сделать программирование еще более «ненормальным», я вообще не буду программировать :). За исключением простых bash-скриптов кода не будет.

Шаг 1 — Строим базовые автоматы



Создадим текстовый файл со списком всех объектов. Это будет наш алфавит.
norwegian
englishman
dane
german
swede
white
red
...


Построим базовые автоматы, каждый из которых допускает только одно слово из алфавита.
j=1
for i in `cat alph`; do
    echo -e "0 1 $j\n1" | fstcompile --acceptor > $i 
    ((j=$j+1))
done


fstcompile — команда пакета openfst, компилирующая текстовое представление автомата в бинарное. Это нужно для того, чтобы потом применять к этому автомату различные операции.

И так, у нас появился список файлов-автоматов. Они очень тривиальны. К примеру, автомат beer будет выглядить так:



Он эквивалентен регулярному выражению «beer». Пока все довольно просто. Кроме того нам понадобятся еще два базовых автомата — пустое множество, и любая строка, т.е. звездочка *. Строим.

Шаг 2 — Строим пустой автомат и звездочку



Пустая строка, автомат 'empty':
 echo '0' | fstcompile --acceptor > empty 


Звездочка, автомат 'star':
cp empty star
for i in `cat alph`; do
    fstunion star $i star
done
fstclosure star star

Последний делается простым объединением базовых автоматов и замыканием. В регулярных выражениях это всего лишь (englishman|dane|...|cat|dog|...)*. Этот автомат будет таким:


Шаг 3 — Строим дома



Правила будет удобней описывать, если создать более комплексные автоматы, такие как национальность, цвет и т.д. Опять, использую несложный скрипт:

c="./concat.sh"

$c norwegian star                                   > r1
$c star englishman red star                         > r2
$c star animal drink cigarette nation star          > r3
$c star dane color animal tea star                  > r4
$c star malboro nation color cat star               > r5_0
$c star cat drink cigarette nation color animal drink malboro star > r5_1
$c star yellow animal drink dunhill star            > r6
$c star german color animal drink rothmans          > r7
$c house house nation color animal milk cigarette house house > r8
$c star malboro nation color animal water star      > r9_0
$c star water cigarette nation color animal drink malboro star > r9_1
$c star bird drink pallmall star                    > r10
$c star swede color dog star                        > r11
$c star norwegian color animal drink cigarette nation blue star > r12_0
$c star blue animal drink cigarette norwegian star  > r12_1
$c star blue horse star                             > r13
$c star beer winfield star                          > r14
$c star green animal coffee star                    > r15

fstunion r5_0 r5_1      > r5
fstunion r9_0 r9_1      > r9
fstunion r12_0 r12_1    > r12



Правила 5, 9 и 12 являются составными. Я определяю каждую часть отдельно, а потом делаю объединение. Скрипт concat.sh всего лишь делает конкатинацию автоматов, переданных в аргументах:
cp empty _c
for i in $*; do
    fstconcat _c $i _c
done;
cat _c; rm _c;


Итак, на выходе получим автоматы r1,r2...,r15. Все готово для финального шага.

Шаг последний — Пересечение



./intersect.sh r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 > result


Где intersect.sh — пересечение автоматов в аргументах.
cp cl _c
for i in $*; do
    fstintersect _c $i _c
done;
cat _c; rm _c;


На этом можно было бы и закончить — посмотреть автомат и узнать у кого рыба. Но я с самого начала не учел одну вещь — в моих правилах каждое из слов может повторятся. К примеру, два человека могут пить одно пиво и заводить одно животное. Это неверно по условиям задачи. Создавать такой фильтр крайне неудобно, используя регулярные языки, т.к. у нас нет способа «запомнить», что такое слово уже было. Но ограничить как-то нужно. По этому подвергаем финальный результат следующему скрипту.

i="./intersect.sh"
d="fstdifference"

for i in `cat alph`; do
    fstdifference cl $i > differ 
    fstconcat differ $i | fstconcat - differ | fstrmepsilon - | fstdeterminize - | fstminimize - > ${i}_cont
done

cp result out
for i in `ls *_cont`; do
    echo $i
    fstintersect $i out | fstrmepsilon - | fstdeterminize - | fstminimize - out
done

rm differ
rm *_cont


Этот скрипт формирует специальный авотомат для каждого слова из алфавита, и применяет его к результату. Таким образом, отметаются пути с повторяющимися словами. В итоге, финальный результат (а по сути, автомат 'out') выглядит так:



Это частичное изображение автомата (все не влезло). Каждые пять слов определяют дом. Как видно из рисунка, немец разводит рыбок.

Заключение



Вот такой вот необычный способ решения задачи. Но кроме всего прочего он показывает, что регулярные языки — это довольно мощная штука. Более того, если верить Ульману, любую математическую проблему можно представить как нахождения строки в определенном языке. Что и было показано.

ps и да, мьсе действительно знает толк в извращениях :)
+113
11370
88

Комментарии (43)

+6
VYBGSS, #
И все-таки на Прологе такие задачки быстрее все описываются.
0
Andrew1000000, #
Не то что на brainfuck'е.
0
lightcaster, #
Пожалуй. Но я по этому и поместил ее в «ненромальное» программирование. ;)
+2
Cryptochild, #
Капитан Очевидность говорит нам, что пролог — специализированный язык для решения логических задач. Естественно, что описание этой задачи на нём быстрее.
0
lightcaster, #
Вообще, изначально хотел обойтись только регекспами. Но количество строк для перебора слишком велико.
+8
Levsha100, #
Снимаю шляпу!
+4
darkfrei, #


Логика задачи сильно напоминает логику судоку, достроить всю картинку по имеющимся минимально необходимым данным.
+8
JanKefir, #
Разрешите поинтересоваться — на чем рисунки делались? :-)
+6
lightcaster, #
В openfst входит утилитка fstdraw. Она конвертит автомат в dot-файл формата graphviz. Этот файл затем рендерится в png (или ps, svg...):
fstdraw --acceptor --isymbols=alph.st out out.dot
dot -Tpng out.dot >out.png
0
debug22, #
> dot -Tpng out.dot >out.png
если интересовавшемуся мсье лень зайти под линь, то
dot -Tpng -oout.png out.dot

и вообще, у graphvis очень годный ман. всем бы такие.
0
Kukunin, #
я из решения на википедии не понял, почему красный дом не может быть первым, потому что там живет англичанин. Религия не позволяет или почему?
0
PiJon, #
Можно попробовать решить самостоятельно, хотя бы на бумаге.
+2
pomkaster, #
Два первых условия:
1. Норвежец живёт в первом доме.
2. Англичанин живёт в красном доме.
Красный дом не может быть первым, потому что в красном доме живёт англичанин, а в первом доме живёт норвежец.
Я думаю в условии подразумевается, что двойной национальности нету неукого.
0
Kukunin, #
ааа. деградирую…
P.S. наивно считал, что смогу решить в уме и войти в 2% умников =(
0
Karamultuck, #
Норвежец живёт в первом доме.
Англичанин живёт в красном доме.
значит красный — не первый
–2
avrfun, #
Кстати, загадка носит название «загадки Эйнштейна»,
хотя на самом деле он никакого отношения к ней не имеет.
+1
avrfun, #
автор так и написал :)
+1
lightcaster, #
Вы правы :) Я написал об этом в самом начале.
+1
avrfun, #
Хотел узнать для решения каких задач Вы обычно используете пролог?
Только академический интерес или же коммерческие разработки тоже существуют?
Не работал на прологе, поэтому такие вопросы.
+1
lightcaster, #
Я не использую пролог :)

Ну, в принципе язык интересный. Однако писать что-то практическое на нем сложно. Разве что использовать как часть какой-то системы принятия/поддержки решений. И даже в этом случае чаще используются другие решатели.

Но просто чтобы поиграть с логикой первого порядка — пролог замечательная вещь.
+2
PiJon, #
В школе решал эту задачку спокойно и полагал что вхожу в 2% этих самых. Только потом прочитал, что решать надо в уме.
+1
Rudolfo, #
Главное результат, а не объём памяти :)
+2
enibeniraba, #
Около 20% могут дать правильный ответ не думая. Если серьезно, то мне кажется, что 2% это сильно преувеличенное значение.
0
mark_ablov, #
держать в уме 5 таблиц 5x5 действительно не просто.
фактически 16 байт информации, однако требует большой концентрации.
0
AirLight, #
Может потому что мозг хранит информацию не битами, а отдельными значениями? это получается 125 единиц табличных данных, плюс 25 отдельных сущностей, плюс какой-то лог. А для того чтобы не насиловать мозг, можно сначала поупражняться на задачках размерностью 3 и 4.
0
Lerk, #
Задачку даже с бумажкой и ручкой далеко не все могут решить однозначно — без предположений типа «допустим в этом доме...». А про решение в уме таки и вовсе… шахматисты, наверное, могут на раз-два)
+1
sourcerer, #
Может, Вы хотели сказать: «Около 20% могут угадать правильный ответ, не думая»?
0
ykrop, #
вы правы. если национальностей 5, то вероятность попадания в правильный ответ 20%. но умное лицо еще не признак ума.
0
AirLight, #
А я эту задачку решал составлением таблиц в экселе, ушло всего каких-то 6 часов.
0
sourcerer, #
Школьникам на олимпиадах по математике часто подобные задачки дают. В наших краях — с ограничением по времени в 4 часа на 8 задач. И ничего, многие решают менее чем за полчаса. Без всяких экселей.
0
AirLight, #
Почти любой человек может ее решить за полчаса с помощью смекалки, но вот разработать методологию решения — это задача на уровень выше.
+2
Anexroid, #
Я решал на бумажке «методом судоку». Писал программу ни Си, которая делает тоже самое почти тем же методом. Жду пока кто-нибудь решениие на Brainfuck'е сделает, если это возможно, конечно.
0
lightcaster, #
Конечно, на Brainfuck'е это можно решить. Он, как и Си — Тьюринг полный.

А регулярные выражения (или язык, что одно и тоже) — на несколько ступеней ниже. Вот по этому мне и было интересно решить загадку таким методом.
0
Anexroid, #
Я в курсе, что Brainfuck — Тьюринг полный, но вот страшно представить сколько кода на BF будет…
0
lightcaster, #
Да, думаю много.
0
qmax, #
я 98ой.
объясните, пожалуйст, как получилось пересечение регекспов.
0
lightcaster, #
ответил ниже…
0
lightcaster, #
Я пересекал не регекспы, а соответствующие им автоматы.

Давайте поясню. Вот есть у меня два регекспа
A: 1*
B: *2
С: 1*2

Пересечением A и B будет С. Вобщем, то это не сложно понятно. Их пересечением будет все, что начинается на 1, заканчивается на 2.
Но есть проблема — у меня нет правил как из A и B получить их пересечение C.

Для этого я беру автоматы для A и B (которые полностью эквивалентны регулярным выражениям) и строю их пересечение.

A:


B:


C:


Автомат C — то же самое что и регулярное выражение С.

+1
Jedi_Knight, #
Решите тогда уж этот частный случай: darnley.livejournal.com/25666.html

1. Каждый день в домике, имеющем чётный номер, преподаватель собирает кубик Рубика, попивая молоко.
2. Преподаватель, программирующий на Хаскеле, иногда для смеха объявляет функцию tea — в честь своего любимого напитка.
3. Однажды преподаватель, играющий на скрипке, облил смычок своим любимым персиковым соком.
4. Преподаватель, чьё хобби — чистить трубы, программирует на функциональном языке программирования.
0
lightcaster, #
Забавно :) Но этим методом будет сложно, там контекстных правил много.
0
atamur, #
Если добавите кармы до 5 опубликую топик с решением задачи на Haskell.
0
lightcaster, #
плюсанул
0
atamur, #
Спасибо. Кому интересно — вот статья.

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