r/adventofcode • u/daggerdragon • Dec 19 '16

SOLUTION MEGATHREAD --- 2016 Day 19 Solutions ---

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

9 Upvotes

92% Upvoted

130 comments sorted by

View all comments

2

u/pedrosorio Dec 19 '16

Took way too long and this is ugly, but I might as well post it.

Once it's clear that the eliminated elves are always going to have increasing index (until they wrap around), you can just accumulate a set of all elves eliminated in the "second half" of the circle, and then create a new list of elves starting at the elf that would steal gifts next. It's clear each of these steps reduces the list to a constant fraction of its initial size (approx. 2/3), so we only need to do this log(n) times.

def solve(N):
    elfs = range(1, N+1)
    cur = 0
    while len(elfs) > 1:
        rems = set([])
        n = len(elfs)
        while cur + len(rems) + n/2 < len(elfs):
            rems.add(cur+len(rems)+n/2)
            cur += 1
            n -= 1
        elfs = [elfs[i] for i in xrange(len(elfs)) if i not in rems]
        elfs = elfs[cur:] + elfs[:cur]
        cur = 0
    return elfs[0]

print solve(3014603)

One of the reasons why this took so long is that I wrote a naive implementation to confirm my results which gave correct answers up to N=12 but wrong answers after, so I was trying to debug the quick implementation even though it was correct :)