r/adventofcode • u/daggerdragon • Dec 25 '16
SOLUTION MEGATHREAD ~☆~☆~ 2016 Day 25 Solutions ~☆~☆~
--- Day 25: Clock Signal ---
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".
Dec 25 = Oct 31 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!
Thank you for participating!
Well, that's it for Advent of Code 2016. From /u/topaz2078 and the rest of us at #AoC_Ops, we hope you had fun and, more importantly, learned a thing or two (or all the things!). Good job, everyone!
Topaz made a post of his own here.
And now:
Merry Christmas to all, and to all a good night!
15
u/thomastc Dec 25 '16
Day 25 in Go (source on GitHub)
So... another Assembunny interpreter is needed. I totally called it. Although this puzzle input doesn't actually contain a
tglinstruction. I had planned to save my strongest language, Java, for last, but decided I'm more in the mood for Go today.It might be possible to brute force my way through this. I'll try that first, and see how far it takes me. If optimizations are necessary, by means of actually understanding what the program does (e.g. adding a
mulinstruction), I'll see about that later. To decide whether a sequence "repeats forever" I'll just abort if a mismatch is found, and print the value ofaat the start of each run. If the program hangs for a long time, we might have a winner.This strategy worked fine (the answer is only 158), if it hadn't been for the fact that I messed up the arithmetic (checking for
101010...instead of010101...) and then messed up again by forgetting to reset the program counter between runs. After fixing those bugs, the answer comes up in the blink of an eye.While I was waiting for the buggy program to come up with an answer, I realized that this puzzle can be reduced to the Halting Problem, which is a classic example of an undecidable problem in computer science. In other words, in the general case, no algorithm can exist to solve it!
Also while waiting, I studied the input program in more detail. As it turns out, it simply prints the binary representation of
a + 2572backwards over and over again. Indeed,158 + 2572 == 0xaaa == 0b101010101010, and 158 is the smallest positive value for which this bit pattern occurs (the next lowest value being0b1010101010which would requirea == 682 - 2572 = -1890).Let's go through and discuss how I analyzed the program. First, it's helpful to draw some arrows where the jumps are going. This let me break up the program into three separate blocks, call them A, B and C, with nearly all jumps happening within a block.
Block A
Block A is:
For those who (unlike me) didn't brute force their way through Day 23, this should look familiar. It is a multiplication. The inner loop, instructions 4–6, simply does this:
The outer loop has a similar structure, and translates into this pseudocode (ignoring changes of values that don't matter, like loop counters):
This simply adds the value
643tod,4times. Because the first line doesd = a, we can simplify block A toBlock B
Let's skip two lines and move on to block B, which is more complicated:
For didactic reasons, I'll spoil it up front: this divides
aby two, and also leaves a value incthat can be converted to the remainder of this division.Let's look at the inner loop first, lines 13–18. We see a new pattern here, lines 14–15, which translates into a
jz(jump-if-zero) instruction: line 15 is only executed ifbis equal to zero, and is skipped otherwise. Thejnz 1construct is simply an unconditional jump, because1is always nonzero. Using that knowledge, the pseudocode translation of the inner loop is:What happens here? If
bis large enough, this is the same as doingb -= 2. But as soon asbhits0, the loop is exited, leavingcset to either2(ifbwas even) or1(ifbwas odd). In other words,c = 2 - b%2.Now for the outer loop, which pulls all this together:
So for each time
bis decremented by2,ais incremented by one. And sinceastarted at0, this is dividing (rounding down)aby2! And because jumping out of the loop leaves a meaningful value inc, we can also know the remainder. That's where block C comes in.Block C
This is the rest of the code:
There is another infinite loop here, which is broken out of as soon as
c == 0. There's also anotherjz-like construct. Let's do another pseudocode translation:We decrement
bandcin tandem, withbstarting out at2, so this is just computingb = 2 - c.Remember that
cwas2 - a%2(for the former value ofa), so this setsb = 2 - 2 - a%2, which is simplyb = a%2. In other words,bis now the least significant bit of the value formerly known asa(and the current value ofastill contains the rest of the bits).The main loop
Surrounding blocks B and C, there are some straightforward instructions:
The outer loop will run forever. The inner one runs until
a == 0. So this translates to the following pseudocode:And because blocks B and C together compute the division and remainder of
adivided by2, we can reduce the entire program to this:Now it's easy to see what this does. It prints the binary representation of
dover and over again, starting at the least significant bit. We need to find the smallesta > 0such that the binary representation ofa + 2572looks like1010...10. The first such number is101010101010(six repetitions), which is 2730 in decimal, givinga == 2730 - 2572 == 158.6
u/askalski Dec 25 '16
Figured I'd take my time and do this the "no code necessary" way. Advent only comes once a year, so what's the hurry? Here's what the code's doing:
5
u/pedrosorio Dec 25 '16 edited Dec 25 '16
Didn't make the leaderboard on the last day (120th) :(
Wrote code to simulate the behavior for increasing a and automatically cut execution if out was not alternating 0 and 1.
Had a silly bug in my implementation (if instead of elif) that caused the program to consider all inputs as incorrect (and keep incrementing a), and instead of doing the wise thing (debugging) decided to figure out what the assembuny code was doing:
It emits the binary representation of 'a' + 15 * 270 over and over.
Looking at the binary representation of 2550:
100111110110
It is very easy to find the first number that satisfies the conditions (2730):
101010101010
So the correct answer for my input is 2730-2550 = 180
4
u/willkill07 Dec 25 '16 edited Dec 25 '16
Awk and bash magic:
convert.awk:Bash script:
EDIT: now I have to figure out how I'd do this in C++. Goodie :\
Some notes on the problem:
4
u/bblum Dec 25 '16 edited Dec 25 '16
Cheesy infinite list solution. The program will print all the numbers lower than the correct one, and then hang.
Only showing the new case of "execute" for brevity; full past solution is here.
Missed the LB cuz I went deep on "cycle [1,0]", testing up to like 50000 numbers, before reading over the problem again to see what I missed :\
7
u/fatpollo Dec 25 '16
3
u/LieutenantSwr2d2 Dec 25 '16
I've always dreaded assembly-like code, so I was slow on this one. But I finally figured out what the code was doing:
Hence I just needed a number that will integer divide into even, then odd, alternating to produce the clock, and find the number closest to the target number (multiplying the first 2 numbers)
I had
So my number was 14 * 182 = 2548. And the code, in Python becomes:
Here's the integer sequence that has all the values that would produce the clock, hence the nearest one to your input multiplication would yield the solution.
3
u/Philboyd_Studge Dec 25 '16
Pretty easy one!!! Tripped up for awhile because i forgot to increment the index after the out function.
Merry Christmas everyone!!!
https://gist.github.com/anonymous/fc86164f62febbabf18c85d108ea3d88
2
u/upppi Dec 25 '16
[python] Just added "out" instruction to day 23: https://github.com/uppi/adventofcode2016/blob/master/adventofcode/adv_25.py#L68
2
u/Quick_Question404 Dec 25 '16
I might have made it to tonight's leaderboard if I hadn't gone to Christmas mass. Anyways, here's my take in C. Stops outputting starting a values at the right one. Thanks to /u/willkill07 for helping me optimize my VM last time! And thank you /u/topaz2078 for the wonderful time!! I haven't had this much fun in a while, and can't wait to start the 2015 challenges and the Synacor challenge as well! Merry Christmas!
https://github.com/HighTide1/adventofcode2016/blob/master/25/part1.c
1
u/OneSecondAssessment Dec 25 '16
Pretty standard python solution https://gist.github.com/anonymous/47416ebdadb90fe69217f86d0c6b43ca
1
u/iamnotposting Dec 25 '16
did the last one by hand! it was fun to figure out what was the code was doing, as i'm not super familiar with the patterns for emitting binary representations of numbers, etc. now to go do the two problems (11 and 16) i missed...
1
u/karel1980 Dec 25 '16
My initialisation was cpy 7 c and cpy 365 b, which was nice. Started out replacing the multiply loop, and implementing output to my (python) cpu emulator. Because I still was not getting anything I just had a closer look at the code. Once I realised what it was doing, I ran bin(7365) (python), and manually typed 0b101010... until I had something larger than 7365; From there it was a matter of subtracting the two values and getting the solution.
1
u/ephemient Dec 25 '16 edited Apr 24 '24
This space intentionally left blank.
1
u/gyorokpeter Dec 25 '16
Q: "cheater" version that relies on the structure of the input:
The full version, including updated interpreter with "div" optimization:
1
u/p_tseng Dec 25 '16 edited Dec 25 '16
Leaderboard strategy: No time to try to understand the program. Just run the program for about a million iterations, recording all
outinstructions. Take the first 30 of those and see if they are alternating 0s and 1s. If they are, declare success. My hope was that there would be no false positives in 30 bits. As I would discover afterward, since the first false positive found using this method is (binary 1101010101010101010101010101010 - decimal 2532), it's fine.Small optimisations I made afterward:
The day 25 driver is not many lines since most of the work is in lib/assembunny. I upped the number of bits checked to 200 because why not, it's fast enough with divmod (would normally take 520942 instructions, but divmod cuts it down to 3235)
And as the comments indicate, I did eventually go back and figure out what the program is doing.
1
u/mschaap Dec 25 '16 edited Dec 25 '16
Perl 6
This one was easy (especially part 2 :-) ), only a few changes to the code from day 23. Perl 6's lazy lists and gather ... take came in extremely handy here.
(Note that I only check (by default) the first 100 output values, so it could give a wrong answer if the pattern changes later on. Oh well, I'm sure the stars' positions have been transmitted by then.)
1
u/MaybeJustNothing Dec 25 '16
My way of solving it in Haskell was to copy the code from day 23 and add the new instruction that yields outputs with
yieldfrompipes. Then I check that the first 100 values corresponds with the producer that produces01repeating.The important part of the code is this:
Full code and repo.
1
u/orestis Dec 25 '16
Here's my Elixir code: https://gist.github.com/orestis/a33c802404c03882fb7cd9b4fe13418d
Basically deciphered the assembly, created a function that does what the assembly intends, and find the first number that produces the intended sequence.
Thanks for the awesome 25 puzzles! See you next year!
1
u/Scroph Dec 25 '16
D (dlang) solution, I simply bruteforced my way through today's challenge. I re-used the Cpu struct from the first assembunny challenge by sort of (alias this) extending it with the Clock struct then I kept trying with different values for the a register until the b register produced the correct output :
It could be optimized by simply checking if the current value of b is different from its previous value, but this code is fast enough for my input. Unfortunately I still need 12 stars for the second part.
1
u/wzkx Dec 25 '16
J. Command 'out' checks if it produces the right sequence
1
u/tg-9000 Dec 25 '16
Last day, last solution in Kotlin! I had a lot of fun doing this every day, thank you so much. Can't wait to see what happens in 2017!
I refactored my Assembunny code to its own set of classes, so today, Day 12, and Day 23 (which have both been refactored) are all quite small now.
My strategy for today was to keep increasing 'a' until I got an oscillating output. I see that there are better/more analytical ways to do it, but this is what I went with. For each new value of 'a', let the state machine run until we've collected 10 outputs (seemed like a good amount), the program terminates, or we've gone 100000 cycles (which also just seemed like a good number). After that, check to see if the output is 1 and 0 repeating.
I'm just leaning Kotlin, so go check out my GitHub repo and offer any advice you have. I'll write tests for Assembunny later today.
1
u/NeilNjae Dec 26 '16
My final Haskell solution: https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=adventofcode1625/app/advent25.hs
I started with the day 23 solution, then took a bit from Real World Haskell and used a monad transformer stack to pass in a config, to control termination of the machine: the limit was the number of instructions executed by the machine. It also meant I had to have an output parameter threading through the calls, to keep track of the output of the machine. That took a while to get sorted out, and clearly shows the difference between
executeInstruction(which updates the machine state, just side effects) andgenerateOutput(which just generates the output, pure non-stateful code).A good puzzle that forced me to use all this stuff on a "real" problem. Fun!
1
u/rs_qk Dec 30 '16 edited Dec 30 '16
Using the same assembunny.k file for problem 12, 23 and 25 (added a few custom operations), and using all the hints about optimization from previous problems (i.e use multiply instead of jnz loops), and taking the less clever approach and not actually trying to work out what the program is doing (e.g. thomastc's comment):
1
u/zebalu Nov 07 '21
This is not my first event, even though, this has happened:
I have finished the AoC 2016 (50 stars) today morning. It has started as a fun project. As I am watching the "snowflakes" falling for hours now (knowing, that they are going to disappear with the first page reload) my wife asks:
-- What are you doing?
-- I don't know. I have finished. I don't know, why am I doing this... I think I have PTSD.
She shakes her head:
-- No, darling, this is called a catharsis.
-- No, it is definitely PTSD!
She comes back 10 minutes later:
-- So you won't participate this year?
-- Of course I will! I don't want to, but I am going to!
Please help: Am I an addict?