Хто розводить рибок? Або вирішення загадки Ейнштейна регулярною мовою

Багато хто стикався з головоломкою про п'ять різнокольорових будинків, у кожному з яких живе людина зі своїми улюбленими тваринами, напоєм та цигарками. Ця загадка приписується Ейнштейну, хоча прямих доказів цьому немає. Повний текст цієї головоломки є на вікіпедії.

Її можна вирішити на папері або в умі, послідовно виключаючи невідповідні варіанти. Однак її також можна вирішити більш технічно. Один із способів – написати програму на пролозі. Але тут я хочу її вирішити, використовуючи простіші механізми — регулярні вирази. А саме, перекласти умови загадки на мову регекспів і звести завдання до пошуку відповідного рядка у всьому допустимому наборі рядків. До речі, цей набір рядків показаний малюнку.

Ідея

Сама ідея не моя, почув її в одній відеолекції. Проте, там її вирішували надто витончено. Я спробував вирішити її більш просто та прямолінійно.

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 – 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 english man 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 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 - | fstвизначення - | fstminimize - > $_cont done cp result out for i in `ls *_cont`; do echo $i fstintersect $i out | fstrmepsilon - | fstвизначення - | fstminimize - out done rm differ rm *_cont

Цей скрипт формує спеціальний авотомат для кожного слова з алфавіту та застосовує його до результату. Таким чином, відкидаються шляхи з словами, що повторюються. У підсумку, фінальний результат (а по суті автомат 'out') виглядає так:

Це часткове зображення автомата (все не влізло). Щоп'ять слів визначають будинок. Як видно з малюнка, німець розводить рибок.

Висновок

Ось такий незвичайний спосіб вирішення завдання. Але до того ж він показує, що регулярні мови — це досить потужна штука. Більше того, якщо вірити Ульману, будь-яку математичну проблему можна представити як знаходження рядка у певній мові. Що було показано.

ps і так, мьсе дійсно розуміється на збоченнях :)