Solution for Advent of Code 2016 - Day 19: An Elephant Named Joseph

Link to the puzzle text

Part 1

In this puzzle, we should simulate a gift distribution system. Elves are sitting in a circle with one gift each. The exact number of initial elves is the input given. Starting with elf numbered 1, each elf takes all the gifts from the elf sitting left from him. Elves without any gifts left leave the circle. This is repeated until only one elf remains. The number of this elf is the required answer.

We can solve this by simply following the instructions. We start with a list of elves still in the circle, numbered 1 to our input. Each elf takes the gifts left of him, so if we reach the start again, every second elf has been eliminated. We then just have to keep track if the last elf in the list eliminates the first one. This is the case with an odd number of elves currently in the list.

def solve_part_one(num_elves):
    elves = list(range(1, num_elves + 1))
    while len(elves) > 1:
        offset = len(elves) % 2
        elves = elves[::2]
        if offset:
            elves = elves[1:]
    return elves[0]

Part 2

In part 2. the elves take the gifts from the elf across the circle instead of the one left of them.

After simulating this process for several number of elves, a pattern became clear: For powers of 3 (3, 9, 27, 81, 243, ...) the last number wins. For numbers slighty larger, the winner increases by one. So for 85 (= 81 + 4) elves, number 4 wins. This pattern holds until the last power wins. From there one, the increase is. So for 166 (= 81 + 81 + 4) elves, number 129 (81 + 2 * 4) wins. So we wrote an explicit formula and checked it against the brute-force simulation.

def solve_part_two(num_elves):
    i = 1
    while i * 3 < num_elves:
        i *= 3
    if num_elves > 2 * i:
        return 2 * num_elves - 3 * i
    return num_elves - i

Link to my solutions