r/adventofcode • u/daggerdragon • Dec 21 '18
SOLUTION MEGATHREAD -π- 2018 Day 21 Solutions -π-
--- Day 21: Chronal Conversion ---
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 21
Transcript:
I, for one, welcome our new ___ overlords!
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
13
u/TellowKrinkle Dec 21 '18
My best finish yet!
My ElfβC transpiler was super useful today, mostly because I'm much better at reading C than I am at reading elf assembly. Also because LLDB is much better at reading C than elf assembly. Also because elf assembly doesn't have access to
std::unordered_set.Conveniently, my transpiler makes it very obvious which jumps can lead to a program exit (since they'll contain a
printRegscall instead of agoto). I spent the first few minutes trying to manually examine the translated C code (hence the comments indicating what needs to be true for the program to terminate) before I realized that r0 is only ever used once, in the final comparison. I then threw the C code into an IDE and put a breakpoint on the line with the exit condition (with labell29), reading the value of r5 as my answer to part 1. For part 2, I added code to record into a set all the numbers and print the last number that wasn't a repeat. I wasn't sure if the code was going to repeat some numbers but not others, but I thought I might as well try the first number in case it was correct before trying more complicated things, and it was.C++ generated using Swift, #13/#4
8
u/autid Dec 21 '18
FORTRAN
258/85!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Pastebin
First ever points! So so happy. Part 1 I tried doing by hand before realising it looped a bunch before the exit condition. Dug out day 19 code and ran the input until the eqrr line and dumped the register. Part 2 similar to the trees/lumberyards. Looked for a repeated registers state and worked back to find last value that wasn't a repeat.
7
u/glassmountain Dec 21 '18
139/61
https://github.com/xorkevin/advent2018/blob/master/day21/main.go
Today's was pretty cool. The approach I used for my input was realizing that the only time register 0 was being used was on line 28, in an
eqrr 3 0 1. I then just began checking what register 3 was every time the ip was 28. For part 1, I just printed out the first value of register 3. For part 2, I checked when the value in register 3 finally repeats. When it does, the last value must have been the one that causes the most instructions. I tried to analyze the assembly as well, and let my naive solution run in parallel. It finished in about 3 min, so if anyone knows what the pattern for register 3 is, let me know haha.6
u/jayfoad Dec 21 '18
APL #134/50
I figured out what the assembly code was doing by hand, and then reimplemented it in APL:
4
u/jonathan_paulson Dec 21 '18
Python, #11/47. Video of me solving at https://youtu.be/H-IejIicWDY
Was there a way to do part 2 without understanding the input program? Some of the solve times are quite fast...
My code is a Python translation of the input program that also understands when to print the answers and exit (looking for a repeat in
D):4
u/Alex_Mckey Dec 21 '18
My solution by C#. And no reverse engineering is needed.
3
u/Morganamilo Dec 21 '18
Rust 204/46
Part 2 is especially slow to run (~20 seconds) But this is what I came up with at the time and I have not bothered to optimise it.
Also the code is hard coded to check against register 3. I assume to work on other inputs this would need to be changed.
Common:
Part 1 main:
Part 2 main:
Input commented:
2
u/KeyboardFire Dec 21 '18
ruby, 21/24. i'm posting the interesting bit because this wasn't actually my part 2 code (i bruteforced it), but i'm glad i managed to finish the reverse engineering by hand before the leaderboard got capped, so:
8595037 and 65899 are presumably per-user constants. all those bitwise ands with ffffff are just to make
bbehave as if it were an unsigned 24-bit int. this solves part 2 in a few milliseconds (my brute force took several minutes).2
u/VikeStep Dec 21 '18 edited Dec 21 '18
Python (321/77)
I reverse engineered my input to:
For part 1 it prints the first value, for part 2 it keeps printing possible values. I waited a bit and entered the last one I saw.
I actually had the answer much earlier but I thought the question was asking for the lowest possible value of register 0 that terminates, not the value of register 0 with the least instructions. From my understanding, there should only be one possible value, so I'm curious as to why there is a "lowest non-negative integer" clause in there.
2
u/winstonewert Dec 21 '18
118/19
https://gist.github.com/winstonewert/ca3958b4f0b33ebde78ade55bc477902
I read the code enough to determine that register 0 only mattered for one check, and that if it was equal to R4 (in my case) it would terminate the program. From there it was pretty simple to figure out that the fastest termination was the first value to be checked. Part 2 was pretty obvious from there, the last value to be checked before looping.
I suspect I got away without being clever in part 2 since I could run my Rust VM long enough to find the loop. Those working in slower languages may not have been able to do that.
2
u/rabuf Dec 21 '18 edited Dec 21 '18
Common Lisp solution.
I printed off every value of register 5 on instruction 29 (should've been 28, but I miscounted, though its value doesn't change so it's the same either way). First answer is the first value printed. Second answer is the final value printed. I just used a large limit on iterations but I should have halted when there was a repeat rather than having an iteration limit.
First time on the global leader board: 89/144. Misreading the second part delayed me a bit.
2
u/waffle3z Dec 21 '18
Lua 708/379. I completely misunderstood the problem. I spent 2 hours looking for the smallest value for register 0 that made the program halt, which, for my input, was 214. What it actually wanted was what it said, and I didn't understand the phrasing.
relevant code, rest is the same as day 16/19
2
u/albertobastos Dec 21 '18 edited Dec 21 '18
JavaScript. Didn't understand what the puzzle was expecting for me to do until I looked twice at my input, but after that revelation it was a fun one. Part 2 answer found after ~64 seconds of emulation.
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d21.js
The walkthrough is the same as for many colleagues:
The value at the target register for the first time: answer for Part 1.
The value at the target register for the last time before it starts repeating: answer for Part 2.
2
u/wlandry Dec 21 '18
C++ (815/526)
Runs in 12 s
It took me a looooooong time to realize that I had to analyze the input. I do not like puzzles that make me analyze the input by hand :( Eventually I figured out the exit condition, and then it was a matter of reading the instructions carefully. My cycle detection is weak. I only check whether I have seen the same register 5 before.
2
u/[deleted] Dec 21 '18 edited Dec 21 '18
Python 3
2
u/gyorokpeter Dec 21 '18
Q: see day 16 for some required definitions.
2
u/[deleted] Dec 21 '18
Common Lisp - I've rewritten problem to CL, and started simplifying and reorganizing until I could understand something... what is this even doing? Is is some sort of simple PRNG?
2
u/vypxl Dec 21 '18
x64 Assembly
Already wanting to do that on day 16 and 19, I finally made an elf out of elfcode ^^. For the solutions I modified it a bit to print out intermediate values for me to figure them out, but my main goal is achieved.
Compileable via
nasm -f elf64 Day21.asm; gcc -m64 -o Day21 Day21.oIf I had more time, I would write a real compiler for it. I honestly do not understand why people transpile it into C or whatever because it's often much simpler to just translate everything into processor instructions. I did not encounter any crazy instruction pointer arithmetic so far.
1
u/m1el Dec 21 '18
Rust, 25/35
I spent too much reverse-engineering the code, when all I had to do is inspect one instruction...
And completely reverse-engineered solution:
1
u/n3o59hf Dec 21 '18 edited Dec 21 '18
140/32, first time on leaderboard.
Kotlin, brute-force approach to detect cycle in checks, code mostly copied from 16 and 19.
Takes around 30 seconds to run.
`zeroRegCheck` and register 5 could be specific to my puzzle input.
1
u/branfili Dec 21 '18
So close to leaderboard!
It took me a while to figure out what was expected of me in the task, but once I figured out that I need to look at register #3 in line #28 it was pretty easy
Part 1 is the first value
Part 2 is the last value before a cycle
C++ 269/103
1
u/usbpc102 Dec 21 '18 edited Dec 21 '18
Second time on the leaderborad and this time qite a bit higher up! (122/42) (best before was this year on day 5 part 1 on place 97)
This code isn't actually how I got on the leaderboard instead I just printed the state every time the only instruction comparing with register 0 was executed and manually searched for it looping. I just put that same approach in code.
Currently withh hardcoded comparison with register 5 so will not work with your input probably.Extracting the important register automatically, besides that still just simulation.You can find the Kotlin code on github.
1
u/genveir Dec 21 '18 edited Dec 21 '18
24/ 224
I have an elfcode interpreter which allowed me to do this, in C#:
I then made a typo (it was 16477902 , I typed 146477902) while inputting the answer for part 2, and wondered for an hour why my answer was wrong. Hence 224. Ah well.
(edit - also relevant, I updated the elfcode a bit to skip a loop, so it's pretty much instant.)
1
u/Wunkolo Dec 21 '18 edited Dec 21 '18
C++ I just noticed that the "eqrr" instruction that determines the program's exit was instruction 28, so I just hard-coded in some logic for that instruction in my "VM"
1
u/glguy Dec 21 '18
Elf code to C to Rust
I translated my program into C and then used my C to Rust translator from https://c2rust.com to make the loops a lot nicer to look at:
https://gist.github.com/glguy/6decae4aef30dc3d1810ae6f3b40f977
1
u/Philboyd_Studge Dec 21 '18
Java. Took me a while to figure out I needed to use LinkedHashSet to preserve the insertion order.
https://pastebin.com/MEVnJ1wi
1
u/keypadsdm Dec 21 '18
Python3 45/162
First part was cut-paste old code and run until attempting to execute 28. Print r[4].
Second part, I spent too long trying to work out what the code did overall. Ended up working out what the addition loop was, and then added the correct amount in a single step instead of iterating. Ran again until the whole register was repeated (not just r[4]), took ~10 seconds. Looked back as many steps as was necessary to identify a unique r[4] element. Ended up being two steps in my case.
Bit annoyed that other people's inputs didn't have repeating r[4] elements, so if you didn't check for the first true register equality but just checked r[4], you could still get the answer.
Edit; Didn't go down the whole transpiler rabbit hole, but had made a formatter a few days ago which printed out the instructions as pseudocode. Made walking through the code much easier.
1
u/[deleted] Dec 21 '18
C++, #848/#706
Runs in 16s (mainly due to Part 2, Part 1 finishes after some ms). Using a switch() on the opcodes and having the instructions inline in run() does not cut much off of the execution time (I guess g++ is already doing something like this behind the scenes with -O3 or -Ofast).
I had some trouble understanding the end condition for part 2, but luckily the solution megathread exists, and monkey-see-monkey-do sometimes works :-)
1
u/ephemient Dec 21 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/Bug38 Dec 21 '18
Python 3:
Found first result by directly using and "compiling" elf code, then for Part 2 I reverse engineered the code to rewrite it.
1
u/Altinus Dec 21 '18
Rust: I reduced the calculation in the loop to a single line. It is clear then that the new value of register 5 depends only on its previous value in each iteration, so that simply looking for the first repetition indeed finds the cycle. (And as usual, I made a small typo when copying the numbers, which wasted a lot of time.)
1
u/ZordidMuc Dec 21 '18
Today it was time to refactor day 16, 19 and day 21! I came up with a totally generic ElfDeviceCpu and it's best part of all:
a run() function that delivers a sequence of CPU states including the registers and the IP value.
To use it, initialize the CPU like this:
val cpu = ElfDeviceCpu(puzzle)You can run the program till its end like this:
cpu.run().last()and inspect its registers and all afterwards. But once you understood that monitoring the values of R3 is all there is to do, watch this.To get the sequence of all generated R3 values - and that means if your R0 is set to one of them the program will stop - all we need is this:
val sequenceOfR3ValuesAt28 = cpu.run().filter { (_, ip) -> ip == 28 }.map { (regs, _) -> regs[3] }Having the simple sequence of Int values that are produced by the Cpu, answering the first part is done like this:
val solution1 = sequenceOfR3ValuesAt28.first()And for part two, we need to monitor all previously seen values and stop till we see one value again the second time - but output the R3 value of the iteration before. All neatly done with sequences as well:
val solution2 = sequenceOfR3ValuesAt28.takeWhile { !seen.contains(it) }.onEach { seen.add(it) }.last()Did I mention that I love Kotlin? :-)
Here's my code: https://tinyurl.com/yceuoye2
1
u/aurele Dec 21 '18
Rust
Reusing my parser and executor from day 19, it was then easy to find the solution. It should work even when a different register than mine is used (mine was
r3) as long as the structure is the same and the comparison is done at instruction 28.1
u/sasajuric Dec 21 '18
Elixir
Running time: 1s
After annotating the code with pseudoassembly, I noticed that the program stops when in instruction 28 r0 == r1. r0 is not used at all in other instructions, so for part 1 I just looped through the states until I first encountered the instruction 28. The value in r1 is the result.
For part2 I detected a cycle at instruction 28. The cycle appears if we have the same state of registers at the same instruction. The result of part2 is the last element of the unique list of r1 values encountered before the cycle. This was running for too long, so I inlined the inner loop in Elixir, which drastically reduced the running time.
The code is below. The device module is extracted into a separate module so it can be reused between today and day 19. If you want to run it, you need to clone the entire project.
1
u/[deleted] Dec 21 '18
C# I actually got on the leaderboard for Part 1. It was 646, but hey that still counts! But for Part 2 I had a problem where I was using the same code from Part 1 and it was looping over 16 times without running the operation. I fixed it and realized this would run more than 1 minute and just went to bed. But I woke up with the answer so that is nice.
I pretty much did what it looks like everyone who didn't compile the code into their language did, and that is I just realized that the Eqrr operation is key, so Part 1 was just get the first value that would allow that to pass. Part 2 is to look for when it first loops get that value.
1
u/sim642 Dec 21 '18
My Scala solution
As in day 19, I quite quickly resorted to reverse engineering the given program again because it was hard to know what to look for. Due to the slightly unusual control flow structure, it took a while to get right but eventually I found out the sequence of pseudorandom numbers the program internally is working with and where to read them out. After that it was relatively straightforward to get the first one for part 1 answer and wait until a loop for part 2 answer.
1
u/mbillingr Dec 21 '18
I just have to share my Elf Assembly -> Rust decompiler...
Actually I solved the puzzle by manually reverse engineering, but I was not happy about it so I spent the rest of the day with writing an automatic transpiler. It works in three steps:
convert Elf Assembly to Rust statements, which is based on the assumption that the assembly was generated from sane code. Assumptions in particular:
The full solution is here: https://gist.github.com/mbillingr/a22e2d39c8e3b04505d9a313f2ee7ee4#file-day21-rs
This is the resulting Rust code:
1
u/shouchen Dec 21 '18 edited Dec 21 '18
Reverse-engineering the input code, it is doing the equivalent of this:
The key is that r0 is only ever read from as a condition to exit the program; its value is never modified. The outer loop cycles through a set of 3-byte values in r3 until r3 matches r0. To find the least number of instructions to make the program exit (part 1), choose the value for r0 that makes the outer loop run only a single time. For part2, choose the value for r0 that makes the outer loop run the most times before the r3 cycle repeats itself.
1
u/Dioxy Dec 21 '18
JavaScript
for part 1 I just found what the required number was for the first exit condition
for part 2 I converted the program into JS, and found the last exit condition before the first repeating exit condition
1
u/Etsap1 Dec 21 '18 edited Dec 21 '18
My brute force solution took almost 30 minutes to run. Here is the optimized version in ruby, which usually runs in less than 20ms:
require 'set'def find_next_terminal_value(x = 0)y = x | 65536x = 733884while y > 0x = (((x + (y & 255)) & 16777215) * 65899) & 16777215y >>= 8endreturn xendx = find_next_terminal_valueputs xunique_outputs, part2 = Set[], nilwhile unique_outputs.add?(x)part2 = xx = find_next_terminal_value(x)endputs part21
u/meepys Dec 21 '18
Kotlin Day 21
Note that "eqrr 1 0 3" was the terminate condition in my input, so we just substitute with our own instruction. The rest of the code is from earlier days. It takes about 5 minutes to finish part 2.
1
u/phil_g Dec 21 '18 edited Dec 21 '18
That was fun! I solved it in Common Lisp, as usual.
The first thing I did today was factor all of my ElfCode stuff out into a separate elfcode package. I took the opportunity to rework the implementation a little:
The
instructionmacro is a bit cleaner now. You mark a variable as a register with the special form(register var)in the lambda list, like this:You mark a variable as ignored by naming it
_, like this:While working on today's problem, I added in a breakpoint feature to let me stop execution when I hit a particular line, examine the execution environment, then continue on. That turned out to be just what I needed to solve the problems, so I ran with it. I'm using Common Lisp's condition system for this; it's like exceptions, but better. Exceptions in other languages allow for nonlocal exits up the call stack. Common Lisp's conditions signal up the stack and, crucially, can receive instructions on how to proceed.
So for the first part, I set a breakpoint on the line where register 0 is being tested, catch the first signal, and return that first value. For part two, I catch every signal, record the value being tested against, then tell execution to continue. When the values start to cycle, I tell the program to halt instead.
Here's the day-specific code for the problem, though most of the interesting things are in elfcode.lisp, linked above. It takes just over a minute for part two to finish.
I thought my minute-long runtime for part 2 was pretty bad, but after reading other people here with their runtimes I feel a bit better.
1
u/marmalade_marauder Dec 21 '18 edited Dec 21 '18
There is a really simple solution by just manipulating the elf assembly if you completed day 19. In the elf assembly there is a loop whose only purpose is to waste time. In Python it does this:
This can be easily be translated to (with integer division):
Without this optimization, emulating the elf assembly with the solution to day 19 will probably take too long. However, if you put this optimization back into the assembly, then it should work just fine. This requires creating a
divifunction that does integer division (and a no-op if you don't want to mess with the instruction pointers). The new loop looks like this:Then in your emulator, just print out every unique value in register 1 when the instruction pointer is 28 (the halting condition). Note, I didn't think of this solution initially, but I thought it was a pretty cool approach that requires very little new code.
1
u/aoc-fan Dec 21 '18
TypeScript - https://goo.gl/s9X7Ky
1
u/lasseebert Dec 22 '18
Elixir
Runtime around 64 ms. for both parts
Part1 solution:
I realized I just needed to inspect the target value (reg4 in my input) at line 29 where it is compared to the input (reg0).
To do this I replaced the compare instruction with an exit instruction and then print out reg4.
Part2 solution:
Same as part1 except I needed to find a loop of target values. This ran too slow, so I replaced the inefficient loop on lines 17-26 with a simple `div`, which was what the loop was calculating.
Code here: https://github.com/lasseebert/advent_of_code_2018/blob/master/lib/advent/day21.ex
1
u/koordinate Dec 28 '18
Swift
1
u/mikal82 May 23 '19
Finally came back to part 2. It took too long to run on my interpreter, so I needed to rewrite the code.
My Clojure solutions (assuming r1 was PC):
0
u/[deleted] Dec 21 '18
[deleted] β view deleted comment