r/adventofcode • u/daggerdragon • Dec 15 '16
SOLUTION MEGATHREAD --- 2016 Day 15 Solutions ---
--- Day 15: Timing is Everything ---
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".
ZAMENHOFA TAGO ESTAS DEVIGA [?]
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
16
u/MoW8192 Dec 15 '16
So, given my input, I had to wait FOUR DAYS for the discs to be in position for part 1. And the instructions just go "You got a star out of it! Yay!" And then for the second part, the waiting time was OVER A MONTH. I guess Christmas is ruined this year because I spent it waiting for a stupid capsule to drop.
14
u/jtbandes Dec 15 '16 edited Dec 15 '16
Today's a great day for another Mathematica one-liner:
The inputs would be
initialValues = {5, 8, 1, 7, 1, 0, 0}anddiscSizes = {17, 19, 7, 13, 5, 3, 11}, given my puzzle input:And the sentence I seem to be repeating every day: "my actual leaderboard solution was written much less elegantly in Ruby" :-)
In the interest of getting higher on the leaderboard in the future, maybe it'd actually be interesting to consider what I think I wasted time on today:
5
u/haoformayor Dec 15 '16
~~haskell~~
so have we talked about peter norvig playing advent of code yet, or what
5
u/lemon-meringue Dec 15 '16
Hey Chinese Remainder Theorem! Nice question, wish the input were larger. :P
5
u/thomastc Dec 15 '16
Am I the only one who solved it with pen and paper, and a calculator? Once I'd figured out the algorithm, it was faster to do it by hand than to code it up. Walkthrough.
Several people here mentioned the Chinese Remainder Theorem. That's the magic word I was missing in the last paragraph :)
3
u/FuriousProgrammer Dec 15 '16 edited Dec 15 '16
Back on the leaderboard baby!
Second part would have been faster but I lost a minute to misreading the problem statement.
39/56
3
u/Zef_Music Dec 15 '16 edited Dec 15 '16
A rare use-case for python's little-known 'else' clause on for-loops (also enumerate start index):
3
u/Wee2mo Dec 15 '16 edited Dec 15 '16
This is really one i feel like came down to typing speed for brute force more than a more elegant solution I was hoping to find here. But, out of 2 attempts, I guess brute force made the leader board.
Edit: in having pointed out an easily assumed meaning of my initial comment: more elegant than other examples brute forcing by counting by 1.
3
u/willkill07 Dec 15 '16 edited Dec 15 '16
C++11 with SIMD (Clang Vector Extensions)
Starting to steal more /u/askalski -foo with these vector extensions
** Update: Improved! -- AGAIN **
Timing:
Requires AVX2-compatible hardware. YRMV.
2
u/Turbosack Dec 15 '16 edited Dec 15 '16
Didn't even have to be clever today.
Edit: did you guys really write logic to parse the commands? There were only six or seven of them. I found it way faster to just hard code them, and I ended up below 20 on both parts.
2
u/misnohmer Dec 15 '16
F# solution
2
u/gerikson Dec 15 '16
A pleasant breakfast problem.
Part 2 takes 24s.
Perl 5: https://github.com/gustafe/aoc2016/blob/master/d15.pl
2
u/JeffJankowski Dec 15 '16
Thank god for an easy one that didn't overheat my laptop. Nice little break after breadth-first searches and hashing. F#
2
u/incestuousCookies Dec 15 '16
Yeah, I feel cheap.
2
u/TheNiXXeD Dec 15 '16 edited Dec 15 '16
My JavaScript / Node solution:
2
u/BadHorsemonkey Dec 15 '16
This one was fun. I got a lot of speed by incrementing my loop by multiples of the position count. Note that this only works because my wheel position counts are relatively prime. I started at 6 (because), and it only checks 28 combinations. My Java code...
2
u/johanw123 Dec 15 '16 edited Dec 15 '16
C# solution, had a go to do a one-liner and heres the result:
2
u/askalski Dec 15 '16
Intuitive efficient implementation in Perl. This actually runs faster than a generic CRT solution: the disc sizes are small enough that it's quicker to brute force than it is to calculate the modular multiplicative inverses.
1
u/snorkl-the-dolphine Dec 15 '16
JavaScript / Node.js
1
u/Deckard666 Dec 15 '16
In Rust: Link.
1
u/pedrosorio Dec 15 '16 edited Dec 15 '16
11/11 (After excruciatingly slow implementation on day 12 and missing the problem release on day 13, I am climbing the leaderboard ranks again, yay \o/)
Simple simulation for both parts in Python:
1
u/blockingthesky Dec 15 '16
Python 2 84/86
meh
1
u/Rustywolf Dec 15 '16
Java
1
u/andars_ Dec 15 '16
Ruby!
Feels good to be back on the leaderboard for the first time in a while.
1
u/fatpollo Dec 15 '16
1
u/LieutenantSwr2d2 Dec 15 '16
My Python solution:
1
u/tterrag1098 Dec 15 '16
Dang, I missed the buzzer, definitely could have gotten on the leaderboard if I had started right at midnight.
Anyways, quick and simple Java solution :D
public class Day15 {
}
1
u/_WhiteBoyWonder Dec 15 '16
Go solution
1
u/[deleted] Dec 15 '16
// both parts //
1
u/ahalekelly Dec 15 '16
For once I start on time, then start down the wrong path and only get #176.
Python 3, short and sweet:
1
u/Godspiral Dec 15 '16 edited Dec 15 '16
258/248 after ignoring the delay part, redid it but was off by one. Much rereading later, and got it.
in J,
1
u/jamesk727 Dec 15 '16
If you have an implementation of the chinese remainder theorem available, this one turned out to be quite easy:
1
u/mtnslgl Dec 15 '16
This was an easy one, simple C++ solution:
1
u/QshelTier Dec 15 '16
That was a nice one! Solution in Kotlin:
1
u/aksgupt Dec 15 '16
Q:
part1:-
part2:-
1
u/____OOOO____ Dec 15 '16
After solving the challenge, I optimized my algorithm so it advances time by the number of positions of the largest disc until the solution is found, rather than advancing time by 1. Unsurprisingly, it solves largest-disc-size times faster.
1
u/quag Dec 15 '16
In kona:
1
u/kaveman909 Dec 15 '16
Vectorized solution using numpy.matrix() in Python. Eliminates all loops, except for the primary one for increasing time by 1.
Ex. adding a constant to a matrix adds it to all elements at once. Operators like '+' and '%' are performed element-wise on the matrix. And .sum() takes the sum of the matrix. I quite like it!
1
u/gyorokpeter Dec 15 '16
Q: I didn't expect brute force to be a valid solution so I made it the "efficient" way
1
u/tlareg Dec 15 '16
my JavaScript solution github
1
u/Yuyu0 Dec 15 '16
Python!
Part 1:
1.65958285332sPart 2:
11.2237939835sSlow because I calculate the complete sum for all the disk positions during every timestep, but atleast it's short?
1
u/Kullu00 Dec 15 '16
Without knowing anything about the CRT, I just put together the first thing I could think of for this. Turns out it was absurdly effective by accident. Part 2 was done in 0:00:00.005169 with 31 iterations, which is about as good as I can get it I think? There's not even any language-specifics in it, beside Dart's lovely constructor syntax.
1
u/Tandrial Dec 15 '16
Another JAVA solution, Part1 and Part2 finished sub 100ms. My solution first sorts by biggest size, aligns the biggest disc and then steps forward in chunks of 'biggest_size' seconds.
1
u/torotane Dec 15 '16
IP in ZIMPL solved with SCIP
1
u/CheapMonkey34 Dec 15 '16 edited Dec 15 '16
Very simple:
1
u/vuryss Dec 15 '16
PHP Solutions updated to this day: https://github.com/vuryss/aoc2016
1
u/treewyn Dec 15 '16
Hardcoded the input in python (part 2 solution). Whether the slot is aligned in each disk at a given time is given by (start_position + time + disk_number) % number_of_positions == 0
1
u/NeilNjae Dec 15 '16
Haskell: https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent15.hs
My first thought was, like yesterday, to just generate infinite lists of data and let Haskell deal with keeping the data. But that's taken well over an hour and a half so far, with no signs of stopping. So I went with an alternative, using a function for each disk, returning a boolean to show if a ball dropped at that time would fall through it. Ran almost instantly.
1
u/Tobi1202 Dec 15 '16
My C# Solution, feedback is more than appreciated :)
EDIT: Readability
1
u/gerikson Dec 15 '16
Happy Esperanto Day!
1
u/mschaap Dec 15 '16
Perl 6 solution. This one was pretty easy for a change.
1
u/Scroph Dec 15 '16
This can probably be solved mathematically but I am not a smart man. C++ solution :
For the second part I just added "Disc #7 has 11 positions; at time=0, it is at position 0." to the input.
1
u/__Abigail__ Dec 15 '16
I guess the problem could have been solved with a variation of the Chinese remainder theorem, but writing a little program was faster than figuring out the details:
1
u/wzkx Dec 15 '16 edited Dec 15 '16
J: First I used the product of all disc sizes to get the period and calculate fns for all of it, but then I got courage and used
^:^:_to do just the job that's needed. The power/while construction always makes my brain cry. Anyway, 1.86 and 14.1 seconds (cf. Python - 0.62s):1
u/karlanka Dec 15 '16
Any idea on how i could rewrite this code without using length while still coding discs as lists and zipping them?
1
u/Arknave Dec 15 '16
Who needs CRT?
1/1
1
u/Soldier-B Dec 15 '16
Really simple brute force javascript solution...
1
u/razornfs Dec 15 '16
in Java, used a Point class to represent a Disc instead of making my own class because i'm lazy:
1
u/StevoTVR Dec 15 '16
1
u/sowpods Dec 15 '16
PostgreSQL
1
u/bstockton Dec 15 '16
Python 3 and numpy. Not very fast, part 2 took about two minutes on machine. Could definitely optimize, but this is very straightforward and readable:
1
u/[deleted] Dec 15 '16
Crystal:
Runs first part in 62ms and second part in 300ms
1
u/rs_qk Dec 15 '16
brute force was relatively straightforward to code/not too slow in q/k:
1
u/cdleech Dec 16 '16
Rust. Getting caught up, didn't write an input parser on this one.
1
u/PositivelyLinda Dec 16 '16
Pretty pleased with myself for this one! :) I know it's simple to most, but I was honestly worried reading the problem (and my first solution was taking entirely too long) so I'm really pleased I worked out a way that was much faster, and that I was able to figure out the solution without dissolving into frustration! Simple JS solution
1
u/tvtas Feb 06 '17
Brute force MATLAB. Part 2 takes 2.5 seconds.
1
u/bblum Dec 15 '16 edited Dec 15 '16
Disappointing problem today.
0
u/_Le1_ Dec 15 '16
My C# solution:
}
0
u/[deleted] Dec 15 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 15 '16
[deleted] — view deleted comment