187 lines
4.2 KiB
Python
187 lines
4.2 KiB
Python
import re
|
|
|
|
store = {}
|
|
ops = []
|
|
|
|
with open("day24") as f:
|
|
l = next(f)
|
|
while l.strip():
|
|
match = re.match(r'([xy][0-9]+): ([01])', l)
|
|
store[match.groups()[0]] = bool(int(match.groups()[1]))
|
|
l = next(f)
|
|
|
|
l = next(f)
|
|
while l.strip():
|
|
match = re.match(r'([a-z0-9]+) (AND|OR|XOR) ([a-z0-9]+) -> ([a-z0-9]+)', l)
|
|
ops.append((match.groups()[1], match.groups()[0], match.groups()[2], match.groups()[3]))
|
|
l = next(f, "")
|
|
|
|
def calc(op, a,b):
|
|
match op:
|
|
case "AND":
|
|
return (a and b)
|
|
case "OR":
|
|
return (a or b)
|
|
case "XOR":
|
|
return (a ^ b)
|
|
|
|
from copy import copy
|
|
def run(ops, store):
|
|
store = copy(store)
|
|
done = False
|
|
while not done:
|
|
done = True
|
|
for op in ops:
|
|
if op[3] not in store: done = False
|
|
|
|
if op[1] in store and op[2] in store:
|
|
store[op[3]] = calc(op[0], store[op[1]], store[op[2]])
|
|
return store
|
|
|
|
def bin_to_int(prefix: str, store):
|
|
from collections import deque
|
|
num = deque()
|
|
sorted_store = sorted(store.items())
|
|
for item in sorted_store:
|
|
if item[0].startswith(prefix):
|
|
num.appendleft(str(int(item[1])))
|
|
return int(''.join(num), 2)
|
|
|
|
s = run(ops, store)
|
|
print(bin_to_int("z", s))
|
|
|
|
# This should calculate x+y with logic gates, so effectively we're
|
|
# looking at some kind of binary adder
|
|
#
|
|
# more specifically looking at the first few gates, this seems to
|
|
# match a standard full adder:
|
|
# https://en.wikipedia.org/wiki/Adder_(electronics)#/media/File:Full-adder_logic_diagram.svg
|
|
#
|
|
# y00 XOR x00 -> z00
|
|
# y00 AND x00 -> hfm
|
|
#
|
|
# y01 XOR x01 -> hqt
|
|
# hfm XOR hqt -> z01
|
|
#
|
|
# hqt AND hfm -> hkm
|
|
#
|
|
# x01 AND y01 -> qng
|
|
#
|
|
# qng OR hkm -> dmw
|
|
#
|
|
# y02 XOR x02 -> bfr
|
|
# dmw XOR bfr -> z02
|
|
# bfr AND dmw -> fvk
|
|
#
|
|
# ...
|
|
#
|
|
# Let's hope there's no mean traps otherwise I'm screwed
|
|
|
|
def find_op(op, a, b, ops):
|
|
for it in ops:
|
|
if it[0:3] == (op, a, b):
|
|
return _(it)
|
|
|
|
if it[0:3] == (op, b, a):
|
|
return _(it)
|
|
|
|
def find_partial(op, a, b, ops):
|
|
for it in ops:
|
|
if it[0] == op and it[1] in [a,b]:
|
|
return _(it)
|
|
|
|
if it[0] == op and it[2] in [a,b]:
|
|
return _(it)
|
|
|
|
x = 1
|
|
y = 1
|
|
z = 1
|
|
|
|
carry = "hfm"
|
|
carry_op = ("AND", "y00", "x00")
|
|
|
|
failed = []
|
|
consumed = []
|
|
|
|
trans = [("z07", "nqk"), ("pcp", "fgt"), ("fpq", "z24"), ("z32", "srn")]
|
|
def _(s):
|
|
global trans
|
|
if type(s) is tuple:
|
|
return *s[0:3], _(s[3])
|
|
|
|
ts = None
|
|
for t in trans:
|
|
if s in t:
|
|
ts = t
|
|
break
|
|
|
|
if ts:
|
|
return ts[0] if ts[1] == s else ts[1]
|
|
|
|
return s
|
|
|
|
|
|
|
|
|
|
while x < 45:
|
|
x1 = find_op("XOR", f"x{x:02d}", f"y{y:02d}", ops)
|
|
if x1:
|
|
consumed.append(x1)
|
|
else:
|
|
op = ("XOR", f"x{x:02d}", f"y{y:02d}")
|
|
print(f"Could not find expected x1 {op}")
|
|
failed.append(op)
|
|
|
|
a2 = find_op("AND", f"x{x:02d}", f"y{y:02d}", ops)
|
|
if a2:
|
|
consumed.append(a2)
|
|
else:
|
|
op = ("AND", f"x{x:02d}", f"y{y:02d}")
|
|
print(f"Could not find expected a2 {op}")
|
|
failed.append(op)
|
|
|
|
x2 = find_op("XOR", f"{x1[3]}", f"{carry}", ops)
|
|
if x2 and x2[3] == f"z{x:02d}":
|
|
consumed.append(x2)
|
|
else:
|
|
op = ("XOR", f"{x1[3]}", f"{carry}", f"z{x:02d}")
|
|
print(f"Could not find expected x2 {op}")
|
|
failed.append(op)
|
|
|
|
x2 = find_partial("XOR", f"{x1[3]}", f"{carry}", ops)
|
|
if x2: print(f"Found partial x2 {x2}")
|
|
|
|
|
|
a1 = find_op("AND", f"{x1[3]}", f"{carry}", ops)
|
|
if a1:
|
|
consumed.append(a2)
|
|
else:
|
|
op = ("AND", f"{x1[3]}", f"{carry}")
|
|
print(f"Could not find expected a1 {op}")
|
|
failed.append(op)
|
|
|
|
a1 = find_partial("AND", f"{x1[3]}", f"{carry}", ops)
|
|
if a2: print(f"Found partial a1 {a1}")
|
|
|
|
|
|
o1 = find_op("OR", f"{a1[3]}", f"{a2[3]}", ops)
|
|
if o1:
|
|
consumed.append(o1)
|
|
else:
|
|
op = ("OR", f"{a1[3]}", f"{a2[3]}")
|
|
print(f"Could not find expected o1 {op}")
|
|
failed.append(op)
|
|
|
|
o1 = find_partial("OR", f"{a1[3]}", f"{a2[3]}", ops)
|
|
if a2: print(f"Found partial o1 {o1}")
|
|
|
|
|
|
x += 1
|
|
y += 1
|
|
carry = o1[3]
|
|
carry_op = o1
|
|
|
|
coll = []
|
|
for t in trans:
|
|
coll.extend(t)
|
|
print(','.join(sorted(coll)))
|