Загадка Эйнштейна: Кто выращивает рыбок?

Идея

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

Для удобства приведу здесь текст загадки:

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

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

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

А вы читали?  Речной песок для аквариума своими руками

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

Реализация

Конечные автоматы буду строить с помощью библиотечки

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

Создадим текстовый файл со списком всех объектов. Это будет наш алфавит.

norwegian
englishman
dane
german
swede
white
red
...

Построим базовые автоматы, каждый из которых допускает только одно слово из алфавита.

j=1
for i in `cat alph`; do
echo -e "0 1 $jn1" | fstcompile --acceptor
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

Adblock detector