Advent of Code Day 23

I had a remarkable amount of trouble with this one: to the point that I ended up downloading a different solution to sanity check that my input wasn't broken. It took three attempts to realize that I'd only get the expected output if I

  • walked over all computers in order
  • completely exhausted each computer's input/output to get an ordering that would get the right answer.

The correct answer for part 2 is the function attempt3.

It didn't help that I fell asleep before this problem so I missed any chances for a leaderboard for part .

In [14]:
def readfile(path):
    with open(path) as input_file: 
        return input_file.read().rstrip('\n')

def params(program, i, count):
    modes = str(program[i] // 100)[::-1]
    result = []
    
    for x in range(count - 1):
        arg = program[i + 1 + x]
        if x >= len(modes) or modes[x] == "0":
            result.append(program[arg])
        elif modes[x] == "2":
            result.append(program[program.offset + arg])
        else:
            result.append(arg)
            
    output = program[i + count]
    if len(modes) >= count and modes[count - 1] == "2":
        output += program.offset
        
    result.append(output) # output
    return result

def add(program, i, **kwargs):
    assert program[i] % 100 == 1
    a, b, out = params(program, i, 3)
    program[out] = a + b
    return i + 4, None
    
def mul(program, i, **kwargs):
    assert program[i] % 100 == 2
    a, b, out = params(program, i, 3)
    program[out] = a * b
    return i + 4, None

def inp(program, i, input_value, **kwargs):
    assert program[i] % 100 == 3
    out, = params(program, i, 1)
    program[out] = input_value
   #  print(f"> {program[i]} program[{out}] = {program[out]}")
    return i + 2, None

def out(program, i, **kwargs):
    assert program[i] % 100 == 4
    val, _ = params(program, i, 2)
   #  print(f"> {val}")
    return i + 2, val
    
def jit(program, i, **kwargs):
    assert program[i] % 100 == 5
    test, ip, _ = params(program, i, 3)
    if test != 0:
        return ip, None
    return i + 3, None

def jif(program, i, **kwargs):
    assert program[i] % 100 == 6
    test, ip, _ = params(program, i, 3)
    if test == 0:
        return ip, None
    return i + 3, None

def lt(program, i, **kwargs):
    assert program[i] % 100 == 7
    a, b, out = params(program, i, 3)
    program[out] = int(a < b)
    return i + 4, None

def eq(program, i, **kwargs):
    assert program[i] % 100 == 8
    a, b, out = params(program, i, 3)
    program[out] = int(a == b)
    return i + 4, None

def rbo(program, i, **kwargs):
    assert program[i] % 100 == 9
    delta, _ = params(program, i, 2)
    program.offset += delta
    # print (f"> rbo = {program.offset}" )
    return i + 2, None

operations = { 1: add, 2: mul, 3: inp, 4: out, 5: jit, 6: jif, 7: lt, 8: eq, 9: rbo }

class Program(list):
    def __init__(self, *args, **kwargs):
        super(Program, self).__init__(args[0])
        self.offset = 0

def compute(program, debug=False):
    program = Program(program)
    
    l = len(program)
    i = 0
    output_value = None
    last_output = None
    
    while i < l:
        op = program[i]
        if op == 99:
            if debug: 
                print(f">> exit {output_value}")
            return 
        
        if debug:
            print(f">> {i}, {list(enumerate(program))[i:i+5]}")
            
        if op % 100 == 3:
            input_value = yield
        else:
            input_value = None
            
        i, output_value = operations[op % 100](program, i, input_value=input_value)
        
        if output_value is not None:
            yield output_value
        
    raise Exception("Didn't terminate properly")
    
def process(listing):
    lst = list(map(int, listing.split(",")))
    lst.extend([0] * 100000)
    return lst
In [5]:
input23 = readfile("AoC/input23.txt")
In [11]:
from collections import defaultdict, deque

def problem(debug=False, soln=1):
    computers = []
    for i in range(0, 50):
        computer = compute(process(input23))
        computers.append(computer)

        # Boot up
        assert next(computer) == None
        assert computer.send(i) == None

    insts = defaultdict(deque)

    nat = None

    empty = None
    last_nat = None

    nat_counter = 100

    next_is = deque()
    count_i = None
    idle = False

    while True and nat_counter >= 0:
        if idle:
            nat_counter -= 1

            if debug or True:
                print(f"## nat -> 0: {nat}")
            assert nat is not None

            if nat[1] == last_nat:
                return nat[1]
            last_nat = nat[1]

            insts[0].append(nat[0])
            insts[0].append(nat[1])
            next_is.append(0)

        count_i = 0
        idled = 0
        idle = False
        while True:
            # print(insts)

            i = count_i
            count_i = (count_i + 1) % 50

            if i == 0 and idled == 50:
                idle = True
                break
            elif i == 0:
                idled = 0

            has_input = bool(insts[i])
            outs = []

            if has_input:
                x_in = insts[i].popleft()
                y_in = insts[i].popleft()
                if debug:
                    print(f"{i} <- {x_in}, {y_in}")

                outs.append(computers[i].send(x_in))
                outs.append(computers[i].send(y_in))
            else:
                outs.append(computers[i].send(-1))

            outs = list(filter(None, outs))
            addr = outs.pop(0) if outs else None

            if addr == None:
                if not has_input:
                    idled += 1
                continue

            while len(outs) < 2:
                inp = next(computers[i])
                assert inp is not None
                outs.append(inp)

            x = outs.pop(0)
            y = outs.pop(0)

            if debug:
                print(f"{i} -> {addr}, {x}, {y}")

            if addr == 255:
                if debug:
                    print(f"nat <- {x, y}")
                if soln == 1:
                    return (x, y)
                else:
                    nat = (x, y)
            else:
                next_is.append(addr)
                insts[addr].append(x)
                insts[addr].append(y)

problem(False, 2)

# 0 -> 8, 137926, 16250
## nat -> 0: (47857, 16250)
## nat -> 0: (47857, 13817)
## nat -> 0: (47857, 10435)
## nat -> 0: (47857, 5734)
## nat -> 0: (47857, -1)
## nat -> 0: (47857, -1)
Out[11]:
-1
In [16]:
def attempt2(input23):
    computers = [compute(process(input23)) for _ in range(50)]

    for i in range(50):
        computers[i].send(None)
        assert computers[i].send(i) == None

    i = -1
    instructions = defaultdict(deque)
    idled = 0
    nat = None

    idle_counter = 0

    while True:
        i = (i + 1) % 50

        if i == 0:
            if idled == 50:
                print(nat)

                idle_counter += 1
                if idle_counter > 50:
                    return nat

                instructions[0].append(nat[0])
                instructions[0].append(nat[1])
            idled = 0
            
        outputs = []
        has_instructions = bool(instructions[i])
        if has_instructions:
            outputs.append(computers[i].send(instructions[i].popleft()))
            outputs.append(computers[i].send(instructions[i].popleft()))
        else:
            outputs.append(computers[i].send(-1))

        outputs = list(filter(lambda x: x is not None, outputs))

        if not outputs:
            if not has_instructions:
                idled += 1
            continue

        while len(outputs) < 3:
            output = computers[i].send(None)
            assert output is not None, "Unexpected none"
            outputs.append(output)

        assert (outputs[0] >= 0 and outputs[0] <= 50) or outputs[0] == 255
        if outputs[0] == 255:
            nat = (outputs[1], outputs[2])
        else:
            instructions[outputs[0]].append(outputs[1])
            instructions[outputs[0]].append(outputs[2])

attempt2(input23)
(47857, 16250)
(47857, 13817)
(47857, 10435)
(47857, 5734)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
(47857, -1)
Out[16]:
(47857, -1)
In [29]:
def attempt3(input23):
    computers = [compute(process(input23)) for _ in range(50)]

    for i in range(50):
        computers[i].send(None)
        assert computers[i].send(i) == None

    i = -1
    instructions = defaultdict(deque)
    idled = 0
    nat = None
    last_nat = None

    idle_counter = 0

    while True:
        i = (i + 1) % 50

        if i == 0:
            if idled == 50:
                print(nat)
                idle_counter += 1
                if idle_counter > 50:
                    return nat

                if last_nat == nat[1]:
                    return last_nat
                last_nat = nat[1]

                instructions[0].append(nat[0])
                instructions[0].append(nat[1])
            idled = 0
            

        had_instructions = bool(instructions[i])

        total_outputs = []
        while True:
            outputs = []
            if instructions[i]:
                outputs.append(computers[i].send(instructions[i].popleft()))
                outputs.append(computers[i].send(instructions[i].popleft()))
            else:
                outputs.append(computers[i].send(-1))

            while outputs[-1]:
                outputs.append(computers[i].send(-1))

            outputs = list(filter(lambda x: x is not None, outputs))
            if not outputs:
                break

            total_outputs.extend(outputs)

        if not total_outputs:
            if not had_instructions:
                idled += 1
            continue

        for j in range(0, len(total_outputs), 3):
            assert (total_outputs[j] >= 0 and total_outputs[j] <= 49) or total_outputs[j] == 255
            if total_outputs[j] == 255:
                nat = (total_outputs[j + 1], total_outputs[j + 2])
            else:
                instructions[total_outputs[j]].append(total_outputs[j + 1])
                instructions[total_outputs[j]].append(total_outputs[j + 2])

attempt3(input23)
(47857, 16250)
(47857, 14829)
(47857, 13748)
(47857, 12957)
(47857, 12390)
(47857, 11989)
(47857, 11706)
(47857, 11508)
(47857, 11369)
(47857, 11272)
(47857, 11204)
(47857, 11156)
(47857, 11123)
(47857, 11099)
(47857, 11083)
(47857, 11071)
(47857, 11063)
(47857, 11057)
(47857, 11053)
(47857, 11050)
(47857, 11048)
(47857, 11047)
(47857, 11046)
(47857, 11046)
Out[29]:
11046