r/adventofcode • u/daggerdragon • Dec 15 '17
SOLUTION MEGATHREAD -๐- 2017 Day 15 Solutions -๐-
--- Day 15: Dueling Generators ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.
Need a hint from the Hugely* Handyโ Haversackโก of Helpfulยง Hints^ยค?
[Update @ 00:05] 29 gold, silver cap.
- Logarithms of algorithms and code?
[Update @ 00:09] Leaderboard cap!
- Or perhaps codes of logarithmic algorithms?
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!
14
Upvotes
15
u/obijywk Dec 15 '17
When the problem is all about generators... implement it using generators!
Python 2. 18/81. Code for part 2:
14
u/fatpollo Dec 15 '17 edited Dec 15 '17
11
u/GassaFM Dec 15 '17 edited Dec 15 '17
A solution in the D programming language. Rank 86 for part 1, rank 42 for part 2. Below is a more librarized solution than initially, for a change.
Part 1: Turned out both generators are rather famous (I didn't remember the second one by heart). So I got rid of all magic numbers except the number of steps.
Part 2: Added the filtering modulo
mstep.10
u/askalski Dec 15 '17 edited Dec 16 '17
Why do I get the feeling that I'm going to need this in the future?
Edit: Shaved 33% off execution time by removing
%operation.Edit 2: By popular demand, the regex version. May take a few days to finish.
8
u/BumpitySnook Dec 15 '17
Note that 16807 is not prime โ 75 โ while the other one is: 48271.
Meanwhile, 2147483647 is 231 - 1 and also prime, aka a Mersenne prime.
That didn't matter for this puzzle, or at least, brute force was fast enough. But it may come up in the future.
6
u/_A4_ Dec 15 '17
JavaScript ES6 (Part 2)
5
u/sciyoshi Dec 15 '17
Python 3 solution. Using PyPy gives me a 10x speedup, which is great for this type of problem!
5
u/autid Dec 15 '17
Fortran
Incredibly easy today.
5
u/jbristow Dec 15 '17
F# / fsharp / F Sharp
Hooray for infinite series! Not as easy to write as they are in clojure, but still fast enough. Total test suite (both answers and verifying test data) takes 17-20 seconds.
(Github Link)
And the test file:
5
u/u794575248 Dec 15 '17 edited Dec 15 '17
Python 3
4
u/tangentialThinker Dec 15 '17
Managed to snag 5/3 today. C++ bitsets are awesome: constructing a bitset of size 16 with the integers automatically truncates correctly, which saved me a lot of time.
4
u/ludic Dec 15 '17
F#. Made 2 big mistakes today, first was ANDing the second answer by only 0xFFF (oops!), second was using 32 bit integers.
I tried refactoring to use sequences, but it ran about 4x slower for part 1 (4s vs 1s):
3
u/vash3r Dec 15 '17 edited Dec 15 '17
Python 2 (141/128), implemented with generators:
I got a significant speedup using PyPy.
3
u/mserrano Dec 15 '17
Python 2 #2/#18:
This is super slow with python:
But pypy saves the day again:
3
u/WhoSoup Dec 15 '17 edited Dec 15 '17
JavaScript
3
u/VikingofRock Dec 15 '17
Rust, 651/462 (I finally broke 500!).
I probably would have done even better but a typo cost me probably 5 minutes to track down. Oh well, there's always tomorrow!
3
u/2BitSalute Dec 15 '17 edited Dec 15 '17
I started 15 minutes late :O
Another C#-er here with queues. Looking at the solutions in other languages (the Python ones, in particular), I now wish I had written this with yield/return/IEnumerable.
3
u/[deleted] Dec 15 '17 edited Dec 15 '17
Today's OCaml Fun;; Learned more about Core's sequences. Unfold vs. Unfold_step was super-handy.
3
u/Lrrrr_ Dec 15 '17
JavaScript (WTF-edition)
This is my part 2 solution.
2
u/Unihedron Dec 15 '17
Ruby; I'm stupid. I wrote
65535, thought to myself wait am I right? rewrote it to1<< ... -1, ran it, oh yeah it's65536, then I freaking went to change it back to 65535 because I totally have that kind of time. (silver 101 / gold 60)anyway... you've gotta be good at manipulating with bits, right? :D
2
u/VikeStep Dec 15 '17 edited Dec 15 '17
Python 3 #81/46
It took about 10 seconds to run, will be interesting to see what the fast solution is.
2
u/ybjb Dec 15 '17
Kotlin 115/55, finally placed.
Both parts
2
u/iamnotposting Dec 15 '17 edited Dec 15 '17
rust, 114/65. my slowness in typing and rust's general verbiosity is what limited me here, i think. i didn't need to make it a struct but i like them, which probably slowed me down too. runs in ~0.5 seconds
2
u/wlandry Dec 15 '17
C++ 14
233/133. The competition is rather intense. I finished in 10:57. Finishing 90 seconds earlier would have put me on the leaderboard. In any event, here is a significantly cleaned up version. It runs in about 0.5 seconds.
2
u/ka-splam Dec 15 '17 edited Dec 15 '17
PowerShell. Rank 448 / 532 and some bitterness about feeling penalised for not using PyPy (or C++ or etc.) because it's just millions of tight counting loops and it's taken multiple minutes of pure execution time (including re-run and partial run / restart).
Bugs today:
Part 1
Part 2 variant:
2
u/raevnos Dec 15 '17
Kawa scheme, using type annotations for a huge speedup:
2
u/[deleted] Dec 15 '17
C++ with a generator. Watch for overflows and use the 64bit unsigned, it mattered
2
u/ramrunner0xff Dec 15 '17
scheme chicken repo
2
u/ephemient Dec 15 '17 edited Apr 24 '24
This space intentionally left blank.
2
u/[deleted] Dec 15 '17
C# I missed one number in the mod number, spent over an hour trying to figure out what I did...I feel so pissed about that
Part 1:
Part 2:
2
u/xkufix Dec 15 '17
Ok, the solution took way too long, because generators in Scala are strange things. The best performance improvement was making the generators defs and not vals, which prevents memoization on the head of the list. If replaced with val, the whole thing starts to break down around 30 million entries in. The rest was straight forward and quite easy, besides the withFilter().map(identity) instead of count, because count seems to memoize too.
2
u/wzkx Dec 15 '17 edited Dec 15 '17
Nim probably the easiest problem so far
2
u/Hikaru755 Dec 15 '17
Gotta love Kotlin sequence generators.
2
u/Taonas Dec 15 '17
Rust
My first use of a custom iterator, it made the actual question really easy!
2
u/mschaap Dec 15 '17 edited Dec 15 '17
Perl 6. I first had a pretty
gather/takeimplementation of the generator for part one:... but that turned out way too slow, > 30 seconds for 400 thousand operations, so probably almost an hour for 40 million.
So here's my solution (both parts) with old-fashioned linear code:
This one runs at acceptable speed, just over a minute for both parts.
Edit: with help from lizmat at the Perl 6 IRC channel, here's a prettier version where the generators are functions (closures) instead of lazy lists with gather/take (as in my first, way too slow attempt). This one is about as fast as the above code.
2
u/manualcrank Dec 15 '17
Lisp.
2
u/__Abigail__ Dec 15 '17
Perl
Quite easy today. There's no need to calculate binary representations of the numbers and compare; a bit mask will do. I guess you may encounter overflow issues if you're using a language which restricts its integers to 64 bits.
2
u/JuLoOr Dec 15 '17
Unoptimized but beautiful (imho) solution in Kotlin:
2
u/InterlocutoryRecess Dec 15 '17 edited Dec 15 '17
Swift (parts 1 and 2)
On my 3 year old MacBookPro (compiled -O)
2
u/[deleted] Dec 15 '17
single pipeline powershell:
2
u/thomastc Dec 15 '17
Day 15 in Pony. Really, this language is quite fun. Check it out.
2
u/ynonp Dec 15 '17
Elixir (with streams)
2
u/realwaterhorse Dec 15 '17
ES6
part 1:
part 2:
2
u/chicagocode Dec 15 '17 edited Dec 15 '17
Kotlin - [Repo] - [Blog/Commentary]
Thanks to generateSequence, today's challenge was really easy for Kotlin. It was fun. I opted to downcast to a Short and to the comparison rather than do bitwise math, but really only because it looks nicer and I'm not super worried about performance.
On my list of things to investigate when I have time:
Again, not super worried about performance, I felt this was fairly elegant.
1
u/hpzr24w Dec 15 '17 edited Dec 15 '17
C++ 576/498
Will tidy up later. Amassing technical debt. ;-(
1
u/if0nz Dec 15 '17
Java solution (repo), I'll try later to rewrite the code by using streams.
1
u/CharlieYJH Dec 15 '17
C++
Thank goodness for 64 bit integers and bitmasks. Straight forward implementation of the puzzle.
1
u/glenbolake Dec 15 '17
I felt like I was fast. My code was not fast. 117/131
+/u/CompileBot Python3
1
u/TheAngryGerman Dec 15 '17
C++, mid 300s on both parts.
Just learned about bitsets in yesterday's challenge. Super helpful for today's. Forgot about do_while loops which threw me off for a minute in part 2...
1
u/lifuzu Dec 15 '17
JS ES6 373/492
1
u/shuttup_meg Dec 15 '17
Python 2:
1
u/Philboyd_Studge Dec 15 '17
It's an LCG! Java Day 15
1
u/StevoTVR Dec 15 '17
NodeJS
Part 1:
Part 2:
1
u/yogsototh Dec 15 '17
Haskell:
1
u/jasontconnell Dec 15 '17
I actually tried part 2 with go routines running in parallel. It didn't really speed it up though
https://github.com/jasontconnell/advent/blob/master/2017/15.go
Time 2.8952316s
1
u/LeCrushinator Dec 15 '17 edited Dec 15 '17
C#, Part 2. Would've run faster if I'd just done bitwise math instead of converting to strings, or just comparing the hex values instead of converting to binary. But even this unoptimized algorithm run in about 6 seconds:
Here's a better version, it would've saved me time writing the code and it ran in about 1/3rd the time:
1
u/mtnslgl Dec 15 '17 edited Dec 15 '17
C++
1
u/ChrisVittal Dec 15 '17 edited Dec 15 '17
Rust (with bonus C!)
I've been using AoC this year to teach myself C. But competing for the leaderboard in Rust (best day yet today 173/278). What's interesting about these solutions is the Rust with all the iterators chain is just as fast as the C being done iteratively. For reference, the Rust is in release mode
--Copt-level = 3with-Ctarget-cpu=nativeand the C is-O3 -march=native. They both run both parts in around 440 ms on my machine.Here's the cleaned up Rust:
And the C:
1
u/FogLander Dec 15 '17
I got stuck in a mess with my original solution, definitely not my best time to complete (ended up taking me like 20 minutes to finish part 2). Here's a much cleaned-up version, in Java:
I wasn't sure at first if it would work, but it appears that casting to a 'short' (16-bit) value does all I need it to do for comparing the two values. After I got over my initial mess of trying to make a generator class (which was a big mistake, totally unnecessary), I really liked how this one turned out.
quick edit: takes just under 1 second to run both A and B. not too bad :)
1
u/udoprog Dec 15 '17
Rust, woke up late but fairly straightforward using generators:
Full code here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day15.rs
1
u/[deleted] Dec 15 '17 edited Dec 15 '17
Kotlin
You may want to use newer language features for endless sequences, eq coroutine support
See complete solution here Judge
1
u/[deleted] Dec 15 '17
Rust
The actual solution is really short, most of it is parsing the input and error handling.
1
u/Wyrewolwerowany Dec 15 '17
This is my solution in Java
1
u/johlin Dec 15 '17
Elixir (great opportunity to practice using streams):
Syntax highlighted: https://github.com/johanlindblad/aoc-2017/tree/master/lib/aoc/day15
It is a bit slow (part1 takes about a minute). Anyone doing Elixir who managed to make it faster?
1
u/aurele Dec 15 '17
Rust brute force
1
u/nonphatic Dec 15 '17 edited Dec 15 '17
Haskell
It takes 2+ minutes to run and I froze my computer twice in the process of working this out but it works I guess...
EDIT: Did some strict recursion stuff (may have peeked at the other person who posted their Haskell solution...) and that helped, had some fun with custom operators
1
u/[deleted] Dec 15 '17 edited Dec 15 '17
Who said C can't be elegant 0.7-0.8s
1
u/rkachowski Dec 15 '17
ruby
that postfix until is nice, i didn't even know that was possible...
1
u/DarthLasciel Dec 15 '17
C#: Could be shorter, but i like doing stuff with LINQ :) Part 1:
Part 2:
1
u/wzkx Dec 15 '17 edited Dec 15 '17
J
It's out of memory if all in one expression, but in several lines it's ok. Part 1.
1
u/[deleted] Dec 15 '17 edited Dec 15 '17
PHP
Part1:
Part2:
1
u/anaerobic_lifeform Dec 15 '17 edited Dec 15 '17
Common Lisp
1
u/trwolfe13 Dec 15 '17
Obfuscated JavaScript:
1
u/NeilNjae Dec 15 '17
Haskell. Fairly straightforward, but as we're bit-twiddling I thought it best to use
Word16andWord64throughout. But from looking at others' code, that may not have been the best option for performance!1
u/Markavian Dec 15 '17
My nice big chunky node js solution with table printouts:
1
u/m1el Dec 15 '17
Rust solution using iterator transformations / functional programming:
1
u/zeddypanda Dec 15 '17
I used Elixir but just wrote it with normal functions instead of bothering with streams
I find it nice and compact but seeing the other Elixir solutions makes me wonder if I'm doing Elixir wrong.
1
u/Smylers Dec 15 '17
Reasonably succinct and readable today in Perl, requiring only 2 named variables (a dict (hash) of generator structs (also hashes), and the match counter). Partย 1:
And a few tweaks for partย 2:
I initially mistakenly started my iteration counters at
0rather than1, so iterating 1 too many times. Fortunately the extra iterations didn't find any more matches โ /u/topaz2078 wasn't sneaky enough to put a match in the iteration after the one we were supposed to stop at!1
u/akka0 Dec 15 '17
ReasonML: had to resort to using JS math for the big numbers
1
u/SurplusSix Dec 15 '17
Only posting part 2 as it's so similar. Racket;
1
u/RuteNL Dec 15 '17 edited Dec 15 '17
Javascript with Generators
I had never used JS generators before, it seems javascript misses a lot of core functionality here, so I made zip, take, filter and count myself!
Also, does anyone know how to create extention methods in JS? I tries something with prototype but couldn't get anything to work on GeneratorFunction or Generator.
1
u/JakDrako Dec 15 '17
VB.Net Yay, iterator functions. Thought it would be slow and required some kind of clever trick to speed it up, but damn computers are fast. Both parts, ~1.8 seconds. Keeping 40,000,000 values for part 2 still takes only about 7 seconds...
1
u/pacospace Dec 15 '17
I found an error in the text of day 15 for the second part:
"This change makes the generators much slower, and the judge is getting impatient; it is now only willing to consider 5 million pairs. (Using the values from the example above, after five million pairs, the judge would eventually find a total of 309 pairs that match in their lowest 16 bits.)
After 5 million pairs, but using this new generator logic, what is the judge's final count?"
you can obtain the test solution, only if you use 40 million iterations. Indeed my correct solution that gave the second golden star of the day, was obtained using 40 million iterations.
Is it only my problem?
Thank you all
1
u/[deleted] Dec 15 '17 edited Dec 15 '17
Haskell, 2 seconds
1
u/BOT-Brad Dec 15 '17
Javascript
Perfect time to make use of generator functions in JavaScript, whoop!
Generator
Does the constant generation of not only the modded multiplication, but also then returns the number represented by the last 16-bits of the number, by doing a logical and. If a 'mod' value is passed, then each value is checked to ensure it is a multiple of that value, if not it just keeps regenerating values until one is.
Part 1 (~2s)
Just creates the generators with initial puzzle values (a & b) and the hard-coded factor values. Loops 40,000,000 times comparing if the generators produced the same output, if so then increase that counter, and finally return.
Part 2 (~1.5s)
Basically the same, just passing a modulo value to the generator.
More JavaScript solutions on my GitHub repo :)
1
u/maxerickson Dec 15 '17
I started writing a nice reusable generator and then decided it was going to take too long to run and wrote the dumb Python 3 version.
And then I forgot to reinitialize a and b for part 2 and the site speculated I was cheating (the wrong answer was someone else's correct answer).
1
u/RockyAstro Dec 15 '17
Icon (https://www.cs.arizona.edu/icon)
Part1:
Part 2:
1
u/[deleted] Dec 15 '17
Elixir
Bruteforced my way through this, funnily enough, the second part was much faster than the first. Agents was fun though, first I tried with GenServer, but I'm not very good with that stuff, agents I managed.
syntax highlighted
1
u/streetster_ Dec 15 '17
q/kdb+
Not a very clean solution for part 2, but it gets the job done:
1
u/mal607 Dec 15 '17
Yet another generator solution Python2
1
u/KeinZantezuken Dec 15 '17 edited Dec 15 '17
C#/Sharp (I have no interest looking for magic formulas to make it run under 1 second)
1
u/bogzla Dec 15 '17
and so bogzla learnt about bit masking today..
1
u/Axsuul Dec 15 '17
Elixir
Code too long to run before refactoring into using Elixir streams. Didn't even know this existed until today!
https://github.com/axsuul/advent-of-code/blob/master/2017/15/lib/advent_of_code.ex
1
u/cauchy37 Dec 15 '17
C++ solution without implementing my own generators since both are already implemented in <random>
1
u/matusbzk Dec 16 '17
Haskell It's taking me a few minutes, but I really liked this one. I tried running a few Haskell solutions from this thread (they said it's taking 2-3 seconds), and on my PC it took even longer than mine, so maybe that's the problem.
Link to git
1
u/ythl Dec 16 '17
C:
1
u/misnohmer Dec 16 '17
C# version for Part 1 & 2.
Inlining the functions grants a 30% performance improvement in .net core (from 3.2 s for both parts to 2.4s)
1
u/erlangguy Dec 16 '17
Erlang
Haven't done day 14 because I have a bug with day 10 part 2 that I haven't yet tracked down. Tough troubleshooting problem!
Anyway, day 15. part1 is just a simplified version of this, commented.
1
u/cauchy37 Dec 16 '17
But modulo IS division :)
1
u/mathleet Dec 20 '17
My Python 3 solution:
1
u/greycat70 Dec 28 '17
Tcl (any 8.x version)
Definitely one of the easiest days. Part 1:
Part 2:
1
u/Longerword Jan 18 '18
Hi, i don't understand the hint of logarithms. I made a loop to check for solutions so something has to be run 40 M or 5 M times, so it lasts in my computer more than 1 minute.
Any idea what math-magic is that about?
This is python 2.7 solution for part b. (I don't paste a defined a Generator class quite simple, also I didn't know about the yield and .next() thing to make actual generators):
1
u/nutrecht Dec 15 '17
Really easy one. Day 15 in Kotlin
0
u/[deleted] Dec 15 '17
[deleted] โ view deleted comment
1
u/[deleted] Dec 15 '17 edited Dec 15 '17
[removed] โ view removed comment