[ 2024 Day 17 Part 2 ] Genetic Algorithm

#!/usr/bin/env python

import re
import random

data = """Register A: 32916674
Register B: 0
Register C: 0

Program: 2,4,1,1,7,5,0,3,1,4,4,0,5,5,3,0"""

#data = """Register A: 2024
#Register B: 0
#Register C: 0
#
#Program: 0,3,5,4,3,0"""

init, prog = data.split("\n\n")

A, B, C = 0, 0, 0

lines = init.split("\n")
m = re.match(r"Register A: (\d+)", lines[0].rstrip())
A = int(m.group(1))
m = re.match(r"Register B: (\d+)", lines[1].rstrip())
B = int(m.group(1))
m = re.match(r"Register C: (\d+)", lines[2].rstrip())
C = int(m.group(1))

prog = prog.split(" ")[1]
prog_str = prog
prog = prog.split(",")
prog = [ int(x) for x in prog ]

ninst = len(prog)

print(f"prog has {ninst} instructions")

def disasm(prog):
    pc = 0
    ninst = len(prog)
    first = True

    print(prog)

    f = open("dis.asm", "w")

    for pc in range(0, ninst, 2):
        inst = prog[pc]
        oper = prog[pc+1]

        if inst == 0:
            print(f"ADV {oper}", file=f)
        elif inst == 1:
            print(f"BXL {oper}", file=f)
        elif inst == 2:
            print(f"BST {oper}", file=f)
        elif inst == 3:
            print(f"JNZ {oper}", file=f)
        elif inst  == 4:
            print("BXC ---", file=f)
        elif inst == 5:
            print(f"OUT {oper}", file=f)
        elif inst == 6:
            print(f"BDIV {oper}", file=f)
        elif inst == 7:
            print(f"CDIV {oper}", file=f)
        else:
            print(f"odd, we shouldn't have instruction {inst}")
            print(f"PC={pc}")
            raise IndexError
    f.close()


def combo(A, B, C, oper):
    if oper == 0:
        return oper
    elif oper == 1:
        return oper
    elif oper == 2:
        return oper
    elif oper == 3:
        return oper
    elif oper == 4:
        return A
    elif oper == 5:
        return B
    elif oper == 6:
        return C
    elif oper == 7:
        print("7 isn't a valid operand for a combo instruction")
        raise IndexError
    else:
        print(f"{oper} isn't a valid operand.")
        raise IndexError

f = open("trace.txt", "w")

def lprint(x):
    print(x, file=f)

def runprog(A, B, C, prog):
    pc = 0
    ninst = len(prog)
    first = True

    output = ""


    while pc < ninst:
        inst = prog[pc]
        oper = prog[pc+1]
        pc += 2

        lprint(f"PC: {pc} running inst {inst}")
        if inst == 0:
            # adv instruction
            den = pow(2, combo(A, B, C, oper))
            lprint(f"ADV {den}")
            A = int(A / den)
        elif inst == 1:
            # bxl instruction
            B = B ^ oper
            lprint(f"BXL {oper}")
        elif inst == 2:
            # bst instructions
            val = combo(A, B, C, oper) & 7
            lprint(f"BXL {val}")
            B = val
        elif inst == 3:
            # jnz instruction
            if A != 0:
                lprint(f"JNZ {A}")
                pc = oper
        elif inst  == 4:
            lprint("BXC")
            B = B ^ C
        elif inst == 5:
            # out instruction
            # lprint(f"OUT {combo(oper)%8}")
            if not first:
                output += ","
            first = False
            output += str(combo(A, B, C, oper)%8)
        elif inst == 6:
            # bdiv instruction
            den = pow(2, combo(A, B, C, oper))
            lprint(f"BDIV {den}")
            B = int(A / den)
        elif inst == 7:
            # cdiv instruction
            den = pow(2, combo(A, B, C, oper))
            lprint(f"CDIV {den}")
            C = int(A / den)
        else:
            print(f"odd, we shouldn't have instruction {inst}")
            print(f"PC={pc}")
            raise IndexError
    return output

disasm(prog)

def ioc(s0, s1):
    if len(s0) != len(s1):
        raise IndexError
    cnt = 0
    for a, b in zip(s0, s1):
        if a == "," or b == ",":
            continue
        if a == b:
            cnt += 1
    return cnt

from termcolor import colored

def cprint(matches, x):
    global prog_str
    print(f"{matches}: ", end="")
    for c0, c1 in zip(x, prog_str):
        if c0 == ',':
            print(",", end="")
        elif c0 == c1:
            print(colored(c0, "green"), end="")
        else:
            print(c0, end="")
    print()

lo = 2**45
hi = 2**48-1

poolsize = 10000
pool = []

def computescore(out):
    global prog_str
    if len(prog_str) != len(out):
        return 100
    else:
        return 16-ioc(prog_str, out)

for _ in range(poolsize):
    A = random.randint(lo, hi)
    B = 0
    C = 0
    out = runprog(A, B, C, prog)
    score = computescore(out)
    pool.append([score, A, out])

pool.sort()

gen = 0

def mutate(a):
    return a ^ (1 << random.randint(0, 47))

def crossover(a, b):
    ba = bin(a)
    bb = bin(b)
    if len(ba) != len(bb):
        return a
    else:
        s = random.randint(0, len(ba)-1)
        r = ba[:s] + bb[s:]
        if len(r) != len(ba):
            raise IndexError
        return int(r, 2)



while True:

    gen += 1
    print(f"Generation {gen}")

    acheck = set()
    for s, a, o in pool:
        acheck.add(a)

    for i in range(poolsize//2, poolsize):
        if random.random() < 0.02:
            s, a, o = pool[i]
            a = mutate(a)
            while a in acheck:
                a = mutate(a)
            acheck.add(a)
            o = runprog(a, 0, 0, prog)
            s = computescore(o)
            pool[i] = [s, a, o]
        else:
            # crossover
            p0 = random.randint(0, poolsize//2-1)
            p1 = random.randint(0, poolsize//2-1)
            a = crossover(pool[p0][1], pool[p1][1])
            while a in acheck:
                p0 = random.randint(0, poolsize//2-1)
                p1 = random.randint(0, poolsize//2-1)
                a = crossover(pool[p0][1], pool[p1][1])
            acheck.add(a)
            o = runprog(a, 0, 0, prog)
            s = computescore(o)
            pool[i] = [s, a, o]
    pool.sort()
    for i in range(5):
        print(i, pool[i])