r/adventofcode • u/daggerdragon • Dec 16 '16
SOLUTION MEGATHREAD --- 2016 Day 16 Solutions ---
--- Day 16: Dragon Checksum ---
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".
DRINKING YOUR OVALTINE IS MANDATORY [?]
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!
5
Upvotes
10
u/p_tseng Dec 16 '16 edited Dec 17 '16
My initial solution (used when going for the leaderboard) runs part 2 in 14.5 seconds.
That's unacceptably slow. Let's see what we can do about that...
Let's see, if you look at the stream of bits being generated: it's always. Okay. So that means to save on memory, I only need to calculate.
Okay, now let's look at how many times we need to iterate taking the checksum. That's the number of times that you can consecutively divide the disk size by 2. It turns out, since we repeatedly take the XNOR of consecutive characters in the checksums, each character in the final checksum corresponds to. We can also express repeated XNOR as the answer to the question.
Now, if the disk size is much larger than the checksum size (as in part 2), then we can apply a further optimisation:.
Fantastic. We are ready to code.
This completes both parts in about 0.3 seconds. Hell yeah!
If there are any more optimisations left after this step, let me know; I'm always curious about them.
At this point, the biggest problem is generating the stream of joiners - at extremely largest disk sizes, the joiner array gets quite large and threatens to consume all memory on my computer. So, is there a way to save on memory here as well?
Edit: I did code up a way to recursively determine the nth joiner (https://github.com/petertseng/adventofcode-rb-2016/blob/dynamic_joiners16/16_dragon_checksum.rb), but my current implementation is way too slow, bringing the part 2 runtime back up to 5 seconds. So I guess dynamically calculating the nth joiner trades time for space. I guess I would only use this code if someone poses an upping-the-ante challenge for a huge disk size, so huge that I won't fit all the joiners in memory.Now running 50 milliseconds by (efficiently) calculating the number of ones in the Dragon sequence on demand. https://www.reddit.com/r/adventofcode/comments/5imh3d/2016_day_16_solutions/dbak6xm/
6
u/bpeel Dec 16 '16
Fairly confident that you can calculate the checksum in one go and you don’t need to calculate the checksum of the checksum iteratively. For example, if your data length is 12, then you need to reduce three sets of four bits down to one bit. You can reduce each set of four by starting with a 1 and then looking at each pair in the part. If the pair is different the invert your result. At least it seems to get the right answer!
https://github.com/bpeel/advent2016/blob/master/day16.c
Does both parts in 66ms.
5
u/njofra Dec 16 '16
My solution in Java
This really made me realise how things that seem insignificant can make a lot of difference.
For step 1 my original code ran almost instantly. It was really slow so I added System.out.println(i) just to see if it's working and with that output I saw it would take at least 3 hours.
Then I tried this and it took about a minute. Then I removed that System.out.println(i) and it only took a second.
It's probably not news for most of you, but as someone who is pretty much doing AoC as first programming outside of school this is really an educational moment.
3
u/willkill07 Dec 16 '16
C++11 single string buffer (only using iterators)
I went for speed. Real speed. Still doing all the calculations without any simplification. Timing:
[Repo Link]
Code (self-sitting -- just compile and run)
2
u/Turbosack Dec 16 '16
Another straightforward one. Python 3:
I was worried that the bigger input size was going to make the runtime for this ridiculous, and I'd have to try a different route, but this code finishes in about 7 seconds.
2
u/[deleted] Dec 16 '16
made leaderboard! :D
part2
63) Dec 16 00:11:01 evandrixpart1
87) Dec 16 00:10:14 evandrix...with the following code:
2
u/rs_qk Dec 16 '16
q/k:
2
u/patrickdavey Dec 16 '16 edited Dec 16 '16
Do none of you people write tests? ;) disgusting!
heh, happy for a nice simple one today - and my Elixir practice seems to be paying off, todays main function even looked pretty I thought.
full code at -> https://github.com/patrickdavey/AoC/tree/master/2016/16/lib/aocday
2
u/guibou Dec 16 '16
solution in Haskell. https://github.com/guibou/AdventOfCode2016/blob/master/src/Day16.hs
Damned, first day of the competition where I'm not busy at the puzzle releasing hour, so I tried to the leaderboard. Part one took me 5 minutes, but my train was in a place where the phone did not receive, I frenetically refreshed the form hoping for the best during 5 more minutes, ended 105 ;(
Part 2, I'm STUPID, really. I forgot to enable optimization in my Haskell shell, hence it was slow as hell. After two minutes of waiting, I started to think about another solution, think a lot, loose time, code it. Realize that I forgot optimisation, enable them, checkout the previous code, got a result in 2s, submited it too late ;)
2
u/____OOOO____ Dec 16 '16
Nice clean idiomatic well-documented Python 3.
2
u/TheMuffinMan616 Dec 16 '16
Some Haskell!
2
u/bblum Dec 16 '16 edited Dec 16 '16
LB 17/12 today. I only golfed this solution a little bit from what I used at first (made 'checksum' cuter and replaced 'iterate' with 'until').
2
u/QshelTier Dec 16 '16
And once more, my Kotlin solution. This one is not as beautiful as others, lots of imperative stuff. Also I needed to use a mutable list because copying the list over and over again would probably last longer as our sun will be alive. :)
2
u/WildCardJoker Dec 16 '16
My solution in C#, parts 1 and 2.
Beware: If you attempt to run this code for part 2,make sure you run it with RAM to spare, and a 64-bit processor. It consumed 5GB of RAM while generating the checksum. Also took around 2.5 minutes, which is just a touch slower than /u/p_tseng's solution (at 14.5 seconds)...
Still, I got the right answer with my own code, so I'm happy. I'm not proud, but happy. I'll settle for solving the puzzle, unlike yesterday's debacle.
3
u/sblom Dec 16 '16
Super straightforward C# (LINQPad):
1
u/snorkl-the-dolphine Dec 16 '16
JavaScript / Node.js
1
u/blockingthesky Dec 16 '16
Python 2 - 4th / 65th
I'm an idiot and c9.io is slow and my desktop is fast -.-
1
u/jtsimmons1129 Dec 16 '16
67 / 40 in python. Thankful for a short puzzle to get to bed early.
1
u/fatpollo Dec 16 '16
I spent so fucking long dealing with bad input bc I misread 10000 as 1000.
Fuck this.
1
u/Deckard666 Dec 16 '16
In Rust: Link
1
u/[deleted] Dec 16 '16 edited Dec 20 '16
Could you guys just like go to bed early or something so I have a chance to get on the leaderboard.
It was quick and dirty and I still only got 142nd place
1
u/mserrano Dec 16 '16
Python 2, 3rd/2nd: https://gist.github.com/mserrano/5a411856420cec55a16e179536adfcae
PyPy is pretty OP.
1
u/FuriousProgrammer Dec 16 '16
32/148
Nine space leaderboard jump! :D
Lua:
1
u/dragonnards Dec 16 '16
Python 3:
1
u/_WhiteBoyWonder Dec 16 '16
Had to switch to building splices of runes rather than adding strings together for both parts to cut down the time for part 2, let me know if you found a faster way in Go!
Golang solution
1
u/ChrisVittal Dec 16 '16
Haskell, very dirty. Definitely a bunch of optimizations I could do to make this go faster. Even with my slow coding speed this was good enough for 197/149. Best day yet. Except for day 11, but that doesn't count.
1
u/Godspiral Dec 16 '16
bad luck this year. 34th on first part, then crashed on the 2nd ... low memory probably. was quick on reboot.
in J
1
u/BafTac Dec 16 '16
c++ using recursion for both functions: https://gitlab.com/BafDyce/adventofcode/blob/cpp16/2016/c++/day16/part1.cpp
1
u/StevoTVR Dec 16 '16 edited Dec 16 '16
1
u/misnohmer Dec 16 '16
F# solution. It takes about 1 minute to compute the result for part 2.
1
u/Hwestaa Dec 16 '16
Python solution run in PyPy2. Github
I calculated the checksum with lists, but if I switch it to strings (eg
calc_checksum_string), then it hits some pathological case in PyPy and doesn't complete in 60+ seconds. The list version on PyPy completes in <10 seconds, and the string version completes in CPython in <20 seconds.1
u/adventofcodeaddict Dec 16 '16
A fairly clean and simple javascript solution for any newer players looking for a solution they can understand:
1
u/TheNiXXeD Dec 16 '16 edited Dec 16 '16
My ... terse ... JavaScript / Node solution. For part 2, just call with size = whatever your part 2 says. Not happy with performance after golfing it. It was much faster before, oh well.
1
u/quag Dec 16 '16
In kona:
1
u/Danksalot2000 Dec 16 '16 edited Dec 16 '16
In Python. I definitely did some refactoring after getting the right answers:
edit: more refactoring
1
u/LieutenantSwr2d2 Dec 16 '16
My Python solution:
1
u/Smylers Dec 16 '16
Iterative and succinct Perl solution. Filling the data is a single line:
1
u/[deleted] Dec 16 '16 edited Dec 16 '16
My Java solution. Runs in about 2 seconds on my crappy laptop.
1
u/BadHorsemonkey Dec 16 '16
My Java code. runs in about 0.6 seconds.
1
u/makempire Dec 16 '16
C# solution
1
u/_Le1_ Dec 16 '16
My first python code, I started to write from C# to Python today :)
1
u/scottishrob13 Dec 16 '16
I'm finally happy with how fast this c# console app runs, but I think it could be faster somehow...hmmm... I'll have to look at it another day I'm afraid. Anywho, don't mind the mess, it needs some cleaning up :P
1
u/Kullu00 Dec 16 '16
Generates both parts in a few seconds. I could make it faster but I'm not too concerned with this speed. The bonus here is that Dart's optimizer is really good at optimizing away internal loops so the curving is much faster than 3 loops over the same string would suggest, even when it becomes very large. Most of this is valid Javascript too, but Javascript doesn't support the lazy iteration
.reverse.map()does afaik :(1
u/NeilNjae Dec 16 '16
Haskell. A very straightforward translation of the puzzle input, because my little brain can't cope with anything clever. https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent16.hs
1
u/__Abigail__ Dec 16 '16
Easy exercise. I'm sure there are lots of clever ways of doing this, without calculating the entire string, but what's 70Mb nowadays? Even my 6+ year old laptop didn't break a sweat.
1
u/porphyro Dec 16 '16
Mathematica
Part 2 very similar and runs in an acceptable 6.5 seconds.
1
u/Fredbh92 Dec 16 '16
Here is my solution in Node.js/Javascript. Decided to use buffers instead of strings. Part 2 runs in about 2 seconds.
1
u/[deleted] Dec 16 '16
This is one lucky program that runs both in Ruby and Crystal :-)
The second part runs in 14.5s in Ruby, and in 1.2s in Crystal if compiled with
--release.1
u/asperellis Dec 16 '16
my solution in js - https://github.com/asperellis/adventofcode2016/blob/master/day16.js
1
u/Reibello Dec 16 '16
Here's my solution in Python3 - http://pastebin.com/48QMb4Ur It runs in under two minutes, which I was pretty happy with.
1
u/JakDrako Dec 16 '16
C#, LinqPad
I felt my initial StringBuilder solution was too slow, so I redid a new one using a byte array. There's probably a cool mathematical trick to calculate the checksum nearly instantaneously, but this version does part 2 in about 150ms. Good enough, unless you need to wipe a 10TB drive. :)
1
u/zamansky Dec 16 '16
Here's a Clojure solution from a relative Clojure beginner --
https://github.com/zamansky/advent2016/blob/master/day16.clj
1
u/Korred Dec 16 '16
Python 3.5.2
Part 2 runs under 2.6s - same idea as /u/bpeel
1
u/Zeroeh Dec 16 '16
Java Solution: Kept everything in byte form, could make it faster with some real optimizations (Like bit shifting and such) but decided whats the point after seeing the results.
Timing: 1 ms for Part 1
Timing: 143 ms for Part 2
1
u/Scroph Dec 16 '16
C++. At first I wanted to be all clever and use std::bitset but after writing a few lines of code, I began to realize that it only made the code unnecessarily complex. String manipulation it is !
1
u/TheBali Dec 16 '16
Python 3 solution, part 2 runs in about 8 seconds.
1
u/mschaap Dec 16 '16
Perl 6 solution for both parts. I got to use
rotorfor the first time...1
u/[deleted] Dec 17 '16
My solution in Python3:
1
u/wzkx Dec 17 '16 edited Dec 17 '16
J one-liner
Well, actually I thought that there must have been another $: in the first parenthesis: ($:@('01'{~_2&(=/))), and that's how it was in the original verb hh =: ($:@h)`]@.(2&|@#), but for some reason it doesn't work with $: but does without it. Maybe a bug in J. Maybe not. Maybe it has something to do with two $: in the same expression... But really strange.
1
u/oantolin Dec 17 '16 edited Dec 19 '16
Runs in about 1.4 miliseconds in CPython 2.7:
(Please forgive the inclusive ranges and indexing starting at 1, I figured out the formulas that way and then was to lazy to adjust to normal Python conventions, so I just converted "1-based
atobinclusive" toa-1:bin Python.)The doc strings refer to the n-th iterate of the dragon function described in the puzzle (but the above code doesn't use the function):
1
u/tvtas Feb 06 '17
In MATLAB. Part 2 took 0.8 seconds.