Om vi tittar pÄ koden sÄ bestÄr den av 14 snarlika sektioner
inp w
mul x 0
add x z
mod x 26
div z A
add x B
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y C
mul y x
add z y
Om vi översÀtter detta till exempelvis Python skulle det kunna se ut sÄ hÀr
inp w
x = x * 0
x = x + z
x = x % 26
z = z / A
x = x + B
x = (x == w)
x = (x == 0)
y = y * 0
y = y + 25
y = y * x
y = y + 1
z = z * y
y = y * 0
y = y + w
y = y + C
y = y * x
z = x + y
Efter lite uttrycksförenklingar blir det
inp w
x = (z % 26 + B != w)
z = z / A
z = z * (25 * x + 1)
z = z + (w + C) * x
x kommer bara kunna ha vÀrdet 1 eller 0 sÄ lÄt oss konstantpropagera de vÀrdena.
inp w
if z % 26 + B != w:
x = 1
z = z / A
z = z * (25 * x + 1)
z = z + (w + C) * x
else:
x = 0
z = z / A
z = z * (25 * x + 1)
z = z + (w + C) * x
förenkla igen
inp w
if z % 26 + B != w:
z = (z / A) * 26 + w + C
else:
z = z / A
VÀrdena för A Àr antingen 1 eller 26, sju av varje, och pÄ den hÀr formen Àr det ganska klart att de enda fallen dÀr vi kommer fÄ tillbaka en nolla i z Àr dÄ vi lyckas lyckas utföra divisionen med 26 utan att lÀgga till nÄgra nya vÀrden till z. Med andra ord, om nÄgra av testerna i eql x w Àr sanna Àr det bara de vÀrdena vi behöver fortsÀtta att kontrollera. Inga av de andra vÀrden kommer att kunna fÄ ner z till 0 igen.
HÀr kommer pmonad, den virtuella maskinen som kör alla inputs parallellt. Koden Àr ganska rÀttfram. Det enda knepiga Àr shrink som reducerar storleken pÄ det state som skickas runt. Körtid pÄ min Skylake Àr runt 30 minuter och minnesÄtgÄngen Àr mÄttlig.
from collections import defaultdict
from itertools import product
import re
import numpy as np
program = [re.match("(\w\w\w) (\w) ?(\w|\-?\d+)?$", l.strip())
for l in open("input24").readlines()]
anydigit = 0x3fe
norestrictions = np.array([anydigit] * 14)
def shrink(l):
"""Merge list members if they are identical in all but one restriction"""
def is_mergeable_range(a, i):
"""Since a is sorted it is enough to look at nine sequential elements
to see if they are mergeable range. Comparing row i to the next eight
row produces a boolean matrix. "and" it columnwise to see if all the
rows compared identically to row i. If that was true for 13 columns
we can merge the nine restrictions into one.
"""
return (i + 8 < a.shape[0] and
np.logical_and.reduce(a[i + 1:i + 9] == a[i]).sum() == 13)
# Collect restrictions per value
d = defaultdict(list)
for v, r in l:
d[v].append(r)
for v, l in d.items():
last = []
while len(l) != len(last):
last = l
a = np.array(l, dtype = np.short)
include_in_sort = tuple(a[:,i]
for i in range(14)
if (a[:,i] != anydigit).any())
# If merged back to [anydigit, anydigit, ..., anydigit] we're done
if include_in_sort:
a = a[np.lexsort(include_in_sort)]
l = []
i = 0
while i < a.shape[0]:
if is_mergeable_range(a, i):
l.append(np.bitwise_or.reduce(a[i:i + 9]))
i += 9
else:
l.append(a[i])
i += 1
d[v] = l
# Go back to the (one value, one restriction) form
return [(v, r) for v, restrictions in d.items() for r in restrictions]
def input_digit(condition, i):
"""The value i and the matching restriction"""
a = norestrictions.copy()
a[condition] = 1 << i
return a
def inp(a, b, state):
"""Set a to [1,2, ..., 9] with matching restrictions"""
digit = state['digit']
state['digit'] += 1
state[a] = [(i, input_digit(digit, i)) for i in range(1, 10)]
return state
def addi(a, b, state):
state[a] = [(v + b, r) for v, r in state[a]]
return state
def add(a, b, state):
"""Add all values in a to all values in b if the restrictions allow it.
Special case for adding something to zero.
"""
s = state[a]
if s[0] == 0 and (s[1] == norestrictions).all(): # copy operation?
state[a] = state[b]
else:
state[a] = [(t1 + t2, r)
for (t1, r1), (t2, r2) in product(s, state[b])
if (r := r1 & r2).all()]
return state
def muli(a, b, state):
"""Multiply all values in a with b, unless b is 0, then it is just 0"""
if b != 0:
state[a] = [(v * b, r) for v, r in state[a]]
else:
state[a] = [(0, norestrictions)]
return state
def mul(a, b, state):
"""Multiply all values in a with all values in b if the restrictions
allow it. Special case for multiplying something with one.
"""
s = state[a]
if s[0] == 1 and (s[1] == norestrictions).all(): # copy operation?
state[a] = state[b]
else:
state[a] = [(t1 * t2, r)
for (t1, r1), (t2, r2) in product(s, state[b])
if (r := r1 & r2).all()]
return state
def divi(a, b, state):
b = int(b)
state[a] = shrink([(v // b, x) for v, x in state[a]])
return state
def modi(a, b, state):
b = int(b)
state[a] = shrink([(v % b, x) for v, x in state[a]])
return state
def eqli(a, b, state):
state[a] = [(int(v == b), x) for v, x in state[a]]
return state
def eql(a, b, state):
"""Test all values in a for equality with all values in b and enforce
restrictions.
To reduce the amount of data we only keep the numbers that can lead to a
successful result and we know the "eql x w" instruction must be true for
the numbers that will be accepted by MONAD.
So if any test was successful, keep only the "true" values and discard
the "false" values.
"""
l = [[],[]]
for (t1, r1), (t2, r2) in product(state[a], state[b]):
e = int(t1 == t2)
l[e].append((e, r1 & r2))
state[a] = l[1] or shrink(l[0])
return state
def pmonad():
def is_immediate(b):
return b and b[0] in "-0123456789"
start = [(0, norestrictions)]
state = { 'digit' : 0, 'x' : start, 'y' : start, 'z' : start, 'w' : start }
for m in program:
instr, a, b = m[1], m[2], m[3]
if is_immediate(b):
instr += "i"
b = int(b)
# No need for a switch, just evaluate instr to get the function
state = eval(instr)(a, b, state)
return state['z']
z0 = pmonad()
decode = { 1 << i : str(i) for i in range(10) }
l = [int("".join(decode[digit] for digit in zero[1])) for zero in z0]
print(max(l), min(l))
