2024-12-17
[Go to index] [Advent of Code website] [My code on Gitlab]
Well, that was painful.
Today was about building a computer, which was fine, then using it, which wasn’t. Let me explain.
We have a computer with three registers (A
,
B
and C
), which is able to perform a bunch of
different operations. The input is a text file containing the initial
value of the registers, and a program like this example:
Register A: 729
Register B: 0
Register C: 0
Program: 0,1,5,4,3,0
The program is a succession of numbers, which need to be interpreted
pairwise as opcode, operand
. How to interpret those
opcode
s and operand
s is detailed on the puzzle page, but the
main point is that everything is base-8: there are 8 operations,
operands can take values 0-7, everything is encoded in 3 bits. That will
turn out to be very useful later.
The goal in the first part is to determine the output of the program
(one of the instructions is out, x
, which outputs
x
(or rather the “combo” of x
, as defined in
the puzzle)).
For the program above, we could rewrite it assembly-like as:
adv 1
out 4
jnz 0
Which, given the rules laid out in the puzzle, would perform the operations:
0: A <- A//2
1: PRINT A%8
2: if A != 0:
3: goto 0
4: END
From the initial state of A=729
, we would therefore
get:
A <- 364, PRINT 364%8 = 4
A <- 182, PRINT 6
A <- 91, PRINT 3
A <- 45, PRINT 5
A <- 22, PRINT 6
A <- 11, PRINT 3
A <- 5, PRINT 5
A <- 2, PRINT 2
A <- 1, PRINT 1
A <- 0, PRINT 0
END
So we just need to code all of the operations. Rather than going object-oriented, this time I went with some global variables, which felt more appropriately old school:
= {
REGISTER 'A': 0,
'B': 0,
'C': 0
}list[str] = []
STDOUT: list[int] = []
PROGRAM: int = 0 instrptr:
instrptr
is the instruction pointer, which will tell us
where we are in the program.
Then we encode the “combo value” thing:
class InvalidComboValueException(Exception):
pass
def combo(op: int) -> int:
if 0 <= op < 4:
return op
if op == 4:
return REGISTER['A']
if op == 5:
return REGISTER['B']
if op == 6:
return REGISTER['C']
raise InvalidComboValueException(f"op: {op}")
Make some helper functions to manipulate things:
= Callable[[int], None]
Instruction
def set_register(r: str, v: int) -> None:
global REGISTER
= v
REGISTER[r]
def get_register(r: str) -> int:
return REGISTER[r]
def incptr(i: int = 2) -> None:
global instrptr
+= i
instrptr
def jumpto(v: int) -> None:
global instrptr
= v
instrptr
def printout(v: int) -> None:
global STDOUT
str(v))
STDOUT.append(
def clearout() -> None:
global STDOUT
STDOUT.clear()
And finally create our instruction set:
def adv(op: int) -> None:
'A', int(get_register('A')/(2**combo(op))))
set_register(
incptr()
def bxl(op: int) -> None:
'B', get_register('B')^op)
set_register(
incptr()
def bst(op: int) -> None:
'B', combo(op)%8)
set_register(
incptr()
def jnz(op: int) -> None:
if get_register('A') != 0:
jumpto(op)return
incptr()
def bxc(op: int) -> None:
'B', get_register('B')^get_register('C'))
set_register(
incptr()
def out(op: int) -> None:
%8)
printout(combo(op)
incptr()
def bdv(op: int) -> None:
'B', int(get_register('A')/(2**combo(op))))
set_register(
incptr()
def cdv(op: int) -> None:
'C', int(get_register('A')/(2**combo(op))))
set_register(
incptr()
= {
INSTRUCTION_SET 0: adv,
1: bxl,
2: bst,
3: jnz,
4: bxc,
5: out,
6: bdv,
7: cdv
}
Then we have the execution loop, and a function to print the status of the computer for debugging purposes.
def execute() -> bool:
if instrptr >= len(PROGRAM):
return False
+1])
INSTRUCTION_SET[PROGRAM[instrptr]](PROGRAM[instrptrreturn True
def execute_program():
while execute():
continue
def print_status():
print(f"PROGRAM STATUS:")
print(f"Register A: {get_register('A')}")
print(f"Register B: {get_register('B')}")
print(f"Register C: {get_register('C')}")
print(f"PROGRAM: {PROGRAM}")
print(f"instrptr: {instrptr}")
print(f"STDOUT: {','.join(STDOUT)}")
Now we need to parse the input file and actually “load” the program by setting the registers and putting the opcodes and operands in the instruction list:
def load_program(data: str):
global PROGRAM
= r"Register A: (\d+)\nRegister B: (\d+)\nRegister C: (\d+)\n\nProgram: ([\d|,]+)"
pattern
= re.match(pattern, data)
things if things is None or len(things.groups()) != 4:
raise InvalidProgramException()
= things.groups()
a, b, c, program 'A', int(a))
set_register('B', int(b))
set_register('C', int(c))
set_register(= [int(p) for p in program.split(',')]
PROGRAM
def load_from_file():
with open("day17", r) as fp:
= fp.read()
data load_program(data)
We can now load and execute the program and get the result:
"")
load_from_file(
execute_program() print_status()
And we get our first part done fairly quickly.
In part 2, we need to find the smallest possible initial
value for the A
register so that the program
outputs itself. So for instance, if we have the program
0,3,5,4,3,0
, and we set A
to
117440
, the output of the program will be
0,3,5,4,3,0
: it outputs itself.
Okay, I thought naively. Let’s start by being dumb and just start
from 0 and increment a
until I find something that
works.
A few minutes later, I cut it off and decided that I would not be
that dumb. So I thought about it. And to think about it, I had
to look at my actual puzzle input. My program was
2,4,1,1,7,5,1,5,0,3,4,4,5,5,3,0
, which translated to:
bst 4
bxl 1
cdv 5
bxl 5
adv 3
bxc 4
out 5
jnz 0
Or, developing a bit further:
0: B <- A%8
1: B <- B xor 1
2: C <- A//(2**B) = A >> B
3: B <- B xor 5
4: A <- A//8 = A >> 3
5: B <- B xor C
6: PRINT B%8
7: if A != 0:
8: goto 0
9: END
It took me a while, but I eventually realized that with the sequence:
A <- A//8
if A != 0:
goto 0
The length of the output was easily determined by the
initial value of A. If A was between 0 and 7, I would get a single
output. Between 8 and 63, I would get two numbers. In general, to get a
size
Oh, no.
That was a bit too big of a space to explore.
I thought about it some more. Couldn’t really find a better idea.
Almost quit. Then I realized something actually useful: at every loop of
my program, I was using the value of A%8
to compute the
output, but then I was dividing it by 8 (ignoring the remainder) and,
crucially, the value of B
and C
at the “end”
of the loop didn’t affect the next printed value.
In other words: if, for instance, I start with A = 34
,
the first number that I print will be some function of 34
(let’s call it f(34)
). Then, A
becomes
34//8 = 4
and the second number that I print will be
f(4)
. Then A
will be set at 0
and
we will stop.
So the last number printed by the program will only
depend on the last nonzero remainder of the successive divisions by 8…
Which are the last 3 bits of A
. So that gives me a
procedure to find A
:
First, for k
between 0 and 7, check which ones gives me
a 0
at the output. Those are “candidates” for the last
three bits of A
.
Then, for each of those candidates, add k*8
(still for
k
between 0 and 7) and check which k
gives us
two numbers corresponding the the last numbers in my program
(3, 0
). Keep going, eliminating the “wrong” paths as we go,
until we get a bunch of candidates that produce the right program. Then
select the smallest.
Because of the way I had set up my “computer”, this was a pain in the *** to implement. I ended up just manually rewriting “my” input program, which unfortunately makes my solution only work for my input. Here it is anyway:
def manual_program(a: int):
= []
out = False
stop while not stop:
= (a % 8)^1
b = a >> b
c = (b^5)
b = a >> 3
a = b^c
b %8)
out.append(b= a == 0
stop return out
def find_min_a(factors: list[int], candidates: list[int]):
for k in range(8):
if len(factors) == 0:
= 0
a else:
= sum(f*(8**(len(factors)-i)) for i, f in enumerate(factors))
a = manual_program(a+k)
out if len(out) == len(PROGRAM):
if all(o == p for o, p in zip(out, PROGRAM)):
+k)
candidates.append(areturn
if all(o == p for o, p in zip(out, PROGRAM[-len(factors)-1:])):
+[k], candidates)
find_min_a(factors
= []
factors = []
candidates
find_min_a(factors, candidates)= min(candidates)
a print(f"Minimum value for a: {a}")
Finally free.