Sean McLemon | Advent of Code

2020-12-08 - Handheld Halting

(original .ipynb)

Day 8 is a simple assembly-code like program (mine is here) which can execute one of three operations (nop, acc and jmp). Part 1 involves interpreting the program and finding the value of the accumulator register at the point that it begins to enter an infinite loop. Part 2 involves "fixing" one of the instructions - swapping a nop to a jmp or vice versa - such that the program doesn't hit an infinite loop, but instead runs to the end of the program.

test_input_str = """nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6"""

puzzle_input_str = open("puzzle_input/day8.txt", "r").read()

def step(instructions, pc, acc):
    opcode, arg = instructions[pc].split(" ")
    new_pc = pc + 1
    
    if opcode == "acc":
        acc += int(arg)
    elif opcode == "jmp":
        new_pc = pc + int(arg)        
    elif opcode == "nop":
        pass
    
    return (new_pc, acc)

def try_run(raw_instructions):
    instructions = raw_instructions.split("\n")

    pc = 0
    acc = 0

    terminal_pc = len(instructions)
    pc_visited = set()   
    
    while not (pc in pc_visited):
        if pc == terminal_pc:
            return (True, acc)
        
        pc_visited.add(pc)
        pc, acc = step(instructions, pc, acc)
    
    return (False, acc)

assert (False, 5) == try_run(test_input_str)
try_run(puzzle_input_str)

(False, 1723)

def mutate_program(addr, raw_instructions):
    instructions = raw_instructions.split("\n")
    opcode, arg = instructions[addr].split(" ")
    
    if opcode == "jmp":
        opcode = "nop"
    elif opcode == "nop":
        opcode = "jmp"
    else:
        pass
    
    instructions[addr] = f"{opcode} {arg}"
    return "\n".join(instructions) #lol


def find_dodgy_instr(raw_instructions):
    len_instructions = len(raw_instructions.split("\n"))
    for n in range(len_instructions):
        new_raw_instructions = mutate_program(n, raw_instructions)
        success, final_acc = try_run(new_raw_instructions)
        if success:
            return final_acc


assert 8 == find_dodgy_instr(test_input_str)
find_dodgy_instr(puzzle_input_str)

846