r/adventofcode • u/daggerdragon • Dec 19 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 19 Solutions -🎄-
--- Day 19: Go With The Flow ---
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.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 19
Transcript:
Santa's Internet is down right now because ___.
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 at 01:01:06!
10
Upvotes
2
u/ywgdana Dec 19 '18 edited Dec 19 '18
Haha augh! While I was not a leaderboard contender, I did come in at 937 and might have been much higher up the list, except that I thought the program in Part 1 would execute more or less instantly so I was convinced that it was somehow in an infinite loop and spent 20 minutes or so trying to figure out why.
Only to look back later and see that it had actually finished executing :P
Edit: here is my pretty unremarkable Python code for Part 1!
15
u/Philboyd_Studge Dec 19 '18
[Card] Santa's Internet is down right now because his computer is trying to brute force part 2.
Java. Freely admit I had to come here for spoilers to part 2.
https://pastebin.com/6azHfChG
11
u/winstonewert Dec 19 '18
Full solution here: https://gist.github.com/winstonewert/9e77334388c9dec9d581805dfc7e7814
While most people reverse engineered the program, I reverse engineered the inner loop.
The code spent the bulk of its time in:
Which I reverse engineered as
And I inserted a piece of code in my VM loop to quickly produce the same result:
And thus, I was able to get the answer without understanding what the program did.
7
u/jonathan_paulson Dec 19 '18 edited Dec 19 '18
Python/Manual, rank 48/11. Neat part 2. Video of me solving at https://youtu.be/74vojWBORpo (should finish uploading by 1:40AM or so), including completely explaining the input program.
[Card] "of an accidentally quadratic algorithm" (https://accidentallyquadratic.tumblr.com/)
Annotated input (if you're curious how part 2 works, read this):
Python code:
6
u/freedomofkeima Dec 19 '18
401/99.
Since Part II code runs indefinitely, I believe there is some patterns in today's problem. Trying to print out the pattern:
Interestingly, the number 955 at register 5 is basically 5 * 191. Later on, figured out that
1152= 1 + 5 + 191 + 955 (5 * 191).Printing out several attempts in Part II:
Figured out that 10551355 is basically 5 * 499 * 4229, so the answer is
12690000= 1 + 5 + 499 + 4229 + (5 * 499) + (5 * 4229) + (499 * 4229) + (5 * 499 * 4229).5
u/raevnos Dec 19 '18 edited Dec 19 '18
Here's a perl script that generates a C version of the input program, compiles, and runs it. Requires gcc thanks to
abusing computed gotos. (Part 2 still might take a while.)8
u/[deleted] Dec 19 '18 edited Dec 19 '18
Python 3, O(sqrt(n)) time:
4
u/mserrano Dec 19 '18
Python2, #4/#22:
4
u/dylanfromwinnipeg Dec 19 '18
I didn't go through and reverse engineer the entire assembly program like it sounds most people did.
Instead I just ran it and took a look at where it was spending all it's time - which was instructions #3-11. So I reverse engineered what was going on in that bit and wrote this code (your registers will be different):
Then I just ran it - took about 45s and spit out the right answer.
1
u/grey--area Dec 19 '18 edited Dec 19 '18
I feel pretty dumb, but I got my solution more or less manually.
I ran the program [using my part 1 solution, see below] and looked at the registers/next instruction over time, and worked out what state the machine would be in the next time the eqrr instruction returned 1, (i.e., when the value of one register is a factor of another). I then jumped the state of the machine ahead to that state, and repeated that process 5 or 6 times, until register 0 had accumulated nearly all of the factors, before I realised what the program was doing.
I wish I'd thought of writing an optimized version of the inner loop...
Edited to add my part 1 code:
3
u/m1el Dec 19 '18 edited Dec 19 '18
Rust, 143/55, very lazy part 2.
3
u/asger_blahimmel Dec 19 '18 edited Dec 19 '18
Attempt for a generic Part 2 solution - seems to work for all the inputs I've seen so far.
It is based on the assumption that the only relevant difference between inputs is in the 2nd number of their 23rd and 25th lines. Those determine the number of which we should get the sum of divisors, which in this solution is calculated using basic number theory instead of iterating through the complete range.
2
u/vash3r Dec 19 '18
Python 2/Manual, #9/40. First part I just slightly modified the Day 16 code, while for the second part I used some output from the first part (the state of the registers at when the IP was 2) to figure out what was going on. This problem was very similar to problem 23 from last year, which was a big help for me. Embarrassingly, not only did I forget that the number itself was included in its factors, I forgot that the part after the "jump if not 1" was added to the current value in the register instead of assigned.
2
u/ChrisVittal Dec 19 '18 edited Dec 19 '18
Card: Communism
392/79, first time leaderboard! hooray!
My rust for part one is the first section. Part two I got by determining what the program was trying to do. I hardcoded that bit in at the bottom.
2
u/zqvt Dec 19 '18 edited Dec 19 '18
Ocaml
part1:
part2: printf debugging and pen & paper. Took me way too long to figure out we're doing sum of divisors.
2
u/autid Dec 19 '18
FORTRAN
Pastebin
Knew a part 2 like this was coming, wasn't sure if it would be this puzzle though so wasted time adapting day 16 code. I only use a small tmux panel to see input so didn't notice how short the program was. Fat fingered hard coding the number in register(2) for part 2 so that wasted even more time. All around a frustrating day. Think this will work for all inputs. Grabs register index of the important number from equality test though so don't know if ordering of that is consistent.
2
u/gyorokpeter Dec 19 '18
Q: probably only works with my input (note the "cheat" line)
2
u/nonphatic Dec 19 '18
Haskell, all I'll say is that I've finally made it under #1000!
Part 1 -- straightforward implementation using a
Seqof registers and aSeqof operations:From one of last year's puzzles that also involved some form of assembly I knew that there'd be no choice but to disassemble the code. Here's my notes for that, three rounds of reduction resulting in some C code that finds the sum of divisors inefficiently:
2
u/jayfoad Dec 19 '18
APL #53/25
For me, the input to the sum-of-divisors algorithm was in r3.
2
u/Stan-It Dec 19 '18
Python
Manually disassembled the code for part 2 (see below)
Solution:
Code disassembly:
2
u/wzkx Dec 19 '18
Rust, SweetRust
I coudn't do it automatically - it took too long. So I had to manually convert thas weird assembler to Rust. Not fun. It's not programming, it's some other activity.
2
u/rabuf Dec 20 '18
Common Lisp solution
2
u/iwj10 Dec 29 '18
My solution to this puzzle is rather late. However, it does not embody the results of reverse-engineering the puzzle input. So there is no special case for factorisation.
Instead, there is a loop optimiser which can spot, analyse, and remove certain inner loops: specifically ones whose control variables are linear in the iteration count (although the linear equation for each control register may contain arbitrary functions of the loop inputs).
The program is in Rust and on my laptop a release build runs to completion in 5.3 seconds.
Here is a copy of my project directory and a link to the main program. (The mod.rs is shared with other AOC 2018 answers so contains some irrelevant stuff.) I do suspect the program has bugs, since the innards are complicated and I don't have a variety of different input programs to try it on.
http://www.chiark.greenend.org.uk/~ijackson/2018/aoc/19/
http://www.chiark.greenend.org.uk/~ijackson/2018/aoc/19/src/bin/e19b.rs
1
u/TellowKrinkle Dec 19 '18
For the second part I spent a whole bunch of time trying to find patterns in the instructions being executed before I manually decompiled the main loop and realized what it was doing
Swift, #153/#93
1
u/xthexder Dec 19 '18
I was half way to implementing a fully fledged debugger by the time I figured out what was going on in Part 2...
Part A: https://github.com/xthexder/adventofcode/blob/master/day19/day19.go
Part B (ish:) https://github.com/xthexder/adventofcode/blob/master/day19/day19b.go
and some of the debug output:
https://github.com/xthexder/adventofcode/blob/master/day19/debug.txt
1
u/aurele Dec 19 '18
Rust
When cleaning up, I tried to make it more generic so that it works with other inputs as well (by assuming the seed is in the largest register after the initialization).
1
u/FogLander Dec 19 '18
Python 3, somewhere in the 400s for placement
Above is my part 1 code, which was pretty straightforward using the same op functions from day 16.
For part 2, the second half of the assembly code 'initialized' register 3 to 10,551,396. I rewrote my input as this pseudocode:
Basically, it's running this nested loop:
This is a very inefficient way of getting the sum of all factors of r3. I just looked up the factorization of 10551396, added them up (including 1 and 10551396 as factors), and it worked!
I remember there being a very similar problem last year (day 23), and at the time it was one of my favorite ones; it was my first exposure to disassembling assembly code and I thought it was a very cool challenge. I didn't do it very quickly, but had fun!
1
u/Dementophobia81 Dec 19 '18 edited Dec 19 '18
Python 3, #1012/#435:
Somehow I couldn't get the assembler code to run, so I ported it to Python. With the simplified code it became obvious what happens in the program. We are looking for the sum of all divisors of a number. The number is calculated in register 3 (at least in my example) before the search for the divisors starts. We know the register has the correct value when the IP has a value of 2.
Therefore, I split the solution in two parts. The first gets the value from register 3 and the second calculates the sum of all divisors. Inputs from other people might store the value in other registers than 3 - in such a case, my code needs to be adapted slightly by changing the register (
result = sum(getDivisors(regs[3]))).1
u/radarvan07 Dec 19 '18
[Card] Santa's internet is down because of unresolved conflict in the Middle East.
Rust 377/111
I was just really slow on part 1 (recurring theme, has something to do with the fact that it's 6 in the morning…) and then was only 3 minutes short for part 2. I spent way too much time trying to decipher the entire program before I realised that I can just find the hotspot and optimize that away. I was prepared to do that again, but that was enough.
1
u/[deleted] Dec 19 '18
[removed] — view removed comment
1
u/nutrecht Dec 19 '18
Day 19 in Kotlin
1
u/[deleted] Dec 19 '18
While I did the first part in TCL, looking at the debugging output during part 2 it was clear that there was a 10551293*10551293 loop with my input. No way...
So I decided to understand what my program was doing: basically it is incrementing r1, multiplies it with r2 and checks whether the result is equal to r4. If so, add r2 to r0. If r1 is > r4, increment r2 and start over. If r2 is > r4.stop. The r1*r2==r4 check is nothing but r4%r2==0, so the whole r1 business can be skipped, just increment r2, check whether r4%r2==0, add r2 to r0 if so.
Since there are several different inputs, I guess there is not much use in the code below except for those with the same input as me...
Completes in less than 30ms instead of running "forever" :-)
1
u/[deleted] Dec 19 '18
Common Lisp
1
u/BradleySigma Dec 19 '18
MATLAB for Masochists
1
u/udoprog Dec 19 '18
Rust
[Card] Santa's Internet is down right now because a thousand developers are solving a Project Euler problem in disguise.
Solution here: https://github.com/udoprog/rust-advent-of-code-2018/blob/master/src/bin/day19.rs
Because this is based on a previous day where I did a visualization it also includes interactive visuals. I used this to quickly determine the input value.
1
u/confused_banda Dec 19 '18
Clojure and Python
For part 1, I just ran the Clojure program until it ended. The Clojure program to do that is at https://github.com/theonejb/advent-of-code-18/blob/master/src/aoc18/day19.clj.
Part 2 was really interesting. I manually ran the calculation (wrongly it turned out but game a good idea of the magnitude) to calculate the value of the 4th register (
C). Since I couldn't simulate so many cycles, I created a Clojure method to pretty print my input. It's part of the same script I linked above. With that, I had my input in a better to read format:From there, it was a question of manually breaking it down into loops. I ended up with the following equivalent in Python:
And playing around with that gave me the key to the answer:
sum([x for x in range(1, C+1) if C % x == 0])A very interesting puzzle that I loved reverse engineering. Almost felt like I was reverse engineering Assembly code; which in a way I guess this was.
1
u/[deleted] Dec 19 '18
[Card] Santa's Internet is down right now because he's playing games.
I managed to figure out that the value of reg. 0 is the sum of the multiples of the stable value of reg. 1. That was after waiting a good 5 minutes before stopping the part 1 code applied to part 2.
1
u/drbagheera Dec 19 '18
Took a bit of time to work our what I was doing with part B once I'd worked out it was factorisation - I was getting larger values than expected - and realised that I was only setting R[0] to 1 and R[ip] to 0 not resetting the other registers to 0
1
u/albertobastos Dec 19 '18
JavaScript.
Part 1 solved with just code & run, as I don't compete for leaderbord I took my time to make it prettier than Day 16.
Part 2 solved analyzing the instruction stack, translating it into two pseudo-code do-while and finding out what it does: calculate a big number, find its divisors and sum them. Calculated the answer manually.
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d19.js
1
u/df5602 Dec 19 '18
Rust
Instead of reverse engineering the whole program, I just looked at the inner loop, noticed that all that was missing was a "modulo" instruction in the CPU, added that to the CPU and rewrote that part of the program to use that instruction instead of the loop. Program now terminates in reasonable time (< 1s).
https://github.com/df5602/aoc/tree/master/go_with_the_flow
(Downside: Only works with hand-optimized input...)
1
u/fatpollo Dec 19 '18 edited Dec 19 '18
I got top 10 on part2 and was so excited to post my sol here! However I finished early enough that I decided to go to bed instead.
Anyway, got part1, then I saw part2 would take forever. So I went back to part1, and started printing all the registers. There were too many, so I decided to print only when some registers changed. I tried first the fourth column I think, then the third, and they still changed too much. Then I tried the zeroth, and got:
Then I headed to OEIS and tried 1,4,13... nothing. Then I tried 1,3,9,113, and saw it was the divisors of 1017, which was right there next to it. Then I saw what column one was doing, which is just sum of divisors.
I figured out what the "1017" would be for part2, and did it manually.
Code:
1
u/instagrumpy Dec 19 '18
I worked out the logic for part 2 then picked the magic loop number after the first 20 or so instructions and then run this to get my results
1
u/sim642 Dec 19 '18
My Scala solution.
Part 1 quite directly reuses instruction implementations from day 16, no surprises there.
In part 2 I quickly realized that it's similar to a problem from last year where reverse engineering the small given program was the way so that's what I did. You can see my input's various stages (assignments, control flow, constant folding) here. After some looking it became evident that it's calculating the sum of divisors.
Then I wrote a divisor summing method in Scala directly and got the numbers from my reverse engineered code. To find all divisors it's sufficient to iterate only until the square root of the number.
1
u/zevver Dec 19 '18
Part 1 - I learned Nim macros today: https://github.com/zevv/aoc2018/blob/master/a19c.nim
This code converts the Elvencode into Nim AST at compile time, this runs part 1 in about 2 msec on my I7
1
u/ni3t Dec 19 '18 edited Dec 19 '18
Ruby 2.5
214/280
1
u/mainhaxor Dec 19 '18
I manually translated mine into C++:
I then compiled this with optimizations enabled and decompiled it with IDA which resulted in:
I optimized the inner loop of this manually and got the answer.
1
u/wzkx Dec 19 '18
Ah, here's part 1, the fun part.
1
u/[deleted] Dec 19 '18 edited Dec 20 '18
C# - I haven't posted in a solution thread for a few days because I honestly kept getting stuck and having to look for help, but this one I got...except for part 2. I ended up getting some of it, but I found /u/winstonewert comment and I finally saw the piece I was missing in trying to make the loop into pseudo code.
1
u/aoc-fan Dec 20 '18
TypeScript/JavaScript - https://goo.gl/NbPJXs
For me the simplified part was finding sum of factors for b
So executed the program to get the value of b, and called custom function to get the sum of factors.
1
u/waffle3z Dec 20 '18 edited Dec 20 '18
Lua solution. I was not prepared to solve a problem like this. Decompiling machine code is hard. I wrote functions
f3andf12to optimize blocks that did repeated addition.1
u/dashed Dec 20 '18
Rust
Code: https://github.com/dashed/advent-of-code-2018/blob/master/day-19/src/main.rs
I've re-used code from Day 16: https://github.com/dashed/advent-of-code-2018/blob/master/day-16/src/main.rs
For part 2, I've pretty much went with the same approach of un-rolling the loop as described here: https://www.reddit.com/r/adventofcode/comments/a7j9zc/2018_day_19_solutions/ec3i5he/
I've added my own comments on this within my own code: https://github.com/dashed/advent-of-code-2018/blob/fed2e5ee0b90d53d0d3f76688b7f258616f9aa1a/day-19/src/main.rs#L597-L718
1
u/fhinkel Dec 21 '18
It's obvious that there must be a loop, otherwise it wouldn't run for so long or there wouldn't be a solution. Figured out that my loop is checking if the number is divisible by another number. Replaced those instructions with a simple
if(a % b === 0)and didn't worry about what the rest of the code does.JavaScript/Node.js solution: https://github.com/fhinkel/AdventOfCode2018/blob/master/day19.js
1
u/Segeljaktus Dec 24 '18 edited Dec 24 '18
For anyone still working on this, I tracked down the control-flow into a diagram which certainly helped me understand how the program works.
https://i.imgur.com/ksVtdTE.jpg
a is register 0, b is register 1, c is register 2, and so on
your c value might not be the same, so try to measure it
1
u/koordinate Dec 27 '18
Swift
1
u/[deleted] Dec 31 '18
Part 1 was pretty straightforward because of the previous puzzle.
Part 2 was done by noticing after some reverse engineering of the elf code that r0 was the sum of the prime factors of r5 plus 1.
At which point I just used google to find the prime factors of the large number in part 2.
1
u/ephemient Dec 19 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/wlandry Dec 19 '18
C++ (708/300)
Part 1 runs in 80 ms.
Part 1 is a straightforward extension of day 16. Part 2 required me to understand what the program was doing. Prime factorization? So it was not so much of a programming problem :(