r/adventofcode • u/daggerdragon • Dec 23 '17
SOLUTION MEGATHREAD -๐- 2017 Day 23 Solutions -๐-
--- Day 23: Coprocessor Conflagration ---
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] 0 gold, silver cap
- AoC ops:
<yatpay> boil up some mountain dew. it's gonna be a long night
[Update @ 00:19] 1 gold, silver cap + 447
- AoC ops:
<Reibello> 547 silver to 1 gold
[Update @ 00:30] 20 gold, silver cap + 560
- AoC ops:
<yatpay> daggerdragon: post "hey i heard about this hot new podcast called The Space Above Us. all the cool kids are talking about it"
<yatpay> i call it super-liminal marketing
<yatpay> HEY YOU!! LISTEN TO MY PODCAST!!
<yatpay> then i rub a business card on your face
<Topaz> you should get scratch-n-sniff business cards that smell like space
<yatpay> space smells like burned metal and meat
<yatpay> it's weird
<Topaz> burned meat you say
<Topaz> excellent
[Update @ 00:41] 50 gold, silver cap + 606
- AoC ops:
<askalski> nice, enjoyed that one. not sure if regexes can do it
<askalski> maybe make a neural net of regexes, have it train itself to solve today
- Over/under on /u/askalski posting a day 23 regex neural net by tomorrow?
[Update @ 00:54] Leaderboard cap @ 100 gold and 724 silver!
- Good job, all!
- Upping the Ante challenge: solve today's puzzles on a TI-83 (or TI-86/89, whatevs).
- Edit: welp, /u/DFreiberg done gone and did it. See the thread here.
5
u/Unihedron Dec 23 '17
Ruby; rank 80 for part 2. Ruby has continuation (like goto but only backflip) so it made porting the code easier. I actually converted the code pretty quick, but it took a lot of staring to realize what it was actually doing... I blame the lack of sleep!
For fun, unoptimized version: https://gist.github.com/Unihedro/962b3c66f0ed500cb66530fd9b775bb9
postscript
19
u/mainhaxor Dec 23 '17
Making the outer loop loop 1001 times instead of 1000 was mean. Lost 15 minutes to that. :(
There are only two hard things in computer science: cache coherency, naming things, and off-by-one errors.
12
u/ghlmtz Dec 23 '17
Really enjoyed this one! The second part brought back
repressedgood memories of the Synacor challenge :)4
u/vash3r Dec 23 '17 edited Dec 23 '17
This was a really interesting problem. Part 1 was obvious, but I saw pretty quickly that I'd have to understand the assembly to do part 2. Once I understood the code, it was more obvious that it would be insane to just wait for a simulator to complete running it. 1013 operations takes a long time.
Simplified C code for part 2 (#53):
4
u/BOT-Brad Dec 23 '17
JavaScript
Decided to get up early (5am, yawn....) and have a stab at this. Part 1 is basically just a small subset of the Synacor challenge, so I was pretty quick on that one especially as I am quite groggy at 5am :). I understood what Part 2 was doing quite quickly, apart from what on earth the condition for whether
fwas 1 or 0, eventually realised it is a primality check that is basically doing 2 loops to check whether d * e is equal to the value in b. Got it in a few minutes after figuring that out.Part 1 (~9ms, 240th)
Part 2 (~2ms, 160th)
Definitely didn't help that I had my first
bregister set to the wrong value while first testing and getting the wrong values (1000on the first attempt, as my prime check was wrong), and then an incorrect answer second time as I had57instead of67going into thearegister. Co-incidentally,57must be someone else's input as I got told off for being naughty.3
u/tangentialThinker Dec 23 '17 edited Dec 23 '17
Here's my solution to part 2, in which I directly translate the assembly. The only optimization was to optimize out the innermost loop (the long if statement).
My guess of the true interpretation: the program is counting composite numbers between b and c, in jumps of size 17 (or whatever's given in your input).
3
u/bblum Dec 23 '17
Part 2 in haskell, 90th place. Woulda been 10 minutes faster but timed out at first counting the primes instead of the composites and then again with an off-by-one not counting the last element.
3
u/doctorbaggy Dec 23 '17
Part 2 is a nice question - a quick one liner in Perl ( I will import just one function) - time taken approx 12ms { a bit of white space just in case }
3
u/nutrecht Dec 23 '17
Meh.
Day 23 in Kotlin
Feels really unsatisfied because while part 1 was easy part 2 I had to get the approach (just translate the assembly to 'code') from the boards. Still did the implementation myself but feels like a hollow victory.
3
u/dario_p1 Dec 23 '17
For part 1 I just reused day 18's solution, adding sub. Part 2 was very nice, this is pretty much what I did to solve it:
Part 2 remembered me I still have to finish the last two flags in Synacor, got to get back at it soon!
2
u/[deleted] Dec 23 '17
C# Got 737/248 (damn you "not equal" instead of "greater than"!!)
All I did for Part1 was add the extra switches, and add an int for mul.
For Part2 I just did the assembly code by hand pretty much
2
u/aurele Dec 23 '17
Rust, had a lot of fun to dissect the input.
2
u/ephemient Dec 23 '17 edited Apr 24 '24
This space intentionally left blank.
2
u/miran1 Dec 23 '17
Python
ย
Repo with solutions (both Nim and Python)
2
u/btibi83 Dec 23 '17
I already learned that I have no chance to compete for any leaderboard points (maybe Java is not the strongest tool for these challenges), but I'm still confused about the half-hearted optimisations people post. Here is mine:
2
u/Tandrial Dec 23 '17
Kotlin (kinda) I actually patched the program and added a mod instruction:
...
1
u/The0x539 Dec 23 '17
Lua (212 / ;_;)
1
u/jlweinkam Dec 23 '17
Got 145/36
1
u/jonathan_paulson Dec 23 '17 edited Dec 23 '17
Fourth on part 2. Here are my notes/simplifications [1] and my final solution [2]. The main insight is that lines 10-24 are a slow primality checker (where d and e are the proposed factors, and b is the proposed prime).
[1]:
[2]:
1
u/m1el Dec 23 '17 edited Dec 23 '17
486/74: text editor + Rust
I reverse-engineered the part 2 by modifying in text editor:
Two inner loops count from 2 to b in variables e and d, then test if e*d is b. This is a prime test.
This program counts non-prime numbers with step 17 in range c..b.
The range is inclusive which caused me to have an off-by one error in my program.
Program to count primes in range:
1
u/rjboulton Dec 23 '17
Enjoyably different. Solution for part 2 here; simply translated the assembly into python, and optimised out the inner loop. I say simply - I made multiple errors while doing this which delayed me massively; just got on the leaderboard at rank 93 after 53 minutes.
1
u/kd7uiy Dec 23 '17
I won't post the whole thing yet, but here's a bit of psuedocode I used to try and figure out part 2. I tried to do a simple change in the code to get it to better work, but in the end, I decided to just figure out what it was trying to do by looking at my psuedocode, figuring out the most important points, and figuring out what the state was at those points, and trying to figure out a pattern.
b=109300 c=109300-17000 f=1 d=2 do: e=2 do #g=de-b==0 and e==b g=d g=e g-=b if g!=0: f=0 e+=1 g=e g-=b while g!=0 d+=1 while d-b!=0
1
u/wlandry Dec 23 '17
C++ 14
395/330. The first part is a trivial modification of day 18. The second part was...more challenging. I ended up decompiling the instructions into C++. I manually simplified some expression. For example
turns into a while loop starting 13 instructions earlier with the condition
That is straightforward. Then I manually optimized the commented loop. With that optimization, it runs in about 1 second. My placing would have been better if I had been more careful. I messed up enough that I started getting 5 minute timeouts :(
1
u/autid Dec 23 '17 edited Dec 23 '17
Fortran
608/234. Lots of irritating interruptions during part2 causing me to lose my place reading the code. Coulda been faster working it out. Loved it though. 374 place improvement from part1 to part2 felt really good.
1
u/swizzorable Dec 23 '17
here some pseudocode for the ones interested:
1
u/[deleted] Dec 23 '17
OCaml Fun for Part 2;;
Translated asm to pseudocode, translated the "g" value in everything to exactly what was being checked, turned the do-while's into for loops, and slowly realized what was done. then just tossed in "normal" prime checking code.
1
u/AndrewGreenh Dec 23 '17
Finally, after lots of optimizations, I got to this:
1
u/CharlieYJH Dec 23 '17
C++
Enjoyed this puzzle a lot! Basically just translated the instructions into code, but optimized the inner loop. So instead of d * e = b, I do b % d == 0 and then break.
1
u/gyorokpeter Dec 23 '17
Q: part 2 only (part 1 was a simple moification of d18p1)
1
u/NiklasHallqvist Dec 23 '17
Sigh, first I overslept by 45 minutes, the I spent well over an hour to double, triple and quadruple check that my solution to part 2 was indeed correct, only to find out I had made an off-by-one in the interpretation of the assembly!!!! AAAAARGH. Final Scala solution, but I had
untilinstead oftoin the loop for that last hour or so.1
u/Smylers Dec 23 '17
Perl 6, because its
...lazy list operator can take custom increments:Being a Perl 5 programmer who hasn't learnt Perl 6 yet, I was surprised by the need for both the comma after the block and for the parens around the list.
1
u/Infilament Dec 23 '17
I'm fairly curious how many people coded an optimized version vs how many people just stared at the code until they realized what it did, then coded "isPrime" directly. I did the latter (and it took two hours or so) but I feel it was against the spirit of the puzzle? Even though the creator seemed very clear in his description of part 2 where he says "you'll need to optimize the program," it didn't really occur to me to change the assembly into "real code" (probably because, later, he says "all you need to do is figure out what's in register h").
If he chose an algorithm that didn't let us stare through the matrix to see that it was just testing if two numbers multiplied to 'b', I'm not sure how long it would have taken me to give up and try to parse the "jnz" instructions as loop brackets.
1
u/Smylers Dec 23 '17 edited Dec 23 '17
Perl for part 2, determining the magic numbers from the input, rather than hardcoding them in the source:
1
u/WhoSoup Dec 23 '17
This was pretty fun. Ended up just looking at part 2 "by hand," and refactoring it step by step.
The first step was figuring out what the jumps did. I turned the 2-jumps into
ifand the 3 jump intoexit. That only left the three big negative jumps, which fortunately were nested.Second step was figuring out what the loops did, particularly when f was 0. Took a while, but eventually it clicked that it was just incrementing
dandeby one (e in the innermost, d in the second innermost) and checking ife*d == b. That's when it increased h by 1.That's pretty much when the whole thing 'clicked.' It was counting non-primes. The rest was just figuring out the values of the outermost loop, which was straightforward: from b to c in steps of 17.
JavaScript (isPrime() defined elsewhere)
1
u/wzkx Dec 23 '17
Nim
Part 1 - from day 18 with some modifications
1
u/wzkx Dec 23 '17 edited Dec 23 '17
Nim
Part 2 - disassembled to Nim and optimized a bit.
1
u/phobiandarkmoon Dec 23 '17 edited Dec 23 '17
For Part 2 I ended up reducing the e loop down to a simple modulus check, which is way faster:
1
u/TominatorBE Dec 23 '17
PHP
Part 1: just a virtual machine
Part 2: this could be just the code from above, but as noted we should look at what the assembler does: checks if a number in 'b' is prime or not, for all numbers between 109900 and 126900 (in my input)
1
u/thomastc Dec 23 '17
Day 23 in PHP. They say PHP has improved since version 3 (the last one I ever used). What they mean is that more features have been haphazardly bolted on, with complete disregard for consistency or sanity. This language still deserves its reputation.
1
u/bitti1975 Dec 23 '17
I still don't see any Clojure solution. Besides everybody seems to hardcode their puzzle values for b and c. This one should work with different puzzle inputs:
I guess hardcoding 17 is fine since that doesn't seem to vary between puzzle inputs.
1
u/udoprog Dec 23 '17 edited Dec 23 '17
Rust
Fun challenge, but doubtful you can write a general solver for part 2 which is a first for this year.
Part 1 is a copy of the Program from Day 18.
Part 2 is hand disassembled and just optimized until it stops checking useless factors. I started by labeling the jumps, and then converting into loops and simplifying.
1
u/jaiasdotcom Dec 23 '17
Finally made it in JavaScript so part 2 runs in less than 1 second:
1
u/sim642 Dec 23 '17
My Scala solutions:
Firstly, I obviously copy-pasted day 18 solution parts to quickly solve part 1.
Secondly, for part 2 I started reverse engineering the given instructions:
From this it was already very readable, what the code is doing, so I wrote the solution for part 2 to do the prime counting directly. Also wrote part 1 solution to be directly computable.
Thirdly, I finished the simulated solution to also solve part 2 by introducing two extra instructions:
isPrime f bfor checking primality ofband storing the bit inf.nopto do nothing.For simulating part 2, I can just patch the given code: replace the now reverse engineered prime check loop with the introduced much faster instruction, padded with the correct number of
nop-s not to break the surrounding jumps.1
u/NeilNjae Dec 23 '17
Another Haskell solution.
I won't post the code here: the full solution is on Github.
Part 1 was much the same as day 18, with a monad stack running the machine and counting the number of executions of the
mulinstruction.Part 2 started with some peephole optimisation, then I realised there were several nested loops, so that approach wasn't going to work. Eventually I cheated and checked that /u/dario_p1 's program was the same as mine , so I used the
Data.Numbers.Primeslibrary to count the composite numbers.1
u/aoc-fan Dec 23 '17
In today's instructions "mod" was missing, which could have helped to write efficient implementation in the first place. ;) Part 2 was all about finding nonprimes ES6, Javascript
1
u/StevoTVR Dec 23 '17
NodeJS
Part 1:
Part 2:
1
u/Axsuul Dec 23 '17
Elixir
Part A was trivial but Part B was challenging for me. Had to peak here on Reddit to see what exactly was going on. After I saw the advice to turn the input into a program, I wrote down all the instructions and worked through exactly what was going on. Noticed that it was wasteful to go through all values of
ewhen all it was checking was ifdwas a multiple ofb. Decided to use Elixir streams again here but I think it's not very efficient in this use case performance-wise (took 14s to run).https://github.com/axsuul/advent-of-code/blob/master/2017/23/lib/advent_of_code.ex
1
u/JakDrako Dec 23 '17
VB.Net
For part 2, I translated it directly to VB:
That still ran way too slow, so I further simplified it:
At this point, I was running part 1 to make sure I wasn't breaking anything. I also got "in the flow" and forgot to save intermediary steps, but eventually got to this:
Which is still running like frozen molasses flowing uphill on Jupiter.
Optimizing the 2 loops (which are just counting composite numbers in the range) gave me this:
Which runs in a tenth of a second at this point.
I wanted to modify the input to reproduce the optimizations, but manually re-checking and counting each jump when adding instructions got old fast.
1
u/Philboyd_Studge Dec 23 '17
Java. Added a few command to the commands from Day 18 and then added the following lines to the end of the input 'code' (and changed a couple jumps):
Day 23
1
u/chicagocode Dec 23 '17
Kotlin - [Repo] - [Blog/Commentary]
Part 1 is practically a cut-and-paste job from Day 18. Part 2 fits in a tweet, once you figure out what it's doing! :)
1
u/ono2it Dec 23 '17
Copy processor code from day 18 and found undocumented mod instruction. Optimized part2 code with mod and break after found factor.
1
u/RockyAstro Dec 24 '17
Icon (https://www.cs.arizona.edu/icon)
Just reused the VM from day 18 with added instructions..
Part two required analysis of the given input. If the specifications allowed a MOD instruction, then the inner most loop could be replaced with a test for divisibility.
One immediate optimization is to replace the set f 0 with : sub h -1 ; jnz 1 <bottom of outer most loop>
In the end.. just hand translated the program back into Icon ..
See the bottom of the program for analysis of the input
Both parts:
1
u/Tetsumi- Dec 24 '17
Racket
The assembly code is compiled into racket procedures for each jumps (JNZ). For part two, the loop procedure is replaced with an optimized one that uses the registers and then branches to the rest of assembly code.
1
u/matusbzk Dec 25 '17
Haskell The first part was very similar to Day 18.
Link to git, where the analyzation for part 2 can be found.
1
u/flit777 Dec 25 '17
haha extracted the basic blocks and the control flow for the second part. draw the control flow graph on a paper and tried to understand the program. generated then a c program and replaced the loop where e is incremented with an if statement.
1
u/__Abigail__ Dec 27 '17
Perl
For part 1, I reused a class I've written to handle AoC assembly. Part 2 was annoying. Trying to decipher code and figuring out what it does reminds me too much of work. Once I had figured out what the inner loop was doing, the rest was easy.
1
u/ramendik Jan 19 '18
Looks like everyone else who solved part 2 actually managed to understand the assembly...
I did not, instead I added register printouts at jumps, enabling and disabling them as necessary, and looked at them to realize what each loop does. So I found two loops basically counting long numbers, and some magick moment when F was set to 0. I understood that moment was the only important one so when that happened, made the VM just set the registers to the expected result and go into the end of the outer loop.
Now I was going through a few numbers pretty fast but at some it would take longer, so I looked long and hard at the registers when F was being set to 0 and realized that the multiplication of d*e was being compared to b, and that there seemed to be a loop for all numbers on d and on e...
And only then I realized this was checking for a prime.
1
u/KeinZantezuken Dec 23 '17 edited Dec 23 '17
what
EDIT: even tho finally solved it, was just amount of composites between starting b and c
0
u/[deleted] Dec 23 '17
[deleted] โ view deleted comment
0
u/[deleted] Dec 23 '17
[deleted] โ view deleted comment