Логическая загадка эйнштейна про дома. Загадка Эйнштейна: кто выращивает рыбок? Отгадай! Эйнштейн о своей загадки

Школа Юрия Окунева

Привет, друзья. С вами Юрий Окунев. С советскими пионерами разобрались. Сегодня возьмем планку повыше. Отгадаем загадку Энштейна.

Загадка Эйнштейна - известная логическая задача, авторство которой приписывается Альберту Эйнштейну.

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

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

В своей самой тяжёлой редакции задача предполагает решение в уме, без использования каких-либо записей или средств сохранения информации. Без этого головоломка заметно теряет в сложности, поскольку может быть решена простым составлением таблицы с исключением заведомо противоречивых вариантов - и следовательно мало что говорит о способностях испытуемого."

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

Вопрос: кто выращивает рыбок?

Подсказки:

Норвежец живет в первом доме.
Англичанин живет в красном доме.
Зеленый дом находится левее белого.
Датчанин пьет чай.
Тот, кто курит Rothmans, живет рядом с тем, кто
выращивает кошек.
Тот, кто живет в желтом доме, курит Dunhill.
Немец курит Marlboro.
Тот, кто живет в центре, пьет молоко.
Сосед того, кто курит Rothmans, пьет воду.
Тот, кто курит Pall Mall, выращивает птиц.
Швед выращивает собак.
Норвежец живет рядом с синим домом.
Тот, кто выращивает лошадей, живет в синем доме.
Тот, кто курит Philip Morris, пьет пиво.
В зеленом доме пьют кофе.

Попробуйте угадать, кто выращивает рыбок?

И сегодня я предлагаю вам попрактиковаться и примерять на себя роль сыщика, разгадав одну задачу, а если быть точнее, то это загадка Эйнштейна про 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 доме находится француз, и он держит хорьков, значит кошки у японца. Из национальностей у нас остался испанец, его мы и вписываем во вторую ячейку. А ещё мы знаем, что он очень любит кофе.

Не потеряйте. Подпишитесь и получите ссылку на статью себе на почту.

Альберт Эйнштейн известен не только своими исследованиями и открытиями, несколькими сотнями работ по физике и книгами и статьями в области публицистики, истории и философии, но и другими интересными фактами. Далеко не все знают, что ещё до того, как стать учёным, он создал интереснейшую задачу. Её называют загадкой Эйнштейна и именно ей посвящена представленная статья.

Загадка Эйнштейна

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

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

Итак, задача.

Оригинальный текст загадки Эйнштейна

Текст загадки:

На улице расположены пять домов.
Англичанин проживает в доме красного цвета.
Испанец держит собаку.
Украинец любит чай.
Дом зелёного цвета расположен сразу справа от дома белого цвета.
Курящий «Old Gold», разводит улиток.
В доме жёлтого цвета живёт курящий «Kool».
В доме по центру пьют молоко.
Норвежец живёт в доме №1.
Сосед курящего «Chesterfield», держит в доме лису.
В доме, соседнем с тем, где держат лошадь, живёт курящий «Kool».
Курящий «Lucky Strike», любит апельсиновый сок.
Японец курит «Parliament».
Норвежец живёт в доме, расположенном рядом с домом синего цвета.

Вопрос: Кто пьёт воду, а кто держит зебру?

Для более точного понимания нужно добавить, что все дома окрашены в разные цвета, а все их жители являются представителями разных национальностей, они содержат разных животных, предпочитают разные напитки, а также курят сигареты разных марок. И примечание: когда говорится справа — это значит справа от вас. В исходном условии, правда, не указывается, что дома стоят подряд, и нет никакой информации о том, что кто-то вообще может пить воду или держать зебру. Т.е. посылки для решения загадки можно назвать неявными (в сравнении с другими подобными логическими задачами), что значительно усложняет решение.

Решение загадки Эйнштейна

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

Шаг №1 (в скобках указаны пункты текста загадки)

Согласно условию, норвежец проживает в доме №1 (10). Откуда начинается отсчёт – не важно, т.к. нас заботит не направление нумерации домов, а только их порядок. (10) и (15) говорят о том, что дом №2 – синего цвета. Так какого цвета дом №1? Он не может быть ни зелёным, ни белым, т.к. они должны быть рядом, исходя из цвета дома №2 и (6). Также дом №1и не красный, т.к. в красном проживает англичанин. Соответственно, дом №1 – жёлтого цвета.

Далее следует, что в доме №1 курят сигареты «Kool» (8), а в доме №2 есть лошадь (12). Норвежец из жёлтого дома №1, курящий «Kool», не пьёт чай (5), не пьёт кофе (4) , не пьёт молоко (9) и не пьёт апельсиновый сок (13). Получается, что норвежец и есть тот, кто пьёт воду.

Шаг №2

Какие сигареты курят в синем доме №2, где есть лошадь?

«Kool» курят в доме №1 (8). «Old Gold» курит тот, у кого в доме улитки (7). Если, например, предположить, что в доме №2 курят «Lucky Strike», то получится, что там предпочитают и апельсиновый сок (13). Значит, кто может жить в доме №2? Не норвежец (10), не англичанин (2), не испанец (3), не украинец (5) и не японец (14). Но такой ситуации быть не может, а значит, это не «Lucky Strike».

Если предположить, что это «Parliament», то получится, что в доме №2 живёт японец (14). Но что он пьёт? Не чай (5), не кофе (4), не молоко (9) и не сок (13). Такого вариант тоже быть не может, а значит, это не «Parliament». Вывод остаётся один: в доме №2 курят «Chesterfield».

Кто живёт в синем доме №2, курит «Chesterfield» и у кого есть лошадь? Он не может быть норвежцем (10), англичанином (2), испанцем (3) и японцем (14). Соответственно, это украинец, который пьёт чай (5).

Шаг №3

Учитывая, что «Chesterfield» курят в доме №2, то из (11) становится ясно, что лиса находится либо в доме №1, либо в доме №3. Но в каком?

Для начала, допустим, что лиса в доме №3. Тогда, что пьёт человек, курящий «Old Gold» и разводящий улиток? Т.к. вода и чай уже исключены на первых двух шагах и это не может быть сок (13) и молоко (9), то остаётся кофе, который пьёт житель зелёного дома (4). Следовательно, если лиса в доме №3, то в доме зелёного цвета живёт человек, курящий «Old Gold», разводящий улиток и пьющий кофе. Кто он? Это не норвежец (10), не украинец (5), не англичанин (2), не японец (14) и не испанец (3). Такого вариант быть не может, а значит, лиса находится в доме №1.

Шаг №4

Исходя из всех предыдущих размышлений, получается, что апельсиновый сок и кофе пьют в оставшихся домах №5 и №4. Не важно, в каком – что. Поэтому, назовём их просто «дом с соком» и «дом с кофе».

Где живёт человек, курящий «Old Gold» и разводящий улиток? Не в доме с соком, т.к. там живёт тот, кто курит «Lucky Strike» (13). Допустим, что он живёт в доме с кофе. Получается, что человек, курящий «Old Gold», разводящий улиток и пьющий кофе, живёт в зелёном доме (4). А этого, опять же, быть не может (руководствуемся рассуждениями из шага №3). Выходит, что человек, курящий «Old Gold» и разводящий улиток, живёт в доме №3.

Из всего это следует, что человек, курящий «Parliament», живёт в доме зелёного цвета, где любят кофе. А это – японец (14). Далее получается, что испанцем является человек, курящий «Lucky Strike», пьющий апельсиновый сок и держащий собаку. Размышляя таким же способом, получаем, что англичанин должен проживать в доме №3, который должен быть красного цвета. Исключая всё остальное, приходим к выводу, что испанец живёт в доме белого цвета.

Очевидно, что зебра находится в доме у японца.

Ответ на загадку Эйнштейна

Но здесь следует учесть один момент: в решении, которое мы представили, было предположено, что дом №1 находится с краю слева. Если представить, что дом №1 находится с краю справа, то ситуация немного изменится, но ответ будет тем же:

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

Другой вариант загадки Эйнштейна

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

В доме №1 проживает норвежец.
Англичанин живёт в доме красного цвета.
Дом зелёного цвета стоит слева от дома белого цвета, рядом с ним.
Датчанин любит чай.
Курящий «Marlboro», живёт рядом с тем, кто держит кошек.
Жилец жёлтого дома курит «Dunhill».
Немец курит «Rothmans».
Жилец центрального дома пьёт молоко.
Сосед курящего «Marlboro», пьёт воду.
Курящий «Pall Mall» разводит птиц.
Швед держит собак.
Норвежец живёт в доме рядом с домом синего цвета.
Тот, кто держит лошадей, живёт в доме синего цвета.
Курящий «Winfield», пьет пиво.
В доме зелёного цвета пьют кофе.

Вопрос: Кто из жильцов разводит рыбок?

Удачи вам в решении этой задачи!

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

Многие из нас слышали такую фразу о загадке Эйнштейна : “Лишь 2% людей смогут ее решить” . Это не совсем так, вернее это выражение нуждается в дополнении. Может быть и на самом деле лишь пятидесятая часть населения сможет ее решить, но без использования бумаги и ручки (либо вещей, которые их могут заменить). По сути для чистого решения этой задачи у нас в распоряжении должна быть лишь наша память и логика . Если же использовать какие-либо дополнительные способы запоминания (ручка, бумага), то загадка теряет львиную долю сложности – но мне почему то ломать мозг не хочется, поэтому при первом прочтении этой загадки я сразу схватился за листок)

Единой версии загадки Эйнштейна сейчас нет, существует множество ее вариаций. Я приведу в пример самую знаменитую версию Загадки Эйнштейна.

Условия Загадки Эйнштейна.

На улице – пять домов .
У каждого дома – свой цвет .
В каждом доме - живет 1 человек .
У каждого человека – своя национальность .
Каждый предпочитает курить уникальную марку сигарет, пить свой напиток и содержать животных.

Ну что, со вступлением закончили – теперь перейдем к подсказкам (ну просто офигеть какие простые подсказки )

Норвежец живёт в первом доме.
Англичанин живёт в красном доме.
Зелёный дом находится слева от белого , рядом с ним.
Датчанин пьёт чай .
Тот, кто курит Marlboro , живёт рядом с тем, кто выращивает кошек .
Тот, кто живёт в жёлтом доме, курит Dunhill .
Немец курит Rothmans .
Тот, кто живёт в центре , пьёт молоко .
Сосед того, кто курит Marlboro , пьёт воду .
Тот, кто курит Pall Mall , выращивает птиц .
Швед выращивает собак .
Норвежец живёт рядом с синим домом.
Тот, кто выращивает лошадей , живёт в синем доме.
Тот, кто курит Winfield , пьет пиво .
В зелёном доме пьют кофе .

Вопрос же к загадке Эйнштейна звучит следующим образом: Кто разводит рыбок? Ха! подумаете Вы, ан нет; не все так просто. Пока мы будем определять кто разводит рыбок мы чуть ли не узнаем биографию каждого участника головоломки, и самым последним действием все таки сможем определить кто же все таки этот любитель рыбок . (нет бы сделали вопрос: в каком доме живет Норвежец? (:)

Ну что? собрали волю в кулак, схватили ручку с листочком (или может попробуете в уме?) и вперед: за ответом на загадку Эйнштейна .

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

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

Идея

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

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

Норвежец живёт в первом доме.
Англичанин живёт в красном доме.
Зелёный дом находится слева от белого, рядом с ним.
Датчанин пьёт чай
Тот, кто курит 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 и да, мьсе действительно знает толк в извращениях:)