Advent of Code 2024

advent_of_code_2024.py

"""Solutions for 2024 Advent of Code puzzles.

https://adventofcode.com/2024
"""
import argparse
from collections import Counter, defaultdict
from copy import deepcopy
from functools import cmp_to_key
from itertools import permutations, product
from math import gcd, log2, prod
import re

def day_1_part_1():
    """Solve Day 1 Part 1 puzzle."""
    with open('day_1.txt') as in_file:
        locations = [
            [int(x) for x in line.split()]
            for line in in_file
        ]
    left, right = zip(*locations)
    return sum(abs(l - r) for l, r in zip(sorted(left), sorted(right)))


def day_1_part_2():
    """Solve Day 1 Part 2 puzzle."""
    with open('day_1.txt') as in_file:
        locations = [
            [int(x) for x in line.split()]
            for line in in_file
        ]
    left, right = zip(*locations)
    right_count = Counter(right)
    return sum(l * right_count[l] for l in left)


def day_2_part_1():
    """Solve Day 2 Part 1 puzzle."""
    def check_report(report):
        return all(i < j <= i + 3 for i, j in zip(report[:-1], report[1:]))

    with open('day_2.txt') as in_file:
        reports = [
            [int(x) for x in line.split()]
            for line in in_file
        ]
    safe_report_count = 0
    for report in reports:
        is_safe = check_report(report) or check_report(report[::-1])
        safe_report_count += is_safe
    return safe_report_count


def day_2_part_2():
    """Solve Day 2 Part 2 puzzle."""
    def check_report(report):
        return all(i < j <= i + 3 for i, j in zip(report[:-1], report[1:]))

    def check_report_slices(report):
        return any(
            check_report(report[:i] + report[i+1:])
            for i in range(len(report))
        )

    with open('day_2.txt') as in_file:
        reports = [
            [int(x) for x in line.split()]
            for line in in_file
        ]
    safe_report_count = 0
    for report in reports:
        is_safe = check_report(report) or check_report(report[::-1])
        if not is_safe:
            is_safe = check_report_slices(report) or check_report_slices(report[::-1])
        safe_report_count += is_safe
    return safe_report_count


def day_3_part_1():
    """Solve Day 3 Part 1 puzzle."""
    with open('day_3.txt') as in_file:
        memory = in_file.read()
    matches = re.findall(r'mul\((\d{1,3}),(\d{1,3})\)', memory)
    return sum(int(a) * int(b) for a, b in matches)


def day_3_part_2():
    """Solve Day 3 Part 2 puzzle."""
    with open('day_3.txt') as in_file:
        memory = in_file.read()
    enabled = re.sub(r"don't\(\).*?(?:$|do\(\))", '', memory, flags=re.DOTALL)
    matches = re.findall(r'mul\((\d{1,3}),(\d{1,3})\)', enabled)
    return sum(int(a) * int(b) for a, b in matches)


def day_4_part_1():
    """Solve Day 4 Part 1 puzzle."""
    with open('day_4.txt') as in_file:
        word_search = [list(row.strip()) for row in in_file]

    # Add padding to the word search to avoid edge cases
    for i, row in enumerate(word_search):
        word_search[i] = ['*'] + row + ['*']
    padded_row = ['*' for _ in range(len(word_search[0]))]
    word_search = [padded_row] + word_search + [padded_row]

    count = 0
    directions = [
        (-1, 0), (1, 0), (0, -1), (0, 1),
        (-1, -1), (-1, 1), (1, -1), (1, 1),
    ]
    for y, row in enumerate(word_search):
        for x, char in enumerate(row):
            if char != 'X':
                continue
            for dx, dy in directions:
                for i, search_char in enumerate('MAS', start=1):
                    if word_search[y + i * dy][x + i * dx] != search_char:
                        break
                else:
                    count += 1
    return count


def day_4_part_2():
    """Solve Day 4 Part 2 puzzle."""
    with open('day_4.txt') as in_file:
        word_search = [list(row.strip()) for row in in_file]

    for i, row in enumerate(word_search):
        word_search[i] = ['*'] + row + ['*']
    padded_row = ['*' for _ in range(len(word_search[0]))]
    word_search = [padded_row] + word_search + [padded_row]

    count = 0
    directions = [(-1, 1), (1, 1), (-1, -1), (1, -1)]
    patterns = ['MSMS', 'MMSS', 'SSMM', 'SMSM']
    for y, row in enumerate(word_search):
        for x, char in enumerate(row):
            if char != 'A':
                continue
            pattern = ''.join(word_search[y + dy][x + dx] for dx, dy in directions)
            if pattern in patterns:
                count += 1
    return count


def day_5_part_1():
    """Solve Day 5 Part 1 puzzle."""
    with open('day_5.txt') as in_file:
        rule_data, update_data = in_file.read().strip().split('\n\n')

    rules = {i: set() for i in range(10, 100)}
    for rule in rule_data.split('\n'):
        before, after = [int(x) for x in rule.split('|')]
        rules[before].add(after)

    total = 0
    for update in update_data.split('\n'):
        pages = [int(x) for x in update.split(',')]
        for i, page in enumerate(pages):
            if any(other_page not in rules[page] for other_page in pages[i + 1:]):
                break
        else:
            total += pages[len(pages) // 2]
    return total


def day_5_part_2():
    """Solve Day 5 Part 2 puzzle."""
    with open('day_5.txt') as in_file:
        rule_data, update_data = in_file.read().strip().split('\n\n')

    rules = {i: set() for i in range(10, 100)}
    for rule in rule_data.split('\n'):
        before, after = [int(x) for x in rule.split('|')]
        rules[before].add(after)

    def sort_key(x, y):
        if y in rules[x]:
            return -1
        elif x in rules[y]:
            return 1
        return 0

    total = 0
    for update in update_data.split('\n'):
        pages = [int(x) for x in update.split(',')]
        for i, page in enumerate(pages):
            if any(other_page not in rules[page] for other_page in pages[i + 1:]):
                pages.sort(key=cmp_to_key(sort_key))
                total += pages[len(pages) // 2]
                break
    return total


def day_6_part_1():
    """Solve Day 6 Part 1 puzzle."""
    with open('day_6.txt') as in_file:
        lab_map = [list(row.strip()) for row in in_file]

    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    d = 0
    x, y = next((x, y) for y, row in enumerate(lab_map) for x, char in enumerate(row) if char == '^')
    while 0 <= x < len(lab_map) and 0 <= y < len(lab_map[0]):
        dx, dy = directions[d]
        if lab_map[y][x] == '#':
            x, y = x - dx, y - dy
            d = (d + 1) % 4
        else:
            lab_map[y][x] = 'X'
            x, y = x + dx, y + dy
    return sum(row.count('X') for row in lab_map)


def day_6_part_2():
    """Solve Day 6 Part 2 puzzle."""
    with open('day_6.txt') as in_file:
        lab_map = [list(row.strip()) for row in in_file]

    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    start = next((x, y) for y, row in enumerate(lab_map) for x, char in enumerate(row) if char == '^')

    # Find all the traversed points. These are all we need to check for loops.
    x, y = start
    d = 0
    to_check = set()
    while 0 <= x < len(lab_map) and 0 <= y < len(lab_map[0]):
        dx, dy = directions[d]
        if lab_map[y][x] == '#':
            x, y = x - dx, y - dy
            d = (d + 1) % 4
        else:
            if lab_map[y][x] != '^':
                to_check.add((x, y))
            x, y = x + dx, y + dy

    def is_loop(m, x=start[0], y=start[1]):
        d = 0
        traversed = {(x, y, d)}
        while 0 <= x < len(m) and 0 <= y < len(m[0]):
            dx, dy = directions[d]
            if m[y][x] == '#':
                x, y = x - dx, y - dy
                d = (d + 1) % 4
            elif m[y][x] == 'X' and (x, y, d) in traversed:
                return True
            else:
                m[y][x] = 'X'
                traversed.add((x, y, d))
                x, y = x + dx, y + dy
        return False

    total = 0
    for x, y in to_check:
        new_map = deepcopy(lab_map)
        new_map[y][x] = '#'
        if is_loop(new_map):
            total += 1
    return total


def day_7_part_1():
    """Solve Day 7 Part 1 puzzle."""
    with open('day_7.txt') as in_file:
        equations = []
        for line in in_file:
            test, values = line.split(': ')
            equations.append((int(test), [int(x) for x in values.split()]))

    def check_equation(test, values, operators):
        total = values[0]
        for operator, value in zip(operators, values[1:]):
            if total > test:
                return False
            elif operator == '+':
                total += value
            elif operator == '*':
                total *= value
        return total == test

    total = 0
    for test, values in equations:
        for option in product('+*', repeat=len(values)-1):
            if check_equation(test, values, option):
                total += test
                break
    return total


def day_7_part_2():
    """Solve Day 7 Part 2 puzzle."""
    with open('day_7.txt') as in_file:
        equations = []
        for line in in_file:
            test, values = line.split(': ')
            equations.append((int(test), [int(x) for x in values.split()]))

    def check_equation(test, values, operators):
        total = values[0]
        for operator, value in zip(operators, values[1:]):
            if total > test:
                return False
            elif operator == '+':
                total += value
            elif operator == '*':
                total *= value
            elif operator == '|':
                total = int(str(total) + str(value))
        return total == test

    total = 0
    for test, values in equations:
        for option in product('+*|', repeat=len(values)-1):
            if check_equation(test, values, option):
                total += test
                break
    return total


def day_8_part_1():
    """Solve Day 8 Part 1 puzzle."""
    with open('day_8.txt') as in_file:
        antenna_map = [list(row.strip()) for row in in_file]

    antennas = {}
    for y, row in enumerate(antenna_map):
        for x, char in enumerate(row):
            if char != '.':
                antennas.setdefault(char, set()).add((x, y))

    antinodes = set()
    for points in antennas.values():
        for (x1, y1), (x2, y2) in permutations(points, 2):
            dx, dy = x2 - x1, y2 - y1
            x, y = x2 + dx, y2 + dy
            if 0 <= x < len(antenna_map[0]) and 0 <= y < len(antenna_map):
                antinodes.add((x, y))
    return len(antinodes)


def day_8_part_2():
    """Solve Day 8 Part 2 puzzle."""
    with open('day_8.txt') as in_file:
        antenna_map = [list(row.strip()) for row in in_file]

    antennas = {}
    for y, row in enumerate(antenna_map):
        for x, char in enumerate(row):
            if char != '.':
                antennas.setdefault(char, set()).add((x, y))

    antinodes = set()
    for points in antennas.values():
        for (x1, y1), (x2, y2) in permutations(points, 2):
            dx, dy = x2 - x1, y2 - y1
            divisor = gcd(dx, dy)
            dx, dy = dx // divisor, dy // divisor
            x, y = x2, y2
            while 0 <= x < len(antenna_map[0]) and 0 <= y < len(antenna_map):
                antinodes.add((x, y))
                x, y = x + dx, y + dy
    return len(antinodes)


def day_9_part_1():
    """Solve Day 9 Part 1 puzzle."""
    with open('day_9.txt') as in_file:
        disk_map = [int(x) for x in in_file.read().strip()]
    blocks = []
    for i, block_count in enumerate(disk_map):
        file_id = i // 2 if i % 2 == 0 else None
        blocks += [file_id] * block_count
    l, r = 0, len(blocks) - 1
    while l < r:
        if blocks[r] is None:
            r -= 1
        elif blocks[l] is not None:
            l += 1
        else:
            blocks[l], blocks[r] = blocks[r], blocks[l]
    return sum(i * (x or 0) for i, x in enumerate(blocks))


def day_9_part_2():
    """Solve Day 9 Part 2 puzzle.

    This one took me a couple of hours. Lots of fussing with indices before
    deciding to rework the data structure.
    """
    with open('day_9.txt') as in_file:
        disk_map = [int(x) for x in in_file.read().strip()]
    disk, spaces, files = [], [], []
    for i, block_count in enumerate(disk_map):
        is_file = (i % 2 == 0)
        if is_file:
            files.append((i // 2, block_count, len(disk)))
        else:
            spaces.append((block_count, len(disk)))
        disk += [int(i // 2) if is_file else None for _ in range(block_count)]

    while files:
        file_id, file_len, file_index = files.pop()
        for i, (space_len, space_index) in enumerate(spaces):
            if file_index < space_index:
                break
            if space_len >= file_len:
                disk[file_index:file_index + file_len] = [None] * file_len
                disk[space_index:space_index + file_len] = [file_id] * file_len
                if space_len > file_len:
                    spaces[i] = (space_len - file_len, space_index + file_len)
                else:
                    spaces.pop(i)
                break
    return sum(i * (x or 0) for i, x in enumerate(disk))


def day_10_part_1():
    """Solve Day 10 Part 1 puzzle."""
    with open('day_10.txt') as in_file:
        topographic_map = [[int(x) for x in row.strip()] for row in in_file]

    def traverse(root_x, root_y):
        summits = set()
        queue = [(root_x, root_y, 0)]
        while queue:
            x, y, depth = queue.pop(0)
            next_depth = depth + 1
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                in_bounds = 0 <= nx < len(topographic_map[0]) and 0 <= ny < len(topographic_map)
                if in_bounds and topographic_map[ny][nx] == next_depth:
                    if next_depth == 9:
                        summits.add((nx, ny))
                    else:
                        queue.append((nx, ny, next_depth))
        return len(summits)

    total = 0
    for y, row in enumerate(topographic_map):
        for x, cell in enumerate(row):
            if cell == 0:
                total += traverse(x, y)
    return total


def day_10_part_2():
    """Solve Day 10 Part 2 puzzle."""
    with open('day_10.txt') as in_file:
        topographic_map = [[int(x) for x in row.strip()] for row in in_file]

    def traverse(root_x, root_y):
        total = 0
        queue = [(root_x, root_y, 0)]
        while queue:
            x, y, depth = queue.pop(0)
            next_depth = depth + 1
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                in_bounds = 0 <= nx < len(topographic_map[0]) and 0 <= ny < len(topographic_map)
                if in_bounds and topographic_map[ny][nx] == next_depth:
                    if next_depth == 9:
                        total += 1
                    else:
                        queue.append((nx, ny, next_depth))
        return total

    total = 0
    for y, row in enumerate(topographic_map):
        for x, cell in enumerate(row):
            if cell == 0:
                total += traverse(x, y)
    return total


def day_11_part_1():
    """Solve Day 11 Part 1 puzzle."""
    with open('day_11.txt') as in_file:
        stones = [int(x) for x in in_file.read().split(' ')]

    def blink(stones):
        new_stones = []
        for i, stone in enumerate(stones):
            stone_str = str(stone)
            if stone == 0:
                stones[i] = 1
            elif len(stone_str) % 2 == 0:
                midpoint = len(stone_str) // 2
                stones[i] = int(stone_str[:midpoint])
                new_stones.append(int(stone_str[midpoint:]))
            else:
                stones[i] = stone * 2024
        return stones + new_stones

    for _ in range(25):
        stones = blink(stones)
    return len(stones)


def day_11_part_2():
    """Solve Day 11 Part 2 puzzle."""
    with open('day_11.txt') as in_file:
        stones = [int(x) for x in in_file.read().split(' ')]
    stone_counts = Counter(stones)

    def blink(stone_counts):
        new_counts = defaultdict(int)
        for stone, count in stone_counts.items():
            if stone == 0:
                new_counts[1] += count
            elif len(str(stone)) % 2 == 1:
                new_counts[stone * 2024] += count
            else:
                div = 10 ** (len(str(stone)) // 2)
                new_counts[stone // div] += count
                new_counts[stone % div] += count
        return new_counts

    for _ in range(75):
        stone_counts = blink(stone_counts)
    return sum(count for _, count in stone_counts.items())


def day_12_part_1():
    """Solve Day 12 Part 1 puzzle."""
    with open('day_12.txt') as in_file:
        grid = [list(line.strip()) for line in in_file]
    visited = [[False] * len(grid[0]) for _ in range(len(grid))]

    def flood_fill(x, y, target):
        points = set()
        in_bounds = 0 <= y < len(grid) and 0 <= x < len(grid[0])
        if not in_bounds or visited[y][x] or grid[y][x] != target:
            return points
        points.add((x, y))
        visited[y][x] = True
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            points.update(flood_fill(x + dx, y + dy, target))
        return points

    def get_area_and_perimeter(points):
        area = len(points)
        perimeter = 0
        for x, y in points:
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if (x + dx, y + dy) not in points:
                    perimeter += 1
        return area, perimeter

    regions = []
    for y, row in enumerate(grid):
        for x, cell in enumerate(row):
            if not visited[y][x]:
                points = flood_fill(x, y, cell)
                regions.append(get_area_and_perimeter(points))
    return sum(area * perimeter for area, perimeter in regions)


def day_12_part_2():
    """Solve Day 12 Part 2 puzzle."""
    with open('day_12.txt') as in_file:
        grid = [list(line.strip()) for line in in_file]
    visited = [[False] * len(grid[0]) for _ in range(len(grid))]

    def flood_fill(x, y, target):
        points = set()
        in_bounds = 0 <= y < len(grid) and 0 <= x < len(grid[0])
        if not in_bounds or visited[y][x] or grid[y][x] != target:
            return points
        points.add((x, y))
        visited[y][x] = True
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            points.update(flood_fill(x + dx, y + dy, target))
        return points

    def get_area_and_sides(points):
        count = 0
        for x, y in points:
            # The number of sides is equal to the number of corners
            for dx, dy in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
                w, h, d = (x + dx, y), (x, y + dy), (x + dx, y + dy)
                # Convex corners
                # █.   .█   .?   ?.
                # .?   ?.   █.   .█
                if w not in points and h not in points:
                    count += 1
                # Concave corners
                # ██   ██   █.   .█
                # █.   .█   ██   ██
                if w in points and h in points and d not in points:
                    count += 1
        return len(points), count

    regions = []
    for y, row in enumerate(grid):
        for x, cell in enumerate(row):
            if not visited[y][x]:
                points = flood_fill(x, y, cell)
                regions.append(get_area_and_sides(points))
    return sum(area * sides for area, sides in regions)


def day_13_part_1():
    """Solve Day 13 Part 1 puzzle."""
    pattern = re.compile(
        r'Button A: X\+(\d+), Y\+(\d+)\n'
        r'Button B: X\+(\d+), Y\+(\d+)\n'
        r'Prize: X=(\d+), Y=(\d+)'
    )
    def parse(machine):
        return [int(x) for x in pattern.search(machine).groups()]

    with open('day_13.txt') as in_file:
        machines = [parse(machine) for machine in in_file.read().split('\n\n')]

    # This is a linear algebra problem, where we are given the constants
    #     a_x * a + b_x * b = prize_x
    #     a_y * a + b_y * b = prize_y
    #     min(3 * a + b)
    # As a matrix
    #    [ a_x b_x ] [ a ] = [ prize_x ]
    #    [ a_y b_y ] [ b ] = [ prize_y ]
    total = 0
    for a_x, a_y, b_x, b_y, prize_x, prize_y in machines:
        det = a_x * b_y - b_x * a_y
        if det == 0:
            continue
        a = (prize_x * b_y - prize_y * b_x) / det
        b = (a_x * prize_y - a_y * prize_x) / det
        if a >= 0 and b >= 0 and a.is_integer() and b.is_integer():
            total += int(3 * a + b)
    return total


def day_13_part_2():
    """Solve Day 13 Part 2 puzzle."""
    pattern = re.compile(
        r'Button A: X\+(\d+), Y\+(\d+)\n'
        r'Button B: X\+(\d+), Y\+(\d+)\n'
        r'Prize: X=(\d+), Y=(\d+)'
    )
    def parse(machine):
        return [int(x) for x in pattern.search(machine).groups()]

    with open('day_13.txt') as in_file:
        machines = [parse(machine) for machine in in_file.read().split('\n\n')]

    total = 0
    for a_x, a_y, b_x, b_y, prize_x, prize_y in machines:
        prize_x += 10000000000000
        prize_y += 10000000000000
        det = a_x * b_y - b_x * a_y
        if det == 0:
            continue
        a = (prize_x * b_y - prize_y * b_x) / det
        b = (a_x * prize_y - a_y * prize_x) / det
        if a >= 0 and b >= 0 and a.is_integer() and b.is_integer():
            total += int(3 * a + b)
    return total


def day_14_part_1():
    """Solve Day 14 Part 1 puzzle."""
    pattern = re.compile(r'p=(\d+),(\d+) v=(-?\d+),(-?\d+)')
    with open('day_14.txt') as in_file:
        robots = [[int(x) for x in pattern.search(robot).groups()] for robot in in_file]

    w, h = 101, 103
    for _ in range(100):
        for i, (x, y, dx, dy) in enumerate(robots):
            x = (x + dx) % w
            y = (y + dy) % h
            robots[i] = (x, y, dx, dy)
    quadrants = [0] * 4
    m_x, m_y = w // 2, h // 2
    for x, y, _, _ in robots:
        if x == m_x or y == m_y:
            continue
        quadrant = 2 * (x > m_x) + (y > m_y)
        quadrants[quadrant] += 1
    return prod(quadrants)


def day_14_part_2():
    """Solve Day 14 Part 2 puzzle."""
    pattern = re.compile(r'p=(\d+),(\d+) v=(-?\d+),(-?\d+)')
    with open('day_14.txt') as in_file:
        robots = [[int(x) for x in pattern.search(robot).groups()] for robot in in_file]

    w, h = 101, 103

    def render(robots):
        grid = [[' '] * w for _ in range(h)]
        for x, y, _, _ in robots:
            grid[y][x] = '#'
        return '\n'.join(''.join(row) for row in grid)

    for number_of_seconds in range(1, 100000):
        for i, (x, y, dx, dy) in enumerate(robots):
            x = (x + dx) % w
            y = (y + dy) % h
            robots[i] = (x, y, dx, dy)

        # Metric to filter through the search space
        row_counts = Counter(y for _, y, _, _ in robots)
        col_counts = Counter(x for x, _, _, _ in robots)
        max_row = max(row_counts.values())
        max_col = max(col_counts.values())
        if max_row * max_col > 600:
            print(f'\nSeconds = {number_of_seconds}')
            print(render(robots))
            input()

    return number_of_seconds


def day_15_part_1():
    """Solve Day 15 Part 1 puzzle."""
    with open('day_15.txt') as in_file:
        raw_map, raw_instructions = in_file.read().split('\n\n')
    warehouse = [list(row) for row in raw_map.splitlines()]
    instructions = raw_instructions.replace('\n', '')

    robot = next((x, y)
        for y, row in enumerate(warehouse) for x, cell in enumerate(row)
        if cell == '@'
    )
    moves = {
        '^': (0, -1),
        '>': (1, 0),
        'v': (0, 1),
        '<': (-1, 0),
    }

    for instruction in instructions:
        rx, ry = robot
        dx, dy = moves[instruction]
        nx, ny = rx + dx, ry + dy
        if warehouse[ny][nx] == '#':
            continue
        elif warehouse[ny][nx] == '.':
            robot = (nx, ny)
            warehouse[ny][nx] = '@'
            warehouse[ry][rx] = '.'
        elif warehouse[ny][nx] == 'O':
            ox, oy = nx, ny
            to_move = []
            while warehouse[oy][ox] == 'O':
                ox += dx
                oy += dy
                to_move.append((ox, oy))
            if warehouse[oy][ox] == '.':
                for x, y in to_move:
                    warehouse[y][x] = 'O'
                robot = (nx, ny)
                warehouse[ny][nx] = '@'
                warehouse[ry][rx] = '.'

    # print('\n'.join(''.join(row) for row in warehouse))

    return sum(x + 100 * y
        for y, row in enumerate(warehouse) for x, cell in enumerate(row)
        if cell == 'O'
    )

def day_15_part_2():
    """Solve Day 15 Part 2 puzzle."""
    # DOES NOT WORK
    # Could not think of elegant way of doing this
    # Inelegant way was boring
    with open('day_15_test.txt') as in_file:
        raw_map, raw_instructions = in_file.read().split('\n\n')

    raw_map = (raw_map
        .replace('#', '##')
        .replace('O', '[]')
        .replace('.', '..')
        .replace('@', '@.')
    )
    warehouse = [list(row) for row in raw_map.splitlines()]
    instructions = raw_instructions.replace('\n', '')

    boxes = set()
    walls = set()
    for y, row in enumerate(warehouse):
        for x, cell in enumerate(row):
            if cell == '[':
                boxes.add((x, y))
            elif cell == '#':
                walls.add((x, y))
            elif cell == '@':
                robot = (x, y)

    moves = {
        '^': (0, -1),
        '>': (1, 0),
        'v': (0, 1),
        '<': (-1, 0),
    }
    for instruction in instructions:
        rx, ry = robot
        dx, dy = moves[instruction]
        nx, ny = rx + dx, ry + dy
        if (nx, ny) in walls:
            continue
        # Moving right, hits box
        elif dx == 1 and (nx, ny) in boxes:
            ox, oy = nx, ny
            to_move = []
            while (ox, oy) in boxes:
                to_move.append((ox, oy))
                ox += 2
            if (ox, oy) not in walls:
                for x, y in to_move:
                    boxes.add((x + 1, y))
                    boxes.remove((x, y))
                robot = (nx, ny)
        # Moving left, hits box
        elif dx == -1 and (nx - 1, ny) in boxes:
            ox, oy = nx, ny
            to_move = []
            while (ox, oy) in boxes:
                to_move.append((ox, oy))
                ox -= 2
            if (ox, oy) not in walls:
                for x, y in to_move:
                    boxes.add((x - 1, y))
                    boxes.remove((x, y))
                robot = (nx, ny)
        # Moving up, hits left box
        elif dy == -1 and (nx, ny) in boxes:
            ox, oy = nx, ny
            box_row = [(ox, oy)]
            to_move = []
            for (bx, by) in box_row:
                if (bx - 1, by - 1) in boxes:
                    continue
        # Moving up, hits right box
        elif dy == -1 and (nx - 1, ny) in boxes:
            continue
        # Moving down, hits box
        elif dy == 1 and ((nx, ny) in boxes or (nx - 1, ny) in boxes):
            continue
        else:
            robot = (nx, ny)

    def render():
        output = []
        for y, _ in enumerate(warehouse):
            new_row = ''
            for x, _ in enumerate(row):
                if (x, y) in walls:
                    new_row += '#'
                elif (x, y) in boxes:
                    new_row += '['
                elif (x - 1, y) in boxes:
                    new_row += ']'
                elif (x, y) == robot:
                    new_row += '@'
                else:
                    new_row += ' '
            output.append(new_row)
        return '\n'.join(output)

    print(render())
    return sum(x + 100 * y
        for y, row in enumerate(warehouse) for x, cell in enumerate(row)
        if cell == '['
    )


def day_16_part_1():
    """Solve Day 16 Part 1 puzzle."""
    with open('day_16.txt') as in_file:
        maze = [list(row) for row in in_file.read().splitlines()]
    start = next((x, y) for y, row in enumerate(maze) for x, cell in enumerate(row) if cell == 'S')

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = [(start, 0, (1, 0))]
    traversed = set()
    while True:
        (x, y), distance, direction = queue.pop(0)
        if maze[y][x] == 'E':
            return distance
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if maze[ny][nx] == '#' or (nx, ny) in traversed:
                continue
            if (dx, dy) == direction:
                points = 0
            elif (-dx, -dy) == direction:
                points = 2000
            else:
                points = 1000
            queue.append(((nx, ny), distance + 1 + points, (dx, dy)))
            traversed.add((x, y))
        queue.sort(key=lambda x: x[1])


def day_16_part_2():
    """Solve Day 16 Part 2 puzzle."""
    with open('day_16.txt') as in_file:
        maze = [list(row) for row in in_file.read().splitlines()]
    start = next((x, y) for y, row in enumerate(maze) for x, cell in enumerate(row) if cell == 'S')

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = [(start, 0, (1, 0), [start])]
    traversed = {}
    winning_score = 98484
    winning_paths = set()
    while queue:
        (x, y), distance, direction, path = queue.pop(0)
        if maze[y][x] == 'E':
            winning_paths |= set(path)
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if maze[ny][nx] == '#':
                continue
            if (dx, dy) == direction:
                points = 0
            elif (-dx, -dy) == direction:
                points = 2000
            else:
                points = 1000
            new_score = distance + 1 + points
            if traversed.get((nx, ny), winning_score) < new_score:
                continue
            p = path.copy()
            p.append((nx, ny))
            queue.append(((nx, ny), new_score, (dx, dy), p))
            traversed[(x, y)] = new_score
        queue.sort(key=lambda x: x[1])
    return len(winning_paths)


def day_17_part_1():
    """Solve Day 17 Part 1 puzzle."""
    pattern = re.compile(
        r'Register A: (\d+)\n'
        r'Register B: (\d+)\n'
        r'Register C: (\d+)\n\n'
        r'Program: ([\d,]+)'
    )
    with open('day_17.txt') as in_file:
        data = pattern.search(in_file.read()).groups()
    registers = [int(x) for x in data[:-1]]
    program = [int(x) for x in data[-1].split(',')]

    pointer = 0
    output = []

    def combo(x):
        return x if x < 4 else registers[x - 4]

    def adv(x):
        registers[0] = registers[0] // 2**combo(x)

    def bxl(x):
        registers[1] = registers[1] ^ x

    def bst(x):
        registers[1] = combo(x) % 8

    def jnz(x):
        nonlocal pointer
        if registers[0] != 0 and pointer != x:
            pointer = x - 2

    def bxc(x):
        registers[1] ^= registers[2]

    def out(x):
        output.append(combo(x) % 8)

    def bdv(x):
        registers[1] = registers[0] // 2**combo(x)

    def cdv(x):
        registers[2] = registers[0] // 2**combo(x)

    instructions = [adv, bxl, bst, jnz, bxc, out, bdv, cdv]
    while pointer < len(program):
        opcode, operand = program[pointer:pointer + 2]
        instructions[opcode](operand)
        pointer += 2
    return ','.join(str(x) for x in output)


def day_17_part_2():
    """Solve Day 17 Part 2 puzzle."""
    pattern = re.compile(
        r'Register A: (\d+)\n'
        r'Register B: (\d+)\n'
        r'Register C: (\d+)\n\n'
        r'Program: ([\d,]+)'
    )
    with open('day_17_test.txt') as in_file:
        data = pattern.search(in_file.read()).groups()
    registers = [int(x) for x in data[:-1]]
    program = [int(x) for x in data[-1].split(',')]

    # HERE
    # Idea is to invert the program and run it backwards
    # to get to initial register state
    # 2,4,1,1,7,5,4,6,0,3,1,4,5,5,3,0
    # bst, bxc, bxl

    output = program.copy()

    def combo(x):
        return x if x < 4 else registers[x - 4]

    def adv(x):
        registers[0] = registers[0] // 2**combo(x)

    def bxl(x):
        registers[1] = registers[1] ^ x

    def bst(x):
        registers[1] = combo(x) % 8

    def jnz(x):
        nonlocal pointer
        if registers[0] != 0 and pointer != x:
            pointer = x - 2

    def bxc(x):
        registers[1] ^= registers[2]

    def out(x):
        output.append(combo(x) % 8)

    def bdv(x):
        registers[1] = registers[0] // 2**combo(x)

    def cdv(x):
        registers[2] = registers[0] // 2**combo(x)

    instructions = [adv, bxl, bst, jnz, bxc, out, bdv, cdv]

    for a in range(100000000, 10000000000000):
        if a % 100000 == 0:
            print(a)
        registers = [a, 0, 0]
        output = []
        pointer = 0
        while pointer < len(program):
            opcode, operand = program[pointer:pointer + 2]
            instructions[opcode](operand)
            pointer += 2
        if ','.join(str(x) for x in output) == data[-1]:
            return a

parser = argparse.ArgumentParser(description="Run 2024 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()}")