Как решать задачу эйнштейна

Разгадка загадки Эйнштейна
http://akmych.org/various/einstein.html

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

Итак, у нас есть 25 позиций, которые необходимо заполнить следующими данными:

По сути, нам надо заполнить вот такую табличку:

Из подсказок сразу же заполняем ряд ячеек таблицы:

Раз англичанин живёт в красном доме, значит, норвежец в красном жить не может. Равно норвежец не может жить в синем. Не может он жить и в белом, так как зелёный дом находится левее белового, а дом норвежца — самый левый. В зелёном он тоже жить не может, так как справа от зелёного белый дом, а справа от норвежца — синий. Значит, он живёт в жёлтом. Отсюда же делаем и вывод, что норвежец курит Данхилл.

Далее, раз зелёный дом находится левее белого, значит, у него номер либо 3, либо 4. Однако в третьем, среднем, доме пьют молоко, а в зелёном доме пьют кофе — значит номер зелёного дома = 4. Значит, белый дом у нас идёт под номером 5, а красный — под номером 3. Здесь же живёт англичанин. Кофе пьют в 4 доме.

Далее, раз немец курит Мальборо, то он не курит Филипп Моррис, и потому не пьёт пиво. Не пьёт он и молоко, которое пьёт англичанин. Не пьёт и чай — это делает датчанин. Значит, немец пьёт либо воду, либо кофе. Норвежец не может пить пиво (он курит другие сигареты), молоко (не англичанин), кофе (живёт не в зелёном доме), чай (не датчанин). Значит норвежец пьёт воду, а потом немец пьёт кофе, и живёт в зелёном доме. Плюс не забываем, что немец курит Мальборо. И раз воду у нас пьёт норвежец, то его сосед (второй дом) курит Ротманс.

Раз швед у нас выращивает собак, то он не может жить во втором доме (там выращивают лошадей), значит он живёт в пятом доме (белом). Значит во втором доме живёт датчанин, который пьёт чай.

Раз курильщик Пелл Мелл выращивает птиц, то это не швед, а значит — англичанин. Следовательно, швед курит Филипп Моррис и пьёт пиво.

И теперь у нас осталась последняя подсказка:

Ротманс курит датчанин, что живёт во втором доме. Справа от него живёт англичанин, который выращивает птиц, значит, второй сосед датчанина (слева), норвежец, этих кошек и выращивает. А потом рыбок выращивает немец. Ответ найден.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

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

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

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

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

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

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

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

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

Пустая строка, автомат ’empty’:

Звездочка, автомат ‘star’:

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

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

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

Правила 5, 9 и 12 являются составными. Я определяю каждую часть отдельно, а потом делаю объединение. Скрипт concat.sh всего лишь делает конкатинацию автоматов, переданных в аргументах:

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

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

Где intersect.sh — пересечение автоматов в аргументах.

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

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

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

Заключение

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

ps и да, мьсе действительно знает толк в извращениях 🙂

Источник

Задача Эйнштейна

Учёный утверждал, что только 2% людей могут решить в уме эту задачу (так говорят в Википедии).

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

Наша задача звучит так:

В целях ясности следует добавить, что каждый из пяти домов окрашен в свой цвет, а их жители — разных национальностей, владеют разными животными, пьют разные напитки и майнят разные криптовалюты. Ещё одно замечание: в утверждении 6 «справа» означает справа относительно вас.

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

Чтобы не было спорных моментов, добавим следующее:

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

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

Разбираемся с первым домом

В п. 10 явно сказано, что норвежец живёт в первом доме, а если добавить сюда п. 15 (норвежец живёт рядом с синим домом), то становится понятно, что второй дом — синий.

Теперь разберёмся с цветом первого дома. Мы уже знаем, что рядом с первым домом стоит синий дом, а значит это единственный дом, который стоит рядом с первым. Из пункта 6 (зелёный дом стоит сразу справа от белого дома) следует, что первый дом не может быть зелёным или белым — зелёный и белый должны стоять рядом, а у нас рядом с первым домом стоит синий. Остаются красный или жёлтый. Но в красном доме живёт англичанин — так написано в п. 2, поэтому остаётся только жёлтый. Первый дом — жёлтый.

Смотрим, что говорят нам условия задачи про жёлтый дом:

п. 8 — в жёлтом доме майнят Ethereum;

п. 12 — в доме по соседству с тем, в котором держат лошадь, майнят Ethereum.

Но у нас рядом с домом, где майнят Ethereum, стоит только второй дом, поэтому лошадь держат во втором доме.

Переходим к напиткам. Мы уже знаем, что в первом жёлтом доме живёт норвежец, который майнит Ethereum. Вот как это влияет на условия:

Поэтому единственное, что остаётся пить норвежцу, — это вода. Отлично, мы нашли ответ на первый вопрос. Не забудем занести всю найденную информацию в таблицу:

Всё о втором доме

Начнём с криптовалюты.

Мы точно знаем, что это не Ethereum, потому что её майнит норвежец в первом доме. А ещё, раз у жильца синего дома есть лошадь, то он точно не майнит Bitcoin — в п. 7 написано, что тот, кто майнит Bitcoin, разводит улиток. Давайте поработаем с предположениями и проверим, насколько верное каждое из них.

Допустим, что во втором доме майнят IOTA. По п. 13 (тот, кто майнит IOTA, пьёт апельсиновый сок) жилец пьёт апельсиновый сок, а это значит, что тут живёт не украинец, потому что он пьёт чай (п. 5). Это также не англичанин, который живёт в красном доме (п. 2), и не испанец, потому что по п. 3 у испанца есть собака. Японец тоже тут жить не может, потому что по п. 14 японец майнит Monero, а не IOTA. Норвежец же, напомним, живёт в первом доме. Получается, что во втором доме никто не живёт, а такого не может быть, следовательно, наше предположение, что во втором доме майнят IOTA, неверное.

Идём дальше и предположим, что во втором доме майнят Monero, а значит, из п. 14 видно, что тут живёт японец (японец майнит Monero). Поэтому во втором доме не пьют чай, потому что чай пьёт украинец (п. 5), не пьют кофе, потому что кофе пьют в зелёном доме (п. 4). А ещё здесь не пьют молоко — молоко пьют в третьем доме (п. 9), и не пьют апельсиновый сок, потому что сок пьёт любитель IOTA (п. 13). А раз вода уже занята норвежцем, то получается, что во втором доме ничего не пьют. Такого не может быть, а значит, наше предположение, что во втором доме майнят Monero, неверное. Мы выяснили, что там не майнят Ethereum, Bitcoin, IOTA и Monero. Остаётся только Stellar — её и майнят во втором доме.

Давайте выясним национальность, зная название криптовалюты. Это не англичанин, который живёт в красном доме (п. 2), и не испанец с собакой (п. 3), потому что во втором доме держат лошадь. Ещё это не японец, который майнит Monero (п. 14), и не норвежец из первого дома. Получается, что во втором доме живёт украинец, а согласно п. 5 украинец пьёт чай.

Занесём новые данные в таблицу:

Где живёт лиса

Исходя из п. 11 (сосед того, кто майнит Stellar, держит лису), мы понимаем, что раз Stellar майнят во втором доме, то лиса живёт или в первом, или в третьем доме.

Допустим, что лиса — в третьем доме. Теперь делаем внезапный поворот и зададимся вопросом: а что тогда пьёт человек из п. 7, который разводит улиток и майнит Bitcoin? Он не пьёт сок, потому что сок пьёт любитель IOTA (п. 13), и молоко — его пьют в третьем доме, где, как мы предполагаем, держат лису. Вода и чай уже заняты на предыдущих этапах. Остаётся только кофе, который пьют в зелёном доме (п. 4).

А раз так, то получается, что в зелёном доме живёт человек, который разводит улиток, майнит Bitcoin и пьёт кофе. Он точно не норвежец или украинец — мы это выяснили раньше. И это точно не англичанин, который живёт в красном доме (п. 2), не испанец, у которого собака (п. 3), и не японец, который майнит Monero (п. 14). Мы исключили все национальности, а такого не может быть, поэтому наше исходное предположение о том, что лиса живёт в третьем доме — неверное.

Получается, что лиса живёт в первом доме. Добавим это в табличку:

Третий дом

У нас осталось два свободных напитка — кофе и апельсиновый сок, которые пьют в четвёртом и пятом доме.

Тот, кто майнит Bitcoin и разводит улиток, не живёт в доме, где пьют сок, потому что его пьёт любитель IOTA (п. 13). Значит, делаем предположение, что любитель улиток живёт в доме, где пьют кофе, а по п. 4 кофе пьют в зелёном доме. А мы только что разобрали в разделе про лису именно ту ситуацию, когда жилец зелёного дома разводит улиток и пьёт кофе. Тогда мы пришли к выводу, что это невозможно, а значит, любитель улиток не может пить кофе или сок, поэтому он не живёт в четвёртом или пятом доме.

Получается, что любитель улиток, который майнит Bitcoin, живёт в третьем доме.

Четвёртый и пятый дома

В зелёном доме пьют кофе (п. 4), а любитель IOTA пьёт сок (п. 13), поэтому он не может жить в зелёном доме. Получается, что в зелёном доме майнят Monero, а раз так, то это — японец (п. 14).

Это означает, что в оставшемся доме пьют сок и майнят IOTA, и дом этот на 3-м или на 4-м месте (по п. 6 — зелёный дом стоит сразу справа от белого дома). Допустим, в третьем доме живёт испанец, у которого должна быть собака (п. 3), но в таблице в третьем доме уже есть улитки, а значит, испанец с собакой живёт в четвёртом доме, и как раз именно он пьёт сок и майнит IOTA.

Третий дом методом исключения остаётся англичанину, а это значит, что третий дом — красный (п. 2). Получается, что у испанца белый дом.

Запишем всё в таблицу:

Зебра

У нас осталась одна незаполненная клетка в таблице, которая тоже методом исключения достаётся зебре.

Теперь мы можем ответить на вопросы по задаче: воду пьёт норвежец, а зебру держит японец.

Зачем я всё это прочитал?

В любом случае мы вас любим, а Эйнштейн мёртв, но дело его живо.

Источник