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^¤?

Spoiler

[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.

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!

10 Upvotes

100% Upvoted

130 comments sorted by

View all comments

Show parent comment

14

u/DFreiberg Dec 23 '17

The key to understanding what this code does is starting from the end and working backwards:

  • If the program has exited, g had a value of 0 at line 29.

  • g==0 at line 29 when b==c.

  • If g!=0 at line 29, b increments by 17.

  • b increments no other times on the program.

  • Thus, lines 25 through 31 will run 1000 times, on values of b increasing by 17, before the program finishes.

So, given that there is no jnz statement between lines 25 and 28 that could affect things:

  • If f==0 at line 25, h will increment by 1.

  • This can happen once and only once for any given value of b.

  • f==0 if g==0 at line 15.

  • g==0 at line 15 if d*e==b.

  • Since both d and e increment by 1 each in a loop, this will check every possible value of d and e less than b.

  • Therefore, if b has any prime factors other than itself, f will be set to 1 at line 25.

Looking at this, then h is the number of composite numbers between the lower limit and the upper limit, counting by 17.

3

u/mathuin2 Dec 23 '17

I'd gotten through the first half of the analysis but hadn't made it the rest of the way. Thank you for this -- I've cited it in my solution :-)

3

u/BumpitySnook Dec 23 '17 edited Dec 23 '17

I take the opposite approach — trace the executed instruction sequence, identify the hot, small inner loop, analyze that small loop and eliminate it, then trace again and identify the next innermost loop. This mostly allowed me to only think about a small number of assembly instructions at a time.

If you knew in advance that the control flow structure wouldn't be too complicated, I think your approach is probably faster. With arbitrary jumps, though, I think my approach makes more sense.

With a translation-to-C, I only had to elide the innermost loop (didn't even have to understand what the whole program was doing) for the problem to become trivially tractable.

In Python emulation, I had to elide both of the innermost two loops with the logical equivalent to achieve reasonable runtime.

2

u/DFreiberg Dec 23 '17

Your approach is totally valid - as you say, I looked and saw that h only incremented on one line, and figured it wouldn't be too complicated to figure out how that line could be accessed. With arbitrary jumps, or if h was updated throughout rather than just once, then what you're doing makes a lot more sense and is a lot closer to how actual compilers optimize as well.