Arithmetic Logic Unit

Advent of Code 2021 Day 24

Solve for X where X equals...

• the largest valid fourteen-digit number that contains no 0 digits

Meaning X must be...

• A non-negative integer
• 14 digits in length
• Each digit will be a minimum of 1 and maximum of 9

That's our output. What's our input?

• A multi-line string
• Where 14 lines contain two values separated by a space
• And all others consist of three space-separated values

What does our input represent?

• Instructions for processing each consecutive non-negative, non-zero, single-digit number in a 14-character digit

What happens each iteration through the input?

• Either the next digit is queued
• Or the next operation is performed on one of four available variables w, x, y, z
• After the final operation executes, check value stored in z for 0 to confirm whether the larger 14-digit model number is valid

My brute-force algorithm, which runs seemingly forever

Start from model number `99999999999999` and `invalid = true`
While a flag for invalid remains true
  Loop through each digit in the model number
    Initialize the input variable to the current digit
    Execute each command from the list of instructions corresponding to the current index in the model number digit list
  Check whether the `z` variable is equal to `0`
    If it is, update the invalid flag to false
    Else, Reset `w,x,y,z` values to 0 and decrement the model number by one
Return the latest model number whose digits lead to a `z` value of `0`

Sadly, I may never know if this generates the expected answer.

And I had no hunches for other ways to solve this challenge given my lack of formal computer science education.

I only found one eloquent algorithm across Github and Reddit

• JavaScript solver NullDev's solution is concise, fairly understandable, and seems to circumvent the whole searching process. Heck, it appears to cut straight to the guts of this problem set and perform only the bare-minimum amount of arithmetic!

Below is a visualization of how his algorithm works, along with my attempt at describing it in written steps

How did I make this visualization?

• I designed each frame using a screen design tool called Sketch
• I exported JPGs of each frame
• I used an online service, EZGif, to upload each image - named alphabetically so they'd be in the proper order - set a delay time that held each frame for a second, and optimized the resulting GIF before downloading and uploading to dev.to

There are four stages
1. Separate the input into individual lines
2. Loop through the separated input, jumping to the next `inp` instruction after each iteration
   Store the numbers in the third spot for each of three out of the 18 lines:  4, 5 and 15
3. Loop through the newly created set of 3-value lists
   If the value in the first spot is 1
     Store the current iteration's index and the value in the third spot as a pair of values in an array and add it to a new set that will act as a stack
   Else
     Remove the most recently added pair of values from the stack, saving their values: the first representing an index and the second representing an arithmetic number
     Store two values, each at a different location, in a new set, based on the results of some arithmetic
       The first value should be stored at the location referenced by the number in the first position of the most recently added pair
         Store there the minimum number when comparing 9 and the result of calculating the difference of 9 and two values: the value in the second position of the most recently added pair, and the value in the second position of the current iteration's list
       The second value should be stored at the location referenced by the current iteration's index
         Store there the sum of the value stored in the prior step and the result of re-calculating the value in the second position of the most recently added pair, and the value in the second position of the current iteration's list
4. Generate the model number by joining each number stored in the newly-generated set of numbers from stage 3

Lessons learned from this challenge, the solutions I tried to understand, and the conversations I observed on Reddit

• Try solving the challenge outside of a code editor: put pen to paper and draw ideas, scenarios, and guesses. Time spent doing this will help you understand the input and possibly find ways to shortcut the work needed to solve the challenge.
• Study the input before attempting to build an algorithm: for this challenge in particular, there were clear patterns and differences in the patterns that were intentionally designed to lead players toward a more efficient solution. I missed them because I didn't review the input long enough.
• Don't try initially to design an algorithm that works for inputs other than the one given: it could lead to extra work without any payoff in this context

I still don't feel confident attempting to reverse-engineer NullDev's code.

Thus, my star goes unclaimed.

Perhaps I'll return to this challenge later and feel more confident.

For now, I'm ok with this feeling. Enough to move on to the previous day's challenge...