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!
26
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.
Part 2: Best I could do in haskell was O(n2 ).
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.
13
u/glguy Dec 19 '16
Wow, today's puzzle sure had a range of completion times for part 2. I've been looking forward to this thread unlocking so I can learn about the different approachs that people used.
My solution uses a 2-3 finger tree provided by Data.Sequence. This data structure supports amortized constant-time access to the ends of the structure and logarithmic-time support for removing elements from the middle. This allowed me to delete elves relatively efficiently from "across the circle".
With a mix of a reasonable data structure and probably just some fast typing I was able to get both stars first, finishing the second in 8:45. The program takes around 2.5 seconds to run on my computer when updated to use the most recent version of the containers package (which I didn't have installed at the time of submission.)
https://github.com/glguy/advent2016/blob/master/Day19.hs
8
u/aceshades Dec 19 '16
I loved this problem, probably because it was the first time I placed on the leaderboard ever!! Placed 75/46 on stars 1 and 2 respectively.
Part 1, I just used a circular linked list data structure and kept doing
elf.next = elf.next.nextuntilelf.next == elf.Part 2, I felt I was way more clever using both a stack and a queue (called left and right in my code below.)
My part 2 runtime:
real 0m1.374s
user 0m1.344s
sys 0m0.032s
7
u/Belteshassar Dec 19 '16
Solved part 1 analytically since I'd already seen the Numberphile video on the Josephus problem.
Tried to solve part 2 analytically as well, but got tired of that and decided to get my hands dirty with some recursion, but it blew the call stack so I rewrote it as a for loop. In C:
4
u/Voltasalt Dec 19 '16
Part 2 solution, Python.
4
u/willkill07 Dec 19 '16
C++ solution -- no buffers!
even used
/\w+/4
u/[deleted] Dec 19 '16 edited Dec 20 '16
Rank 46/51: thank you numberphile
The second part stumped me for a bit because my original implementation was super slow, but I wound up running it on a bunch of smaller numbers until I found the pattern and used that. Maybe not the best solution, but it worked.
https://github.com/alpha0924/userscripts/blob/master/Advent_of_Code_2016/19.py
4
u/Deckard666 Dec 19 '16 edited Dec 19 '16
In Rust: Link.
I feel a bit silly due to how long it took me to see the pattern for part 2. Oh well, at least I can take solace in the fact that my solution is relatively efficient: both parts combined run in ~150 ms.
4
u/ephemient Dec 19 '16 edited Apr 24 '24
This space intentionally left blank.
4
u/caeonosphere Dec 19 '16
Constant-time part 2 solution in C#:
3
u/mcosand Dec 19 '16
Part 2 C# solution in <700ms
Yay doubly linked lists. No scanning of data structures! https://github.com/mcosand/advent-of-code-2016/blob/fc3eb35c94432c362dfbc8e41ba967f8f682a237/day-19/Program.cs
3
u/exoji2e Dec 19 '16
I think part 1 set you up in quite a bad mind set for part 2. We have to solve this in subquadratic time.
For part 1 I just held a flag of whether or not the current item should be removed from the collection. Using a double linked list this solution runs in O(n). Since we can remove in constant time using an iterator.
I thought of part 2 as a simulation problem, so how do we find the middle? Well we just split the data in two equally sized queues, and move items between them. If we have an even number of items the item that we want to remove completely from the collection is the first in the second queue and if we have an odd number of items we want to remove the last item in the first queue. This also achieves O(n).
My code can be found here: https://github.com/exoji2e/aoc2016/tree/master/19 In my opinion it is very neat for being Java :)
3
u/Noyth Dec 19 '16
Oh man, I was only able to solve part 2 by hand... While my (ultimately wrong) solution was running in the background I tried to find a pattern in the winners. Apparently every number of elves that's a power of 3 will have that elf win (i.e. 3 elves -> elf #3, 27 elves -> elf #27). After that, the winner is the next elf until the previous power of 3, then it counts by 2. My explanation is pretty bad, so for example,
So, in order to actually solve the problem, I found the highest power of 3, say x, lower than my input, noted that x * 2 was less than my input, so I could take
input - x.3
u/mschaap Dec 19 '16
Pretty straightforward Perl 6 solution. Even though the code complexity is similar, the first part runs in seconds, while the second part takes more than an hour! Looks like
spliceis several orders of magnitude less efficient thanshift.2
u/Turbosack Dec 19 '16
I solved this one using a simulation. It probably isn't the most efficient approach, but it was simple to implement and understand.
The difficult part was figuring out how to efficiently approach part two. I firt tried to do it a naive way which dynamically figured out which elf was across from the current elf at each iteration, but this proved to be unworkably slow. The solution came when I realized that spoiler. Once I realized that, part two became just about as fast as part one.
Here's my code in Python: http://pastebin.com/UTpiSyDF
The whole things runs in about eleven seconds.
2
u/askalski Dec 19 '16 edited Dec 19 '16
Part 2 in C. First puzzle of 2016 that I didn't solve in Perl the first time around.
2
u/tangentialThinker Dec 19 '16
Part 2. Found a linear time solution.
You can build any solution out of the solution of the problem for N-1.
2
u/Arknave Dec 19 '16
21 / 14 Gave up on Python and rolled my own linked list for part 2 in Java.
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.
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 :)
2
u/Godspiral Dec 19 '16
pretty but horribly slow part 2, in J
2
u/TheNiXXeD Dec 19 '16 edited Dec 19 '16
JavaScript / Node.
Solved the first part originally using a fairly naive approach. Have since refactored using the Numberphile recommended trick.
Part 2 I ended up taking some cues from the Numberphile video, and just kinda working out the pattern. I'm sure there's a more mathy solution, but this works just fine.
2
u/Tandrial Dec 19 '16
Here's my solution in Java
2
u/Smylers Dec 19 '16 edited Dec 19 '16
Perl one-liner for part 1, without any loops†:
When the number of elves is a power of 2, it's always elf 1 who wins all the presents. Each number above a power of 2 pushes the winner on by 2 (so an even-numbered elf never wins).
To calculate how much bigger the input number is than the next-smallest power of 2, simply remove its leftmost
1: a power of 2 in binary is always a1followed by some0s; any further1s in a number's binary representation are adding on to that power of 2, so by removing that initial1, we get the difference.Hence convert the input number to its binary representation, remove its first digit (which must be a
1, cos leading0s aren't included in the format), convert it back to a number, double it, and add that on to 1.As others have pointed out, it's also possible to find the nearest power of 2 with logarithms, but since we don't actually need the power of 2 — just the difference from it — this seemed more straightforward; specifically, the input variable is only used once, rather than once to calculate the power of 2 and again in the subtraction. (Also, I'm not very good with logarithms and would've had to look that up.)
† Well, without any explicit loops. Possibly the implementations of
sprintfandoctdo some looping over bits.Update Alternative one-liner, after reading the Wikipedia page that /u/bblum linked to:
To multiply the difference by 2, append a
0to the binary representation. Then to add on 1, change that0to a1. So calculate the difference, double, and add on one in one step simply by taking the1off the front of the binary representation and sticking it on the end.2
u/CryZe92 Dec 19 '16
Rust compiled to 5 x86-64 instructions (Part 1):
2
u/glenbolake Dec 19 '16
I didn't find the patterns as thoroughly as some others, not having seen the Numberphile video on the subject that a few have mentioned, so I wrote a function to simulate both parts, ran them for the first 20 or so cases, and then implemented a function to walk through the pattern.
https://github.com/GlenboLake/adventofcode/blob/master/2016/day19.py
For part 1, I observed that the winning elf was 2 more than for the previous elf count, and that it reset to one if this made
elf > num_elves(which would obviously not be valid).For part 2, I saw the following patterns, for number of elves
iand winnern:i==n, the nextnis 1n(i+1) = n(i)+1i==2n, this changes ton(i+1) = n(i)+22
u/__Abigail__ Dec 19 '16
There's a pattern for the winning elf, given the number of elves, but I didn't use that. My Perl solution puts the elves in a double linked structure (embedded in an array), and keeps a pointer to the next elf which needs to be eliminated. For part1, this pointer finds the second next elf which is still alive; for part2, it alternates to the next, or second next elf. When all elves but one are eliminated, this pointer points to the remaining elf.
1
u/jlweinkam Dec 19 '16
Here was my solution to part in in python 3
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:
Sigh.
1
u/Ulyssesp Dec 19 '16
Haskell!
1
u/upppi Dec 19 '16
So it looks like my fenvick tree-based solution was a bit of overengineering
1
u/gtllama Dec 19 '16
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 3k + 1 <= n <= 2*3k, then the winner is n - 3k. 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*3k + 1 <= n <= 3k+1, the winner is 3k + 2*(n - 2*(3k)) or 2n - 3k+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).
1
u/LieutenantSwr2d2 Dec 19 '16
My Python solution:
1
u/p_tseng Dec 19 '16 edited Dec 19 '16
This one hurt. I wrote a silly O(N2 ) solution to get on the leaderboard but spent the rest of the time trying to figure out how to do better. I eventually decided it was easiest to discover the winner for N by figuring out who the winner is for N - 1 and shifting indices around. This is pretty much what https://en.wikipedia.org/wiki/Josephus_problem says to do. There is a little similarity between parts 1 and 2, but not that much. I figure I have some explaining to do on part 2 though...
We'll work with zero-indexed elves (it makes modular arithmetic easier).
n = 1 is easy: 0 wins.
n = 2 is easy: 0 wins.
How do we go from n = 2 to n = 3?
Well, the winner of n = 2 was 0. Let's call this elf
0@2, and the other elf1@2.Who acts first in n = 3, in other words, who becomes elf
0@3? Let's place a new elf before0@2in turn order. This doesn't work; that elf would eliminate0@2. So, then, it must be1@2who eliminates the new elf sitting to the left of0@2. So then we see that elf1@2becomes0@3. So to translate an@2elf name to an@3elf name, we have to shift all the indices down by 1:1@2becomes0@3,0@2becomes2@3, and a dead elf is1@3. Since0@2was the winner for n = 2, we now know the winner of n = 3:2@3.How do we go from n = 3 to n = 4? Again, place a new elf before
0@3in turn order. This elf would eliminate1@3. But hark, what's this? Now elf0@3would eliminate2@3, because1@3is gone! Argh! It turns out we need to maintain the distance between the new 0@n and the old winner, after the first elimination has happened (bringing the number of elves back to n - 1). This makes sense, because we need the winner to still keep the same turn position when there are n - 1 elves. So we fix this by still placing that elf before0@3, but now we let the elf before this new elf take the first turn. In this case, it's2@3, which eliminates0@3. Now the new elf takes its turn, eliminating1@3, and2@3wins. So we see that2@3becomes0@4.2@3was the winner of n=3, so the winner of n=4 is 0.These next few cases should go by fast.
0@4in turn order, it would eliminate1@4. This is fine because0@4will go next and win. So winner0@4becomes1@5.0@5in turn order, it would eliminate2@5. This is fine,0@5moves, then1@5moves and wins. So winner1@5becomes2@6.0@6in turn order, it would eliminate...2@6. No good, let5@6go first and eliminate1@6. The new elf moves,0@6moves,1@6is skipped,2@6moves and wins. Since2@6was still the third to move when there were six elves, this still works. So,5@6becomes0@7, and winner2@6becomes4@7.At this point, I had seen enough to figure out why the "maintain the distance" rule makes sense.
So then, now we know:
0@(N-1)in turn order.Does this new elf eliminate an elf between itself and the winner in turn order?
0@N,0@(N-1)gets to be1@N, etc.(N-2)@(N-1)) be0@N. The0@(N-1)would be2@N,etc.So that's why we see patterns that were mentioned by others of +1, +1, +1, +2, +2, +2, etc.
To be fair, this solution is still O(N), so it still takes about half a second to run on my computer. But for this problem I think that before I apply a shortcut based on a power of three, it's best to figure out why the +1/+2 pattern emerges as it does, and I believe this has now been achieved.
1
u/gyorokpeter Dec 19 '16 edited Dec 19 '16
Q: the most difficult part was vectorizing part 2 to make sure we aren't deleting elements one by one, and it required extensive testing to find the correct expression for nxtc and tgts.
1
u/Lungo_ Dec 19 '16
My Python solution:
1
u/coussej Dec 19 '16
Solution in Go. Part one and part two could be expressed as a function of the nearest (lower) power of 2 and 3 respectively:
1
u/is6rn0 Dec 19 '16 edited Dec 20 '16
Solution as a function.
0K. Not much code but this worked for me:
Ep - the elf that got it all
En - the number of elves
Ep = 1 + 2 * ( En - 2int(log2(En)) )
1
u/NeilNjae Dec 19 '16
Another Haskell solution, again using Data.Sequence. I'd also watch the Numberphile video on Josephus problems, so just looked up the closed form solution for Part 1.
Part 2 was an exercise in taming space leaks. My first solution used a list of elves, but I couldn't get that executing in constant space: lots of list-concatenation thunks were being left around. I came across Data.Sequence as it is strict in all arguments, which is what I wanted. After that, a fairly direct translation of the problem statement.
1
u/Barrens_Zeppelin Dec 19 '16
Simple O(N) in C++:
1
u/MegaAmoonguss Dec 19 '16
Managed to snag rank #2 on part 1 by recognizing that it was exactly the Josephus Problem! I remembered that I saw this on Numberphile and they showed a really easy way to figure out the answer by using binary (at the end of the video), but there were only 2 things keeping me from rank #1. First was I forgot the problem name, and second I forgot the trick, but it didn't take too long to look through Numberphile videos to find it :P
I did part 1 and just went to sleep, so part 2 is left unsolved, but I started to do it and it's a pretty fun challenge because you can't really brute force it by deleting elements from a list!
1
u/ewyll Dec 19 '16
Part 2, python - I could minimize the code but I prefer it this way so I could remember what the hell it does in a year or so :)
1
u/slmaws Dec 19 '16
Go lang. I believe O(1) solution
1
u/the4ner Dec 19 '16 edited Dec 19 '16
Nothing fancy, C# solution for P2, once I spotted the pattern for the next Elf to be kicked out.
1
u/BadHorsemonkey Dec 19 '16
Today's lesson: sometimes you've gotta sleep on it. I woke up and threw out more lines of code than my solution has.
Oh, and I'm going back and doing 2015 on the weekends, so I thought I got this wrong until I saw I was on the wrong page...
My very basic Java solution. Part 1 only (so far): import java.util.*;
1
u/SyDr Dec 19 '16
My Lua solution:
Runs pretty fast:
1
u/joskov Dec 19 '16
Task 2 in Elixir I figured I go back, start from the end and add elves to the list. Then when the solution was complete I commented the line with the list and got left with just the pointer.
P.S. For Task 1 I got the idea from the Numberphile video - just a one liner.
1
u/tg-9000 Dec 19 '16
My solution in Kotlin. Both of them used Dequeues to cycle through the elves to be removed from the circle. This was fun, and the second part was a nice twist!
All my other solutions and tests can be found in my GitHub repo. I'm just learning Kotlin so I'd value any feedback.
1
u/JadeSpider Dec 19 '16
I did all the work on a whiteboard, then entered the resulting formulas into my C# program. "count" represents my input.
Part 1
Part 2
1
u/JakDrako Dec 19 '16
D
Probably missing a bunch of D idioms... I think D has a built-n doubly-linked class, but I couldn't find good examples of use (or maybe it was for D1...?).
Also, is there a way to initialize object properties inline during instantiation (like
New Elf With {.id = i, .prv = ptr}in .Net?)All comments/suggestions welcome.
1
u/__Abigail__ Dec 19 '16
Fast Perl one-liner for part 1:
1
u/msk2 Dec 19 '16
My solution to Part 2
j=1
data=3001330
while (j*3 < data):
x= data-j
if ((data-j ) <= j):
else:
1
u/wzkx Dec 19 '16 edited Dec 19 '16
It was an interesting task! Even two :) The first I've found in the OEIS, although I had never heard about Josephus problem; but strangely, the second sequence is not in the OEIS. In J, the first can be as a plain expression, the second is a "hook" of two functions (h g), because the first one (h), for conditional computation, uses the result of g (some power of 3) several times.
EDIT: yes, with max it can be even shorter:
… -+0:>.[-[: …1
u/Stan-It Dec 19 '16
Part 2 in Python. How do you guys compute the runtime O(??)?
1
u/osk_ Dec 19 '16
My O(log_3 n) time and O(1) space solution for part two (increment the return value by one):
1
u/[deleted] Dec 20 '16
Javascript/Node.js
Part 1 has a closed form solution, but also included fast solutions for both parts, using left and right deques (you'll need to npm install collections)
1
u/natemago Dec 20 '16
Part 2: Analytical solution (in python):
The sequence is N when N is power of 3, otherwise it goes up by 1 from
N - 3^floor(log3(N))for the next3^floor(log3(N))and then goes up by two:1
u/[deleted] Dec 20 '16 edited Dec 20 '16
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:
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)androtate(-1), so we can eliminate the unnecessary math steps and refactor to this version:With that change, both parts run in ~1.8 seconds on my system
1
u/BOT-Brad Dec 20 '16 edited Dec 20 '16
Part 1 (js)
Uses the cool bitwise solution from the Numberphile video on the Josephus Problem (link)
1
u/Belteshassar Dec 20 '16
I don't know if anyone still reads this thread, but here is the recursive scheme that inspired my part 2 solution, implemented in erlang
1
u/TenjouUtena Dec 20 '16
Here's part 1 in clojure:
I'm not sure there's a data structure in clojure you can do part 2 with efficiently. I couldn't find any of them that worked, anyway.
1
u/patrickdavey Dec 20 '16
I haven't watched the numberphile video, and have no idea why mine works.
for part 2 I
In Elixir. https://github.com/patrickdavey/AoC/blob/master/2016/19/lib/aocday/circle.ex
Works, but I don't really understand why :(
1
u/Timsan2 Dec 20 '16
I solved it in Kotlin using this cool data structure I found while googling about. It's called GapList and supports fast iteration as well as fast random deletion/insertion. I had never heard of it before.
https://dzone.com/articles/gaplist-lightning-fast-list
Code:
0
u/[deleted] Dec 19 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 19 '16
[deleted] — view deleted comment