Advent of Code 2019 (Day 5)

aoc2019-05.md

Day 5

from typing import Callable as Fun, Dict, List, Tuple, Optional, NamedTuple
from itertools import accumulate, chain, dropwhile, islice, repeat
from operator import add, mul, eq, lt, getitem

Helper functions

iterate = lambda f: lambda x: accumulate(repeat(x), lambda fx, _: f(fx))
take = lambda n, iterable: tuple(islice(iterable, n))  # From "Itertools Recipes"

Input

Program = List[int]

with open("05-input.txt", "r") as f:
    program: Program = list(map(int, f.read().strip().split(",")))

Part 1

Run an Intcode program

Outputs = List[int]

class Intcode(NamedTuple):
    ptr: Optional[int]  # None halts the program
    prog: Program
    outs: Outputs
        
Modes = Tuple[int, ...]
Operation = Fun[[Modes, Intcode], Intcode]

def diagnostic_code(ops: Dict[int, Operation], prog: Program, input: int) -> int:
    return outputs(ops, prog, input)[-1]

def outputs(ops: Dict[int, Operation], prog: Program, input: int) -> Outputs:
    runs = iterate(execute(ops))(init(prog, input))
    return next(dropwhile(running, runs)).outs

def init(prog: Program, input: int) -> Intcode:
    p = prog.copy()
    p[p[1]] = input
    return Intcode(ptr=2, prog=p, outs=[])

running = lambda ip: ip.ptr is not None

def execute(ops: Dict[int, Operation]) -> Fun[[Intcode], Intcode]:
    def execute_instruction(ip: Intcode) -> Intcode:
        opcode, *modes = instruction(ip.prog[ip.ptr])
        return ops[opcode](modes, ip)
    return execute_instruction

def instruction(inst: int) -> Tuple[int, ...]:
    if inst < 100:  # Just opcode, no parameter modes
        return (inst,)
    *modes, op0, op1 = list(str(inst))
    return int(op0 + op1), *map(int, reversed(modes))

Operations

def operation(f: Fun[[int, int], int]) -> Operation:
    def operate(modes: Modes, ip: Intcode) -> Intcode:
        p = ip.prog.copy()
        m, n = extend(modes)
        p[p[ip.ptr + 3]] = f(PMODE[m](p, ip.ptr + 1), PMODE[n](p, ip.ptr + 2))
        return Intcode(ptr=ip.ptr + 4, prog=p, outs=ip.outs)
    return operate

def extend(modes: Modes) -> Tuple[int, int]:
    return take(2, chain(modes, repeat(0)))

def output(_, ip: Intcode) -> Intcode:
    out = PMODE[0](ip.prog, ip.ptr + 1)
    return Intcode(ptr=ip.ptr + 2, prog=ip.prog, outs=ip.outs + [out])
    
def halt(_, ip: Intcode) -> Intcode:
    return Intcode(ptr=None, prog=ip.prog, outs=ip.outs)

ops = {1: operation(add),
       2: operation(mul),
       4: output,
       99: halt}

Parameter modes

PMODE = (lambda prog, ptr: prog[prog[ptr]],  # Position mode
         getitem)                            # Immediate mode

Solution

assert diagnostic_code(ops, program, input=1) == 7157989

Part 2

def jump_when(cond: Fun[[int], bool]) -> Operation:
    def jump(modes: Modes, ip: Intcode) -> Intcode:
        m, n = extend(modes)
        if cond(PMODE[m](ip.prog, ip.ptr + 1)):
            return Intcode(ptr=PMODE[n](ip.prog, ip.ptr + 2), prog=ip.prog, outs=ip.outs)
        return Intcode(ptr=ip.ptr + 3, prog=ip.prog, outs=ip.outs)
    return jump

def store_when(cond: Fun[[int, int], bool]) -> Operation:
    def store(modes: Modes, ip: Intcode) -> Intcode:
        p = ip.prog.copy()
        m, n = extend(modes)
        if cond(PMODE[m](p, ip.ptr + 1), PMODE[n](p, ip.ptr + 2)):
            p[p[ip.ptr + 3]] = 1
        else:
            p[p[ip.ptr + 3]] = 0
        return Intcode(ptr=ip.ptr + 4, prog=p, outs=ip.outs)
    return store

Extend operations

ops_extended = {**ops,
                5: jump_when(lambda x: x != 0),
                6: jump_when(lambda x: x == 0),
                7: store_when(lt),
                8: store_when(eq)}

Solution

assert diagnostic_code(ops_extended, program, input=5) == 7873292