Решаем задачу Эйнштейна перебором (и программированием)

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

задача про наноботов → решили кодом

задача про безумного рекрутера → решили кодом

угадывание числа за 7 попыток → тоже написали код

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

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

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

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

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

Логика решения кодом

Так как мы будем перебирать все варианты, нам нужно сначала их подготовить. У нас есть такие списки:

При проверке мы будем использовать такой принцип:

номер элемента в списке соответствует номеру дома

Это значит, что если на первом месте в списке национальностей стоит англичанин, а в списке цветов на том же месте — жёлтый, то это значит, что англичанин живёт в жёлтом доме. Точно так же будем работать и с остальными списками.

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

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

Из пяти элементов списка можно составить 120 различных вариантов перестановок. Это значит, что у нас будет 120 вариантов комбинаций национальностей, 120 вариантов комбинаций цветов дома и так далее. Нам нужно проверить все комбинации всех пяти списков, а это значит, что мы сделаем пять вложенных циклов. В итоге общее число комбинаций равно 120⁵ = 24 883 200 000.

Вариантов перебора у нас очень много, поэтому писать код будем на Python — с таким количеством вариантов он будет работать быстрее, чем на JavaScript.

👉 Как установить и начать писать на Python

Готовим данные

Пройдёмся по условию и запишем все найденные параметры каждый в свой список:

# исходные данные
nation_orig = ['eng','isp','ukr','nor','jap']
color_orig = ['red','green','white','yellow','blue']
animal_orig = ['dog','horse','snail','fox','zebra']
drink_orig = ['coffee','tea','milk','juice','water']
money_orig = ['bitcoin','etherium','stellar','iota','monero']

Теперь для каждого списка нужно составить все варианты перестановок — те самые 120 вариантов каждого списка. Используем для этого встроенный модуль itertools — с его помощью можно получить все перестановки одной командой:

itertools.permutations()

Permutations работает так: если у нас есть набор чего-то типа (1, 2, 3), то permutations вернёт нам (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Проблема в том, что нам нужны списки, а результат будет в виде кортежа. Нам будет удобнее работать с кортежами, поэтому сразу переведём результат в нужный вид командой list():

# модуль для быстрого получения всех перестановок
import itertools

# получаем все перестановки всех списков
nation_perm = list(itertools.permutations(nation_orig))
color_perm = list(itertools.permutations(color_orig))
animal_perm = list(itertools.permutations(animal_orig))
drink_perm = list(itertools.permutations(drink_orig))
money_perm = list(itertools.permutations(money_orig))

Вам может быть интересно:

Задача ЭйнштейнаОптимизация кода: ускоряем работу в двести тысяч раз6 проверенных способов для измерения скорости программы на Python

Проверяем условия

Нам нужно проверить сразу 15 условий для каждой комбинации. Чтобы было проще, вынесем проверку в отдельную функцию. На вход она получит текущие варианты всех списков, поэтому сразу укажем их как входные параметры:

# выполняем все проверки, заданные в условии
def all_check(nation, color, animal, drink, money):

Разберём все проверки на трёх условиях, а остальные сделаем по аналогии.

Англичанин живёт в красном доме. Мы договорились, что индексы элементов у нас отвечают за номера домов. Для проверки первого условия нам нужно посмотреть, совпадает ли индекс национальности с индексом цвета. Для этого используем команду .index() — она вернёт индекс элемента в списке. В итоге проверка этого условия на Python будет выглядеть так:

if nation.index(‘eng’) == color.index(‘red’):

В центральном доме пьют молоко. Элементы списка нумеруются с нуля: 0,1,2,3,4. Получается, средний дом — это дом с индексом 2. Проверим, стоит ли молоко на этой позиции:

if drink.index(‘milk’) == 2:

Сосед того, кто майнит Stellar, держит лису. Сосед — это значит, что индекс его дома на единицу больше или меньше соседнего. При этом нам неважно, с какой стороны сосед — слева или справа, нас устроит любой вариант. Получается, что мы можем выбрать или один вариант, или другой. Зная это, составим такую проверку:

(money.index(‘stellar’) == animal.index(‘fox’) – 1 or money.index(‘stellar’) == animal.index(‘fox’) + 1)

Теперь используем эти принципы, чтобы составить все 14 проверок из условия задачи. В конце сразу добавим вывод найденной комбинации, если все проверки пройдут успешно:

# выполняем все проверки, заданные в условии
def all_check(nation, color, animal, drink, money):
    # проверяем все условия сразу
    if (nation.index('eng') == color.index('red') 
        and nation.index('isp') == animal.index('dog')
        and color.index('green') == drink.index('coffee')
        and nation.index('ukr') == drink.index('tea')
        and color.index('green') - 1 == color.index('white')
        and money.index('bitcoin') == animal.index('snail')
        and color.index('yellow') == money.index('etherium')
        and drink.index('milk') == 2
        and nation.index('nor') == 0
        and (money.index('stellar') == animal.index('fox') - 1 or money.index('stellar') == animal.index('fox') + 1)
        and (animal.index('horse') == money.index('etherium') - 1 or animal.index('horse') == money.index('etherium') + 1)
        and money.index('iota') == drink.index('juice')
        and nation.index('jap') == money.index('monero')
        and (nation.index('nor') == color.index('blue') - 1 or nation.index('nor') == color.index('blue') + 1)):
        # выводим найденный результат    
        print('✅✅✅')
        print(color)
        print(nation)
        print(drink)
        print(money)
        print(animal)

Организуем циклы

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

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

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

# перебираем все комбинации по очереди
for n in range(120):
    print(n)
    for c in range(120):
        for a in range(120):
            for d in range(120): 
                for m in range(120):
                    # и проверяем, выполнились ли все условия задачи
                    all_check(list(nation_perm[n]), list(color_perm[c]), list(animal_perm[a]), list(drink_perm[d]), list(money_perm[m]))

Запускаем код

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

Когда программа закончила работать, посмотрим вывод в терминале — появилось там решение или нет:

Если мы сравним найденное решение с тем, что мы получили с помощью выкладок, то увидим, что они полностью совпадают:

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

Что дальше

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