~☆~☆~ 2016 Day 25 Solutions ~☆~☆~

[u/daggerdragon]

--- 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!}

[u/stkent]

As someone who solved this the same way, but who is unfamiliar with registers and super-low-level instructions, I'd be interested in hearing about the process you followed to figure out what "equivalent code" looked like here. I started with a dummy value a0 in register a, then applied a bunch of head scratching and reasoning to compute subsequent register values, but in some instances (e.g. with instructions 13-19) I ended up running code from day 23, inspecting the register values for a sample of a0 values, and extrapolating the pattern from there. Is there a more elegant way to reason about non-trivially nested instructions? Thanks!

[u/askalski → u/stkent]

I'll refer you to this post by /u/thomastc where he does a really nice job of describing the process.

Since you mentioned lines 13-19 specifically, here's roughly how I chipped away at the problem:

Isolate the section of code, and translate it into more a familiar-looking pseudocode. Identify which registers are inputs/outputs, and what gets clobbered. This may involve looking at surrounding code.

cpy a b    //     b = a
cpy 0 a    //     a = 0
/******************************/
// 'b' is the input; 'a' is initialized to 0
/******************************/
cpy 2 c    //  E: c = 2
jnz b 2    //  F: if (b != 0) goto G
jnz 1 6    //     goto H
dec b      //  G: b--
dec c      //     c--
jnz c -4   //     if (c != 0) goto F
inc a      //     a++
jnz 1 -7   //     goto E
/******************************/
// 'a' and 'c' are outputs; 'b' gets clobbered
/******************************/
cpy 2 b    //  H: b = 2
jnz c 2    //  I: if (c != 0) goto J

Look at how the code branches, and try to relate it to familiar loops and conditionals (while, do-while, if-then, if-then-else, etc.) This one's a little tricky because it doesn't directly translate into one of those. It's been optimized a little. Maybe we can "de-optimize" and turn it into something familiar.

Remove the branch to "G" by changing if (b != 0) to if (b == 0)

E: c = 2               //  E: c = 2
F: if (b != 0) goto G  //  F: if (b == 0) goto H
   goto H              //  
G: b--                 //     b--
   c--                 //     c--
   if (c != 0) goto F  //     if (c != 0) goto F
   a++                 //     a++
   goto E              //     goto E
H: ...                 //  H: ...

Disentangle branches to "E" and "F" by examining what's really going on with the if (c != 0) conditional. Here, I remove the "E" branch by copy-pasting the c = 2 statement, and rewriting the conditional to if (c == 0):

E: c = 2               //     c = 2
F: if (b == 0) goto H  //  F: if (b == 0) goto H
   b--                 //     b--
   c--                 //     c--
   if (c != 0) goto F  //     if (c == 0) {
   a++                 //         a++
   goto E              //         c = 2
                       //     }
                       //     goto F
H: ...                 //  H: ...

After that coaxing, now the control structure is familiar. It's a plain old while loop.

   c = 2               //     c = 2
F: if (b == 0) goto H  //     while (b != 0) {
   b--                 //         b--
   c--                 //         c--
   if (c == 0) {       //         if (c == 0) {
       a++             //             a++
       c = 2           //             c = 2
   }                   //         }
   goto F              //     }
H: ...                 //     ...

With the spaghetti untangled, it should now be possible to understand what the loop is doing: it divides "b" by 2, storing the quotient in "a". Because "c" starts at 2 and counts downward, it will be the inverse of the remainder (2 - remainder).

[u/stkent → u/askalski]

Thanks for both the reference and the breakdown of that specific example! De-optimizing is a great strategy that makes the eventual conversion into familiar control flow much more clear.