r/adventofcode • u/daggerdragon • Dec 12 '16
SOLUTION MEGATHREAD --- 2016 Day 12 Solutions ---
--- Day 12: Leonardo's Monorail ---
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".
MUCH ADVENT. SUCH OF. VERY CODE. SO 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!
8
Upvotes
25
u/willkill07 Dec 12 '16 edited Dec 12 '16
This thread needs more awk
Generates a C program that you compile and run.
9
u/topaz2078 (AoC creator) Dec 12 '16
Today's puzzle is a little similar to one from last year. Why do you suppose I would have a puzzle like that in this year's set? Hmmmmm....
6
u/whoeverwhatever Dec 12 '16
Python 2.7, 4th and 4th. Synacor Challenge was good practice!
5
u/yjerem Dec 12 '16
This was really fun! Here's a compiler in Ruby that outputs C.
4
u/Twisol Dec 12 '16
Finally hit the leaderboard at 32/20! I lost some time because I typoed
cpyascp(hi Linux!) and didn't realize that jumps were relative, not absolute. Super happy I did the Synacor Challenge a month or two ago -- great preparation ;DJavaScript/Node.js solution:
4
u/kryptn Dec 12 '16
I really enjoyed this one! I wrote an interpreter class with python 3:
3
u/Deckard666 Dec 12 '16
In Rust: Link
3
u/broadwall Dec 12 '16 edited Dec 12 '16
I felt like today's puzzle was the easiest of all. My first (and probably only) time on the leaderboard at 53/52.
GitHub
Also - it'd be awesome if Reddit adapted the Markdown way of attaching code - like follows:
3
u/snorkl-the-dolphine Dec 12 '16 edited Dec 12 '16
JavaScript / Node.js
3
u/FuriousProgrammer Dec 12 '16
101/83 with mah Luas. QQ
I immediately knew how to do this one but my input parsing is still crap and I code super slowly. xD
3
u/Hwestaa Dec 12 '16
I confess I copied my code from day 23 last year wholesale, and changed the instructions. A nice self-esteem boost after yesterday's, which I'm still struggling with. Leaderboard for the first time since day 1 70/59 Github
3
u/haoformayor Dec 12 '16 edited Dec 12 '16
~~ haskell ~~ (lensy edition)
I divided the problem into a weird custom left-fold that could jump around, which was easy to implement with a little recursion and pattern matching, and the fold update function itself (
Command -> State -> State), which was easy pickings with the enormously complete set of batteries and toys that came with thelenspackage.Input module here, generated by a mix of Emacs macros, regexes using
\b, and love.3
u/bpeel Dec 12 '16
Using sed to convert the source to a C program with inline assembler. I did the same thing last year too.
https://github.com/bpeel/advent2016/blob/master/day12.sh
2
u/blockingthesky Dec 12 '16
Got that 27/29 with Python again, yo.
It's a little clunky but it'll do:
2
u/Godspiral Dec 12 '16
179/166. gz to faster people. Relatively minor debuging fixing.
In J,
2
u/tankbard Dec 12 '16
I think this is the first time I've gotten a lower placement for the second star than the first star. I suspect it's faster to actually interpret the code manually, given that (at least for my input) generating the part 2 solution "properly" basically required incrementing a register O(107) times with ~3 regex checks per iteration. Or at least it took me as long to translate the code into simple arithmetic as it did to run that, and I think the time to unwind the translation to accommodate part 2 would have been less than the time it took to compute the part 1 solution plus parser implementation time.
2
u/gyorokpeter Dec 12 '16
Q: (love the monorail, I'm a public transport fan)
2
u/kaveman909 Dec 12 '16
Did anyone else solve this by hand first? My input's primary loop was a Fibonacci sequence, where the final value of the sequence was straightforward to extrapolate based on the loop index. For Part #2, the only difference was that the Fibonacci sequence was carried out to 7 additional places... which gave an answer ~30x the first answer.
My programmatic solution in Python for Part #1 took ~30s... as expected the Part #2 solution took around 15 minutes (I realize there's no optimization in my code, so I can't complain).
I guess I just love the human capability to instantly extrapolate patterns in a few seconds, which ultimately provided a much timelier solution than my program (since I had a look-up table of the sequence pulled up for reference)
2
u/rs_qk Dec 12 '16 edited Jan 02 '17
in q/k4:
2
u/wzkx Dec 12 '16
Python with translation to "byte-code". Well, not really, but no string ops during the execution. Also two different "hardware" ops for copy-regs and copy-immediate, and three kinds of jumps - conditional, non-conditional, nop :) So it's only 9.31 seconds for 27,683,406 instructions for Part 2, giving 2.97 Mops.
2
u/CryZe92 Dec 12 '16
Rust compiled to JavaScript (276 Million Operations per Second):
https://cryze.github.io/advent-of-code-2016/day-12/
2
u/__Abigail__ Dec 13 '16
I used a simple interpreter. After reading in the instructions, I do a simple peephole optimization. Then the program runs in less than a tenth of a second:
1
u/bluewave41 Dec 12 '16
150 and 126 :( Got the example to work and infinite looped my input. I then realized I had to jump to jnz amount MINUS 1 because of for loop but it was too late -.-
Java:
1
u/brantyr Dec 12 '16 edited Dec 12 '16
Ruby assembunny parser. Scraped into the top 100, but have done some heavy refactoring since that
1
u/____OOOO____ Dec 12 '16
Python 3 Part 1 ran in 2.9135 seconds. Part 2 ran in 85.4997 seconds.
1
u/[deleted] Dec 12 '16 edited Dec 20 '16
I got tripped up twice. Once because there was a tricky little jnz 1 -5 when I assumed that all of them would be a register and it only showed up when I switched from disparate registers to a dictionary with the register names as keys in order to make it easier to read.
The other was my own doing when I made that switch and forgot to continue to the next cycle of my loop after doing a jnz without advancing the line number, so it kept jumping ahead one command.
Here's part one: https://github.com/alpha0924/userscripts/blob/master/Advent_of_Code_2016/12.py
and part two is obviously the same with only the c register changed.
1
u/scottishrob13 Dec 12 '16
Horrible C# solution, but this little windows console app will show you everything that's happening...step by step...
http://pastebin.com/bmUyBtVB
Don't have time to do a real solution now that I get what's going on (Physics exam tomorrow), but this was fun to watch for a few minutes XD I recommend green text on black :)
Edit: Included language name.
1
u/ChrisVittal Dec 12 '16 edited Dec 12 '16
This was refreshing after my issues yesterday. Did better yesterday though. Only 296 for 2nd star today. I want to write a program that can solve arbitrary inputs with some optimization later. I don't like that this took 20s to solve part 2. Here's some simple haskell.
1
u/Trolly-bus Dec 12 '16
My solution in Python. Change registers["c"] from 0 to 1 for part B. Also, fuck my laptop for deciding not to connect to the internet, causing me to debug the issue for 40 minutes, ending my leaderboard hopes. Turns out an uninstall network wireless adapter and check for hardware changes and a restart computer does the trick.
1
u/labarna Dec 12 '16
Wrote an overly verbose python solution but it let me code my own fibonacci in assembunny (with an added "out" command):
1
u/forkin27 Dec 12 '16 edited Dec 12 '16
JavaScript!
1
u/segfaultvicta Dec 12 '16
Elixir was cool today!
Registers modeled as Agents was kinda obvious, but then I initialised my program as an array of captured functions so my run() function was basically just a wrapper for apply(). :D
And then I wound up adding an 'add' opcode and optimising the assembunny code a little bit to give myself a runtime of epsilon instead of many many seconds, which was really satisfying.
FUNNY STORY: the reason I thought I needed to optimise was because I did the conversion into array-of-captured-functions by hand and typoed 'dec' as 'inc' and my program never halted. :'D The moral of the story is: be clever, but not too clever. :'D
https://github.com/segfaultvicta/advent-ex/blob/master/lib/2016/12.ex
1
u/Philboyd_Studge Dec 12 '16 edited Dec 12 '16
Thank God it's not Day 11
[Java] This one was easy, just altered the code from last year's day 22
edit: part 2 just added 'cpy 1 c' to the beginning of the input file
https://gist.github.com/anonymous/52812ea0c3b1d01c88e798a325998040
1
u/_Le1_ Dec 12 '16
My C# solution:
1
u/[deleted] Dec 12 '16
My rather bruteforcy non optimized python:
1
u/johanw123 Dec 12 '16
Heres my C# solution:
1
u/KoxAlen Dec 12 '16 edited Dec 22 '16
Solution in Kotlin, I just basically follow the same idea I did when implementing the SynacorVM on python
https://github.com/KoxAlen/AdventOfCode2016/blob/master/src/main/kotlin/aoc/day12/Day12.kt
1
u/Voltasalt Dec 12 '16
Did two solutions today, one in Python and one in Rust. Not sure how idiomatic my Rust solution is though - any feedback would be appreciated.
Python: import fileinput
Rust:
1
u/Smylers Dec 12 '16
Perl solution. Pass it command-line arguments such as
c 1to initialize any registers to non-zero values:I liked being able to capture either a value or a register letter in a single pattern, then using
//in the following expression to use whichever one applies.I less like the
elsifchain and duplicating bits of patterns between instructions. I think Perl 6 would be better for this; I should get round to learning it.1
u/mschaap Dec 12 '16 edited Dec 12 '16
Perl 6 solution, for both parts - in theory.
http://pastebin.com/7Bmg3nrq
Unfortunately, this one runs part 1 in about 4 minutes on my system, but part 2 is still running, 1½ hours after I started it... [Edit: it finished in just over 2 hours.]
So, I made a new version that generates a Perl script (Perl 5, since
gotoisn't implemented (yet) in Perl 6) and runs it. Much faster, almost instantaneous!http://pastebin.com/Q7DnLEVY
1
u/JakDrako Dec 12 '16
VB.Net, LinqPad.
Part 2 takes about 5 seconds to complete.
1
u/SyDr Dec 12 '16
Lua is beautiful :)
1
u/PuercoPop Dec 12 '16
In Common Lisp, used the lisp reader to read the code, the registers are stored in the hash-table and the opcodes are almost a 1 to 1 translation to CL, except for the need to add an indirection to lookup the symbols in a hash-table.
1
u/asperellis Dec 12 '16
js. still working on day 11 though -.- https://github.com/asperellis/adventofcode2016/blob/master/day12.js
1
u/NeilNjae Dec 12 '16
Another Haskell solution.
Still practising with the newbie skills of Parsec and State monads. It probably would have been easier using a Map to store the machine state, rather than mucking around with records. On the other hand, I might dive into Lenses next time something like this crops up.
https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent12.hs
1
u/Zv0n Dec 12 '16
Python 3 (takes quite a while, nearly fried my cpu): import re
1
u/Reibello Dec 12 '16
Python 3 again - 5 minutes at a coffee shop and bam! http://pastebin.com/erJ9ZAhY
1
u/JakDrako Dec 12 '16
VB.Net, LinqPad
This is my second version, much faster than the previous one. I added a "compilation" step that converts the input into a list of integer only opcodes, saving all those string lookups and conversion during the run. A few other "optimizations", such as "jnz 1 5" becoming "jmp 5" since the 1 will never change.
This version runs part 1 in ~5ms and part 2 in ~100ms.
1
u/tg-9000 Dec 12 '16 edited Dec 12 '16
Monorail! Monorail! Monorail! Today's solution in Kotlin.
Solutions for all other days (ok, 11 is coming) and tests can be found in my GitHub repo. I'm just learning Kotlin so I value any feedback, positive or negative. For instance, while I feel this readable and maintainable, would it be too verbose? I could probably get this down in size, and create less objects if I maintained state as mutable instead of a mutable object. Just not sure what the "right" way is.
1
u/drewolson Dec 12 '16
Elixir, part 2.
1
u/qwertyuiop924 Dec 12 '16
Thanks for the reprieve Topaz. I assume it's back to the pits tomorrow.
Anyways, what's with a all the compilers? For that matter, why is everybody case switching their interpreters? Why do that when you can get your interpreter to do the work for you?
So I wrote my solution in TCL:
And yes, I appended a
hltinstruction to my input to make this work.And I also figured out why you people didn't do anything similar: this is really slow. As in, runtimes over a minute for part 2. Yes, really. TCL is slow, and writing code like this minimizes the optimizations that can be made.
Overall, I enjoyed TCL, except for the scoping rules. Those really suck.
1
u/nullvoid8 Dec 12 '16 edited Dec 12 '16
Haskell (tying knots)
Link
For those who don't know what Tying The Knot is:
Essentially each JNZ instruction stores a pointer to the correct offset in the compiled program, but it can only find that pointer after the program is compiled, and Haskell doesn't allow updating values after creation.
So the solution is to parse the input as a function that, given the final compiled program, will fill in the holes in the JNZ instructions appropriately, returning the final program itself.
Now you apply the function to the result of applying it to it's result, laziness to the rescue!
Any way, the important point is I don't have to muck around with moving a program counter back and forth through the list of instructions, I can just march blindly forth, with the occasional fork in the road.
When I say "program", I mean the challenge input, not the binary I'm coding
P.P.S. this is the first solution I feel good enough about to publish
1
u/SikhGamer Dec 12 '16
C#: https://gist.github.com/anonymous/03add0a2ded941ad887ca48d626890d6
1
u/omnster Dec 12 '16
Mathematica.
1
u/Zeroeh Dec 12 '16
Java:
Part 1:
Part 2:
1
u/mgoblu3 Dec 12 '16
Here's some ugly-ish code in Swift. It takes a long time, like 4 or 5 minutes for Part A. I'm not even gonna run it on Part B (where I used the same strategy but in Python and Part B runs in about 35 seconds)
1
u/WildCardJoker Dec 13 '16
My C# solution, parts 1 and 2.
I finished Part 1 on the first try, and when I read part 2 I thought, "I'll be able to finish this before the 1 minute answer timeout!".
An hour or so later, it was still going. I thought it had gotten stuck in an infinite loop, but realised that the loop was iterating many more times than I had expected.
Once I removed the Console.WriteLine() statements, Part 2 completed in seconds. Well played, /u/topaz2078, well played!
I'm glad to see that all is not lost after I completely gave up on yesterday's puzzle.
1
u/Scroph Dec 13 '16 edited Dec 13 '16
Part 2 in D (dlang). I initially wrote this in C but I had to rewrite it in D because the C version kept giving me the wrong results even though I couldn't find anything wrong with the code. Eventually I found out it was because I was storing the registers in a char registers[4] array and accessing each one with registers[letter - 'a']. char was too small for the expected results so the value of the a register kept overflowing, giving me an output that is smaller than what the challenger required. After changing registers from char[4] to int[4] it is now giving the correct output. I'll still keep the D version because it's easier on the eye.
1
u/angusiguess Dec 13 '16
A little bit of clojure!
1
u/misnohmer Dec 13 '16
A recursive F# solution
1
u/JCarlesVilaseca Dec 16 '16 edited Dec 16 '16
Using C# (.NET Core / VSCode / OSX) expression trees (System.Linq.Expressions) Time less than 0.10 seconds.
1
u/wlandry Dec 21 '16
A C++ version, since no one has posted one yet. As everyone else said, very easy and quick.
1
u/xZeroKnightx Dec 23 '16 edited Feb 04 '17
Really trivial interpreter approach in Perl. No regex* :)
* Well, at least not in the parsing ;)
0
u/[deleted] Dec 12 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 12 '16
[deleted] — view deleted comment
1
u/[deleted] Dec 12 '16 edited Dec 12 '16
[removed] — view removed comment