10 KiB
AOC 2024 Day 17
Section
The computer knows eight instructions, each identified by a 3-bit number (called the instruction's opcode). Each instruction also reads the 3-bit number after it as an input; this is called its operand.
A number called the instruction pointer identifies the position in the program from which the next opcode will be read; it starts at 0, pointing at the first 3-bit number in the program. Except for jump instructions, the instruction pointer increases by 2 after each instruction is processed (to move past the instruction's opcode and its operand). If the computer tries to read an opcode past the end of the program, it instead halts.
So, the program 0,1,2,3 would run the instruction whose opcode is 0 and pass it the operand 1, then run the instruction having opcode 2 and pass it the operand 3, then halt.
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.
The eight instructions are as follows:
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.
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.
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.
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.
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.)
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.)
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.)
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.)
Here are some examples of instruction operation:
If register C contains 9, the program 2,6 would set register B to 1.
If register A contains 10, the program 5,0,5,1,5,4 would output 0,1,2.
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.
If register B contains 29, the program 1,7 would set register B to 26.
If register B contains 2024 and register C contains 43690, the program 4,0 would set register B to 44354.
e1 = """
Register A: 729
Register B: 0
Register C: 0
Program: 0,1,5,4,3,0
"""
s1 = "4,6,3,5,6,3,5,2,1,0"
e2 = """
Register A: 2024
Register B: 0
Register C: 0
Program: 0,3,5,4,3,0
"""
input = """
Register A: 17323786
Register B: 0
Register C: 0
Program: 2,4,1,1,7,5,1,5,4,1,5,5,0,3,3,0
"""
defmodule ChronospatialComputer do
defstruct a: nil, b: nil, c: nil, program: nil, pc: nil, output: <<>>
def parse(input) do
[registers, program] = input |> String.trim() |> String.split("\n\n", trim: true)
[a,b,c] = for register <- registers |> String.split("\n") do
register |> String.split(": ") |> Enum.at(1) |> String.to_integer
end
pc = program
|> String.split(": ")
|> Enum.at(1)
|> String.split(",", trim: true)
|> Enum.map(&(String.to_integer/1))
|> :binary.list_to_bin()
init(a,b,c,pc)
end
def init(a, b, c, pc) do
%ChronospatialComputer {
a: a,
b: b,
c: c,
program: pc,
pc: 0,
}
end
def run(%ChronospatialComputer{pc: n, program: prog} = computer) when n >= (byte_size(prog)-1) do
computer
end
def run(computer) do
computer |> exec() |> run()
end
def run_while(%ChronospatialComputer{pc: n, program: prog} = computer, _) when n >= (byte_size(prog)-1) do
{:halt, computer}
end
def run_while(computer, predicate) do
if predicate.(computer) do
computer |> exec() |> run_while(predicate)
else
{:false_pred, computer}
end
end
def exec(computer) do
{instruction, operand} = {:binary.at(computer.program, computer.pc), :binary.at(computer.program, computer.pc + 1)}
exec(computer, {instruction, operand})
end
# :adv
def exec(computer, {0, n}) do
%ChronospatialComputer{ computer | a: div(computer.a, 2**combo_op(computer, n)), pc: computer.pc + 2}
end
# :bxl
def exec(computer, {1, n}) do
%ChronospatialComputer{ computer | b: Bitwise.bxor(computer.b, n), pc: computer.pc + 2}
end
# :bst
def exec(computer, {2, n}) do
%ChronospatialComputer{ computer | b: Bitwise.band(combo_op(computer, n), 7), pc: computer.pc + 2}
end
#:jnz
def exec(%ChronospatialComputer{a: 0} = computer, {3, _}) do
%ChronospatialComputer{ computer | pc: computer.pc + 2}
end
def exec(computer, {3, n}) do
%ChronospatialComputer{ computer | pc: n}
end
# :bxc
def exec(computer, {4, _}) do
%ChronospatialComputer{ computer | b: Bitwise.bxor(computer.b, computer.c), pc: computer.pc + 2}
end
# :out
def exec(computer, {5, n}) do
%ChronospatialComputer{computer | output: computer.output <> <<combo_op(computer, n) |> Bitwise.band(7)>>, pc: computer.pc + 2}
end
# :bdv
def exec(computer, {6, n}) do
%ChronospatialComputer{ computer | b: div(computer.a, 2**combo_op(computer, n)), pc: computer.pc + 2}
end
# :cdv
def exec(computer, {7, n}) do
%ChronospatialComputer{ computer | c: div(computer.a, 2**combo_op(computer, n)), pc: computer.pc + 2}
end
# 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.
def combo_op(computer, op) do
case op do
n when n >= 0 and n <= 3 -> n
4 -> computer.a
5 -> computer.b
6 -> computer.c
7 -> throw "received combo op 7 at #{computer.pc + 1}"
end
end
# Runs my AOC input written as Elixir with `a` in register A.
# I could use the code that solves p1, but this runs 10x faster.
def run_with_register_a(a), do: run_with_register_a(a, <<>>)
def run_with_register_a(0, o), do: o
def run_with_register_a(a, o) do
import Bitwise
# 0 to 7
# 0 <= len(b) <= 3
b = (a &&& 7)|> Bitwise.bxor(1)
# a - 7 <= len(c) <= a
c = a >>> b
# 0 <= len(b) <= 3
b = b |> Bitwise.bxor(5) |> Bitwise.bxor(c)
o = o <> <<b &&& 7>>
run_with_register_a(a >>> 3, o)
end
# finds valid values of the `A` register that will cause `run_with_register_a` to return
# an output equal to the program
def quine(program) do
quine(program, 0, 10, 0)
|> Enum.sort()
end
def quine(<<>>, bits, _, _), do: [bits]
# bits is the integer so far
# len is the number of bits to generate
# z is the number of bits in `bits` expressed as 7 + 3*z
def quine(<< first, rest::binary >>, bits, len, z) do
import Bitwise
for i <- 0..((2**len)-1), # first iter - generate 10-bit sequences, do 3-bits on all subsequent loops
# noop on first iter - after, shifts over 7 bits
i = i <<< (10 - len),
# `bits` is always 7+3z bits long, so this will return 7 bits from `bits` and
# adds the three bits from `i` at the beginning
# so j is << i_0, i_1, i_2, b_0, b_1, b_2, b_3, b_4, b_5, b_6 >>
j = (bits >>> 3*z) + i,
# run the program with `j` as input
o = ChronospatialComputer.run_with_register_a(j),
o |> byte_size() > 0,
# take only the sequences that generate the next output we're looking for
# if we're on the last iteration we want sequences that don't generate
# more outputs than we need.
# if we're on any other iteration, we take those outputs because they
# will be combined with more bits on the next loop.
(rest != <<>> and o |> :binary.at(0) == first) or o == << first >> do
# takes the `len` (either 3 or 10 - if it's the first loop) new bits from
# `i` and prepends them to `bits`
(i <<< 3*z) + bits
end |> Enum.flat_map(
fn b ->
# generate the next three bits in the sequence
# we do 3 at a time because the program always shifts a 3 bits after writing
# to the output.
quine(rest, b, 3, z+1)
end
)
end
end
Digging deeper in the device's manual, you discover the problem: this program is supposed to output another copy of the program! Unfortunately, the value in register A seems to have been corrupted. You'll need to find a new value to which you can initialize register A so that the program's output instructions produce an exact copy of the program itself.
For example:
Register A: 2024
Register B: 0
Register C: 0
Program: 0,3,5,4,3,0
This program outputs a copy of itself if register A is instead initialized to 117440. (The original initial value of register A, 2024, is ignored.)
What is the lowest positive initial value for register A that causes the program to output a copy of itself?
[p2answer, _] = ChronospatialComputer.quine(<<2,4,1,1,7,5,1,5,4,1,5,5,0,3,3,0>>)
ChronospatialComputer.run_with_register_a(p2answer)