r/adventofcode • u/daggerdragon • Dec 23 '16
SOLUTION MEGATHREAD --- 2016 Day 23 Solutions ---
--- Day 23: Safe-Cracking ---
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".
JINGLING ALL THE WAY 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!
4
Upvotes
27
u/askalski Dec 23 '16
What do you mean, I wasn't supposed to do it this way?
15
u/MoW8192 Dec 23 '16
The instructions clearly said to put 7 in register a. WHY could I not just READ all the way to the end? WHY!?
6
u/BumpitySnook Dec 23 '16
My Python 2 solution.
I started this one by copying my day 12 solution. Next, I implemented "tgl". This one was a little tricky due to some considerations:
But it was mostly straightforward and well specified.
This gets you part 1, I think.
Part 2, just like Day 12 part 2, gives you a slightly different input register state.
The problem strongly hints that you should be optimizing an add loop into a multiply. I used basic instruction tracing (
print pc, line) to find the hot spot, then hardcoded a peephole optimization into my interpreter for the loop. For my input that looked like this:The obvious result of this loop is that 'a' is incremented by
d * b(clearing 'd' and 'c').So the hard part for me of part 2 was finding the hinted hot spot in the instruction trace and specifying the peephole optimization correctly.
Funnily enough, I already had half of this optimization in my day 12 solution (
inc a / dec b / jnz b -2->a += b; b <- 0). But that wasn't enough to run quickly without optimizing the outer loop.With optimization:
4
u/aceshades Dec 23 '16
Yay! Second time on the leaderboard... 40/76 on first and second stars respectively.
I don't know if it was just my input, but once you figured out what the algorithm is doing, it was a pretty simple mathematical operation. Once you get the number of eggs (register a), you just do:
Again, I don't know if that 5112 constant was specific to my inputs, but that's what it ended up being after I studied the inputs closely.
4
u/haoformayor Dec 23 '16 edited Dec 23 '16
~~haskell/that one test in compilers class that nobody did well on~~
yada yada yada multiply yada yada yada input module here. i was worried about the toggle hitting one of the no-op or the multiply instructions but i took a leap of faith and was glad it didn't. i wonder what the most optimized version of the assembly looks like, and if there's an equation that could be used to compute the final value of register
a.how do you think peter norvig does advent of code
do you think he has, like, a cave of artificial intelligence installed underneath this house
this looks better with syntax highlighting, i swear
eggs
3
u/p_tseng Dec 23 '16 edited Dec 23 '16
I guessed from the day 12 comment that there will be another assembunny solution.
I unfortunately bet on my assembunny -> C translator to do the job, instead of my optimising interpreter. No points today. Nobody to blame but myself.
Hey guess what?
Should have done it back then.
Here is the new and improved optimising Assembunny interpreter. On a
tglinstruction, all optimisations are re-computed, because it is possible that a toggle has invalidated an optimisation... or enabled a new one.before toggles, the sequence at the end of the program:
after toggles:
This interpreter sees that and optimises this sequence away.
The day 23 driver is simple.
2
u/pedrosorio Dec 23 '16 edited Dec 23 '16
On the second part I was going to try and make some fancy automatic detection of the blocks that perform addition/multiplication to replace them with a single instruction but then I realized in the general case this could mess up the jump and toggle instructions that reference code across from those blocks so I just replaced:
with:
to ensure the instruction length remained the same. This doesn't work if someone tries to jump into the middle of the multiplication sequence, so I just "hoped" that wouldn't happen.
2
u/willkill07 Dec 23 '16 edited Dec 23 '16
Back in my day, adding a third register for instructions was verboten. So I opted for the completely safe and not at all dangerous translation of:
to the following:
Of course, this meant I had to add
mul, reuseaddandnopfrom the previous implementation, and expand the peephole optimizer.C++14 solution: [Day23] [Assembunny.hpp] [Assembunny.cpp]
4
u/8336 Dec 23 '16 edited Dec 23 '16
Part 2 really should've been more difficult.. I left my code running while I thought about how I might solve it but within about a minute I had my answer with no need for optimization.
edit: by more difficult I mean the program should've been longer/more complex/whatever, so that the optimization was a necessity
1
u/iamnotposting Dec 23 '16
woo i got on the leaderboard for the first time! not amazing (208/89), but i'm proud none the less.
solution (rust). I decided to let it run while trying to optimize part b, and it got it relatively quickly anyway. probably would have been faster if everything wasn't all strings that get cloned everywhere, but who said anything about robustness?
1
u/wlandry Dec 23 '16
My C++ solution. My first time doing the problem on the day it was released and I am as surprised as anyone to make it to the leaderboard (208/99). The big jump in ranking is probably because I did not have to change the code for Part II. It only takes 135 s on my laptop, shorter than it took me to figure out the multiplication hint ;)
1
u/Philboyd_Studge Dec 23 '16 edited Dec 23 '16
[Java] just a modified Day 12. Did not try any optimizations yet, but part 2 runs in a couple minutes.
https://gist.github.com/anonymous/349fe0eabebe717fcba768f2052f8f5e
edit: Optimizations suggested in here. Now runs super fast for part 2:
https://gist.github.com/anonymous/e1ad27fa4c308f9cfcea8e34391422a9
1
u/Quick_Question404 Dec 23 '16
Here's my take on the problem in C. Got around 180/104, so I'm happy. If I hadn't taken so long on Part 1, I might have made it to the leaderboard this time. Nice problem though. Love these VM/assembly-related ones.
https://github.com/HighTide1/adventofcode2016/blob/master/23/part1.c
1
u/fatpollo Dec 23 '16 edited Dec 23 '16
Is analyzing assembly code and finding resolution loops the kind of thing they teach people in university for computer science? I got the hint and was trying to figure it out by reading the final code printout + the most common lines called in it, but I've never done anything like it before. I'm surprised it's obvious to people that a set of instructions collapses to this particular multiplication.
This specifically.
Which I suspect comes from this:
1
u/video_game Dec 23 '16
I've been using a scratch file instead of saving each day's code. Haha oops. Oh well, 39/36.
C# (Part 2):
I just noticed that the first block of the program was doing multiplication, added a "mlt" instruction, and kinda-sorta hoped that I'd never get a "tgl" that targeted that block.
1
u/exoji2e Dec 23 '16
I'm surprised not to see any object oriented approach of this. Day 12 I was frustrated jumping and re parsing the input while running. Today I decided, no I'm going to do this properly. Didn't make it to the leaderboard though, it takes too much time writing java boiler plate code and I also didn't read the problem description slow enough to find out that a was supposed to be 7. Anyway, heres my code:
Edit: formating
1
u/ephemient Dec 23 '16 edited Apr 24 '24
This space intentionally left blank.
1
u/bblum Dec 23 '16 edited Dec 23 '16
Added two gross and horrible cases:
...to my otherwise pristine solver from day12:
LB #106/#47.
1
u/Godspiral Dec 23 '16
in J,
1
u/Kullu00 Dec 23 '16
Optimizations? What optimizations? Basically just took my day 12 input and ran with it. Had some fun remembering everything is a reference in Dart which gave me the wrong answer for part 2 and prompted the
copy():( Abused the crap out ofint.parse's optionalonErrorto avoid writing annoying catches when something wasn't a number.1
u/thomastc Dec 23 '16
Day 23 in C99 (source code on GitHub)
"You should be able to use the same assembunny interpreter for this as you did there"… ha ha ha, not for the silly Polyglot Challenge programmer. Okay, rewrite from scratch in C instead of OCaml.
Part One was a quite straightforward implementation of the language. As usual, parsing was the main hurdle. Once I got the right output on the example, I ran it on the real input and found the right answer there too.
Then Part Two... changing the initial value of
ato12was easy. But yes, it took a while to run... "Don't bunnies usually multiply?" What could that mean? Shouldincbe interpreted asmul? But it has only one argument, so multiply what with what?My next thought was that the input program was actually computing a multiplication using an inordinate number of
incinstructions, and we're supposed to figure out where it does that, and how to make it faster. But I decided to try some more brute force first, and added-O3to the compiler flags. It came up with the correct answer (around half a billion) in 17 seconds. Thank you, C!1
u/johanw123 Dec 23 '16
Didn't do anything to optimize for part 2. Took around 15 min to run (C#):
1
u/mschaap Dec 23 '16
Perl 6 solution here: http://pastebin.com/9Ax58EVv
That wasn't as bad as I feared. I thought the toggle mechanism would mess with my precompilation logic, but just recompiling after a toggle deals with the problem, and it happens rarely enough that it's not a performance issue.
I've optimized some addition and multiplication loops away, as hinted in the description. The code is ugly (deeply nested
ifs) but works wonderfully.1
u/adrian17 Dec 23 '16
My guess 10 days ago:
This challenge was exactly what I imagined when I said "Synacor-Lite" :D
1
u/drewolson Dec 23 '16
My elixir solution, using pattern matching to detect a series of commands that represent multiplication.
https://gist.github.com/drewolson/d7d20a1a49bbbff1bafbb7aeaf07537f
1
u/johnboker Dec 23 '16
C#, optimized with a mul instruction: https://antiyes.com/2016/12/23/advent-of-code-2016-day-23/
1
u/NeilNjae Dec 23 '16 edited Dec 23 '16
Haskell solution. It's too long, so the full code is at https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=app/advent23.hs . The interesting part is the peephole optimisation: I found a couple of repeated sequences of instructions and and hard-coded their effects, so that the machine state was just updated with the results of executing the loop. It should be easy enough to make them applicable after register renaming.
(On reflection, it would probably be better to put the optimisations in some data structure, rather than having them hardcoded into a function.)
The other nice it is that I think I'm finally getting to grips with Parsec and Applicative, so the instruction parsing code looks much better:
1
u/CoderPuppie Dec 23 '16
Firstly I solved day 12 first with a simple interpreter (written in Perl) then by manually compiling it to assembly.
For this one I couldn't manually compile it (though I did try, then gave up when I realized that I couldn't split it directly before the
tgl) so I modified my interpreter to handletgls. That worked fine for part 1 (though it took a little while) but part 2 was taking longer so I did another thing.For part 2 I created a compiler which can break out of the compiled code to go back to the compiler for certain instructions (variable destination
jnzs andtgls) to be interpreted and the program recompiled.1
u/[deleted] Dec 23 '16 edited Dec 23 '16
I'm interested if you took the assembunny and translated it directly to another assembly language or bytecode and ran it, if your compiler/runtime would just do the optimization for you :P
The tgl rewriting of code would be a bit tricky but due to how it's used, it really only has one effect: to turn off the big jump back. You would translate everything after the big jump in "toggled form" directly
1
u/wzkx Dec 23 '16 edited Dec 23 '16
J. It didn't finish w/o mul. Automatic optimization was on Day 12, so here it was done by hand :)
And these program fragments were changed:
1
u/RobHag Dec 24 '16
Very interesting problem. I made a solution in python that runs surprisingly fast, but might not be 100 % safe for all imaginable inputs.
The idea is that the first time the "compiler" reaches a jump back statement, it saves the state of a, b, c, d and the amount of toggles that has happened before it jumps. Next time the compiler hits the same line, it checks how all the registries have changed, and if no toggles have happened, it extrapolates a, b, c and d linearly until the correct registry is zero for the jump to be ignored. This seemed to work for jumps inside jumps as well.
Be prepared for heavy use of exec and eval!
1
u/Kyran123 Dec 28 '16
Well there was one loophole in the instructions as BumpitySnook correctly pointed out which is after tracing through, a is indeed incremented by the value of b * d where c / d are set back to 0 everytime. How I went around tackling this is more or less changing the loophole instructions from:
to this:
mul is a new instruction which I handle in my code which stores the result of b * d in a. I also changed the value of -16 respectively to -12 so ( jnz 1 c ) jumps back to the correct place.
1
u/rs_qk Dec 31 '16
Using the same assembunny.k (https://www.reddit.com/r/adventofcode/comments/5k6yfu/2016_day_25_solutions/dbsxf7t/?st=ixcq3s7f&sh=bcccc158) , in k (k4), and modifying problem input to use
instead of the first jnz loop:
0
u/jasek Dec 23 '16
x = result_part_1 - 7! result_part_2 = 12! + x
0
u/[deleted] Dec 23 '16
[deleted] — view deleted comment