Advent of Code 2022

advent_of_code_2022.py

# pylint: disable=unspecified-encoding
"""Solutions for 2022 Advent of Code puzzles.

https://adventofcode.com/2022
"""
import argparse
import functools
import itertools
import json
from queue import LifoQueue
import re


def day_1_part_1():
    """Solve Day 1 Part 1 calories puzzle."""
    with open('day_1.txt') as in_file:
        elves = in_file.read().split('\n\n')
    elves = (elf.strip().split('\n') for elf in elves)
    rations = (sum(int(food) for food in elf) for elf in elves)
    return max(rations)


def day_1_part_2():
    """Solve Day 1 Part 2 calories puzzle."""
    with open('day_1.txt') as in_file:
        elves = in_file.read().split('\n\n')
    elves = (elf.strip().split('\n') for elf in elves)
    rations = [sum(int(food) for food in elf) for elf in elves]
    rations.sort()
    return sum(rations[-3:])


def day_2_part_1():
    """Solve Day 2 Part 1 rock-paper-scissors puzzle."""
    rock, paper, scissors = 1, 2, 3
    loss, draw, win = 0, 3, 6
    scores = {
        'A X': rock + draw,
        'A Y': paper + win,
        'A Z': scissors + loss,
        'B X': rock + loss,
        'B Y': paper + draw,
        'B Z': scissors + win,
        'C X': rock + win,
        'C Y': paper + loss,
        'C Z': scissors + draw,
    }
    with open('day_2.txt') as in_file:
        total = sum(scores[move.strip()] for move in in_file)
    return total


def day_2_part_2():
    """Solve Day 2 Part 2 rock-paper-scissors puzzle."""
    rock, paper, scissors = 1, 2, 3
    loss, draw, win = 0, 3, 6
    scores = {
        'A X': loss + scissors,
        'A Y': draw + rock,
        'A Z': win + paper,
        'B X': loss + rock,
        'B Y': draw + paper,
        'B Z': win + scissors,
        'C X': loss + paper,
        'C Y': draw + scissors,
        'C Z': win + rock,
    }
    with open('day_2.txt') as in_file:
        total = sum(scores[move.strip()] for move in in_file)
    return total


def day_3_part_1():
    """Solve Day 3 Part 1 rucksack puzzle."""
    with open('day_3.txt') as in_file:
        rucksacks = in_file.read().splitlines()
    total = 0
    for rucksack in rucksacks:
        middle = len(rucksack) // 2
        item = (set(rucksack[:middle]) & set(rucksack[middle:])).pop()
        total += ord(item) - (96 if ord(item) > 96 else 38)
    return total


def day_3_part_2():
    """Solve Day 3 Part 2 rucksack puzzle."""
    with open('day_3.txt') as in_file:
        rucksacks = in_file.read().splitlines()
    total = 0
    groups = (rucksacks[i:i+3] for i in range(0, len(rucksacks), 3))
    for group in groups:
        item = (set(group[0]) & set(group[1]) & set(group[2])).pop()
        total += ord(item) - (96 if ord(item) > 96 else 38)
    return total


def day_4_part_1():
    """Solve Day 4 Part 1 section overlap puzzle."""
    with open('day_4.txt') as in_file:
        assignments = in_file.read().splitlines()
    overlaps = 0
    for pair in assignments:
        sections = (
            [int(i) for i in section.split('-')]
            for section in pair.split(',')
        )
        outer, inner = sorted(sections, key=lambda x: x[0])
        if outer[0] == inner[0] or outer[1] >= inner[1]:
            overlaps += 1
    return overlaps


def day_4_part_2():
    """Solve Day 4 Part 2 section overlap puzzle."""
    with open('day_4.txt') as in_file:
        assignments = in_file.read().splitlines()
    overlaps = 0
    for pair in assignments:
        sections = (
            [int(i) for i in section.split('-')]
            for section in pair.split(',')
        )
        lower, higher = sorted(sections, key=lambda x: x[0])
        if higher[0] <= lower[1]:
            overlaps += 1
    return overlaps


def day_5_part_1():
    """Solve Day 5 Part 1 crane stacking puzzle."""
    with open('day_5.txt') as in_file:
        initial_stack, steps = in_file.read().split('\n\n')
    # Parse header (containing initial stack list)
    stacks = {}
    header, *initial_stack = initial_stack.splitlines()[::-1]
    for i, char in enumerate(header):
        if char.isdigit():
            stacks[char] = LifoQueue()
            for row in initial_stack:
                if len(row) >= i and row[i] != ' ':
                    stacks[char].put(row[i])
    # Parse steps and apply onto header
    pattern = re.compile(r'move (\d+) from (\d+) to (\d+)')
    for step in steps.splitlines():
        count, src, dst = pattern.match(step).groups()
        for _ in range(int(count)):
            crate = stacks[src].get()
            stacks[dst].put(crate)
    return ''.join(stack.get() for stack in stacks.values())


def day_5_part_2():
    """Solve Day 5 Part 2 crane stacking puzzle."""
    with open('day_5.txt') as in_file:
        initial_stack, steps = in_file.read().split('\n\n')
    # Parse header (containing initial stack list)
    stacks = {}
    header, *initial_stack = initial_stack.splitlines()[::-1]
    for i, char in enumerate(header):
        if char.isdigit():
            stacks[char] = LifoQueue()
            for row in initial_stack:
                if len(row) >= i and row[i] != ' ':
                    stacks[char].put(row[i])
    # Parse steps and apply onto header
    pattern = re.compile(r'move (\d+) from (\d+) to (\d+)')
    for step in steps.splitlines():
        count, src, dst = pattern.match(step).groups()
        crates = [stacks[src].get() for _ in range(int(count))]
        for crate in crates[::-1]:
            stacks[dst].put(crate)
    return ''.join(stack.get() for stack in stacks.values())


def day_6_part_1():
    """Solve Day 6 Part 1 datastream packet puzzle."""
    with open('day_6.txt') as in_file:
        datastream = in_file.read()
    for i, _ in enumerate(datastream, start=4):
        if len(set(datastream[i-4:i])) == 4:
            return i
    raise ValueError("No start-of-packet marker found.")


def day_6_part_2():
    """Solve Day 6 Part 2 datastream packet puzzle."""
    with open('day_6.txt') as in_file:
        datastream = in_file.read()
    for i, _ in enumerate(datastream, start=14):
        if len(set(datastream[i-14:i])) == 14:
            return i
    raise ValueError("No start-of-message marker found.")


def day_7_part_1():
    """Solve Day 7 Part 1 directory map puzzle."""
    dirs, files = {}, {}
    cwd = ''
    reading_files = False
    with open('day_7.txt') as in_file:
        for line in in_file:
            line = line.strip()
            # cd
            if match := re.match(r'\$ cd (.+)', line):
                reading_files = False
                command = match[1]
                if command == '/':
                    cwd = ''
                elif command == '..':
                    cwd = cwd.rsplit('/', 1)[0]
                else:
                    cwd = '/'.join([cwd, command])
                    dirs[cwd] = 0
            # ls
            elif line == '$ ls':
                reading_files = True
            elif reading_files:
                size, name = line.split()
                path = '/'.join([cwd, name])
                if size == 'dir':
                    dirs[path] = 0
                else:
                    files[path] = int(size)
    total = 0
    for directory in dirs:
        dir_size = sum(size for path, size in files.items()
                       if path.startswith(directory))
        if dir_size < 100000:
            total += dir_size
    return total


def day_7_part_2():
    """Solve Day 7 Part 2 directory map puzzle."""
    dirs, files = {}, {}
    cwd = ''
    reading_files = False
    with open('day_7.txt') as in_file:
        for line in in_file:
            line = line.strip()
            # cd
            if match := re.match(r'\$ cd (.+)', line):
                reading_files = False
                command = match[1]
                if command == '/':
                    cwd = ''
                elif command == '..':
                    cwd = cwd.rsplit('/', 1)[0]
                else:
                    cwd = '/'.join([cwd, command])
                    dirs[cwd] = 0
            # ls
            elif line == '$ ls':
                reading_files = True
            elif reading_files:
                size, name = line.split()
                path = '/'.join([cwd, name])
                if size == 'dir':
                    dirs[path] = 0
                else:
                    files[path] = int(size)
    size_needed = sum(size for size in files.values()) - 40_000_000
    size_to_free = 70_000_000
    for directory in dirs:
        dir_size = sum(size for path, size in files.items()
                       if path.startswith(directory))
        if size_needed < dir_size < size_to_free:
            size_to_free = dir_size
    return size_to_free


def day_8_part_1():
    """Solve Day 8 Part 1 tree visibility puzzle."""
    with open('day_8.txt') as in_file:
        trees = [[int(tree) for tree in row] for row in in_file.read().splitlines()]
    size = len(trees)
    visible = [[False] * size for _ in range(size)]

    def traverse_tree_line(tree_line):
        """Update `visible` traversal table with visible trees."""
        height = -1
        for row, column, tree in tree_line:
            if tree > height:
                height = tree
                visible[row][column] = True

    for row, tree_line in enumerate(trees):
        # Left to right
        traverse_tree_line((row, column, tree) for column, tree
                           in enumerate(tree_line))
        # Right to left
        traverse_tree_line((row, column, tree) for column, tree
                           in list(enumerate(tree_line))[::-1])
    for column, tree_line in enumerate(zip(*trees)):
        # Top to bottom
        traverse_tree_line((row, column, tree) for row, tree
                           in enumerate(tree_line))
        # Bottom to top
        traverse_tree_line((row, column, tree) for row, tree
                           in list(enumerate(tree_line))[::-1])
    return sum(sum(row) for row in visible)


def day_8_part_2():
    """Solve Day 8 Part 2 tree visibility puzzle."""
    with open('day_8.txt') as in_file:
        trees = [[int(tree) for tree in row] for row in in_file.read().splitlines()]
    size = len(trees)
    max_score = 0
    for row, tree_line in enumerate(trees):
        for column, tree in enumerate(tree_line):
            i = row - 1
            while i > 0 and trees[i][column] < tree:
                i -= 1
            score = -(i - row)
            i = row + 1
            while i < size - 1 and trees[i][column] < tree:
                i += 1
            score *= i - row
            j = column - 1
            while j > 0 and tree_line[j] < tree:
                j -= 1
            score *= -(j - column)
            j = column + 1
            while j < size - 1 and tree_line[j] < tree:
                j += 1
            score *= j - column
            max_score = max(max_score, score)
    return max_score


def day_9_part_1():
    """Solve Day 9 Part 1 rope bridge puzzle."""
    head, tail = (0, 0), (0, 0)
    history = {tail}
    head_moves = {
        'U': (0, 1),
        'D': (0, -1),
        'R': (1, 0),
        'L': (-1, 0),
    }
    tail_moves = {
        (2, 0): (1, 0),
        (-2, 0): (-1, 0),
        (0, 2): (0, 1),
        (0, -2): (0, -1),
        (2, 1): (1, 1),
        (1, 2): (1, 1),
        (2, -1): (1, -1),
        (1, -2): (1, -1),
        (-2, 1): (-1, 1),
        (-1, 2): (-1, 1),
        (-2, -1): (-1, -1),
        (-1, -2): (-1, -1),
    }
    with open('day_9.txt') as in_file:
        for command in in_file:
            direction, steps = command.strip().split()
            for _ in range(int(steps)):
                head = tuple(h + m for h, m in zip(head, head_moves[direction]))
                diff = tuple(h - t for h, t in zip(head, tail))
                move = tail_moves.get(diff, (0, 0))
                tail = tuple(t + m for t, m in zip(tail, move))
                history.add(tail)
    return len(history)


def day_9_part_2():
    """Solve Day 9 Part 2 rope bridge puzzle."""
    head, tails = (0, 0), [(0, 0) for _ in range(9)]
    history = {tails[-1]}
    head_moves = {
        'U': (0, 1),
        'D': (0, -1),
        'R': (1, 0),
        'L': (-1, 0),
    }
    tail_moves = {
        (2, 0): (1, 0),
        (-2, 0): (-1, 0),
        (0, 2): (0, 1),
        (0, -2): (0, -1),
        (2, 1): (1, 1),
        (1, 2): (1, 1),
        (2, -1): (1, -1),
        (1, -2): (1, -1),
        (-2, 1): (-1, 1),
        (-1, 2): (-1, 1),
        (-2, -1): (-1, -1),
        (-1, -2): (-1, -1),
        (2, 2): (1, 1),
        (-2, 2): (-1, 1),
        (2, -2): (1, -1),
        (-2, -2): (-1, -1),
    }
    with open('day_9.txt') as in_file:
        for command in in_file:
            direction, steps = command.strip().split()
            for _ in range(int(steps)):
                head = tuple(h + m for h, m in zip(head, head_moves[direction]))
                for i, tail in enumerate(tails):
                    prev = head if i == 0 else tails[i - 1]
                    diff = tuple(p - t for p, t in zip(prev, tail))
                    move = tail_moves.get(diff, (0, 0))
                    tails[i] = tuple(t + m for t, m in zip(tail, move))
                history.add(tails[-1])
    return len(history)


def day_10_part_1():
    """Solve Day 10 Part 1 clock cycles puzzle."""
    register_x, cycle, signal, strength = 1, 0, 20, 0
    with open('day_10.txt') as in_file:
        for line in in_file:
            cycle += 1
            if cycle >= signal - 1:
                strength += signal * register_x
                signal += 40
            if line.startswith('addx'):
                cycle += 1
                register_x += int(line.split(' ')[-1])
    return strength


def day_10_part_2():
    """Solve Day 10 Part 2 clock cycles puzzle."""
    register_x, cycle = 1, 0
    draw = list('.' * 240)
    with open('day_10.txt') as in_file:
        for line in in_file:
            if abs(register_x - (cycle % 40)) <= 1:
                draw[cycle] = '#'
            cycle += 1
            if line.startswith('addx'):
                if abs(register_x - (cycle % 40)) <= 1:
                    draw[cycle] = '#'
                cycle += 1
                register_x += int(line.split(' ')[-1])
    lines = [''.join(draw[i:i + 40]) for i in range(0, 240, 40)]
    return '\n'.join(lines)


def day_11_part_1():
    """Solve Day 11 Part 1 monkey throwing puzzle."""
    rounds = 20
    pattern = re.compile(
        r'Monkey (\d+):\s+'
        r'Starting items: ([\d, ]+)\s+'
        r'Operation: new = old ([*+]) (\S+)\s+'
        r'Test: divisible by (\d+)\s+'
        r'If true: throw to monkey (\d+)\s+'
        r'If false: throw to monkey (\d+)'
    )
    monkeys = []
    with open('day_11.txt') as in_file:
        for monkey in in_file.read().split('\n\n'):
            match = pattern.match(monkey).groups()
            monkeys.append({
                'id': int(match[0]),
                'items': [int(item) for item in match[1].split(', ')],
                'increase': {
                    'operator': match[2],
                    'value': 'old' if match[3] == 'old' else int(match[3]),
                },
                'test': {
                    'divisor': int(match[4]),
                    True: int(match[5]),
                    False: int(match[6])
                },
                'inspections': 0,
            })
    for _ in range(rounds):
        for monkey in monkeys:
            while monkey['items']:
                # Pull item for inspection
                item = monkey['items'].pop(0)
                monkey['inspections'] += 1
                # Increase worry
                mi = monkey['increase']
                worry = item if mi['value'] == 'old' else mi['value']
                if mi['operator'] == '+':
                    item += worry
                elif mi['operator'] == '*':
                    item *= worry
                else:
                    raise ValueError(f"Operator {mi['operator']} not supported.")
                # Decrease worry
                item //= 3
                # Check and throw to next monkey
                mt = monkey['test']
                test = (item % mt['divisor'] == 0)
                monkeys[mt[test]]['items'].append(item)
    inspections = sorted([monkey['inspections'] for monkey in monkeys])
    return inspections[-1] * inspections[-2]


def day_11_part_2():
    """Solve Day 11 Part 2 monkey throwing puzzle."""
    rounds = 10000
    pattern = re.compile(
        r'Monkey (\d+):\s+'
        r'Starting items: ([\d, ]+)\s+'
        r'Operation: new = old ([*+]) (\S+)\s+'
        r'Test: divisible by (\d+)\s+'
        r'If true: throw to monkey (\d+)\s+'
        r'If false: throw to monkey (\d+)'
    )
    monkeys = []
    gcd = 1
    with open('day_11.txt') as in_file:
        for monkey in in_file.read().split('\n\n'):
            match = pattern.match(monkey).groups()
            monkeys.append({
                'id': int(match[0]),
                'items': [int(item) for item in match[1].split(', ')],
                'increase': {
                    'operator': match[2],
                    'value': 'old' if match[3] == 'old' else int(match[3]),
                },
                'test': {
                    'divisor': int(match[4]),
                    True: int(match[5]),
                    False: int(match[6])
                },
                'inspections': 0,
            })
            gcd *= int(match[4])
    for _ in range(rounds):
        for monkey in monkeys:
            while monkey['items']:
                # Pull item for inspection
                item = monkey['items'].pop(0)
                monkey['inspections'] += 1
                # Increase worry
                mi = monkey['increase']
                worry = item if mi['value'] == 'old' else mi['value']
                if mi['operator'] == '+':
                    item += worry
                elif mi['operator'] == '*':
                    item *= worry
                else:
                    raise ValueError(f"Operator {mi['operator']} not supported.")
                # Modulo worry (to avoid big int overflow)
                item %= gcd
                # Check and throw to next monkey
                mt = monkey['test']
                test = (item % mt['divisor'] == 0)
                monkeys[mt[test]]['items'].append(item)
    inspections = sorted([monkey['inspections'] for monkey in monkeys])
    return inspections[-1] * inspections[-2]


def day_12_part_1():
    """Solve Day 12 Part 1 hill climbing puzzle.

    This was made to be an A* algorithm, and my literal graduate thesis is a
    waste if I can't write one of these. EDIT: This is short enough for BFS.
    """
    with open('day_12.txt') as in_file:
        grid = [list(row) for row in in_file.read().splitlines()]
    # Build indexed adjacency list to convert to a graph
    start, end = None, None
    nodes = {}
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell == 'S':
                start = (i, j)
                cell = 'a'
            elif cell == 'E':
                end = (i, j)
                cell = 'z'
            nodes[(i, j)] = {
                'value': ord(cell) - ord('a'),
                'neighbors': [],
                'steps': 1000000,
            }
    for (i, j), node in nodes.items():
        for neighbor in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if neighbor in nodes and nodes[neighbor]['value'] <= node['value'] + 1:
                node['neighbors'].append(neighbor)
    # Breadth-first search the graph to calculate steps to get to each node
    nodes[start]['steps'] = 0
    queue = [start]
    while queue:
        node = nodes[queue.pop(0)]
        for neighbor_location in node['neighbors']:
            neighbor = nodes[neighbor_location]
            steps = node['steps'] + 1
            if steps < neighbor['steps']:
                neighbor['steps'] = steps
                queue.append(neighbor_location)
            if neighbor_location == end:
                break
    return nodes[end]['steps']


def day_12_part_2():
    """Solve Day 12 Part 2 hill climbing puzzle."""
    with open('day_12.txt') as in_file:
        grid = [list(row) for row in in_file.read().splitlines()]
    # Build indexed adjacency list to convert to a graph
    start = None
    nodes = {}
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell == 'S':
                cell = 'a'
            elif cell == 'E':
                start = (i, j)
                cell = 'z'
            nodes[(i, j)] = {
                'value': ord('z') - ord(cell),
                'neighbors': [],
                'steps': 1000000,
            }
    for (i, j), node in nodes.items():
        for neighbor in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if neighbor in nodes and nodes[neighbor]['value'] <= node['value'] + 1:
                node['neighbors'].append(neighbor)
    # Breadth-first search the graph to calculate steps to get to each node
    nodes[start]['steps'] = 0
    queue = [start]
    while queue:
        node = nodes[queue.pop(0)]
        for neighbor_location in node['neighbors']:
            neighbor = nodes[neighbor_location]
            steps = node['steps'] + 1
            if steps < neighbor['steps']:
                neighbor['steps'] = steps
                queue.append(neighbor_location)
    return min(node['steps'] for node in nodes.values() if node['value'] == 25)


def day_13_part_1():
    """Solve Day 13 Part 1 pair matching puzzle."""
    LOWER, SAME, HIGHER = -1, 0, 1
    with open('day_13.txt') as in_file:
        pairs = [
            [json.loads(row) for row in pair.strip().split('\n')]
            for pair in in_file.read().split('\n\n')
        ]

    def compare(left, right):
        """Recursively compare left and right pairs."""
        if left is None:
            return LOWER
        if right is None:
            return HIGHER
        if isinstance(left, int) and isinstance(right, int):
            if left < right:
                return LOWER
            if left > right:
                return HIGHER
            return SAME
        if isinstance(left, list) and isinstance(right, list):
            for l, r in itertools.zip_longest(left, right):
                result = compare(l, r)
                if result != SAME:
                    return result
            return SAME
        return compare(
            [left] if isinstance(left, int) else left,
            [right] if isinstance(right, int) else right
        )

    return sum(i for i, pair in enumerate(pairs, 1) if compare(*pair) == LOWER)


def day_13_part_2():
    """Solve Day 13 Part 2 pair matching puzzle."""
    LOWER, SAME, HIGHER = -1, 0, 1
    dividers = [[2]], [[6]]
    with open('day_13.txt') as in_file:
        packets = [
            json.loads(row) for row in in_file.read().split('\n')
            if row.strip()
        ]
    packets += dividers

    def compare(left, right):
        """Recursively compare left and right pairs."""
        if left is None:
            return LOWER
        if right is None:
            return HIGHER
        if isinstance(left, int) and isinstance(right, int):
            if left < right:
                return LOWER
            if left > right:
                return HIGHER
            return SAME
        if isinstance(left, list) and isinstance(right, list):
            for l, r in itertools.zip_longest(left, right):
                result = compare(l, r)
                if result != SAME:
                    return result
            return SAME
        return compare(
            [left] if isinstance(left, int) else left,
            [right] if isinstance(right, int) else right
        )

    packets.sort(key=functools.cmp_to_key(compare))
    first, second = [packets.index(divider) for divider in dividers]
    return (first + 1) * (second + 1)


def day_14_part_1():
    """Solve Day 14 Part 1 sand filling puzzle."""
    AIR, SAND, ROCK, SOURCE = '.', 'o', '#', '+'
    with open('day_14.txt') as in_file:
        rock_paths = [json.loads(f"[[{row.replace('->', '],[')}]]")
                      for row in in_file]
    # Normalize the data to simplify visualization
    min_x, max_x, max_y = 1000, 0, 0
    for rock_path in rock_paths:
        for x, y in rock_path:
            min_x, max_x, max_y = min(min_x, x), max(max_x, x), max(max_y, y)
    for i, rock_path in enumerate(rock_paths):
        rock_paths[i] = [(x - min_x, y) for x, y in rock_path]
    max_x -= min_x
    grid = [[AIR] * (max_y + 1) for _ in range(max_x + 1)]
    source = (500 - min_x, 0)
    grid[source[0]][source[1]] = SOURCE
    # Load grid with rocks
    for rock_path in rock_paths:
        for (x1, y1), (x2, y2) in zip(rock_path[:-1], rock_path[1:]):
            if y1 == y2:
                start, end = min(x1, x2), max(x1, x2) + 1
                points = ((x, y1) for x in range(start, end))
            elif x1 == x2:
                start, end = min(y1, y2), max(y1, y2) + 1
                points = ((x1, y) for y in range(start, end))
            for x, y in points:
                grid[x][y] = ROCK
    # Fill structure with sand until full
    done = False
    number_of_grains = 0
    while not done:
        x, y = source
        while True:
            if y == max_y:
                done = True
                break
            elif x in [-1, max_x] or grid[x][y + 1] == AIR:
                y += 1
            elif x == 0 or grid[x - 1][y + 1] == AIR:
                x, y = x - 1, y + 1
            elif x == max_x or grid[x + 1][y + 1] == AIR:
                x, y = x + 1, y + 1
            else:
                break
        if not done:
            number_of_grains += 1
            grid[x][y] = SAND
    # print('\n'.join([''.join(row) for row in zip(*grid)]))
    return number_of_grains



def day_14_part_2():
    """Solve Day 14 Part 2 sand filling puzzle."""
    AIR, SAND, ROCK, SOURCE = '.', 'o', '#', '+'
    with open('day_14.txt') as in_file:
        rock_paths = [json.loads(f"[[{row.replace('->', '],[')}]]")
                      for row in in_file]
    # Normalize the data to simplify visualization
    min_x, max_x, max_y = 1000, 0, 0
    for rock_path in rock_paths:
        for x, y in rock_path:
            min_x, max_x, max_y = min(min_x, x), max(max_x, x), max(max_y, y)
    # Add very large ("infinite") floor
    min_x, max_x, max_y = min_x - 500, max_x + 500, max_y + 2
    rock_paths.append([[min_x, max_y], [max_x, max_y]])
    for i, rock_path in enumerate(rock_paths):
        rock_paths[i] = [(x - min_x, y) for x, y in rock_path]
    max_x -= min_x
    grid = [[AIR] * (max_y + 1) for _ in range(max_x + 1)]
    source = (500 - min_x, 0)
    grid[source[0]][source[1]] = SOURCE
    # Load grid with rocks
    for rock_path in rock_paths:
        for (x1, y1), (x2, y2) in zip(rock_path[:-1], rock_path[1:]):
            if y1 == y2:
                start, end = min(x1, x2), max(x1, x2) + 1
                points = ((x, y1) for x in range(start, end))
            elif x1 == x2:
                start, end = min(y1, y2), max(y1, y2) + 1
                points = ((x1, y) for y in range(start, end))
            for x, y in points:
                grid[x][y] = ROCK
    # Fill structure with sand until full
    number_of_grains = 0
    while True:
        x, y = source
        while True:
            if grid[x][y + 1] == AIR:
                y += 1
            elif grid[x - 1][y + 1] == AIR:
                x, y = x - 1, y + 1
            elif grid[x + 1][y + 1] == AIR:
                x, y = x + 1, y + 1
            else:
                break
        number_of_grains += 1
        grid[x][y] = SAND
        if (x, y) == source:
            break
    return number_of_grains


def day_15_part_1():
    """Solve Day 15 Part 1 sensor-beacon puzzle."""
    pattern = re.compile(r'Sensor at x=(\d+), y=(\d+): '
                         r'closest beacon is at x=(-?\d+), y=(-?\d+)\n')
    with open('day_15.txt') as in_file:
        sensors = [[int(x) for x in pattern.match(row).groups()]
                   for row in in_file]
    # Keep a set of all x coords where a beacon cannot be located
    y_target = 2_000_000
    no_beacon = set()
    for x_sensor, y_sensor, x_beacon, y_beacon in sensors:
        radius = abs(x_beacon - x_sensor) + abs(y_beacon - y_sensor)
        if y_sensor - radius <= y_target <= y_sensor + radius:
            dy = abs(y_target - y_sensor)
            dx = radius - dy
            no_beacon.update({*range(x_sensor - dx, x_sensor + dx + 1)})
    # Remove beacons that may exist in the target row
    for _, _, x_beacon, y_beacon in sensors:
        if y_beacon == y_target and x_beacon in no_beacon:
            no_beacon.remove(x_beacon)
    return len(no_beacon)


def day_15_part_2():
    """Solve Day 15 Part 2 sensor-beacon puzzle."""
    pattern = re.compile(r'Sensor at x=(\d+), y=(\d+): '
                         r'closest beacon is at x=(-?\d+), y=(-?\d+)\n')
    with open('day_15.txt') as in_file:
        sensors = [[int(x) for x in pattern.match(row).groups()]
                   for row in in_file]
    # Keep a set of all x coord ranges where a beacon cannot be located
    max_coordinate = 4_000_000
    y_targets = range(max_coordinate + 1)
    for y_target in y_targets:
        no_beacon = []
        for x_sensor, y_sensor, x_beacon, y_beacon in sensors:
            radius = abs(x_beacon - x_sensor) + abs(y_beacon - y_sensor)
            if y_sensor - radius <= y_target <= y_sensor + radius:
                dy = abs(y_target - y_sensor)
                dx = radius - dy
                left = min(max(x_sensor - dx, 0), max_coordinate)
                right = min(max(x_sensor + dx, 0), max_coordinate)
                no_beacon.append((left, right))
        no_beacon.sort()
        i = 1
        while i < len(no_beacon):
            x1_min, x1_max = no_beacon[0]
            x2_min, x2_max = no_beacon[i]
            if x2_min - 1 <= x1_max < x2_max:
                no_beacon[0] = (x1_min, x2_max)
            i += 1
        x = no_beacon[0][1]
        if x != max_coordinate:
            break
    return (x + 1) * 4_000_000 + y_target


def day_16_part_1():
    """Solve Day 16 Part 1 valve opening puzzle."""
    pattern = re.compile(r'Valve (\w+) has flow rate=(\d+); '
                         r'tunnels? leads? to valves? (.+)\n')
    valves = {}
    with open('day_16.txt') as in_file:
        for row in in_file:
            valve, rate, neighbors = pattern.match(row).groups()
            valves[valve] = {
                'rate': int(rate),
                'neighbors': neighbors.split(', '),
            }
    # Important! Convert the valves into a weighted graph containing only
    # nodes with usable valves (rate > 0). This greatly simplifies the search
    # space and smooths over corner cases.
    indices = {v: i for i, v in enumerate(valves)}
    distances = [[1000] * len(indices) for _ in indices]
    for name, valve in valves.items():
        valve_index = indices[name]
        for neighbor in valve['neighbors']:
            neighbor_index = indices[neighbor]
            distances[valve_index][neighbor_index] = 1
    # Floyd–Warshall DP algorithm for calculating edge weights
    for k, i, j in itertools.product(indices.values(), indices.values(), indices.values()):
        distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

    root = 'AA'
    nodes = [
        {'name': name, 'rate': valve['rate']}
        for name, valve in valves.items()
        if valve['rate'] > 0 or name == root
    ]
    for i, node in enumerate(nodes):
        node['neighbors'] = {
            j: distances[indices[node['name']]][indices[neighbor['name']]]
            for j, neighbor in enumerate(nodes)
            if i != j
        }
    root_index = next(i for i, node in enumerate(nodes) if node['name'] == root)

    depth = 30
    max_score = 0
    queue = [{
        'node': root_index,
        'steps': 0,
        'traversed': [False] * len(nodes),
        'score': 0,
    }]
    while queue:
        entry = queue.pop()
        if entry['steps'] == depth:
            max_score = max(entry['score'], max_score)
        else:
            moved = False
            i = entry['node']
            for j, distance in nodes[i]['neighbors'].items():
                new_step = entry['steps'] + distance + 1
                if new_step + distance < depth + 1 and not entry['traversed'][j]:
                    moved = True
                    new_traversed = entry['traversed'].copy()
                    new_traversed[i] = True
                    new_traversed[j] = True
                    new_score = entry['score'] + nodes[j]['rate'] * (depth - new_step)
                    queue.append({
                        'node': j,
                        'steps': new_step,
                        'traversed': new_traversed,
                        'score': new_score,
                    })
            if not moved:
                queue.append({
                    'node': entry['node'],
                    'steps': depth,
                    'traversed': entry['traversed'],
                    'score': entry['score'],
                })
    return max_score


def day_16_part_2():
    """Solve Day 16 Part 2 valve opening puzzle.

    This took me a *long* time. The breakthrough came from simplifying the
    valves into a weighted graph.
    """
    pattern = re.compile(r'Valve (\w+) has flow rate=(\d+); '
                         r'tunnels? leads? to valves? (.+)\n')
    valves = {}
    with open('day_16.txt') as in_file:
        for row in in_file:
            valve, rate, neighbors = pattern.match(row).groups()
            valves[valve] = {
                'rate': int(rate),
                'neighbors': neighbors.split(', '),
            }
    # Important! Convert the valves into a weighted graph containing only
    # nodes with usable valves (rate > 0). This greatly simplifies the search
    # space and smooths over corner cases.
    indices = {v: i for i, v in enumerate(valves)}
    distances = [[1000] * len(indices) for _ in indices]
    for name, valve in valves.items():
        valve_index = indices[name]
        for neighbor in valve['neighbors']:
            neighbor_index = indices[neighbor]
            distances[valve_index][neighbor_index] = 1
    # Floyd–Warshall DP algorithm for calculating edge weights
    for k, i, j in itertools.product(indices.values(), indices.values(), indices.values()):
        distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

    root = 'AA'
    nodes = [
        {'name': name, 'rate': valve['rate']}
        for name, valve in valves.items()
        if valve['rate'] > 0 or name == root
    ]
    for i, node in enumerate(nodes):
        node['neighbors'] = {
            j: distances[indices[node['name']]][indices[neighbor['name']]]
            for j, neighbor in enumerate(nodes)
            if i != j
        }
    root_index = next(i for i, node in enumerate(nodes) if node['name'] == root)

    depth = 26
    max_score = 0
    queue = [{
        'nodes': [root_index, root_index],
        'steps': [0, 0],
        'traversed': [False] * len(nodes),
        'score': 0,
    }]
    while queue:
        entry = queue.pop()
        if all(step == depth for step in entry['steps']):
            max_score = max(entry['score'], max_score)
        else:
            options = [[] for _ in entry['nodes']]
            for i, option, step in zip(entry['nodes'], options, entry['steps']):
                for j, distance in nodes[i]['neighbors'].items():
                    if step + distance < depth and not entry['traversed'][j]:
                        option.append([j, step + distance + 1])
                if not option:
                    option.append([i, depth])
            for (i, step_1), (j, step_2) in itertools.product(*options):
                # Cannot flip same valve
                if i == j:
                    continue
                new_score = entry['score'] + (
                    nodes[i]['rate'] * (depth - step_1) +
                    nodes[j]['rate'] * (depth - step_2)
                )
                # A manual heuristic to chop paths that are not scoring well
                if new_score + 100 * (depth - min(step_1, step_2)) > max_score:
                    new_traversed = entry['traversed'].copy()
                    new_traversed[i] = True
                    new_traversed[j] = True
                    queue.append({
                        'nodes': [i, j],
                        'steps': [step_1, step_2],
                        'traversed': new_traversed,
                        'score': new_score,
                    })
    return max_score


parser = argparse.ArgumentParser(description="Run 2022 Advent of Code solutions.")
parser.add_argument('day', type=int, choices=range(1, 26), metavar='[1, 25]',
                    help='Advent code day to run.')
args = parser.parse_args()
part_1, part_2 = locals()[f'day_{args.day}_part_1'], locals()[f'day_{args.day}_part_2']
print(f"Part 1:\n{part_1()}\n")
print(f"Part 2:\n{part_2()}")