DEV Community đŠâđģđ¨âđģ is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Jules

Posted on

AoC 2015 - Day 13 - Permutate!

Day 13 is all about happiness, and there's nothing wrong with that! Here's the puzzle:

Typical lines of puzzle input look like this:

```Mallory would lose 99 happiness units by sitting next to George. Carol would gain 33 happiness units by sitting next to Frank.```

There is enough data to work out the happiness gained (or lost) by any two people sitting next to each other.

For Python programmers, this puzzle relies heavily on the Itertools library, and one of its functions, `permutations()`, which will give us every possible seating order. We can then work out which seating order will make everyone the least miserable most happy. đ

First, though, we need to load the data. I am going to use two Python data types: dictionary (for happiness) and list (for people). For the two lines of puzzle input above, we should end up with:

``````happiness{('Mallory', 'George'): -99,
('Carol', 'Frank'): 33}
people['Mallory', 'George', 'Carol', 'Frank']
``````

Each entry in `happiness{}` is keyed on the two names in the 'relationship', with an integer value showing the change in happiness. Here's how I parsed the puzzle input:

``````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])
``````

A strength of Python is the ability to chain statements together, so we can handle two `replace()` calls in one line of code. The first takes the word 'lose' from the input, and makes it a minus sign on the word '99'. Then we simply throw 'gain ' away, so 'gain' and 'loss' statements end up with the same number of words. The `[:-2]` slices off the last two characters of the string, the full-stop and the line-feed. So we end up with this:

`Mallory would -99 happiness units by sitting next to George`

We then call `split()`, which uses white space to split a string if we don't specify something else. So we end up with:

`['Mallory', 'would', '-99', ... etc. ..., 'George']`

We can then pick off bits of the split string to populate `happiness{}` and `people[]`, with `[-1]` being a Pythonic way of referencing the last item in a list.

Even though we're only storing the 'left' person in each line of data, we'll still end up with more entries in the `people` list than we need, but we can deal with that now:

``````people = list(set(people))
``````

Items in sets must be unique, so a quick way to drop duplicates from a list is to cast them to a set. We then need to cast it back to a list, because of our next line of code:

``````perms = permutations(people)
``````

The `permutations()` function takes an iterable, and sets are not iterable. The output is an iterable object that contains every permutation of the input. So if we ran `perms = permutations([1, 2, 3])`, we would expect to see all six valid permutations:

``````(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
``````

It is also possible to pass a second parameter to `permutations()`, which limits the size of each permutation. So if we passed 2 as the second parameter in the above example (`perms = permutations([1, 2, 3], 2)`), we would expect the following output:

``````(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
``````

We now go through every possible combination, working out the net happiness. Note that if I find Mallory next to George, I need to check what effect Mallory has on George, and vice versa. We also need to remember that we're dealing with a round table: the person at the end of the permutation is also sitting next to the person at the beginning! Since we'll end up calculating maximum happiness in Part 2, I ended up with this code in its own function:

``````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
``````

The variable names are on the long side, but I prefer this if it makes the code easier to read.

Calling this function generates the solution to Part 1:

``````print(get_max_happiness(perms))
``````

Part 2 just adds to the complexity a little:

All we need to do is add ourselves into the mix. First, we need to add ourselves to the `happiness{}` dictionary, in a way that shows it makes no difference to anyone's happiness who we sit next to:

``````for person in people:
happiness[(person, 'me')] = 0
happiness[('me', person)] = 0
``````

We then ensure that we are counted in the permutations:

``````people.append('me')
``````

And then it's as easy as generating a new set of permutations including 'me', and calculating the best permutation:

``````perms = permutations(people)
print(get_max_happiness(perms))
``````

The first thing you notice is that Part 2 takes much longer to run. Why is that?

Well, as you saw above, when you have three items, there are six possible permutations. When choosing the first item in the permutation, there are three possibilities. When choosing the second item, there are two remaining possibilities. And having picked the first two, we are left with one possibility. So the number of permutations is `3 x 2 x 1 = 6`, or '3 factorial', or simply '3!'.

In the puzzle input, there are 8 people in total:

`8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 8! = 40,320`

When we add an extra person to the mix, we are generating 9 times as many permutations:

`9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 9! = 362,880`

There doesn't seem to be any obvious way of speeding up the code, either, and there is a lot of brute force in the Python code in the Reddit megathread. It seems you simply have to plough through every permutation.