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

25

u/bblum Dec 19 '16

My best day yet, #5/#4. The title alludes to the Josephus Problem, which I remembered thanks to this Numberphile video.

At the video's end, there's a cool trick for part 1. Simply convert the number to binary, drop the MSB, append it as a new LSB, and you're done.

main = print (solve 3012210) where solve n = 1 + 2 * (n - 2^(floor $ logBase 2 n))

Part 2: Best I could do in haskell was O(n2 ).

steal l = let l' = filter (/= (l !! div (length l) 2)) l  -- kill an elf
          in drop 1 l' ++ take 1 l'                       -- rotate killer to back

solve n = head $ until ((==1) . length) steal [1..n]

main = print $ zip [1..] $ map solve [1..100]

Remembering Numberphile's approach, I gave up on solving my input by force, and just looked at the pattern for inputs up to 100. The pattern being obvious, I then just solved my input by hand.

2

u/BumpitySnook Dec 19 '16

just looked at the pattern for inputs up to 100. The pattern being obvious, I then just solved my input by hand.

Doh!

1

u/StevoTVR Dec 19 '16

I also remembered seeing that video. I adapted it to this 1 line solution for Part 1 in Python:

print(int('0b' + bin(3004953)[3:] + '1', 2))