И сегодня я предлагаю вам попрактиковаться и примерять на себя роль сыщика, разгадав одну задачу, а если быть точнее, то это загадка Эйнштейна про 5 домов. Говорят, что он придумал её, когда был маленьким и заявлял, что справиться с ней смогут всего лишь 2% населения планеты. В наше время она немного видоизменилась, но всё равно не утратила своей сложности.
Задача
Условие загадки состоит в том, что вы должны выяснить, у какого именно человека находится аквариум с рыбками, внимательно изучив пункты с данными ещё четырёх людей, имеющих разные предпочтения в напитках, домашних животных и цветовой гамме своих жилищ.
- Японец живёт в первом доме.
- А француз в красном.
- Бирюзовый дом стоит немного левее синего.
- Испанец любит пить кофе.
- Человек, который предпочитает Davidoff, живёт по соседству с тем, у кого много кошек.
- Человек, живущий в доме зелёного цвета, курит Monte Carlo.
- А бельгиец Camel.
- Тот, кто проживает в центральном доме, пьет йогурт.
- А тот, кто живёт рядом с тем, кто курит Davidoff, пьет молоко.
- Человек, который любит сигареты Parlament, разводит хорьков.
- Африканец держит у себя карликовых пинчеров.
- Японец живет по соседству с фиолетовым домом.
- А в фиолетовом доме обитает человек, который любит мышек.
- Человек, который любит фанту, курит Rothmans.
- А тот, кто живёт в доме, стены которого в бирюзовых тонах, любит пиво.
Решение
Итак, а теперь непосредственно само решение. У нас есть несколько точных данных, которые мы уже можем зафиксировать в таблице.
Точные данные
| Номер дома | 1 | 2 | 3 | 4 | 5 |
| Национальность | Японец | ||||
| Напиток | йогурт | ||||
| Сигареты | |||||
| Питомцы | мышки | ||||
| Цвет дома | фиолетовый |
Цветовая гамма домов
Для японца красный не подходит, там обжился француз, фиолетовый также не наш вариант, потому что он находится рядом. Также он не бирюзовый, потому что справа от бирюзового должен быть синий. Исключив все варианты, получается, что наш японец находится в зелёном доме. Далее выясняем, что, если бирюзовый дом находится левее синего, то значит он под номером 4 или 3. Тот, кто находится в центральном доме, любит йогурт, а в бирюзовом – пиво. Выходит, что любитель пива под номером 4, а синий цвет в 5 ячейке. Остаётся красный, он и будет под номером 3, а ещё мы знаем, что там живёт француз.
| Номер дома | 1 | 2 | 3 | 4 | 5 |
| Национальность | японец | француз | |||
| Напиток | йогурт | пиво | |||
| Сигареты | Monte Carlo | ||||
| Питомцы | мышки | ||||
| Цвет дома | зелёный | фиолетовый | красный | бирюзовый | синий |
Задача становится всё интересней и интересней, не так ли?
2-й этап
Теперь пробуем выяснить, что предпочитает выпивать бельгиец. Тот, кто употребляет фанту, любит Rothmans, а бельгиец покуривает Camel, так что фанта не подходит. Йогурт пьёт француз, а кофе – испанец. Остаётся или молоко, или пиво. Японец также не пьёт фанту, потому что курит не Rothmans, а также не пьёт йогурт, потому что мы знаем, что это прерогатива француза. Пиво употребляет житель бирюзового дома, а кофе – испанец. Получается, напиток японца – молоко, а бельгийца – пиво. Рядом с тем, кто любит молоко, живёт человек, курящий Davidoff, а рядом с японцем только номер 2.
| Номер дома | 1 | 2 | 3 | 4 | 5 |
| Национальность | японец | француз | бельгиец | ||
| Напиток | молоко | йогурт | пиво | ||
| Сигареты | Monte Carlo | Davidoff | Camel | ||
| Питомцы | мышки | ||||
| Цвет дома | зелёный | фиолетовый | красный | бирюзовый | синий |
Этап 3, заключительный
Мы знаем, что во 2 доме держат мышей, а африканец занимается карликовыми пинчерами, значит это не его дом. Остаётся номер 5. Тот, кто курит Parlament, разводит хорьков, мы знаем, что у африканца пинчеры, поэтому получается, что это француз. Остались сигареты Rothmans, и они принадлежат африканцу, как и любовь к фанте.
| Номер дома | 1 | 2 | 3 | 4 | 5 |
| Национальность | японец | испанец | француз | бельгиец | африканец |
| Напиток | молоко | кофе | йогурт | пиво | фанта |
| Сигареты | Monte Carlo | Davidoff | Parlament | Camel | Rothmans |
| Питомцы | кошки | мышки | хорьки | Карликовые пинчеры | |
| Цвет дома | зелёный | фиолетовый | красный | бирюзовый | синий |
Тот, кто курит Davidoff, живёт рядом с ценителем кошек, то есть или с 3, или с 1 домом. Но мы знаем, что в 3 доме находится француз, и он держит хорьков, значит кошки у японца. Из национальностей у нас остался испанец, его мы и вписываем во вторую ячейку. А ещё мы знаем, что он очень любит кофе.
Многие сталкивались с головоломкой про пять разноцветных домов, в каждом из которых живет человек со своими любимыми животным, напитком и сигаретами. Эта загадка приписывается Эйнштейну, хотя прямых подтверждений этому нет. Полный текст этой головоломки есть на википедии .
Ее можно решить на бумаге или в уме, последовательно исключая неподходящие варианты. Однако, ее также можно решить более технично. Один из способов - написать программку на прологе. Но здесь я хочу ее решить используя более простые механизмы - регулярные выражения. А именно, перевести условия загадки на язык регекспов и свести задачу к поиску подходящей строки во всем допустимом наборе строк. Кстати, этот набор строк показан на рисунке.
Идея
Сама идея не моя, услышал ее в одной видеолекции. Однако, там ее решали слишком уж изощренно. Я попытался решить ее более просто и прямолинейно.Для удобства приведу здесь текст загадки:
- Норвежец живёт в первом доме.
- Англичанин живёт в красном доме.
- Зелёный дом находится слева от белого, рядом с ним.
- Датчанин пьёт чай
- Тот, кто курит Marlboro, живёт рядом с тем, кто выращивает кошек.
- Тот, кто живёт в жёлтом доме, курит Dunhill.
- Немец курит Rothmans.
- Тот, кто живёт в центре, пьёт молоко.
- Сосед того, кто курит Marlboro, пьёт воду.
- Тот, кто курит Pall Mall, выращивает птиц.
- Швед выращивает собак.
- Норвежец живёт рядом с синим домом.
- Тот, кто выращивает лошадей, живёт в синем доме.
- Тот, кто курит Winfield, пьет пиво.
- В зелёном доме пьют кофе.
Чтобы решить задачу нужно найти такую последовательность домов, цветов, национальностей, напитков и сигарет, чтобы они удовлетворяли правилам выше
И так, что и где мы будем искать. Для начала нужно каким-то образом формализовать правила. У нас пять домов, цветов, национальностей, напитков, животных и сигарет. Произвольный вариант дома с «жильцами» может выглядеть так:
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. И каждая из этих букв может принимать одно из пяти своих значений.
Замечательно. То, что остается сделать - перевести правила на язык регулярных выражений:
- ^norwegian \w+
- \w+ englishman red \w+
- \w+ dane \w \w tea \w+
Но есть плохая новость. Текст, по которому будет проходить поиск может быть ОЧЕНЬ большим. Если точнее, он будет размером (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 и да, мьсе действительно знает толк в извращениях:)
Охотник неожиданно столкнулся на пустыре нос к носу с медведем. Оба испугались и побежали в разные стороны: охотник – на север, а медведь – на запад. Пробежав какое-то расстояние, охотник опомнился, направил ружьё точно на Юг, выстрелил и убил медведя.
Какого цвета был медведь?
История эта произошла на Северном полюсе. Когда охотник стрелял, он, должно быть, находился непосредственно на самом центре Северного полюса. Теперь более-менее ясно? Нетрудно будет догадаться, что медведь мог быть исключительно БЕЛЫМ. Я слышал другие варианты решений этой головоломки (даже такие, в которых утверждается, что на Северном и Южном полюсах медведи не водятся), но предложенное выше объяснение кажется мне наиболее разумным.
Соседи
Некоторые утверждают, что эта загадка была составлена Эйнштейном в детстве, и что 98% людей не сумеют решить эту задачу.
На улице стоят 5 домов разного цвета. В каждом доме живёт человек другой национальности. У каждого есть свой любимый напиток, каждый предпочитает свою марку сигарет и у каждого есть своё отличное от всех других домашнее животное.
- Англичанин живёт в красном доме.
- Швед держит собаку.
- Датчанин пьёт чай.
- Зелёный дом стоит рядом с белым домом, слева.
- Хозяин зелёного дома любит кофе.
- Человек, который курит “Pall Mall”, разводит птиц.
- Владелец жёлтого дома предпочитает курить “Dunhill”.
- Человек, живущий в доме посередине, пьёт только молоко.
- Норвежец живёт в первом доме.
- Человек, который курит “Blends” живёт по соседвству с владельцем котов.
- Хозяин лошади живёт по соседству с курильщиком “Dunhill”.
- Тот кто курит “Blue Master”, пьёт пиво.
- Немец предпочитает сигареты “Prince”.
- Дом норвежца стоит рядом с голубым домом.
- Один из соседей курильщика “Blends” пьёт только воду.
Кто разводит рыбок?
Вы относитесь к 2%, которые могут решить эту задачу?
Так что, если Вы еще не попытались сами ее решить, а даже если и попытались рекомендую Вам сначала посмотреть ту статью (хотя бы потому, что существует несколько разновидностей загадки Эйнштейна ).
В этой статье я приведу решение загадки Эйнштейна и дам ответ на вопрос: кто выращивает рыбок?
Кстати, пришлось немного поколдовать с порядком вывода статей на блоге, чтобы сначала (сверху) выводилась , а сразу под ней (то есть эта статья).
Итак, освежили воспоминания посмотрев предыдущую запись, вспомнили условия, а теперь перейдем к непосредственному решению загадки Эйнштейна .
Загадка Эйнштейна решение и ответ.
Для удобство разобьем решение на 4 части и будем использовать таблицы. А что бы Вам было удобно откройте условие, так как мы часто будем ссылаться на него.
1 часть.
Далее мы можем определить какого цвета первый дом (Норвежца) – из (3) ясно, что он не может быть ни белым, ни зеленым; так же он не может быть и красным (2). Следовательно первый дом – дом Норвежца – Желтый.
Из (6) в первом доме курят «Dunhill», а из (13) – во втором доме содержится лошадь.
Теперь определим, что пьет Норвежец (первый дом, желтого цвета, сигареты «Dunhill»). Из (4) – ясно что это не чай, из (15) – это не кофе, из (8) – это не молоко, из (14) – это не пиво; следовательно это вода,. Значит, Норвежец пьет воду!
А теперь все мысли оформим в табличку:
2 часть.
Из (9) понятно, что человек из 2го дома (синий) курит «Rothmans».
Определим теперь национальность человека из второго дома (синий дом, курит «Rothmans», содержит лошадь). Ясное дело это не Норвежец, из (2) – не англичанин, из (11) – не швед, из (7) – не немец. Значит во втором доме проживает Датчанин, который еще (4) и чай пьет!
3 часть.
Используя (15) становится понятным, что зеленый дом не третий, ток как там пьют кофе, а не молоко. Так же он не пятый, поскольку справа есть дом (3). Тогда Зеленый дом – третий, а белый пятый, и красный – третий,а еще в нем живет англичанин (2). Значит в зеленом домике попивают кофе, а для белого остается лишь пиво. Согласно (14) в белом доме курят «Winfield» (в белом доме еще и курят! шутка).
Итак, табличка:
4 часть.
Определим место жительства немца, который покуривает «Marlboro» (7). А жить он может только в 4 – зеленом доме. Следовательно курильщик «Pall Mall» разводит птиц и живет в третьем красном доме – это человек из Англии.
Шведу остается только пятый дом. Из (11) – у шведа есть собака. Из (5) – кошка проживает в первом или третьем доме, но третий уже занят птицами, значит кошка все таки в первом доме.
Как Вы видите остался только один знак вопроса в таблице… Да, да, да это животное, это рыбки!!! Теперь каждому понятно кто разводит рыбок ? ведь все животные уже заняты.
Итак, рыбок разводит Немец , который живет в четвертом зеленом доме, пьет кофе и курит «Marlboro».
