2021-12-24 - Arithmetic Logic Unit
(original .ipynb)
NOTE: Abject failure on this one. I'm gonna come back and kick its ass in a couple of days :D
puzzle_input_str = open("puzzle_input/day24.txt").read()
from advent import listify
from math import floor
@listify
def parse_args(args):
for arg in args:
if arg.isnumeric() or (arg[0] == "-" and arg[1:].isnumeric()):
yield int(arg)
else:
yield arg
def parse_line(line):
parts = line.split(" ")
return parts[0], parse_args(parts[1:])
# - add a b - Add the value of a to the value of b, then store the result in variable a.
# - mul a b - Multiply the value of a by the value of b, then store the result in variable a.
# - div a b - Divide the value of a by the value of b, truncate the result to an integer, then store the result in variable a. (Here, "truncate" means to round the value toward zero.)
# - mod a b - Divide the value of a by the value of b, then store the remainder in variable a. (This is also called the modulo operation.)
# - eql a b - If the value of a and b are equal, then store the value 1 in variable a. Otherwise, store the value 0 in variable a.
def value(v, env):
if type(v) == int:
return v
assert v in "wxyz"
return env[v]
# - inp a - Read an input value and write it to variable a.
def inp(args, env):
a = args[0]
v = env["input"].pop(0)
env[a] = v
def add(args, env):
a, b = args
env[a] = value(a, env) + value(b, env)
def mul(args, env):
a, b = args
env[a] = value(a, env) * value(b, env)
def div(args, env):
a, b = args
env[a] = value(a, env) // value(b, env)
# env[a] = floor(value(a) / value(b))
def mod(args, env):
a, b = args
env[a] = value(a, env) % value(b, env)
def eql(args, env):
a, b = args
env[a] = 1 if value(a, env) == value(b, env) else 0
ops = {
"inp": inp,
"add": add,
"mul": mul,
"div": div,
"mod": mod,
"eql": eql
}
def transpile_inp(args, env):
a = args[0]
print(f"\n{a} = input.pop(0)")
def transpile_add(args, env):
a, b = args
print(f"{a} += {b}")
def transpile_mul(args, env):
a, b = args
print(f"{a} *= {b}")
def transpile_div(args, env):
a, b = args
print(f"{a} /= {b}")
def transpile_mod(args, env):
a, b = args
print(f"{a} %= {b}")
def transpile_eql(args, env):
a, b = args
print(f"{a} = 1 if {a} == {b} else 0")
def transpile_mv_imm(args, env):
a, b = args
print(f"{a} = {b}")
transpile_ops = {
"inp": transpile_inp,
"add": transpile_add,
"mul": transpile_mul,
"div": transpile_div,
"mod": transpile_mod,
"eql": transpile_eql,
"uop_mv_imm": transpile_mv_imm
}
from collections import defaultdict
def parse_program(input_str):
return [parse_line(line.strip()) for line in input_str.strip().split("\n")]
def execute(program, program_input):
env = {
"input": program_input,
"w": 0,
"x": 0,
"y": 0,
"z": 0
}
for op, args in program:
ops[op](args, env)
return env
def elim_mul_zero(program):
# there's a lot of this:
# y *= 0
# y += 25
# which can be simplified to
# y = 25
# do this via code so I make fewer mistakes
last_line = len(program) - 1
new_program = []
next_is_nop = False
for curr_line, (curr_op, curr_args) in enumerate(program):
if next_is_nop:
next_is_nop = False
continue
if curr_line == last_line:
new_program.append((curr_op, curr_args))
continue
next_op, next_args = program[curr_line + 1]
if len(curr_args) != 2 or len(next_args) != 2:
new_program.append((curr_op, curr_args))
continue
curr_a, curr_b = curr_args
next_a, next_b = next_args
mult_by_zero = curr_op == "mul" and type(curr_b) == int and curr_b == 0
then_accumulate = next_op == "add"
into_same_reg = curr_a == next_a
if all((mult_by_zero, then_accumulate, into_same_reg)):
new_program.append(("uop_mv_imm", [curr_a, next_b]))
next_is_nop = True
else:
new_program.append((curr_op, curr_args))
return new_program
def peephole_simplify(program):
program = elim_mul_zero(program)
return program
def transpile(program, program_input):
# program = peephole_simplify(program)
for op, args in program:
transpile_ops[op](args, None)
def test_negate():
code = """
inp x
mul x -1
"""
program = parse_program(code)
env = execute(program, [10])
assert env["x"] == -10
def test_mul():
code = """
inp z
inp x
mul z 3
eql z x
"""
program = parse_program(code)
env = execute(program, [10, 30])
assert env["z"] == 1
env = execute(program, [10, 20])
assert env["z"] == 0
# Here is an ALU program which takes a non-negative integer as input, converts it into binary,
# and stores the lowest (1's) bit in z, the second-lowest (2's) bit in y, the third-lowest (4's)
# bit in x, and the fourth-lowest (8's) bit in w:
def test_mod():
code = """
inp w
add z w
mod z 2
div w 2
add y w
mod y 2
div w 2
add x w
mod x 2
div w 2
mod w 2
"""
program = parse_program(code)
env = execute(program, [7581])
assert env["z"] == 1
assert env["y"] == 0
assert env["x"] == 1
assert env["w"] == 1
def test():
test_negate()
test_mul()
test_mod()
def submarine_model_numbers():
# start from the largest 14 digit number and work down
n = int("".join("9"*14))
limit = int("1" + "".join("0") * 13)
while n > 0:
if n % 10_000 == 0:
print(n)
n_str = str(n)
if "0" not in n_str: # do I do this or does the code handle it?
yield [int(d) for d in n_str]
n -= 1
def part_one(input_str):
test()
monad = parse_program(input_str)
# for model_number in submarine_model_numbers():
# env = execute(monad, model_number)
# if env["z"] == 0:
# return "".join(model_number)
n = [9] * 14
env = execute(monad, n)
print(env)
# transpile(monad, n)
return 0
part_one(puzzle_input_str)
# print("part one:", part_one(puzzle_input_str))
w,x,y,z = 0,0,0,0 program_input = [9,9,9,9,9,9,9,9,9,9,9,9,9,9] assert len(program_input) == 14 w = program_input.pop(0) z_div = 1 x_inc = 13 w_inc = 14 x = z x %= 26 z = z // 1 x += 13 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 5 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 1 x += 15 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 14 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 1 x += 15 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 15 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 1 x += 11 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 16 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -16 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 8 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -11 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 9 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -6 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 2 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 1 x += 11 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 13 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 1 x += 10 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 16 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -10 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 6 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -8 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 6 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -11 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 9 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 1 x += 12 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 11 y *= x z += y print(w,x,y,z) w = program_input.pop(0) x = z x %= 26 z //= 26 x += -15 x = 1 if x == w else 0 x = 1 if x == 0 else 0 z = z * ((25 * x) + 1) y = w + 5 y *= x z += y print(w,x,y,z)
def step(w, z, z_div, z_inc, w_inc):
# print(" ", w,z)
if (z % 26 + z_inc) != w:
z = (z // z_div) * 26
z += w + w_inc
else:
z = (z // z_div)
return z
params = (
( 1, 13, 5),
( 1, 15, 14),
( 1, 15, 15),
( 1, 11, 16),
(26, -16, 8),
(26, -11, 9),
(26, -6, 2),
( 1, 11, 13),
( 1, 10, 16),
(26, -10, 6),
(26, -8, 6),
(26, -11, 9),
( 1, 12, 11),
(26, -15, 5)
)
from heapq import heapify, heappush, heappop
# assume that z won't be greater than 1024
z_max = 1024
# prime the queue
queue = []
for w in range(1, 10):
for z in range(z_max):
z_out = step(w, z, *params[-1])
if z_out == 0:
heappush(queue, ([str(w)], z))
while candidate := heappop(queue):
number, target_z = candidate
i = 13 - len(number)
print(len(queue), len(number))
if i < 0:
print("".join(number))
break
for w in range(1, 10):
for z in range(z_max):
z_out = step(w, z, *params[i])
if z_out == target_z:
heappush(queue, ([str(w)] + number, z))
# w,x,y,z = 0,0,0,0
# program_input = [9,9,9,9,9,9,9,9,9,9,9,9,9,9]
# z = step(program_input.pop(0), z, 1, 13, 5)
# z = step(program_input.pop(0), z, 1, 15, 14)
# z = step(program_input.pop(0), z, 1, 15, 15)
# z = step(program_input.pop(0), z, 1, 11, 16)
# z = step(program_input.pop(0), z, 26, -16, 8)
# z = step(program_input.pop(0), z, 26, -11, 9)
# z = step(program_input.pop(0), z, 26, -6, 2)
# z = step(program_input.pop(0), z, 1, 11, 13)
# z = step(program_input.pop(0), z, 1, 10, 16)
# z = step(program_input.pop(0), z, 26, -10, 6)
# z = step(program_input.pop(0), z, 26, -8, 6)
# z = step(program_input.pop(0), z, 26, -11, 9)
# z = step(program_input.pop(0), z, 1, 12, 11)
# z = step(program_input.pop(0), z, 26, -15, 5)
# print(z)
def step(w, z, z_div, z_inc, w_inc):
if (z % 26 + z_inc) != w:
z = (z // z_div) * 26
z += w + w_inc
else:
z = (z // z_div)
return z
params = (
( 1, 13, 5),
( 1, 15, 14),
( 1, 15, 15),
( 1, 11, 16),
(26, -16, 8),
(26, -11, 9),
(26, -6, 2),
( 1, 11, 13),
( 1, 10, 16),
(26, -10, 6),
(26, -8, 6),
(26, -11, 9),
( 1, 12, 11),
(26, -15, 5)
)
def tick(w, z, z_div, x_inc, w_inc):
x = z % 26 + x_inc
z = z // z_div
# print(x, w)
x = 1 if x == w else 0
x = 1 if x == 0 else 0
z = z * ((25 * x) + 1)
y = w + w_inc
y *= x
z += y
# print(" ", w,x,y,z)
return w,x,y,z
from math import inf
params = (
( 1, 13, 5),
( 1, 15, 14),
( 1, 15, 15),
( 1, 11, 16),
(26, -16, 8),
(26, -11, 9),
(26, -6, 2),
( 1, 11, 13),
( 1, 10, 16),
(26, -10, 6),
(26, -8, 6),
(26, -11, 9),
( 1, 12, 11),
(26, -15, 5)
)
number = []
target_z = 0
for i in range(13, -1, -1):
z_div, x_inc, w_inc = params[i]
for w in range(9, 0, -1):
for z in range(0, 2**24):
w_, x_, y_, z_ = tick(w, z, z_div, x_inc, w_inc)
if z_ == target_z:
print("found a number")
number.insert(0, str(w))
target_z = z
break
else:
raise Exception("we didn't find a workable (w,z) pair")
print("the number is...")
print("".join(reversed(number)))
print("")
177_058_402 4_294_967_296 print(2**24)