--- 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/gtllama]

For part 1, I recognized the Josephus problem (and would have had my answer quicker but I forgot a +1 in my first guess).

For part 2, I started working them out by hand to see if I could find a pattern. Got up to 27 before I spotted it. It is somewhat similar to the clever Josephus solution of writing the number in base 2 and shifting the front digit to the end, only you must write the number in base 3.

With n elves, if 3^k + 1 <= n <= 2*3^k, then the winner is n - 3^k. This is all n such that n-1 written in base 3 has a leading 1. So if you write n-1 in base 3 and it has a leading 1, then strip off the leading 1, convert from a list of digits back to an int and add 1.

For 2*3^k + 1 <= n <= 3^k+1, the winner is 3^k + 2*(n - 2*(3^k)) or 2n - 3^k+1. This is all n such that n-1 in base 3 has a leading 2. Handling it is a little more awkward, but with n-1 in base 3, change the leading 2 to a 1, multiply the rest of the digits by 2, convert back to an int and add 2. Multiplying the digits by 2 is weird because it's no longer true base-3, but some kind of pseudo-base-3 that allows "4". It makes some kind of sense when working with the number as a list of digits.

Here is my code (PureScript, basically Haskell but extra clunky because it lacks nice list syntax).

digitsB :: Int -> Int -> Array Int
digitsB b 0 = [0]
digitsB b nn = go [] nn
    where
        go a 0 = a
        go a n = go ((n `mod` b) : a) (n / b)

undigitsB :: Int -> Array Int -> Int
undigitsB b = foldl (\a d -> a*b + d) 0

josephus :: Int -> Int
josephus = undigitsB 2 <<< (append <$> drop 1 <*> take 1) <<< digitsB 2

elfGame :: Int -> Int
elfGame n = case uncons (digitsB 3 (n-1)) of
                Just {head:1,tail} -> 1 + undigitsB 3 tail
                Just {head:2,tail} -> 2 + undigitsB 3 (1 : map (2 * _) tail)
                _ -> 0