Advent of Code Day 17 was quite tough. I finally solved it after noticing some patterns, lets figure it out!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

We are given the rules of a 3 bit computer (ie numbers ranging from 0 to 7) computer with three register A, B and C on how it processes its programs. Each program has an instruction (identified by its opcode) followed by its operand.

There are two types of operands:

1. Literal Operand - where the value of the operand is the operand itself.
2. Combo Operand - Value of the combo operand can be found through these rules:
   • 0 to 3 - value is the operand itself.
   • 4 - value is the contents of Register A.
   • 5 - value is the contents of Register B.
   • 6 - value is the contents of Register C.

There are 8 types of instructions:

1. Opcode 0 - adv instruction. Calculates the division of value of register A with 2 raised to the power of instruction’s combo operand and stores it in register A.
2. Opcode 1 - bxl instruction. Calculates bitwise XOR of the values in register B and instruction’s literal operand and stores it in register B.
3. Opcode 2 - bst instruction. Calculates the value of its combo operand modulo 8 and stores it in register B.
4. Opcode 3 - jnz instruction. Does nothing if value in Register A is 0. If not, it sets the instruction pointer to the literal value of the instruction’s literal operand, in which case the instruction pointer is not increased by 2 after this instruction is done processing.
5. Opcode 4 - bxc instruction. Calculates bitwise XOR of the values in register B and C and stores it in register B.
6. Opcode 5 - out instruction. Calculates the value of its combo operand modulo 8 and outputs the value.
7. Opcode 6 - bdv instruction. Calculates the division of value of register A with 2 raised to the power of instruction’s combo operand and stores it in register B.
8. Opcode 7 - cdv instruction. Calculates the division of value of register A with 2 raised to the power of instruction’s combo operand and stores it in register C.

The input is the values of register A, B and C along with a program. We need to find the output of the given program.

Solution

This is fairly straightforward, we just need to ensure we have read the problem statement correctly and are implementing it exactly right.

Let’s start with writing a function to calculate the combo operand for any given operand:

func getComboOperand(input int64, registerA, registerB, registerC int64) int64 {
	switch input {
	case 0, 1, 2, 3:
		return input
	case 4:
		return registerA
	case 5:
		return registerB
	case 6:
		return registerC
	case 7:
		return 7
	}
	return input
}

Now, we can write a function that processes the opcode and operand and performs the correct instruction. We need to ensure that the func apart from returning the modified registers, also returns output (in case the opcode is 5) and any change to instruction pointer (in case of opcode 3).

func processOpcode(operand int64, opcode int64, registerA, registerB, registerC int64, ip int64) (int64, int64, int64, int64, int64) {
	comboOperand := getComboOperand(operand, registerA, registerB, registerC)
	var output int64
	output = -1

	switch opcode {
	case 0:
		registerA = registerA / int64(math.Pow(2, float64(comboOperand)))
	case 1:
		registerB = registerB ^ operand
	case 2:
		registerB = (comboOperand % 8)
	case 3:
		if registerA != 0 {
			ip = operand
		}
	case 4:
		registerB = registerB ^ registerC
	case 5:
		output = int64(comboOperand % 8)
	case 6:
		registerB = registerA / int64(math.Pow(2, float64(comboOperand)))
	case 7:
		registerC = registerA / int64(math.Pow(2, float64(comboOperand)))
	}
	return registerA, registerB, registerC, ip, output
}

Now we just need to call the above function for each pair of opcode and operands:

func doCalc(a, b, c int64, inst []int64) []int64 {
	var ip int64
	var output []int64
	for ip < int64(len(inst)-1) {
		var newIP, o int64
		newIP = ip
		o = -1
		a, b, c, newIP, o = processOpcode(inst[ip+1], inst[ip+0], a, b, c, ip)
		if newIP == ip {
			ip += 2
		} else {
			ip = newIP
		}
		if o != -1 {
			output = append(output, o)
		}
	}
	return output
}

The final answer will be what is returned by the above function.

Part 2

Now, we need to find the minimum value of A for which the program will return a copy of itself.

Solution

TIL: A computer that returns a copy of its source code is a called a Quine.

When I tried to first loop through values of A, incrementing it by 1 each time, it quickly became evident that this value of A is large and we can’t just wait brute force it. We will have to think of a clever solution.

So, the first thing I did was double the value of register A till we arrive at the same length as the output. Then I kept printing out the values of output by incrementing A by 1 and notices a pattern.

I noticed that the output for the program would only change the first few digits and the latter digits are only changing at a specified interval. I started printing which digit is changing and at what interval. After many trial and errors, I found that every nth digit changes after 8^nth change in the value of Register A.

So we can get the desired output by simply fixing each digit one at a time, starting from the LSB. For each changed value of A, we will find the first digit that is different than the desired output. We will increment A by (8 raised to the power of position of the digit). We will continue doing this till we find the value of A that gives us the desired output.

Implementing this is simple enough:

func findValueOfA(a, b, c int64, inst []int64) int64 {
	output := []int64{}
	a = 1
	for {
		output = doCalc(a, b, c, inst)

		if reflect.DeepEqual(output, inst) {
			return a
		}

		if len(inst) > len(output) {
			a *= 2
			continue
		}

		if len(inst) == len(output) {
			for j := len(inst) - 1; j >= 0; j-- {
				if inst[j] != output[j] {
					// Key Insight: every nth digit increments at every 8^n th step.
					// https://www.reddit.com/r/adventofcode/comments/1hg38ah/comment/m2gkd6m/
					a += int64(math.Pow(8, float64(j)))
					break
				}
			}
		}
	}
}

And that’s it! The above function will give us the answer to part two! You can find my final code here.

Some folks solved this using recursion (I’m not sure how that would work, if you used recursion, send me your solution, I’d love to take a look!). Some even more smart folks, came up with a challenging input to test the speed of solutions. The above solution works pretty fast with this challenging test case so I’m pretty happy!

While it seems so much more easier in retrospect, spotting this pattern wasn’t easy. Even after I did spot the pattern I wasn’t sure if it is indeed right, so it involved a lot of trial and error to arrive at the solution. This was one of those days that makes me appreciate Eric (even more than usual) on coming up with such unique puzzles while also educating us about something new!

How did you solve Day 17? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.