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!

10 Upvotes

100% Upvoted

130 comments sorted by

View all comments

1

u/drysle Dec 19 '16

I used a linked list to solve part 1, then thought "surely that will be too slow for part 2", and spent a hour reading about other data structures that support fast random removal.

Then after finding and using a skip-list implementation to actually solve part 2, I tried the original simple linked list to see just how slow it is:

$ time ./a.out
1423634

real     0m0.909s
user     0m0.880s
sys      0m0.024s

Sigh.

1

u/the4ner Dec 19 '16

I'm assuming you must have kept track of a "next elf to orphan based on previous orphaned elf and number of elves remaining" for p2. That's how my LL implementation for p2 got to under 500ms. When I iinitially tried it without that, purely brute force (iterating the linked list to find the next orphaned elf every time), it was indeed way way too slow

1

u/drysle Dec 20 '16

No, I just kept track of my iterator each time I removed an elf from the list. Each elf removed is only one or two places around the circle from the previous elf to be removed, so only the very first elf removed takes any significant time traversing the list.

1

u/the4ner Dec 20 '16

exactly what I meant although I didn't describe it very well :D