Sean McLemon | Advent of Code

Home | Czech | Blog | GitHub | Advent Of Code | Notes


2019-12-21 - Springdroid Adventure

(original .ipynb)

Day 21 puzzle input is an IntCode program (mine is here) which represents a networked computer as part of a bigger network. Part 1 involves connecting a number of these network computers and finding the first

opcode_add = 1
opcode_mul = 2
opcode_read = 3
opcode_write = 4
opcode_jump_true = 5
opcode_jump_false = 6
opcode_lt = 7
opcode_eq = 8
opcode_rebase = 9

opcode_terminate = 99

mode_position = 0
mode_immediate = 1
mode_relative = 2

class IntCodeCpu:
    def __init__(self, memory_image):
        self.memory = [ x for x in memory_image ] # copy memory image, in case it's reused
        self.stalled = True
        self.input_buffer = None
        self.output_buffer = None
        self.pc = 0
        self.initialise_opcodes()
        self.offset = 0
        self.done = False
        
    def start(self, input_buffer, output_buffer, noun=None, verb=None):
        self.input_buffer = input_buffer
        self.output_buffer = output_buffer

        if noun:
            self.memory[1] = noun
        if verb:
            self.memory[2] = verb
           
        return self.run()
            
            
    def run(self):
        instr = self.memory[self.pc]
        self.stalled = False

        while int(instr) != opcode_terminate and not self.stalled:
            (op, modes) = self.decode_instr(instr)
            self.pc = op(modes)
            instr = self.memory[self.pc]

        return self.memory[0]

    #-HELPERS-----------------------------
    def try_pop_mode(self, modes):
        if len(modes) == 0:
            return 0
    
        return modes.pop()
    
    def resize_memory(self, target_addr):
        self.memory += ([0] * (1 + target_addr - len(self.memory)))
    
    #-DECODE-INSTRUCTIONS-----------------
    def initialise_opcodes(self):
        self.opcodes = {
            opcode_add: self.op_add,
            opcode_mul: self.op_mul,
            opcode_read: self.op_read,
            opcode_write: self.op_write,
            opcode_jump_true: self.op_jump_true,
            opcode_jump_false: self.op_jump_false,
            opcode_lt: self.op_lt,
            opcode_eq: self.op_eq,
            opcode_rebase: self.op_rebase
        }    
    
    def decode_instr(self, instr):
        instr = str(instr)
        opcode = self.decode_op(instr)
        modes = self.decode_modes(instr)

        if not (opcode in self.opcodes):
            raise Exception(f"Invalid opcode {opcode}")

        return (self.opcodes[opcode], modes)    
    
    def decode_op(self, instr):
        if len(instr) > 2:
            return int(instr[-2:])
        return int(instr)
    
    def decode_modes(self, instr):
        if len(instr) > 2:
            return [ int(d) for d in instr[:-2]]
        return []
    
    #-MICRO-OPS---------------------------
    def uop_read(self, value, mode):
        if mode == mode_position:
            if value >= len(self.memory):
                self.resize_memory(value)        

            return int(self.memory[value])

        elif mode == mode_relative:
            if self.offset + value >= len(self.memory):
                self.resize_memory(self.offset + value)     

            return int(self.memory[self.offset + value])

        elif mode == mode_immediate:
            return int(value)

        else:
            raise Exception("UNKNOWN MODE")

    def uop_write(self, dst, value, mode):
        if mode == mode_position:
            if dst >= len(self.memory):
                self.resize_memory(dst)
            self.memory[dst] = value

        elif mode == mode_relative:
            if self.offset + dst >= len(self.memory):
                self.resize_memory(self.offset + dst)     

            self.memory[self.offset + dst] = value

        elif mode == mode_immediate:
            raise Exception(f"cannot write {value} to literal {dst}")


    def uop_cond_jump(self, modes, cond):
        param_mode = self.try_pop_mode(modes)
        param_raw = int(self.memory[self.pc + 1])
        param = self.uop_read(param_raw, param_mode)

        dest_mode = self.try_pop_mode(modes)
        dest_raw = int(self.memory[self.pc + 2])
        dest = self.uop_read(dest_raw, dest_mode)

        if cond(param):
            return dest

        return self.pc + 3

    def uop_cmp(self, modes, cmp):

        param0_mode = self.try_pop_mode(modes)
        param0_raw = int(self.memory[self.pc + 1])
        param0 = self.uop_read(param0_raw, param0_mode)

        param1_mode = self.try_pop_mode(modes)
        param1_raw = int(self.memory[self.pc + 2])
        param1 = self.uop_read(param1_raw, param1_mode)

        dest_mode = self.try_pop_mode(modes)
        dest = int(self.memory[self.pc + 3])

        if cmp(param0, param1):
            self.uop_write(dest, 1, dest_mode)
        else:
            self.uop_write(dest, 0, dest_mode)

        return self.pc + 4
        
    
    #-OPCODES-----------------------------
    def op_add(self, modes):
        arg0_mode = self.try_pop_mode(modes)
        arg1_mode = self.try_pop_mode(modes)
        dest_mode = self.try_pop_mode(modes)

        arg0_raw = int(self.memory[self.pc + 1])
        arg1_raw = int(self.memory[self.pc + 2])
        dest = int(self.memory[self.pc + 3])

        arg0 = self.uop_read(arg0_raw, arg0_mode)
        arg1 = self.uop_read(arg1_raw, arg1_mode)

        self.uop_write(dest, str(int(arg0) + int(arg1)), dest_mode)
        return self.pc + 4

    def op_mul(self, modes):
        arg0_mode = self.try_pop_mode(modes)
        arg1_mode = self.try_pop_mode(modes)
        dest_mode = self.try_pop_mode(modes)

        arg0_raw = int(self.memory[self.pc + 1])
        arg1_raw = int(self.memory[self.pc + 2])
        dest = int(self.memory[self.pc + 3])

        arg0 = self.uop_read(arg0_raw, arg0_mode)
        arg1 = self.uop_read(arg1_raw, arg1_mode)

        self.uop_write(dest, str(int(arg0) * int(arg1)), dest_mode)    
        return self.pc + 4


    def op_read(self, modes):
        dest_mode = self.try_pop_mode(modes)
        dest = int(self.memory[self.pc + 1])
        
        # if the input buffer is empty, we should "stall" and 
        # resume later
        if not self.input_buffer:
            self.stalled = True
            return self.pc
        
        val = self.input_buffer.pop()

        self.uop_write(dest, str(val), dest_mode)

        return self.pc + 2

    def op_write(self, modes):
        src_mode = self.try_pop_mode(modes)
        src_raw = int(self.memory[self.pc + 1])
        src = self.uop_read(src_raw, src_mode)

        self.output_buffer.append(src)

        return self.pc + 2

    def op_jump_true(self, modes):
        return self.uop_cond_jump(modes, lambda x: x != 0)


    def op_jump_false(self, modes):
        return self.uop_cond_jump(modes, lambda x: x == 0)

    def op_lt(self, modes):
        return self.uop_cmp(modes, lambda x, y: x < y)

    def op_eq(self, modes):
        return self.uop_cmp(modes, lambda x, y: x == y)

    def op_rebase(self, modes):    
        param_mode = self.try_pop_mode(modes)
        param_raw = int(self.memory[self.pc + 1])
        param = self.uop_read(param_raw, param_mode)

        self.offset += param

        return self.pc + 2
raw_code = open("puzzle_input/day21.txt", "r").read()
code = raw_code.split(",")

def preprocess_ascii_input(instructions):
    int_instructions = [ ord(c) for c in instructions ]
    return int_instructions + [ ord("\n") ]

def skip_line(line):
    return len(line) == 0 or line[0] == "#"

def run_script(script):
    output_buffer = []
    cpu = IntCodeCpu(code)
    script_lines = [ preprocess_ascii_input(script_line) for script_line in script.split("\n") if not skip_line(script_line.strip()) ]
    
    from pprint import pprint
    output = []
    for i, script_line in enumerate(script_lines):
        print(i, script_line)
        cpu.start(script_line[::-1], output_buffer)
        
    maybe_return_value = output_buffer[-1]
    if (maybe_return_value >= 0 and maybe_return_value < 256):
        # the output is printable ascii meaning that we
        # have hit a snag - we should print the output 
        # to see the last dying moments of our dear
        # springbot
        output = "".join([ chr(c) for c in output_buffer ])
        print(output)
    else:
        print("retval = ", maybe_return_value)
# part 1
# reached via some very simple heuristics - if there is
# an gap upcoming just before jump target (D) we should jump:
#
#    @
#    #??.# 
#     ABCD
#
# and if there's a gap immediately in front of us, we should jump
#
#    @
#    #.???
#     ABCD
# 
# otherwise, we'll walk

script_part_1 = """
# if there's a gap *just* before jump target, jump
NOT C T
AND D T
OR T J

# if there's a gap right in front of us, jump
NOT A T
OR T J

# fingers crossed
WALK"""

run_script(script_part_1)
0 [78, 79, 84, 32, 67, 32, 84, 10]
1 [65, 78, 68, 32, 68, 32, 84, 10]
2 [79, 82, 32, 84, 32, 74, 10]
3 [78, 79, 84, 32, 65, 32, 84, 10]
4 [79, 82, 32, 84, 32, 74, 10]
5 [87, 65, 76, 75, 10]
retval =  19354392
# part 2
# 
# more tricky, this time we need to be more careful about our
# fallback of "otherwise, we'll walk"
#
#    ......@..........
#    #####.##.##..####
#           ABCDEFGH
#
# here the existing program believes we can go ahead - but we
# end up being forced to jump. we need to jump before this but
# how do we decide this? a naive guess would be "if there's yet
# another gap upcoming whose last tile is F then jump"

script_part_2 = """
# if there's a gap just before jump target AND
# we can continue jumping if we need, then jump
NOT C J
AND D J 
AND H J

# however make sure NOT to walk a step when 
# being forced to jump would land us in gap
NOT B T 
AND D T 
OR T J

# if there's a gap right in front of us, jump
NOT A T 
OR T J

# fingers crossed
RUN
"""        

run_script(script_part_2)
0 [78, 79, 84, 32, 67, 32, 74, 10]
1 [65, 78, 68, 32, 68, 32, 74, 32, 10]
2 [65, 78, 68, 32, 72, 32, 74, 10]
3 [78, 79, 84, 32, 66, 32, 84, 32, 10]
4 [65, 78, 68, 32, 68, 32, 84, 32, 10]
5 [79, 82, 32, 84, 32, 74, 10]
6 [78, 79, 84, 32, 65, 32, 84, 32, 10]
7 [79, 82, 32, 84, 32, 74, 10]
8 [82, 85, 78, 10]
retval =  1139528802