В настоящий момент снова повторяется так называемая «загадка Эйнштейна», загадка, которую он якобы описал как слишком сложную для решения 98% населения.
Также известная как головоломка «Зебра», она включает в себя определение национальности жителей улицы с домами, цвета этих домов, а также того, какие напитки, сигары и погладить предпочитает обитатель.
В ряд пять домов пяти разных цветов. В каждом доме живет человек разной национальности. Пять владельцев пьют определенный напиток, выкуривают сигару определенной марки и держат определенного питомца.
У владельцев нет одного и того же питомца, они не курят сигары одной марки или пьют один и тот же напиток.
Другие факты:
- Британец живет в красном доме.
- Швед держит собак как домашних животных.
- Датчанин пьет чай.
- Зеленый дом находится слева от белого дома.
- Хозяин зеленого дома пьет кофе.
- Владелец, который курит Pall Mall, разводит птиц.
- Хозяин желтого дома курит "Данхилл".
- Хозяин, живущий в центральном доме, пьет молоко.
- Норвежец живет в первом доме.
- Владелец, который курит Blends, живет рядом с тем, кто держит кошек.
- Владелец, который держит лошадь, живет рядом с тем, кто курит Dunhill.
- Владелец, который курит Bluemasters, пьет пиво.
- Немец курит принца.
- Норвежец живет рядом с синим домом.
- Владелец, который курит Blends, живет рядом с тем, кто пьет воду.
Вопрос в том, кому принадлежит рыба?
Конкретные атрибуты взаимозаменяемы, но головоломка всегда сохраняет две ключевые особенности: количество возможных комбинаций огромно, и есть только одна единственная допустимая комбинация, которая удовлетворяет всем данным фактам.
Наивное решение
В этой головоломке пять наборов из пяти вариантов. Комбинаторно это дает почти 25 миллиардов комбинаций, которые можно подобрать на современном компьютере.
5! ×5! ×5! ×5! × 5! = 24,883,200,000
В наивном решении все, что нам нужно сделать, это создать все возможные комбинации цвета, национальности, сигары, домашнего животного и напитка, а затем опробовать их в каждом доме на улице. Каждый раз, когда мы создаем новую улицу, мы проверяем конфигурацию на основе известных нам фактов - если какие-либо факты опровергаются, мы переходим к следующей комбинации.
В библиотеке Ruby Array есть удобный метод, который поможет нам - перестановка массива #.
Это позволяет нам вложить 5 петель, чтобы создать каждую допустимую улицу.
Теперь нам нужно подумать о том, как мы проверяем факты, изложенные в головоломке.
Если мы предположим, что порядок каждого набора подразумевает номера домов, тогда это делает наш код довольно простым, поскольку дом, в котором появляется каждый вариант (цвет, домашнее животное, сигара и т. Д.), Соответствует его месту в массиве (при условии, что мы индексируем от единицы, а не от нуля. ) т.е.
Теперь нам нужно подумать, как проверить, подтверждаются ли факты. Простейший вид фактов в головоломке - это утверждение позиционной импликации, т. Е.
Хозяин, живущий в центральном доме, пьет молоко.
or
Норвежец живет в первом доме.
Мы можем легко проверить это с помощью теста индекса массива:
Следующий тип фактов объединяет два варианта в один дом, т. Е.
Немец курит принца.
С точки зрения логики предикатов, мы можем определить это правило как A → B или «A подразумевает B». Это означает, что если выкуриваемая в определенном доме сигара - «принц», то национальность владельца - немец (и рефлекторно B → A, поскольку не может быть дубликатов).
Вместо того, чтобы жестко кодировать это, давайте определим метод #implies?, который возвращает true или false в зависимости от того, есть ли в доме на улице жильцы, чьи национальность - немец, обитатель, который курит сигары Prince.
Теперь мы можем определить все факты подразумевает? следующим образом:
Следующий тип фактов является расширением факта #implies?:
Зеленый дом находится слева от белого дома.
Это простой поворот # подразумевает? проверка фактов. Поскольку мы представляем позицию как порядок массивов, мы можем указать это следующим образом:
Есть еще третий тип фактов, который основывается на этом, а именно:
Хозяин, который держит лошадь, живет рядом с тем, кто курит Dunhill.
Это означает, что курильщик Dunhill живет либо слева от владельца лошади, либо справа. Мы можем выразить это так:
Ok! Теперь у нас есть все инструменты, необходимые для проверки известных фактов. Соберем все вместе.
В конце концов (где-то между минутами и часами) это выдаст правильную комбинацию. Если вы все еще хотите выяснить ответ самостоятельно, сейчас самое время добавить этот пост в закладки на потом ;-)
Прокрутите страницу до ответа…
= ›[[: Желтый,: синий,: красный,: зеленый,: белый], [: норвежский,: датский,: британский,: немецкий,: шведский], [: кошки,: лошади,: птицы,: рыба, : dogs], [: water,: tea,: milk,: coffee,: beer], [: dunhill,: blends,: pall_mall,: prince,: bluemasters]]
Это означает:
- Дом 1 желтый. Владелец - норвежец, курит Dunhill, пьет воду и держит кошек.
- Дом 2 синий. Владелец - датчанин, курит бленды, пьет чай и держит лошадей.
- Дом 3 красный. Хозяин - британец, курит Pall Mall, пьет молоко и держит птиц.
- Дом 4 зеленый. Владелец немец, курит принца, пьет кофе и держит рыбу.
- Дом 5 белый. Владелец швед, курит Bluemasters, пьет пиво и держит собак.
Более быстрая реализация!
Итак, у нас есть строительные блоки для решения головоломки Эйнштейна, но алгоритм очень неэффективен. Поскольку он использует вложенные циклы, вы можете перебирать все внутренние циклы, прежде чем приступить к попытке новой внешней комбинации, т.е. если перестановка цветов неправильная, вам нужно перебрать национальности, домашних животных, напитки и сигары, прежде чем переключаться на новый.
Поскольку верна только одна перестановка, это означает, что у вас есть шанс 119/120 начать с неправильного порядка и выполнить в процессе целую кучу бессмысленных тестов.
Что касается наихудшего сценария, нам нужно будет перебрать все 24 миллиарда комбинаций, прежде чем достичь правильной в самом конце. На самом деле, вы встретите комбинацию в среднем где-то посередине, так что вы пройдете в среднем 12 миллиардов тестов, прежде чем получите ответ.
Конечно, мы можем лучше ...
Что, если бы мы могли сбрасывать со счетов плохие перестановки на каждом уровне итерации? Мы значительно сократили проблемное пространство.
Таким образом, мы значительно сократили проблемное пространство с 14 400 до 2880 - это на 80% меньше!
Давайте попробуем это с другими фактами, разместив их тесты на правильном уровне цикла.
Обратите внимание на то, что мы используем #shuffle при настройке параметров. Без этого мы бы получали одинаковое количество циклов каждый раз, когда запускали решающую программу, поэтому приятно видеть, что она работает в разумный промежуток времени, независимо от того, каков начальный порядок перестановок.
Итак, теперь у нас есть решатель, который находит правильное решение примерно в 55 000 тестов. Это всего 0,0002% от количества тестов, необходимых наивному решателю!
Это стабильно работает на моем ноутбуке примерно за пятую долю секунды. Добавьте код, чтобы он отображался красиво, и мы почти закончили с нашим умным решением.
Кто-нибудь в гольф?
Поскольку мы помешаны на эффективности, как насчет того, чтобы найти способы, как сделать наше решение сверхмалым? Приведенное выше решение с методами отображения кода красиво работает примерно на 2837 символов. Как мы можем это уменьшить?
Краткие имена методов
Мы можем сэкономить много места, сократив имена методов и аргументы до отдельных букв.
Более простое представление варианта
Содержание наших вариантов не имеет значения, если все они уникальны. Также можно использовать целые числа
Слияние left_of? с подразумевается?
Методы #left_of? и #implies? практически идентичны по своей реализации, поэтому мы можем объединить их в один и тот же метод.
Теперь мы можем отказаться от метода #left_of? и использовать вместо него i (a, b, c, d, 1).
Используйте #map вместо #each
Мы используем метод #each для перебора коллекций параметров в пяти местах, но метод Ruby #map также выполняет итерацию (и применяет блок к каждому элементу, возвращая новую коллекцию результатов). Это экономит нам несколько персонажей.
тест || следующий
Вместо того, чтобы говорить next if для каждого теста, мы можем добавить к нему суффикс «|| следующий". Таким образом, если тест возвращает false, Ruby оценивает обратную сторону || оператор (ИЛИ) и переходит к следующему элементу в итераторе.
Псевдоним метода #permutation
Мы используем метод перестановки пять раз. Всего 55 символов. Мы можем обернуть это в нашу собственную def и вернуть еще несколько байтов.
Используйте фигурные скобки
Вместо do..end мы можем использовать {} для разграничения наших блоков.
Удалите все ненужные пробелы
Наконец, мы можем удалить все пробелы, если они не являются частью вызова метода.
546 символов
Благодаря всем этим оптимизациям мы уменьшили наш код более чем на 80%!
Довольно здорово! И это загадка Эйнштейна о том, что для меня сделано.
Полный исходный код на Github: https://github.com/seanhandley/einstein
РЕДАКТИРОВАТЬ: Большое спасибо за все комментарии! Многие люди указали, что вам не нужен код для решения этой проблемы ... и это правда. Сначала я сделал это на бумаге и ручке, а потом подумал: «Было бы весело решить эту проблему с помощью кода!». Разгадывать эту головоломку в автономном режиме определенно очень приятно, поэтому не позволяйте всему коду отговаривать вас от попытки.
