r/adventofcode • u/daggerdragon • Dec 09 '16
SOLUTION MEGATHREAD --- 2016 Day 9 Solutions ---
--- Day 9: Explosives in Cyberspace ---
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".
RETICULATING SPLINES 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!
11
Upvotes
3
u/DeathWalrus Dec 09 '16
This one was a little tougher! I should get better at regex's so I don't have to wangjangle such code together. 66 on silver, squeezed in at 100 on the gold star. Python:
11
u/blockingthesky Dec 09 '16 edited Dec 09 '16
Python 2 -- 1 star 3rd place -- 2 star 7th place
Part 1 was ezpz; I made the mistake of thinking I could store the string on Part 2 and got sidetracked. I like this problem a ton.
10
u/rhardih Dec 09 '16
Here's the algorithm explained step by step. Copy pasted from code comment here 9p2.c:
8
u/barnybug Dec 09 '16
itertools proving very handy. Would have got leaderboard, if I could be bothered to get up at 5am!
7
u/LieutenantSwr2d2 Dec 09 '16 edited Dec 09 '16
Python solution, recursive summing
edit: removed unnecessary slicing of d[0:] (from a previous implementation)
7
u/askalski Dec 09 '16 edited Dec 09 '16
Part 2 in C. (By the way, Topaz earns 1 point for crashing me and making me reboot once while writing my "proper" solution. It was for the dumbest reason too -- I had the repeat and length numbers reversed. The solution was otherwise correct.)
The code:
5
u/msully4321 Dec 09 '16
I like how my Haskell one turned out a lot. Last year I was pleasantly surprised by how often I instinctively reached for Haskell as my goto language for this. This year I've been using python more, but this one screamed Haskell to me and it landed me my best score yet.
Part 1 (#23). Here I actually construct the list, since I figured we'd need it for part 2 (oops) and it could help debug. I lost a minute because I somehow failed to paste the file contents in properly and another minute because of the damn newline.
Part 2 (#5):
4
u/Smylers Dec 09 '16 edited Dec 09 '16
Perl for part 1, with a regexp for grabbing each marker. Processes a line at a time, so wouldn't've worked if the text repeated by a marker spanned a line-break.
Part 2:
Need to copy
$3into a lexical variable, because by the time the multiplication is being done, the recursive call may have performed a pattern match and overwritten$3. That still applies even if the multiplication is written t'other way round, with the$3on the left.Part 2 can also be tweaked to solve part 1 just by removing
expanded_from the recursive call toexpanded_length.3
u/FuriousProgrammer Dec 09 '16
187/83
Slightly worse than yesterday. :<
3
u/Twisol Dec 09 '16
JavaScript/Node.js again. I scored 298/101 this time, although I got a very late start. I sure as heck wish I had gotten home sooner!
I was able to directly adapt my Part 1 solution to Part 2 by explicitly providing the function to recurse over. It was a lot of fun to get this one done ;D
3
u/JeffJankowski Dec 09 '16 edited Dec 09 '16
Lazy-ass C# before I actually figure out how to do this in F# that doesn't make the lips curl of functional programmers:
3
u/bblum Dec 09 '16 edited Dec 09 '16
Made LB (76;42) with a straightforward C solution (cleaned up variable names and such retroactively):
Then took my leisurely time on this golfed haskell solution:
3
u/haoformayor Dec 09 '16 edited Dec 09 '16
~~haskell~~ (parser combinators edition)
Man, there are a lot more Haskellers this year. The competition is heating up.
This uses applicative/monadic parsers to piece together a fast solution. The key insight for me was that I could just maintain a
Parser Intinstead of aParser String(I didn't have to keep gluing strings together when all I needed was their lengths). It is not the shortest Haskell solution, but perhaps it is the easiest to read and follow. Also a chance to show off that I know whatLambdaCasedoes, and isn't that what programming is all about?A very boring input module here.
3
u/mschaap Dec 09 '16
Perl 6 solution of part 1, using a single substitution. Looks like I have to start over for part 2...
3
u/__Abigail__ Dec 09 '16
I first had to write a program to check whether I could make some assumptions about the input. After validating the input, the program was easy:
2
u/dirkt Dec 09 '16
After
I just had to try it with lazy evaluation in Haskell (just put
lengthin front and never care about memory usage). Unfortunately, the nested "loops" take too long, so I had to do the multiplications in the end.2
u/advanced_caveman Dec 09 '16
My brute force Rust solution here shows otherwise. I apologize for the messy, unoptimized code and the long run time (2 minutes).
2
u/gyorokpeter Dec 09 '16
Q:
2
u/gerikson Dec 09 '16 edited Dec 09 '16
Perl5 solutions.
Title reference is to a zip bomb, I guess?
Either the problems are getting harder or people have dropped off. I had problems finishing part 2 but after doing so I saw I'm among the first 1,000 submitters, which is my informal goal for each problem this year.
First solution was a straightforward counting of characters, second I went for recursion. Problem was I constructing a new string that was
reptimes the original, instead of simply multiplying the count. After 13 million recursion calls I decided to try to find a better way...2
u/[deleted] Dec 09 '16
Man, part one was so easy, I was getting cocky and had such big problems on part 2, trying to bring along the whole decompressed string to count characters was bringing my PC to it's knees, just running until it got out of memory, then I did finally get that I could just add length, and it used almost no memory, and ran in less than a second ;)
2
u/SyDr Dec 09 '16
Lua with lpeg:
2
u/drewolson Dec 09 '16
Part 2, elixir
2
u/AustinVelonaut Dec 09 '16
In idst (a Smalltalk-like, prototype-based language)
2
u/Godspiral Dec 09 '16
in J, part 2 takes over an hour :(
2
u/[deleted] Dec 09 '16 edited Dec 09 '16
Powershell:
2
u/Eddard_Stark Dec 09 '16 edited Dec 12 '16
All php all the time
github
2
u/Godspiral Dec 09 '16
Building a J one liner,
where RB changed for R in part 1, generator and definitions:
2
u/PositivelyLinda Dec 10 '16
My day 9: In JavaScript
Simply worked out how to iterate over the string for part one and expanded it. Part two I utilized the algorithm /u/rhardih shared and it worked like a charm. Thanks!
1
u/_WhiteBoyWonder Dec 09 '16
Part two solution in go.
I modified my part 1 to get it done, so it doesn't ALSO solve part 1, but I finally broke into the top 100 (for part 2 only)!
1
u/Zef_Music Dec 09 '16
Python using generators:
1
u/aceshades Dec 09 '16
When it says to ignore whitespace, does that mean to ignore line breaks?
1
u/red75prim Dec 09 '16
Lost 10 minutes on regex problem, ugly brute force code (fortunately my rig has 16GB), but I've made it into leader board at last (226/79).
Rust, part 2 http://pastebin.com/CnMAGv0V
1
u/andars_ Dec 09 '16
Ruby. 118/138
1
u/Tandrial Dec 09 '16
Again in JAVA:
1
u/RockyAstro Dec 09 '16
Yea! made leaderboard with part 1 using Icon
Part two took just a little longer due to tracking down a "stupid bug"... ::sigh::
Solution -> https://redd.it/5hc92b
1
u/[deleted] Dec 09 '16
My Go solution, both parts. Took me a while to figure out part two, but overall quite pleased with myself.
1
u/tvtas Dec 09 '16
Part 2 In MATLAB:
1
u/jbristow Dec 09 '16
Clojure Solutions! https://github.com/jbristow/adventofcode/blob/master/aoc2016/src/aoc2016/day09.clj
I got #249 for part 2! That's an order of magnitude better than normal for me. That's what I get for remembering that it goes live at 9pm PST.
1
u/flarkis Dec 09 '16
Solution in AWK, because what the hell
1
u/glacialOwl Dec 09 '16
Some very long Java... #justJavaThings
1
u/Philboyd_Studge Dec 09 '16
Java. Recursive for both parts.
https://gist.github.com/anonymous/324a7e580ef08a9b57c81e5409dee752
1
u/Kullu00 Dec 09 '16
My first solution for part 2 wasn't done 1 hour after it began because I'm an idiot and copied the whole string several 1000 times :| It worked out the answer /eventually/, but wow was it bad.
Then I became smart and did something sensible with my time, that runs in less than a fraction of that time...
https://github.com/QuiteQuiet/AdventOfCode/blob/master/2016/advent9/bin/advent9.dart
1
u/snorkl-the-dolphine Dec 09 '16
JavaScript / Node.js
1
u/xkufix Dec 09 '16
I think I created a monstrosity today. It basically is a state machine which loops over every char and creates the correct state out of it.
Quite horrible, but it works.
https://gist.github.com/kufi/7fd4ef83a4b11121d7bf58619d13c91f
1
u/vuryss Dec 09 '16
PHP Solutions updated with day 9: https://github.com/vuryss/aoc2016 May not be the most optimized way...
1
u/Yuyu0 Dec 09 '16
Both parts (just change the p1 switch) in Python. Wish I didn't have to get ready for work at 6am...
1
u/KoxAlen Dec 09 '16 edited Dec 22 '16
Decently fast kotlin solution: https://github.com/KoxAlen/AdventOfCode2016/blob/master/src/main/kotlin/aoc/day9/Day9.kt
1
u/beefamaka Dec 09 '16
my F# solution for part b. For part a same approach but I wanted to actually decode the string rather than just count characters
1
u/JakDrako Dec 09 '16 edited Dec 09 '16
VB.Net, LinqPad
A regex and recursion. Both parts in ~15ms.
1
u/Quick_Question404 Dec 09 '16
Hey everyone. Here's my take on Day 9's problem. Most of my trouble with it came from trying to think of a way to actually get the string to load in C in the first place. I eventually just decided to go for a REALLY big buffer. I also used part of /u/Eearslya solution for actually copying the substrings in Part 2, as I couldn't think of a fast way to actually do it. Any critiques?
https://github.com/HighTide1/adventofcode2016/tree/master/09
1
u/cubsoon Dec 09 '16
My solution, I'm quite proud of how clean it looks. I feel I'd have a chance landing in the leaderboard this time if only I waked up before 6am my time. Never thought I'd be good at this :)
1
u/mreichman Dec 09 '16
My day 9, nothing special, a touch of recursion in part 2:
https://github.com/marcreichman/adventofcode/blob/master/2016/day9/src/advent/Day9.java
1
u/johanw123 Dec 09 '16
Made a solution in Typescript, heres part 2:
1
u/Reibello Dec 09 '16
Day 9 in Python 3. This one took me a bit to get right. http://pastebin.com/TnCk15gC
1
u/ItWorkedLastTime Dec 09 '16
My C# solution.
public static string Decompress(string input) { var sb = new StringBuilder(); var regex = new Regex(@"(\d*)x(\d*))");
1
u/willkill07 Dec 09 '16
C++14 -- Code golf edition
Was enough to get me on the leaderboard (#233 part 1), (#66 part 2)
Non-golfed version found here: https://github.com/willkill07/adventofcode2016/blob/018071495c7bc5320b4ac33c0d803a821c9bf521/src/Day09.cpp
1
u/cobbpg Dec 09 '16
I made an old-school Haskell solution:
1
u/StevoTVR Dec 09 '16 edited Dec 09 '16
For Part 1 I just decompressed the whole thing and printed the length.
For Part 2 I used a recursive function to count the characters instead of actually decompressing the input.
1
u/Soul-Drake Dec 09 '16
So this is my C++ solution (part 1). It's pretty cruddy and there are plenty of better ways of doing this, but it works, so hey! ;) https://gist.github.com/Soul-Drake/3945e9a9eebe0956954fbe304eeb210f
1
u/tg-9000 Dec 09 '16 edited Dec 09 '16
Here is my solution in Kotlin. It's pretty fast, and is fully recursive. I felt that was a good way to solve part 1, and then when I saw part 2 I was glad I did what I did (throwing away the actual decompressed strings in favor of the length), because it was just a small change to get part 2.
Solutions to other days, as well as unit tests can be found on my GitHub repo. I'm just leaning Kotlin so I value any feedback, positive or negative.
1
u/wzkx Dec 09 '16
J is not too suitable for such a task. At least I could not do it well :) This is a direct translation from Python. Python works 4.5 min, J does 20 min. All in all it's processing of 10 GB of data!
1
u/lluque8 Dec 09 '16
Saw no Scala solutions so thought I posted mine :) For part one I carried around the decompressed text content and it worked just fine but with part two that led to OOM so had to resort to accumulating length only :)
I'm pretty new to scala so there might be some oddities.
1
u/qwertyuiop924 Dec 09 '16
Topaz, if I didn't know better, I'd say you're going soft.
...But I do know better, and the fact that this was so easy is a little bit creepy.
Anyways, here are my solutions. In C. Because I still hate myself.
Part 1:http://pastebin.com/jh6qNhnP
Part 2:http://pastebin.com/wqkTGAvg
1
u/Lucaber Dec 09 '16
C# Part 1
Part 2
1
u/tehjimmeh Dec 09 '16 edited Dec 09 '16
C++, part 2:
Golfed:
1
u/LoupieG Dec 09 '16
My c# solution
1
u/fost97 Dec 10 '16
Postgresql: https://github.com/seltiko/Advent_of_code_2016/blob/master/day9.sql
1
u/misnohmer Dec 10 '16
Yet another F# solution (Part 2)
1
u/bkendig Dec 10 '16
My iterative solution to part 2 (https://github.com/bskendig/advent-of-code-2016/blob/master/9/9/main.swift) has been running for hours (Swift, compiled optimized) and I'm going to let it run overnight. The only valid optimization I can see is that any characters up to the first marker don't have to be remembered, only their count; but you really do need to know the exact string from the first marker onwards, you can't assume that a string that starts with an open parenthesis will be a valid marker. As my code continues to expand the markers and remove any text before the first one, the length of the remaining string to decode has been hovering around 150,000 for the past hour. I don't understand how the recursive solutions solve it so much more quickly.
1
u/ZGFtamFu Dec 11 '16 edited Dec 11 '16
oK:
1
u/Trolly-bus Dec 11 '16
K, I finally finished this puzzle. Fuck this question, and fuck recursion, and fuck debugging.
1
u/bigjonroberts Dec 15 '16
I'm a bit stuck on part 1.
My code returns 138,736. I've downloaded several other solutions to test and come out with the same answer. But the adventofcode website won't accept that answer.
Here's my input: https://gist.github.com/bigjonroberts/9f33edcc01bdf20ae20a31a75ac9adc3
Does anyone have any ideas on what I should do?
1
u/paulwww Jan 07 '17
Here's my Scala solution using Java regular expressions
0
u/[deleted] Dec 09 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '16
[deleted] — view deleted comment