DEV Community

Cover image for Chronospatial Computer
Robert Mion
Robert Mion

Posted on

Chronospatial Computer

#adventofcode #algorithms #javascript #programming

Advent of Code 2024 Day 17

Part 1

This was unavoidable, wasn't it

This 10th anniversary year has had a bit of everything.

So it makes sense that there would be an opcode-themed challenge somewhere.

I don't really enjoy these:

  • It's a gauntlet to re-create the system as described
  • It's near-impossible for me to debug the program other than looking at the final results and hoping I can figure out what went wrong
  • I recall my results being a coin toss: half of my algorithms earned me gold stars, the other got me wrong answers

I'm committed to attempting this, because, well, the title of this series.

But I'm not excited to begin.

Re-re-reading the instructions

A list of 3-bit numbers (0 thru 7) separated by commas

Examples:

0,1,2,3
4,1,3,2
2,5,3,3
Enter fullscreen mode Exit fullscreen mode

I get that.

Three registers named A, B, and C

So, variables that will store data.

...aren't limited to 3 bits and can instead hold any integer

So, example values are:

A
-> 39

B
-> 3920238

C
-> 0
Enter fullscreen mode Exit fullscreen mode

Sounds like - per usual - my program will need to update the correct register to the correct value.

The computer knows eight instructions, each identified by a 3-bit number (called the instruction's opcode)

These will be functions I have to write.

In the program, each of the integers 0-8 will correspond to a function.

Each instruction also reads the 3-bit number after it as an input; this is called its operand

So, in a comma-separated list, each two-digit pair of integers acts as an opcode,operand set.

0,2
Enter fullscreen mode Exit fullscreen mode

...should call the function related to 0 and pass in 2 as input.

A number called the instruction pointer identifies the position in the program from which the next opcode will be read

This is the mechanism that lets the program move through and back over opcode-operand pairs. It's constantly tracking some index within the list of integer-based instructions.

  • If the index is ever outside of the bounds of the list, the program halts or ends.
  • It starts at 0, reading the first pair in the list
  • It almost always moves by two in order to skip over each operand that follows an opcode
  • It may instead follow some jump instruction and move in a different manner

To check the logic thus far:

0,1,2,3
Enter fullscreen mode Exit fullscreen mode
  • First, it reads opcode 0 with operand 1
  • The pointer increases by 2
  • Next, it reads opcode 2 with operand 3
  • The pointer increases by 2
  • The program halts because a pointer location of 4 is outside the bounds of the possible indices in the list (0-3)
Where things get complicated: two operand types

each instruction specifies the type of its operand

  1. Literal operand - the value of the literal operand 7 is the number 7
  2. Combo operand - a little tricker
  • Combo operands 0 through 3 represent literal values 0 through 3.
  • Combo operand 4 represents the value of register A.
  • Combo operand 5 represents the value of register B.
  • Combo operand 6 represents the value of register C.
  • Combo operand 7 is reserved and will not appear in valid programs.

Fantastic.

Next, time to see how each opcode function works.

The eight opcode functions
adv 0
  • division
  • Treat operand as type Combo
  • Numerator is the A register
  • Denominator is 2 raised to the power of the computed value of the operand
  • Round the resulting decimal down to the nearest integer
  • Save the final integer into register A
  • increase pointer by 2
bxl 1
  • bitwise XOR
  • Treat operand as type Literal
  • Compute bitwise XOR of register B and operand
  • Save into register B
  • increase pointer by 2
bst 2
  • modulo
  • Treat operand as type Combo
  • Calculate operand modulo 8
  • Save into register B
  • increase pointer by 2
jnz 3
  • a possible jump instruction
  • Treat operand as type Literal
  • Check register A
  • If 0, do nothing, do not increase pointer by 2
  • otherwise, set pointer to operand
bxc 4
  • bitwise XOR
  • Ignores the operand
  • Compute bitwise XOR of register B and C
  • Save into register B
  • increase pointer by 2
out 5
  • print
  • Treat operand as type Combo
  • Calculate operand modulo 8
  • Print values separated by commas
  • increase pointer by 2
bdv 6
  • division
  • Treat operand as type Combo
  • Numerator is the A register
  • Denominator is 2 raised to the power of the computed value of the operand
  • Round the resulting decimal down to the nearest integer
  • Save the final integer into register B
  • increase pointer by 2
cdv 7
  • division
  • Treat operand as type Combo
  • Numerator is the A register
  • Denominator is 2 raised to the power of the computed value of the operand
  • Round the resulting decimal down to the nearest integer
  • Save the final integer into register C
  • increase pointer by 2

Wow wow wow.

That's a lot.

And that's just the quasi-pseudocode.

I now have to write each function.

Then the whole program.

Thankfully there are several examples that I can use as unit tests.

This should be...fun?

Time to start coding!

Program setup

The input is split into two groups by a double carriage-return:

  • Registers A-C
  • Instruction list

I'll use regex to extract the register values.

And split() to break up each line.

let input = input.split('\n\n')
let [A,B,C] = input[0].split('\n').map(line => +line.match(/\d+/g)[0])
let instructions = [...input[1].matchAll(/\d+/g)].map(el => +el[0])
let pointer = 0
let finalOutput = []
Enter fullscreen mode Exit fullscreen mode

Success!

Combo-value-getter

I need a function that computes the correct value from a combo operand.

function getValueFromCombo(n) {

}
Enter fullscreen mode Exit fullscreen mode

It seems like it just needs to be a multi-clause switch statement:

switch (n) {
  case 0:
    return 0
    break;
  case 1:
    return 1
    break;
  case 2:
    return 2
    break;
  case 3:
    return 3
    break;
  case 4:
    return A
    break;
  case 5:
    return B
    break;
  case 6:
    return C
    break;
  case 7:
    return undefined
    break;
}
Enter fullscreen mode Exit fullscreen mode

That all feels straightforward.

I'll find out where I may have gone wrong as I build each of the eight opcode functions.

Writing eight opcode functions

adv 0
  • division
  • Treat operand as type Combo
  • Numerator is the A register
  • Denominator is 2 raised to the power of the computed value of the operand
  • Round the resulting decimal down to the nearest integer
  • Save the final integer into register A
  • increase pointer by 2

As a program, it looks like:

function adv(operand) {
  A = Math.floor(A / (2 ^ getValueFromCombo(operand)))
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode

In testing it, I found a few errors:

  • The syntax for power of in JavaScript is ** not ^
  • I mistakenly used return in each case of my switch. I changed it to update the value of a variable, then for the function to return that value.
  • I was printing adv expecting it to return something, but it just modifies A. When I print A, I see the expected result.

I hope I don't have this much trouble with the other 7 functions!

bxl 1
  • bitwise XOR
  • Treat operand as type Literal
  • Compute bitwise XOR of register B and operand
  • Save into register B
  • increase pointer by 2

As a program, it looks like:

function bxl(operand) {
  B = B | operand
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode

Seems simple enough.

bst 2
  • modulo
  • Treat operand as type Combo
  • Calculate operand modulo 8
  • Save into register B
  • increase pointer by 2

As a program, it looks like:

function bst(operand) {
  B = getValueFromCombo(operand) % 8
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode

Next.

jnz 3
  • a possible jump instruction
  • Treat operand as type Literal
  • Check register A
  • If 0, do nothing, do not increase pointer by 2
  • otherwise, set pointer to operand

As a program, it looks like:

function jnz(operand) {
  if (A == 0) {
    pointer += 2
  } else {
    pointer = operand
  }
}
Enter fullscreen mode Exit fullscreen mode

Next.

bxc 4
  • bitwise XOR
  • Ignores the operand
  • Compute bitwise XOR of register B and C
  • Save into register B
  • increase pointer by 2

As a program, it looks like:

function bxc(operand) {
  C = B | C
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode

Next.

out 5
  • print
  • Treat operand as type Combo
  • Calculate operand modulo 8
  • Print values separated by commas
  • increase pointer by 2

As a program, it looks like:

function out(operand) {
  finalOutput.push(getValueFromCombo(operand) % 8)
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode

I updated the program setup code to include an output-tracking list.

Next.

bdv 6
  • division
  • Treat operand as type Combo
  • Numerator is the A register
  • Denominator is 2 raised to the power of the computed value of the operand
  • Round the resulting decimal down to the nearest integer
  • Save the final integer into register B
  • increase pointer by 2

As a program, it looks like:

function bdv(operand) {
  B = Math.floor(A / (2 ^ getValueFromCombo(operand)))
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode
cdv 7
  • division
  • Treat operand as type Combo
  • Numerator is the A register
  • Denominator is 2 raised to the power of the computed value of the operand
  • Round the resulting decimal down to the nearest integer
  • Save the final integer into register C
  • increase pointer by 2

As a program, it looks like:

function cdv(operand) {
  C = Math.floor(A / (2 ^ getValueFromCombo(operand)))
  pointer += 2
}
Enter fullscreen mode Exit fullscreen mode

That's all of them. I wonder if they'll work!

Invoking each opcode function based on a number

Simple: use an array!

let opcodes = [adv, bxl, bst, jnz, bxc, out, bdv, cdv]
Enter fullscreen mode Exit fullscreen mode

Given this instruction pair:

3,5
Enter fullscreen mode Exit fullscreen mode

I can use this statement to ensure it calls jnz with input 5:

opcodes[opcode](operand)
Enter fullscreen mode Exit fullscreen mode

Building the instruction-reader

The program should read from the instruction list as long as pointer references a valid index: between 0 and one less than the length of the list.

Sounds like a great use of while:

while (pointer >= 0 && pointer < instructions.length) {
  opcodes[pointer](pointer + 1)
}
Enter fullscreen mode Exit fullscreen mode

Printing any output

After the while loop ends, I need to see any accumulated output:

console.log(finalOutput.join(','))
Enter fullscreen mode Exit fullscreen mode

First attempt at running the example program

The example:

Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0
Enter fullscreen mode Exit fullscreen mode

What my program prints:
Enter fullscreen mode Exit fullscreen mode

Yup. Nothing. Uh-oh.

What's wrong?

I added a statement to see what pointer is: 0, 2, 4

Hmm. That should be longer.

After a few minutes, I saw my glaring issue.

It was wrong of my to just reference pointer here:

opcodes[pointer](pointer + 1)
Enter fullscreen mode Exit fullscreen mode

Instead, I need to access the pointerth index in instructions:

opcodes[instructions[pointer]](instructions[pointer + 1])
Enter fullscreen mode Exit fullscreen mode

Second attempt at running the example program

After running, I see:

4,6,3,5,6,3,5,2,1,0
Enter fullscreen mode Exit fullscreen mode

That's the correct answer!

Woohoo!

Attempting the other example programs

If register C contains 9, the program 2,6 would set register B to 1.

The input is:

Register A: 0
Register B: 0
Register C: 9

Program: 2,6
Enter fullscreen mode Exit fullscreen mode

Running it shows me the correct value for B.

If register A contains 10, the program 5,0,5,1,5,4 would output 0,1,2.

The input is:

Register A: 10
Register B: 0
Register C: 0

Program: 5,0,5,1,5,4
Enter fullscreen mode Exit fullscreen mode

Running it shows me the correct output.

If register A contains 2024, the program 0,1,5,4,3,0 would output 4,2,5,6,7,7,7,7,3,1,0 and leave 0 in register A.

The input is:

Register A: 2024
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0
Enter fullscreen mode Exit fullscreen mode

Running it shows me the correct value in A and the correct output.

If register B contains 29, the program 1,7 would set register B to 26.

The input is:

Register A: 0
Register B: 29
Register C: 0

Program: 1,7
Enter fullscreen mode Exit fullscreen mode

Running it shows me 31. Uh-oh.

Whoops. I now realize I am using the bitwise OR (|), not XOR (^)

Running it again shows me the correct value in B.

If register B contains 2024 and register C contains 43690, the program 4,0 would set register B to 44354.

The input is:

Register A: 0
Register B: 2024
Register C: 43690

Program: 4,0
Enter fullscreen mode Exit fullscreen mode

Running it shows me with an updated register C, not B.

That's because my bxc function incorrectly had me updating B instead of C.

With that fixed, I now see B with the correct value.

What about 7 combo values?

My input has a lot of 7s.

The instructions indicate that 7s will never appear as combo values in valid instructions.

My algorithm currently returns undefined for any combo operands that are 7.

I suppose I'll see an error or NaN if the program fails.

Attempting to run my puzzle input

Here's the moment of truth.

All the examples passed.

Will this work?

Well, it doesn't fail and it generates some output.

Sadly, that output is not the correct answer.

I wonder what's going wrong?

Attempting to debug my algorithm

First, I want to see what pointer is doing.

Looks like it is moving two at a time from 0 to 14, then getting reset to 0, close to 10 times before the program ends.

What would cause it to reset to 0?

jnz of course!

The opcode at index 14 in my puzzle input - and the second-to-last one in a few of the example inputs - is 3: jnz.

That function works according to the value in register A:

  • If it is non-zero, pointer increases by 2 to the next opcode
  • Otherwise, pointer moves to the position equal to the value of the operand. In my input's case: 0 - back to the start

So...what's happening to A throughout the loops?

Well, the function adv is quickly shrinking its value by a magnitude of 8:

  • In my instructions, adv is called with 3 being its operand's literal value
  • The equation getting evaluated each time is A's value being divided by 2 to the power of 3: 8
  • All digits past the decimal are removed, essentially rounding down the resulting quotient

Thus, A decreases quickly from a number in the tens of millions down to 1, then 0.

That's great. But that's just the logic that moves pointer.

Apparently my output list is wrong.

So, how is that getting produced?

Well, output grows any time out is called - opcode 5.

In my input that's the second-to-last opcode called - before jnz.

out receives 5 as an operand, pulling the current value from register B.

B's value is divided by 8, and the remainder is added to the list of output values.

Maybe something isn't working right in this function.

Or maybe B gets an incorrect value when being updated in another function.

I think it's time to walk through the instruction list and try to crack this case open.

Ever feel like a huge idiot?

I walked through the first opcode-operand pairs.

I performed each calculation in my terminal's Node command line interface.

I noted what A, B and C were.

And then I saw them.

The last two functions.

The ones I copied from the first function.

But I forget to fix the bitwise OR operator to the bitwise XOR operator.

Such a small oversight.

And one that cost me a lot of wasted time.

Will it work now?

It should!

Press run.

See new numbers output.

Copy-paste-submit.

Correct answer!!!!

Yay!

It was all worth it for a gold star!

What could Part 2 throw at me?

Part 2

What a fun curveball!

Find the lowest positive magic number for register A that causes the program to generate an output list that matches the instruction list.

Some of my thoughts:

  • It's likely to be a massive integer
  • Attempting to check every positive integer starting at 0 seems fruitless
  • There's clearly a pattern to the way the output behaves, or else the instructions wouldn't need to clarify lowest
  • The output list from my input's A value has fewer values than the program
  • So, not only will I need to identify when the output list's length matches the program's, but also when each of the values match
  • And then probably calculate the lowest common denominator

This definitely seems worth a try, even though I'm so ready to bid this puzzle farewell by now.

Looking for patterns everywhere

This experiment will require iterating through thousands of integers.

So I'll expand upon my core while loop to account:

for (let i = 0; i < 10; i++) {
    A = i
    while (pointer >= 0 && pointer < instructions.length) {
        opcodes[instructions[pointer]](instructions[pointer + 1])
    }
}
Enter fullscreen mode Exit fullscreen mode

Running that helped me see that I was forgetting to reset a few other global variables:

for (let i = 0; i < 10; i++) {
    A = i, B = 0, C = 0
    finalOutput = []
    pointer = 0
    while (pointer >= 0 && pointer < instructions.length) {
        opcodes[instructions[pointer]](instructions[pointer + 1])
    }
}
Enter fullscreen mode Exit fullscreen mode

Much better.

My output length is growing.

Increasing i to 100 continues the trend: output length is growing.

Next, I want to see how big the output length gets.

But I don't want to have to print out each output list for i from 0 to some number near a million.

I only care about the length, and when it is some new value.

I'll use a Set to track unique lengths:

let lengths = new Set()
for (let i = 0; i < 1000; i++) {
    // all earlier code
    lengths.add(finalOutput.length)
}
Enter fullscreen mode Exit fullscreen mode

When I print the contents of Set, I correctly see:

Set(10) { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Enter fullscreen mode Exit fullscreen mode

Perfect!

Now to try exponentially larger integers for i!

10000    -> 14
100000   -> 17
1000000  -> 20
10000000 -> 24
Enter fullscreen mode Exit fullscreen mode

Seems logical.

Well, my puzzle input's instruction list contains 16 integers.

Now I wonder how often the output list contains 16 integers.

Summarizing my latest findings

  • I set i to some fairly high numbers
  • The output list stayed fairly small
  • I adjusted my core loop to a while loop that only escaped when the output length equaled the instruction length
  • And I multiplied i by 10 each iteration to grow it at a faster rate
  • The value of i that appeared in my console was a 1 followed by 14 0s

I then re-considered how the program works, and it made sense:

  • opcodes 0, 6 and 7 update register values
  • My input contains 0,3 and 7,5
  • The 3 causes A to get divided by 8 (2 ^ 3)
  • The 5 causes C to become A divided by 2 ^ B, which is updated in several other opcode functions
  • This pattern of dividing by 8 stands out
  • Because 8 ^ 16 is a number with 15 digits, much like 1 followed by 14 0s

I have now validated that:

  • The lowest positive value for A that generates output that could match the program's instruction list is an integer in the tens or hundreds of trillions (number with almost or equal to 16 digits)

Checking any subset of those would take years of processing time.

So there must be a better pattern to chase.

But first, I really want to know what the lowest integer is that generates an output list size equal to the instruction list.

After some gradually decreasing number incrementation amounts, I found it for my input:

35184372088832
Enter fullscreen mode Exit fullscreen mode

That's the very first time both list sizes are equal.

Cool!

The answer isn't lower than that!

And how about the first time the size of the output list is one greater, 17?

Apparently it's in the 200 trillions!!

Wow!

There's about 165 trillion integers between them.

So, where was I again about finding another pattern to chase?

Storing each time a match is found per index

I need to match 16 values.

I know that each match will only strike once in a while.

So, I want to collect a few matches for each index, then see if there's a pattern to each one's interval for occurring.

My new code to check for the right conditions is:

if (finalOutput.length == instructions.length) {
    for (let j = 0; j < instructions.length; j++) {
        if (finalOutput[j] == instructions[j]) {
            matches[j].push(i)
        }
    }
    console.log(i, matches.map(el => el.length))
    i += 1
}
if (matches.every(el => el.length >= 1)) {
    return false
}
Enter fullscreen mode Exit fullscreen mode
  • I run the program
  • I watch the output fly by
  • And I see where 0s increase

At the start, few numbers increase.

As I drastically check bigger starting numbers, I see more and more numbers increase.

Eventually, I see all but one number increase.

Unfortunately, that one index keeps changing.

I feel like I'm playing whack-a-mole.

...

I eventually found a state where all 16 indices had at least one match with the instructions list.

With that, I wanted to see if the differences between each of the matches within a given index were equal - meaning the match happened on the same interval.

Sadly, they aren't.

So, I'm stumped.

Throwing in the towel

This has become a fruitless scavenger hunt for a needle in a haystack.

It's not how I am supposed to solve the puzzle.

And it's not fun any more.

So, I happily take my one hard-earned gold star, and continue to another day.

Top comments (1)