This December I participated in Advent of Code.

Part 1 was easy, satisfying, kind of nice to do.

Part 2 on the other hand… I tried a lot of different approaches. What ended up working for me was a combination of spreadsheet and paper. My input is reproduced below in full, as I can’t really explain this without it.

First I translated a bit of the program, say “2,4”, into something I could understand, B = A modulo 8. In the pictures below you find this in cell b19 and k4. I kept going, until I had the whole program. I then filtered out some stuff. The second picture represents the core program. (B3 = 7-B1 is a shortcut I discovered along the way.) The only variables at this point are B1 and C1, the rest depend on these 2. So I create the full table, with all the possible values of B1 and C1. I also create the binary column: This will be part of the number in A from the beginning (let’s call it AA). I throw away some combinations that won’t work, because a bit can’t have 2 values at the same time. Then I go hunting.

My expected output (let’s call it OO) ends with a 0. My full table suggests the smallest possible input (part of AA) is 7, because this only contributes 7 to AA. I register (on paper) 7 (in octal) and ????000111 (in binary) and keep going. The next part of OO is 3. The corresponding input can’t be 0 (the 111 from the previous step would then have to also be 100), but 4 works. This is the smallest option. I register 74 (in octal) and ????000111100 (in binary) and keep going.

And that’s it! That’s how I build AA. The only exception is, that sometimes there are no options for a part of the number, then I go back and choose a bigger part of the input in a previously settled spot. 740 doesn’t work for the next part? Try 741.

Phew!

Part 1:

<?php
$input = file_get_contents('./d17input2.txt', true);
foreach(preg_split("/((\r?\n)|(\r\n?))/", $input) as $line) {
	if(preg_match("/Register A/",$line,$matches)) {
		if(preg_match("/(\d+)/",$line,$matches)) {
			$a = $matches[0];
		}
	}
	if(preg_match("/Register B/",$line,$matches)) {
		if(preg_match("/(\d+)/",$line,$matches)) {
			$b = $matches[0];
		}
	}
	if(preg_match("/Register C/",$line,$matches)) {
		if(preg_match("/(\d+)/",$line,$matches)) {
			$c = $matches[0];
		}
	}
	if(preg_match("/Program/",$line,$matches)) {
		if(preg_match_all("/(\d+)/",$line,$matches)) {
			$prg = $matches[0];
		}
	}
}
$inspoi = 0;
$prgend = sizeof($prg);
$commas = "";
while($inspoi < $prgend) {
	$opcode = $prg[$inspoi];
	$operand = $prg[$inspoi+1];
/*
There are two types of operands; each instruction specifies the type of its operand. The value of a literal operand is the operand itself. For example, the value of the literal operand 7 is the number 7. The value of a combo operand can be found as follows:
    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.
*/
	switch($operand) {
		case 0:
		case 1:
		case 2:
		case 3:
			$combo = $operand;
			break;
		case 4:
			$combo = $a;
			break;
		case 5:
			$combo = $b;
			break;
		case 6:
			$combo = $c;
			break;
	}
/*The adv instruction (opcode 0) performs division. The numerator is the value in the A register. The denominator is found by raising 2 to the power of the instruction's combo operand. (So, an operand of 2 would divide A by 4 (2^2); an operand of 5 would divide A by 2^B.) The result of the division operation is truncated to an integer and then written to the A register.*/
	if($opcode == 0) {
		$a = (int) ($a / pow(2, $combo));
	}
/*The bxl instruction (opcode 1) calculates the bitwise XOR of register B and the instruction's literal operand, then stores the result in register B.*/
	if($opcode == 1) {
		$b = $b ^ $operand;
	}
/*The bst instruction (opcode 2) calculates the value of its combo operand modulo 8 (thereby keeping only its lowest 3 bits), then writes that value to the B register.*/
	if($opcode == 2) {
		$b = $combo % 8;
	}
/*The jnz instruction (opcode 3) does nothing if the A register is 0. However, if the A register is not zero, it jumps by setting the instruction pointer to the value of its literal operand; if this instruction jumps, the instruction pointer is not increased by 2 after this instruction.*/
	if($opcode == 3) {
		if($a != 0) {
			$inspoi = $operand;
			continue;
		}
	}
/*The bxc instruction (opcode 4) calculates the bitwise XOR of register B and register C, then stores the result in register B. (For legacy reasons, this instruction reads an operand but ignores it.)*/
	if($opcode == 4) {
		$b = $b ^ $c;
	}
/*The out instruction (opcode 5) calculates the value of its combo operand modulo 8, then outputs that value. (If a program outputs multiple values, they are separated by commas.)*/
	if($opcode == 5) {
		$tmp = $combo % 8;
		echo "$commas$tmp";
		if($commas == "") {
			$commas = ",";
		}
	}
/*The bdv instruction (opcode 6) works exactly like the adv instruction except that the result is stored in the B register. (The numerator is still read from the A register.)*/
	if($opcode == 6) {
		$b = (int) ($a / pow(2, $combo));
	}
/*The cdv instruction (opcode 7) works exactly like the adv instruction except that the result is stored in the C register. (The numerator is still read from the A register.)*/
	if($opcode == 7) {
		$c = (int) ($a / pow(2, $combo));
	}
	$inspoi = $inspoi + 2;
}
echo "\n";
?>

Part 2:

Input:

Register A: 50230824
Register B: 0
Register C: 0
Program: 2,4,1,3,7,5,0,3,1,4,4,7,5,5,3,0

Spreadsheet.