advent2019.py

#!/usr/bin/env python3

import itertools
import operator
import math
import collections
import os
import types
import re
import sys

import defaultlist
import requests
import PIL.Image


def utf(data):
    return data.decode("utf-8")

def lines(data, subparser=None):
    return [(subparser(x) if subparser else x) for x in filter(None, data.split("\n"))]

def first(data):
    return data[0]

def sv(data, sep):
    return data.split(sep)

def csv(data):
    return sv(data, ',')

def ints(data):
    return [int(x) for x in data]


def get_input(day, *, file="input", parser=utf):
    session = os.environ["AOC_SESSION"]
    response = requests.get(
        url=f"https://adventofcode.com/2019/day/{day}/{file}",
        cookies={"session": session},
    )
    if not parser:
        return response.content
    return parser(response.content)


class IntCodeComputer:
    _opcode_parameter_count = {
        1: 3,
        2: 3,
        3: 1,
        4: 1,
        5: 2,
        6: 2,
        7: 3,
        8: 3,
        9: 1,
        99: 0,
    }

    def __init__(self, memory, input=None, ip=0, rb=0):
        self._memory = defaultlist.defaultlist(lambda: 0)
        for idx, value in enumerate(memory):
            self._memory[idx] = value
        self._input = (input or []).copy()
        self._output = []
        self._ip = ip
        self._rb = rb
        self._halted = False

    def poke(self, address, value):
        self._memory[address] = value

    def peek(self, address):
        return self._memory[address]

    def input(self, value):
        self._input.append(value)
        return self

    def _step(self):
        opcode = self._memory[self._ip] % 100
        parameter_modes = self._memory[self._ip] // 100
        self._ip += 1
        parameters = []
        for parameter_index in range(self._opcode_parameter_count[opcode]):
            parameter_mode = parameter_modes // (10 ** parameter_index) % 10
            # raw_value =
            if parameter_mode == 0:
                parameter = self._memory[self._ip]
            elif parameter_mode == 1:
                parameter = self._ip
            elif parameter_mode == 2:
                parameter = self._memory[self._ip ] + self._rb
            else:
                raise ValueError(f"Unknown parameter mode {parameter_mode!r}")
            parameters.append(parameter)
            self._ip += 1
        if opcode == 1:
            val1, val2, dst = parameters
            self._memory[dst] = self._memory[val1 ]+ self._memory[val2]
        elif opcode == 2:
            val1, val2, dst = parameters
            self._memory[dst] = self._memory[val1 ] * self._memory[val2]
        elif opcode == 3:
            dst, = parameters
            if not self._input:
                self._ip -= 2
                return True
            self._memory[dst] = self._input.pop(0)
        elif opcode == 4:
            src, = parameters
            self._output.append(self._memory[src])
        elif opcode == 5:
            val, dst = parameters
            if self._memory[val] != 0:
                self._ip = self._memory[dst]
        elif opcode == 6:
            val, dst = parameters
            if self._memory[val] == 0:
                self._ip = self._memory[dst]
        elif opcode == 7:
            val1, val2, dst = parameters
            self._memory[dst] = 1 if self._memory[val1] < self._memory[val2] else 0
        elif opcode == 8:
            val1, val2, dst = parameters
            self._memory[dst] = 1 if self._memory[val1] == self._memory[val2] else 0
        elif opcode == 9:
            val, = parameters
            self._rb += self._memory[val]
        elif opcode == 99:
            self._halted = True
            return True
        else:
            raise ValueError(f"Unknown opcode {opcode!r}")

    @property
    def output(self):
        return self._output.copy()

    @property
    def halted(self):
        return self._halted

    def run(self):
        while not self._step():
            pass
        return self


def solve_day_1():
    modules = get_input(1, parser=lambda x: ints(lines(utf(x))))

    def fuel_required_for_mass(mass):
        return max(math.floor(mass / 3) - 2, 0)

    yield sum([fuel_required_for_mass(module) for module in modules])

    def total_mass_including_fuel(mass):
        fuel_mass = fuel_required_for_mass(mass)
        if not fuel_mass:
            return fuel_mass
        return fuel_mass + total_mass_including_fuel(fuel_mass)

    yield sum([total_mass_including_fuel(module) for module in modules])


def solve_day_2():
    intcodes = get_input(2, parser=lambda x: ints(csv(first(lines(utf(x))))))

    computer = IntCodeComputer(intcodes)
    computer.poke(1, 12)
    computer.poke(2, 2)
    computer.run()
    yield computer.peek(0)

    for noun in range(100):
        for verb in range(100):
            computer = IntCodeComputer(intcodes)
            computer.poke(1, noun)
            computer.poke(2, verb)
            computer.run()
            if computer.peek(0) == 19690720:
                yield 100 * noun + verb




def solve_day_3():
    paths = get_input(3, parser=lambda x: lines(utf(x), csv))

    def points_between(x1, y1, x2, y2):
        for x in range(x1, x2, x2 > x1 or -1)[1:]:
            yield (x, y1)
        if x1 != x2 and y1 != y2:
            yield (x2, y1)
        for y in range(y1, y2, y2 > y1 or -1)[1:]:
            yield (x2, y)

    def get_points(path):
        x, y = (0, 0)
        for command in path:
            yield x, y
            operation = {
                "D": lambda d: (x, y - d),
                "U": lambda d: (x, y + d),
                "L": lambda d: (x - d, y),
                "R": lambda d: (x + d, y),
            }[command[0]]
            delta = int(command[1:])
            x_next, y_next = operation(delta)
            yield from points_between(x, y, x_next, y_next)
            x, y = x_next, y_next
        yield x, y

    paths_points = [list(get_points(p)) for p in paths]
    intersections = set.intersection(*(set(x) for x in paths_points))
    distances = [sum(abs(x) for x in coord) for coord in intersections]
    yield sorted(distances)[1]
    signal_delays = [
        sum(path_points.index(intersection) for path_points in paths_points)
        for intersection in intersections
    ]
    yield sorted(signal_delays)[1]

def solve_day_4():
    password_range = get_input(4, parser=lambda x: ints(first(lines(utf(x))).split('-')))

    candidates_1 = candidates_2 = 0
    for possible_password in map(str, range(password_range[0], password_range[1] + 1)):
        if possible_password != ''.join(sorted(possible_password)):
            continue

        digit_counts = collections.Counter(possible_password).values()

        if any(x > 1 for x in digit_counts):
            candidates_1 += 1
        if 2 in digit_counts:
            candidates_2 += 1

    yield candidates_1
    yield candidates_2

def solve_day_5():
    intcodes = get_input(5, parser=lambda x: ints(csv(first(lines(utf(x))))))
    computer = IntCodeComputer(intcodes, input=[1])
    computer.run()
    yield computer.output[-1]

    computer = IntCodeComputer(intcodes, input=[5])
    computer.run()
    yield computer.output[0]

def solve_day_6():
    orbit_list = get_input(6, parser=lambda x: [l.split(')') for l in lines(utf(x))])
    orbits = collections.defaultdict(list)
    for orbit in orbit_list:
        orbits[orbit[0]].append(orbit[1])

    def get_orbit_count(name, depth=0):
        if name not in orbits:
            return depth
        return depth + sum(get_orbit_count(child, depth + 1) for child in orbits[name])

    def find_path(root, dest, path=None):
        if root not in orbits:
            return
        if dest in orbits[root]:
            yield (path or []) + [root, dest]
        for child in orbits[root]:
            yield from find_path(child, dest, (path or []) + [root])

    yield get_orbit_count("COM")

    you_path = list(find_path("COM", "YOU"))[0]
    santa_path = list(find_path("COM", "SAN"))[0]

    common_prefix = sum(you_path[i] == santa_path[i] for i in range(min(len(you_path), len(santa_path))))

    yield len(you_path[common_prefix:-1]) + len(santa_path[common_prefix:-1])

def solve_day_7():
    intcodes = get_input(7, parser=lambda x: ints(csv(first(lines(utf(x))))))

    output_signals = []
    for phase_settings in itertools.permutations(range(5)):
        signal = 0
        for phase_setting in phase_settings:
            signal = IntCodeComputer(intcodes, input=[phase_setting, signal]).run().output[0]
        output_signals.append(signal)
    yield max(output_signals)

    output_signals = []
    for phase_settings in itertools.permutations(range(5, 10)):
        signal = 0
        computers = []
        for phase_setting in phase_settings:
            computer = IntCodeComputer(intcodes, input=[phase_setting, signal])
            computers.append(computer)
            signal = computer.run().output[-1]
        while not all(c.halted for c in computers):
            for computer in computers:
                signal = computer.input(signal).run().output[-1]
        output_signals.append(signal)
    yield max(output_signals)


def solve_day_8():
    pixels = get_input(8, parser=lambda x: first(lines(utf(x))))
    width = 25
    height = 6
    layer_size = width * height
    layers = [''.join(layer_pixels) for layer_pixels in zip(*[iter(pixels)] * layer_size)]
    layer_pixel_counts = [collections.Counter(s) for s in layers]
    layer_count_with_fewest_0s = sorted(layer_pixel_counts, key=lambda x: x['0'])[0]
    yield layer_count_with_fewest_0s['1'] * layer_count_with_fewest_0s['2']

    merged_layer = ''.join(re.search('(0|1)', ''.join(x)).group(1) for x in zip(*layers))
    rows = [''.join(x) for x in zip(*[iter(merged_layer)] * width)]

    image = PIL.Image.new('1', (width, height), color='white')
    for y, row in enumerate(rows):
        for x, value in enumerate(row):
            if value == '1':
                image.putpixel((x, y), 0)
    image = image.resize((width * 8, height* 8), PIL.Image.ANTIALIAS)
    # image.save('ok.png')
    # import pytesseract
    # print(pytesseract.image_to_string(image))

    yield '\n' + '\n'.join(r.replace('0', ' ').replace('1', '#') for r in rows)


def solve_day_9():
    # thrilling
    intcodes = get_input(9, parser=lambda x: ints(csv(first(lines(utf(x))))))
    yield IntCodeComputer(intcodes, input=[1]).run().output[0]
    yield IntCodeComputer(intcodes, input=[2]).run().output[0]


def main():
    days = [int(x) for x in sys.argv[1:]] or (x + 1 for x in range(25))
    for day in days:
        function = globals().get(f"solve_day_{day}", None)
        if not function:
            continue
        retval = function()
        if retval is None:
            results = []
        elif isinstance(retval, types.GeneratorType):
            results = retval
        else:
            results = [retval]
        for idx, result in enumerate(results, start=1):
            if idx == 1:
                print(f"Day {day}:")
            print(f"\tResult {idx}: {result}")


if __name__ == "__main__":

    main()