День 13 посвящен счастью, и в этом нет ничего плохого! Вот головоломка:
Типичные линии ввода головоломки выглядят следующим образом:
Mallory would lose 99 happiness units by sitting next to George.
Carol would gain 33 happiness units by sitting next to Frank.
Имеется достаточно данных, чтобы вычислить, сколько счастья приобрели (или потеряли) два человека, сидящие рядом друг с другом.
Для программистов Python эта головоломка в значительной степени опирается на библиотеку Itertools и одну из ее функций, permutations(), которая даст нам все возможные варианты рассадки. Затем мы можем определить, какой порядок рассадки сделает всех наименее наименее несчастными наиболее счастливым. 😉
Однако сначала нам нужно загрузить данные. Я собираюсь использовать два типа данных Python: словарь (для счастья) и список (для людей). Для двух строк головоломки, приведенных выше, мы должны в итоге получить:
happiness{('Mallory', 'George'): -99,
('Carol', 'Frank'): 33}
people['Mallory', 'George', 'Carol', 'Frank']
Каждая запись в happiness{} зависит от двух имен в «отношениях», а целочисленное значение показывает изменение счастья. Вот как я разобрал ввод головоломки:
with open('txt/day13.txt') as f:
for line in f:
line = line.replace('lose ', '-').replace('gain ', '')[:-2]
words = line.split()
happiness[(words[0], words[-1])] = int(words[2])
people.append(words[0])
Сильной стороной Python является возможность объединять операторы в цепочки, поэтому мы можем обработать два вызова replace() в одной строке кода. Первый берет слово ‘lose’ из входных данных и превращает его в знак минус на слове ’99’. Затем мы просто отбрасываем слово ‘gain’, так что утверждения ‘gain’ и ‘loss’ в итоге содержат одинаковое количество слов. [:-2] отрезает два последних символа строки, полный стоп и перевод строки. В итоге мы получаем следующее:
Mallory would -99 happiness units by sitting next to George
Затем мы вызываем split(), которая использует пробел для разделения строки, если мы не указали что-то еще. В итоге мы получаем:
['Mallory', 'would', '-99', ... etc. ..., 'George']
Затем мы можем выбрать кусочки разделенной строки для заполнения happiness{} и people[], причем [-1] — это питонический способ ссылки на последний элемент списка.
Несмотря на то, что мы храним только «левого» человека в каждой строке данных, в итоге в списке people будет больше записей, чем нам нужно, но с этим можно разобраться:
people = list(set(people))
Элементы в наборах должны быть уникальными, поэтому быстрый способ исключить дубликаты из списка — привести их к набору. Затем нам нужно привести его обратно к списку, потому что в следующей строке кода нам нужно будет сделать это:
perms = permutations(people)
Функция permutations() принимает итерируемый объект, а множества не являются итерируемыми. На выходе получается объект iterable, который содержит все перестановки входных данных. Поэтому, если бы мы выполнили perms = permutations([1, 2, 3]), мы бы ожидали увидеть все шесть допустимых перестановок:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Также можно передать второй параметр в permutations(), который ограничивает размер каждой перестановки. Так, если мы передадим 2 в качестве второго параметра в примере выше (perms = permutations([1, 2, 3], 2)), мы получим следующий результат:
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
Теперь мы перебираем все возможные комбинации, вычисляя чистое счастье. Обратите внимание, что если я найду Мэллори рядом с Джорджем, мне нужно проверить, какое влияние Мэллори оказывает на Джорджа, и наоборот. Мы также должны помнить, что имеем дело с круглым столом: человек в конце перестановки также сидит рядом с человеком в начале! Поскольку во второй части мы будем вычислять максимальное счастье, я вынес этот код в отдельную функцию:
def get_max_happiness(perms):
max_happiness = 0
for perm in perms:
this_happiness = 0
for person in range(len(perm)-1):
this_happiness += happiness[(perm[person], perm[person + 1])]
this_happiness += happiness[(perm[person + 1], perm[person])]
#Remember the end person is also sat next to the first person!
this_happiness += happiness[(perm[-1], perm[0])]
this_happiness += happiness[(perm[0], perm[-1])]
max_happiness = max( max_happiness, this_happiness)
return max_happiness
Имена переменных длинноваты, но мне это нравится, так код легче читать.
Вызов этой функции генерирует решение части 1:
print(get_max_happiness(perms))
Часть 2 лишь немного усложняет задачу:
Все, что нам нужно сделать, это добавить себя в микс. Сначала нам нужно добавить себя в словарь happiness{} таким образом, чтобы показать, что для счастья никого не имеет значения, с кем мы сидим рядом:
for person in people:
happiness[(person, 'me')] = 0
happiness[('me', person)] = 0
Затем мы убеждаемся, что нас учитывают в перестановках:
people.append('me')
А дальше все просто — генерируем новый набор перестановок, включающий «меня», и вычисляем лучшую перестановку:
perms = permutations(people)
print(get_max_happiness(perms))
Первое, что вы заметите, это то, что часть 2 выполняется намного дольше. Почему?
Как вы видели выше, когда у вас есть три элемента, существует шесть возможных перестановок. При выборе первого элемента в перестановке есть три возможности. При выборе второго элемента остаются две возможности. А выбрав первые два, мы остаемся с одной возможностью. Таким образом, число перестановок равно 3 x 2 x 1 = 6, или «факториал 3», или просто «3!».
Всего в головоломке 8 человек:
8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 8! = 40,320
Когда мы добавляем еще одного человека, мы генерируем в 9 раз больше перестановок:
9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 9! = 362,880
Похоже, что нет никакого очевидного способа ускорить код, и в коде на Python в мегатреде Reddit много грубой силы. Похоже, вам просто придется перебрать все варианты.