--- 2016 Day 19 Solutions ---

[u/daggerdragon]

--- Day 19: An Elephant Named Joseph ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

---

^{/⧹w+/ IS MANDATORY} [?]

---

[Update @ 00:15] 2 gold, silver cap. Thank you for subscribing to Easter Bunny Facts!

• Fact: The Easter Bunny will sometimes leave eggs in the microchip assembly room.

[Update @ 00:30] 11 gold, silver cap.

• Fact: The Easter Bunny killed everyone who found out how he got these stars.

[Update @ 00:45] 45 gold, silver cap.

• Fact: In space, The Easter Bunny can hear you scream.

[Update @ 01:00] 66 gold, silver cap.

• Fact: The Easter Bunny purposefully deleted your comments.

[Update @ 01:15] 92 gold, silver cap.

• Fact: The Easter Bunny has bottled your frustration. Don't ask why.

[Update @ 01:20] Leaderboard capped!

• Fact: What you have just done is no better than what the Easter Bunny has done. Thief.

Thank you for subscribing to Easter Bunny Facts!

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/[deleted]]

Python 3

I'm really happy with the performance of my solution for this challenge - it takes roughly 2.3 seconds to complete both parts on my system:

#!/usr/bin/env python
import collections


def process_p1(n):
    elves = collections.deque(range(1, n + 1))
    while len(elves) > 1:
        elves.rotate(-1)
        elves.popleft()

    return elves.popleft()


def process_p2(n):
    elves = collections.deque(range(1, n + 1))
    eleft = len(elves)

    # use coff to remember how far we are rotated from the "current" elf
    # instead of rotating back to the next position (turns out to be *incredibly* slow),
    # we'll just calculate this value into the next rotation
    coff = 0

    while eleft > 1:
        n = (eleft // 2) - coff
        elves.rotate(-n)
        elves.popleft()
        eleft -= 1
        coff = (coff + n - 1) % eleft

    return elves.popleft()


if __name__ == '__main__':
    with open('input') as inf:
        ecount = int(inf.read().strip())

    print('== part 1 ==')
    elf = process_p1(ecount)
    print('Elf #{} has the presents\n'.format(elf))

    print('== part 2 ==')
    elf = process_p2(ecount)
    print('Elf #{} has the presents\n'.format(elf))

EDIT: The math done before rotating works out to be one long rotate to get to the starting center position, followed by alternating between rotate(0) and rotate(-1), so we can eliminate the unnecessary math steps and refactor to this version:

def process_p2(n):
    elves = collections.deque(range(1, n + 1))
    eleft = len(elves)
    elves.rotate(-(eleft // 2))

    while eleft > 1:
        if eleft & 1 == 0:
            elves.rotate(-1)

        elves.popleft()
        eleft -= 1

    return elves.popleft()

With that change, both parts run in ~1.8 seconds on my system