DEV Community 👩‍đŸ’ģ👨‍đŸ’ģ

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.

Create account Log in
Cover image for AoC 2015 - Day 13 - Permutate!
Jules
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:

Screenshot of Advent of Code 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']
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

Part 2 just adds to the complexity a little:

Screenshot of Advent of Code puzzle

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
Enter fullscreen mode Exit fullscreen mode

We then ensure that we are counted in the permutations:

people.append('me')
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)

Let's hear from your organization

Create an Organization and start sharing content with the community on DEV.