Advent of Code 2024

from functools import reduce


# Part 1
left_list = []
right_list = []

with open("./input.txt", "r") as input_file:
    for line in input_file.readlines():
        left_num, right_num = map(lambda s: int(s), line.split())
        left_list.append(left_num)
        right_list.append(right_num)

left_list = sorted(left_list)
right_list = sorted(right_list)

total_distance = reduce(lambda acc, pair: acc + abs(pair[0] - pair[1]), zip(left_list, right_list), 0)

print(f"Total Distance is {total_distance}")

# Part 2
total_similarity = 0
for left_num in left_list:
    total_similarity += right_list.count(left_num) * left_num

print(f"Total Similarity is {total_similarity}")

from typing import List


def is_report_safe(report: List[int]) -> bool:
    # Replace the sequence by the sequence of adjacent pair differences
    differences = []
    for x in range(len(report) - 1):
        differences.append(report[x] - report[x + 1])

    # Check that the sign is the same across all differences
    if not all(d < 0 for d in differences) and not all(d >= 0 for d in differences):
        return False

    # Check that the magnitude of each difference is in the correct range
    if not all(abs(d) >= 1 and abs(d) <= 3 for d in differences):
        return False

    return True


with open("./input.txt", "r") as input_file:
    input_lines = input_file.readlines()

safe_reports = 0

# Problem Dampener safe reports
pd_safe_reports = 0
for line in input_lines:
    numbers = list(map(lambda s: int(s), line.split()))

    if is_report_safe(numbers):
        safe_reports += 1
    else:
        # Get every report with a number removed
        tolerable_candidates = []
        for x in range(len(numbers)):
            tolerable_candidates.append(numbers[:x] + numbers[x+1:])

        if any(is_report_safe(tc) for tc in tolerable_candidates):
            pd_safe_reports += 1

print(f"(Part 1) Number of safe reports: {safe_reports}")
print(f"(Part 2) Number of safe reports: {safe_reports + pd_safe_reports}")

import re


with open("./input.txt", "r") as input_file:
    input_text = input_file.read()

# Part 1
mul_regex = re.compile(r"mul\((\d{1,3}),(\d{1,3})\)")
matches = mul_regex.finditer(input_text)

total = sum(map(lambda m: int(m.group(1)) * int(m.group(2)), matches))
print(f"(Part 1) Total is {total}")

# Part 2
mul_regex = re.compile(r"mul\((\d{1,3}),(\d{1,3})\)|don't\(\)|do\(\)")
matches = mul_regex.finditer(input_text)

total = 0
is_enabled = True  # Enabled by default
for match in matches:
    if match.group(0) == "do()":
        is_enabled = True
    elif match.group(0) == "don't()":
        is_enabled = False
    elif is_enabled:
        total += int(match.group(1)) * int(match.group(2))

print(f"(Part 2) Total is {total}")

with open("./input.txt", "r") as input_file:
    input_lines = input_file.readlines()

xmas_count = 0
for line_index in range(len(input_lines)):
    current_line = input_lines[line_index]

    for char_index in range(len(current_line)):
        if current_line[char_index] == "X":
            # There are 8 strings 'next' to the 'X' which could spell "MAS". Store them in
            # `candidates`.
            candidates = []

            # To the right of 'X'
            if char_index + 3 < len(current_line):
                candidates.append(current_line[char_index+1:char_index+4])

            # To the left of 'X'
            if char_index-3 >= 0:
                candidates.append(current_line[char_index-3:char_index][::-1])

            # Above 'X'
            if line_index - 3 >= 0:
                candidates.append(
                    input_lines[line_index - 1][char_index] +
                    input_lines[line_index - 2][char_index] +
                    input_lines[line_index - 3][char_index]
                )

            # Below 'X'
            if line_index + 3 < len(input_lines):
                candidates.append(
                    input_lines[line_index + 1][char_index] +
                    input_lines[line_index + 2][char_index] +
                    input_lines[line_index + 3][char_index]
                )

            # Diagonally above-and-to-the-right of 'X'
            if char_index + 3 < len(current_line) and line_index - 3 >= 0:
                candidates.append(
                    input_lines[line_index - 1][char_index + 1] +
                    input_lines[line_index - 2][char_index + 2] +
                    input_lines[line_index - 3][char_index + 3]
                )

            # Diagonally above-and-to-the-left of 'X'
            if char_index - 3 >= 0 and line_index - 3 >= 0:
                candidates.append(
                    input_lines[line_index - 1][char_index - 1] +
                    input_lines[line_index - 2][char_index - 2] +
                    input_lines[line_index - 3][char_index - 3]
                )

            # Diagonally below-and-to-the-right of 'X'
            if char_index + 3 < len(current_line) and line_index + 3 < len(input_lines):
                candidates.append(
                    input_lines[line_index + 1][char_index + 1] +
                    input_lines[line_index + 2][char_index + 2] +
                    input_lines[line_index + 3][char_index + 3]
                )

            # Diagonally below-and-to-the-left of 'X'
            if char_index - 3 >= 0 and line_index + 3 < len(input_lines):
                candidates.append(
                    input_lines[line_index + 1][char_index - 1] +
                    input_lines[line_index + 2][char_index - 2] +
                    input_lines[line_index + 3][char_index - 3]
                )

            # Any candidate equal to "MAS" means we have a spelling of "XMAS"
            xmas_count += sum(map(lambda c: 1 if c == "MAS" else 0, candidates))

print(f"(Part 1) Count is {xmas_count}")

x_mas_count = 0
for line_index in range(len(input_lines)):
    current_line = input_lines[line_index]

    for char_index in range(len(current_line)):
        if current_line[char_index] == "A":
            # Only consider 'A's that are not on the 'border' of the input
            if (line_index + 1 >= len(input_lines) or
                    line_index - 1 < 0 or
                    char_index + 1 >= len(current_line) or
                    char_index - 1 < 0):
                continue

            # Get the four characters in the relevant positions
            top_left_char = input_lines[line_index - 1][char_index - 1]
            top_right_char = input_lines[line_index - 1][char_index + 1]
            bottom_left_char = input_lines[line_index + 1][char_index - 1]
            bottom_right_char = input_lines[line_index + 1][char_index + 1]

            # Check that we have two crossing 'MAS'
            if (
                # Check for a "MAS" or "SAM" from top-left to bottom-right
                (
                    (top_left_char == "M" and bottom_right_char == "S") or
                    (top_left_char == "S" and bottom_right_char == "M")
                )
                and
                # Check for a "MAS" or "SAM" from top-right to bottom-left
                (
                    (top_right_char == "M" and bottom_left_char == "S") or
                    (top_right_char == "S" and bottom_left_char == "M")
                )
            ):
                x_mas_count += 1

print(f"(Part 2) Count is {x_mas_count}")

from collections import defaultdict
from typing import Dict, List, Optional, Tuple
import re


def get_update_issue(update: List[int]) -> Optional[Tuple[int, int]]:
    """
    Given an update, looks for an issue with the ordering of that update. If one is found,
    returns a tuple `(idx1, idx2)`, where the page at `idx1` should be before the page at
    `idx2`.
    """
    for page_index in range(len(update)):
        current_page = update[page_index]
        already_seen_pages = update[:page_index]

        # We can determine whether the update is valid by checking whether any page which
        # should **not be** before the current is actually before it
        if set(already_seen_pages) & set(page_to_before_list[current_page]) != set():
            # `page_index` is in-front of some element which it should be behind --- we
            # take the index of the earliest violation of this, to reduce iterations.
            return (page_index, update.index(already_seen_pages[0]))

    return None


# Create a mapping such that a given page number maps to all page numbers that the given
# page number needs to appear before
page_to_before_list: Dict[int, List[int]] = defaultdict(list)
page_ordering_rule_re = re.compile(r"(\d+)\|(\d+)")
with open("./page_ordering_rules.txt", "r") as file:
    for line in file.readlines():
        for match in page_ordering_rule_re.finditer(line):
            page_to_before_list[int(match.group(1))].append(int(match.group(2)))

# Retrieve the updates, converting each string-form list to a Python list of `int`s
with open("./pages_to_produce_in_each_update.txt", "r") as file:
    updates = map(lambda line: list(map(lambda s: int(s), line.split(","))), file.readlines())

middle_number_total = 0

# For Part 2, keep track of all incorrectly-ordered updates
incorrectly_ordered_updates: List[List[int]] = []

for update in updates:
    if get_update_issue(update) is None:
        # There is no update issue, so the update is valid, and we can add the
        # middle-number to the running total
        middle_number_total += update[len(update) // 2]
    else:
        incorrectly_ordered_updates.append(update)

print(f"(Part 1) Total is {middle_number_total}")

fixed_middle_number_total = 0
for update in incorrectly_ordered_updates:
    # Determine what the issue is
    update_issue = get_update_issue(update)

    # We'll keep fixing issues until no more are remaining
    while update_issue is not None:
        bad_elem_idx, insert_idx = update_issue

        # Copy a value of the bad element, as we will delete it from the list
        bad_elem = update[bad_elem_idx]
        del update[bad_elem_idx]

        # Re-insert that bad element, but at a place which reduces the violations
        update.insert(insert_idx, bad_elem)

        # Check if there is still an ordering issue
        update_issue = get_update_issue(update)

    fixed_middle_number_total += update[len(update) // 2]

print(f"(Part 2) Total is {fixed_middle_number_total}")

from collections import defaultdict
from enum import Enum
from typing import Dict, List, Set, Tuple


Direction = Enum("Direction", ["UP", "RIGHT", "DOWN", "LEFT"])

with open("./input.txt", "r") as input_file:
    world_lines = input_file.readlines()

# NOTE: We treat the top-left co-ordinate of the world (the input) as `(0,0)`.
# Determine where the guard starts, as well as the location of every obstacle.
starting_pos = (-1, -1)
obstacle_coords = []
for line_index, line in enumerate(world_lines):
    if "^" in line:
        starting_pos = (line.index("^"), line_index)
    obstacle_coords += [(char_index, line_index) for char_index, char in enumerate(line) if char == "#"]
assert starting_pos != (-1, -1)

# For the sake of quicker computation, store each obstacle indexed by it's x-coordinate
# and it's y-coordinate
x_coord_to_obstacles: Dict[int, List[int]] = defaultdict(list)
y_coord_to_obstacles: Dict[int, List[int]] = defaultdict(list)
for obstacle_coord in obstacle_coords:
    x_coord_to_obstacles[obstacle_coord[0]].append(obstacle_coord[1])
    y_coord_to_obstacles[obstacle_coord[1]].append(obstacle_coord[0])

# Keep a set of all coordinates that the guard has visited
visited_locations = set([starting_pos])

# The guard initially faces up
guard_direction = Direction.UP

# (Part 2) Keep a list of in-order visited coordinates, representing the guard's path
original_guard_path = [starting_pos]

current_position = starting_pos
while True:
    # Check if the guard is about to move-out-of-bounds
    match guard_direction:
        case Direction.UP:
            if current_position[1] == 0:
                break
        case Direction.RIGHT:
            if current_position[0] == len(world_lines[0]) - 1:
                break
        case Direction.DOWN:
            if current_position[1] == len(world_lines) - 1:
                break
        case Direction.LEFT:
            if current_position[0] == 0:
                break

    # The guard is not moving out of bounds, so we can get the intended move
    match guard_direction:
        case Direction.UP:
            intended_move = (current_position[0], current_position[1] - 1)
        case Direction.RIGHT:
            intended_move = (current_position[0] + 1, current_position[1])
        case Direction.DOWN:
            intended_move = (current_position[0], current_position[1] + 1)
        case Direction.LEFT:
            intended_move = (current_position[0] - 1, current_position[1])

    # Check if we would be hitting an obstacle
    if world_lines[intended_move[1]][intended_move[0]] == "#":
        # If so, turn-right
        match guard_direction:
            case Direction.UP:
                guard_direction = Direction.RIGHT
            case Direction.RIGHT:
                guard_direction = Direction.DOWN
            case Direction.DOWN:
                guard_direction = Direction.LEFT
            case Direction.LEFT:
                guard_direction = Direction.UP

        continue

    # We have not hit an obstacle, so move to the new location
    current_position = intended_move
    original_guard_path.append(current_position)
    visited_locations.add(current_position)

print(f"(Part 1) {len(visited_locations)}")

#########
# Part 2
#########
def does_loop(new_obstacle_coord):
    # The guard initially faces up
    guard_direction = Direction.UP

    current_position = starting_pos

    # Keep track of visited locations and the direction, to assert a loop
    guard_path: Set[Tuple[Tuple[int, int], Direction]] = set([(current_position, guard_direction)])

    while True:
        # For each case, we determine the obstacles that are in the way for the direction
        # of movement corresponding to that case.
        #
        # If there is no such obstacle, then the guard moves out of the world (and there
        # thus cannot be a loop).
        #
        # Otherwise, there is at least one obstacle along that direction, so we move the
        # guard to it and turn them right.
        match guard_direction:
            case Direction.UP:
                obstacles_in_direction = list(filter(
                    lambda c: c < current_position[1],
                    x_coord_to_obstacles[current_position[0]] + (
                        [] if new_obstacle_coord[0] != current_position[0] else [new_obstacle_coord[1]]
                    )
                ))

                if obstacles_in_direction == []:
                    return False

                obstacles_in_direction.sort()
                nearest_obstacle = obstacles_in_direction[::-1][0]

                current_position = (current_position[0], nearest_obstacle + 1)
                guard_direction = Direction.RIGHT
            case Direction.RIGHT:
                obstacles_in_direction = list(filter(
                    lambda c: c > current_position[0],
                    y_coord_to_obstacles[current_position[1]] + (
                        [] if new_obstacle_coord[1] != current_position[1] else [new_obstacle_coord[0]]
                    )
                ))

                if obstacles_in_direction == []:
                    return False

                obstacles_in_direction.sort()
                nearest_obstacle = obstacles_in_direction[0]

                current_position = (nearest_obstacle - 1, current_position[1])
                guard_direction = Direction.DOWN
            case Direction.DOWN:
                obstacles_in_direction = list(filter(
                    lambda c: c > current_position[1],
                    x_coord_to_obstacles[current_position[0]] + (
                        [] if new_obstacle_coord[0] != current_position[0] else [new_obstacle_coord[1]]
                    )
                ))

                if obstacles_in_direction == []:
                    return False

                obstacles_in_direction.sort()
                nearest_obstacle = obstacles_in_direction[0]

                current_position = (current_position[0], nearest_obstacle - 1)
                guard_direction = Direction.LEFT
            case Direction.LEFT:
                obstacles_in_direction = list(filter(
                    lambda c: c < current_position[0],
                    y_coord_to_obstacles[current_position[1]] + (
                        [] if new_obstacle_coord[1] != current_position[1] else [new_obstacle_coord[0]]
                    )
                ))

                if obstacles_in_direction == []:
                    return False

                obstacles_in_direction.sort()
                nearest_obstacle = obstacles_in_direction[::-1][0]

                current_position = (nearest_obstacle + 1, current_position[1])
                guard_direction = Direction.UP

        # Check for a loop (i.e. a state that we have previously been to)
        if (current_position, guard_direction) in guard_path:
            return True

        guard_path.add((current_position, guard_direction))

# Fact: An obstacle causing a loop **must** be placed along the original guard path, as
# otherwise, the guard's path would remain the same.
num_of_obstacles_causing_loop = len(set(filter(lambda coord: does_loop(coord), original_guard_path)))

print(f"(Part 2) {num_of_obstacles_causing_loop}")

import re
from typing import Iterable, List, Tuple


# Represent each equation as a 2-tuple, where the first element is the target number, and
# the second element is the list of operands
Equation = Tuple[int, List[int]]

# Regex which extracts the target number (Group 1) and input numbers (Group 2)
equation_regex = re.compile(r"(\d*): ((?:\d* ?)*)")

with open("./input.txt", "r") as input_file:
    lines = input_file.readlines()

    equations: List[Equation] = list(map(
        lambda l: (
            int(equation_regex.findall(l)[0][0]),
            list(map(lambda s: int(s), equation_regex.findall(l)[0][1].split()))
        ),
        lines
    ))

#########
# Part 1
#########
total = 0
for equation in equations:
    # We repeatedly break the equation into subproblems by looking at how the final number
    # can be used
    subproblems: Iterable[Equation] = [equation]

    while subproblems != []:
        subproblem = subproblems.pop()
        target_number = subproblem[0]
        remaining_operands = subproblem[1]

        # Determine whether the subproblem is solved, i.e. if there is only one operand
        # left, and it is equal to the target number
        if len(remaining_operands) == 1:
            if target_number == remaining_operands[0]:
                total += equation[0]
                break
            else:
                continue

        final_operand = remaining_operands[-1]
        if target_number % final_operand == 0:
            # If the target number is divisible by the final number, then the final number
            # could be used as a product
            subproblems.append((int(target_number / final_operand), remaining_operands[:-1]))

        # The final number could be used as an addition. Note that if the target number
        # goes negative, the subproblem will fail anyway.
        subproblems.append((target_number - final_operand, remaining_operands[:-1]))

print(f"(Part 1) Total calibration result is {total}")


#########
# Part 2
#########
total = 0
for equation in equations:
    # We repeatedly break the equation into subproblems by looking at how the final number
    # can be used
    subproblems: Iterable[Equation] = [equation]

    while subproblems != []:
        subproblem = subproblems.pop()
        target_number = subproblem[0]
        remaining_operands = subproblem[1]

        # Determine whether the subproblem is solved, i.e. if there is only one operand
        # left, and it is equal to the target number
        if len(remaining_operands) == 1:
            if target_number == remaining_operands[0]:
                total += equation[0]
                break
            else:
                continue

        final_operand = remaining_operands[-1]
        if target_number % final_operand == 0:
            # If the target number is divisible by the final number, then the final number
            # could be used as a product
            subproblems.append((int(target_number / final_operand), remaining_operands[:-1]))

        # The final number could be used as an addition.
        # Note that we now explicitly do not add a subproblem if the target number is
        # negative, as otherwise, the minus sign interferes with the code for the
        # concatenation case.
        if target_number - final_operand >= 0:
            subproblems.append((target_number - final_operand, remaining_operands[:-1]))

        # Account for the concatenation operator
        final_operand_num_digits = len(str(final_operand))

        # Ensure that the target number has at least as many digits as the final operand,
        # so that string slicing is easier to reason about
        if len(str(target_number)) >= final_operand_num_digits:
            # Check that the final digits of the target number is the same as the final
            # operand
            if int(str(target_number)[-final_operand_num_digits:]) == final_operand:
                # Append the subproblem which simulates the concatenation taking place
                new_target_str = str(target_number)[:-final_operand_num_digits]

                if new_target_str == "":
                    # Treat the empty string as a 0
                    subproblems.append((0, remaining_operands[:-1]))
                else:
                    subproblems.append((int(str(target_number)[:-final_operand_num_digits]), remaining_operands[:-1]))

print(f"(Part 2) Total calibration result is {total}")

from collections import defaultdict
from typing import Dict, Iterable, List, Set, Tuple
import itertools


# Note: We essentially use the screen coordinate system
Coord = Tuple[int, int]

with open("./input.txt", "r") as input_file:
    world_lines = list(map(lambda l: l.strip(), input_file.readlines()))

# For every antenna, get a list of locations of that antenna
antenna_to_locations: Dict[str, List[Coord]] = defaultdict(list)
for line_index, line in enumerate(world_lines):
    for char_index, char in enumerate(line):
        if char.isalnum():
            antenna_to_locations[char].append((char_index, line_index))

all_antinode_locations: Set[Coord] = set()
for frequency, antennas in antenna_to_locations.items():
    # Consider every pair of the same antenna frequency
    for (antenna1, antenna2) in itertools.combinations(antennas, 2):
        # Get the vector from `antenna1` to `antenna2`
        a1Toa2 = (antenna2[0] - antenna1[0], antenna2[1] - antenna1[1])

        # Determine the antinode locations
        antinode_locations: Iterable[Coord] = [
            (antenna1[0] - a1Toa2[0], antenna1[1] - a1Toa2[1]),
            (antenna2[0] + a1Toa2[0], antenna2[1] + a1Toa2[1])
        ]

        # Ensure that no antinode is outside the world border
        antinode_locations = filter(
            lambda c: c[0] >= 0 and c[0] < len(world_lines[0]) and c[1] >= 0 and c[1] < len(world_lines),
            antinode_locations
        )

        # Add the antinodes to the global set
        for antinode_location in antinode_locations:
            all_antinode_locations.add(antinode_location)

print(f"(Part 1) Unique antinode locations: {len(all_antinode_locations)}")


#########
# Part 2
#########
def is_coord_valid(c: Coord) -> bool:
    return c[0] >= 0 and c[0] < len(world_lines[0]) and c[1] >= 0 and c[1] < len(world_lines)


all_antinode_locations: Set[Coord] = set()
for frequency, antennas in antenna_to_locations.items():
    # Consider every pair of the same antenna frequency
    for (antenna1, antenna2) in itertools.combinations(antennas, 2):
        # Get the vector from `antenna1` to `antenna2`
        a1Toa2 = (antenna2[0] - antenna1[0], antenna2[1] - antenna1[1])

        # Determine the antinode locations, first going 'backwards' from the first
        # antenna. Note that we also include the first antenna here, as it is part of a
        # pair.
        new_antinode_location = antenna1
        while is_coord_valid(new_antinode_location):
            all_antinode_locations.add(new_antinode_location)

            # Move 'backwards' again
            new_antinode_location = (new_antinode_location[0] - a1Toa2[0], new_antinode_location[1] - a1Toa2[1])

        # Now determine the antinode locations, going 'forwards' from the first antenna
        new_antinode_location = (antenna1[0] + a1Toa2[0], antenna1[1] + a1Toa2[1])
        while is_coord_valid(new_antinode_location):
            all_antinode_locations.add(new_antinode_location)

            # Move 'forwards' again
            new_antinode_location = (new_antinode_location[0] + a1Toa2[0], new_antinode_location[1] + a1Toa2[1])

print(f"(Part 2) Unique antinode locations: {len(all_antinode_locations)}")

#########
# Part 1
#########
from typing import List, Tuple
with open("./input.txt", "r") as input_file:
    disk_map = list(map(lambda c: int(c), list(input_file.read().strip())))

# Have two pointers, which each store the index of a position in the disk map.
# If the index is even, then the pointer is at a file, otherwise it is at free space.
left_ptr = 0
right_ptr = len(disk_map) - 1

# Keep track of the number of blocks processed from the 'left', where 'processed' means
# added to the checksum
processed_blocks = 0

checksum: bool = 0
while True:
    # The left pointer starts the `while` loop as an even index, so determine the
    # checksum contribution of the file there
    assert left_ptr % 2 == 0
    for _ in range(disk_map[left_ptr]):
        checksum += processed_blocks * int(left_ptr / 2)
        processed_blocks += 1

    left_ptr += 1

    # If the left pointer has advanced past the right, then all file blocks have been
    # processed, so we are finished
    if left_ptr > right_ptr:
        break

    # The left pointer is now in free space, so take file blocks from the end until the
    # free space is filled-up
    while disk_map[left_ptr] > 0:
        # Simulate moving a file block from the end and calculating its checksum
        # contribution
        disk_map[right_ptr] -= 1
        checksum += processed_blocks * int(right_ptr / 2)
        processed_blocks += 1
        disk_map[left_ptr] -= 1

        # If the file on the end has finished being moved, then move the right pointer to
        # the next rightmost file
        if disk_map[right_ptr] == 0:
            right_ptr -= 2

            # If the right pointer has now moved behind the left pointer, then there are
            # no more files that we can move into the empty space. Note that we can use a
            # strict inequality, as `right_ptr` and `left_ptr` have different parity here.
            if right_ptr < left_ptr:
                break

    # The free space has finished being processed
    left_ptr += 1

print(f"(Part 1) Checksum is {checksum}")


#########
# Part 2
#########
# A file is a 2-tuple where the first element is the file ID, and the second elements is
# its size
File = Tuple[int, int]


class Segment:
    def __init__(self, max_capacity: int) -> None:
        self.available_capacity = max_capacity
        self.max_capacity = max_capacity

        # Store each file 'contiguously' within the capacity
        self.files: List[File] = []

    def add_file(self, file: File) -> None:
        self.files.append(file)
        self.available_capacity -= file[1]

    def empty(self) -> None:
        self.files = []
        self.available_capacity = self.max_capacity

    def __repr__(self) -> str:
        return f"{{available_capacity: {self.available_capacity}/{self.max_capacity}, files: {self.files}}}"


# Read the input into a list of `Segment`s
segment_disk_map: List[Segment] = []
with open("./input.txt", "r") as input_file:
    for char_index, char in enumerate(input_file.read().strip()):
        if char_index % 2 == 0:
            segment = Segment(int(char))
            segment.add_file((int(char_index / 2), int(char)))
            segment_disk_map.append(segment)
        else:
            segment = Segment(int(char))
            segment_disk_map.append(segment)

# Start from the rightmost file (we assume here that the rightmost file has an even
# index)
right_ptr = len(disk_map) - 1
while True:
    # Determine the space needed for the rightmost file. We assume that there is exactly
    # one file in this segment, as we are only considering even indices (i.e. indices
    # which have exactly one file in)
    file_to_move = segment_disk_map[right_ptr].files[0]
    space_needed: bool = file_to_move[1]

    # Iterate across every odd integer up to the right pointer (files cannot be moved past
    # the right pointer can only be moved into odd indices)
    for i in range(1, right_ptr, 2):
        if segment_disk_map[i].available_capacity >= space_needed:
            # Move the file
            segment_disk_map[i].add_file(file_to_move)
            segment_disk_map[right_ptr].empty()

            # The file has been moved --- we don't need to consider more spans of space,
            # and can move to the next rightmost even file
            break

    # The file failed to be moved, so iterate towards the next rightmost even file
    right_ptr -= 2

    if right_ptr == 0:
        break

# Determine the checksum
checksum = 0
processed_blocks = 0
for segment in segment_disk_map:
    for file in segment.files:
        # Consider each block of the file
        for _ in range(file[1]):
            # Add the product of the file ID and the global index of the block
            checksum += file[0] * processed_blocks
            processed_blocks += 1

    # If there is any available capacity left, it must be on the 'right' of the segment,
    # and we consider it here
    processed_blocks += segment.available_capacity

print(f"(Part 2) Checksum is {checksum}")

from typing import List, Tuple


Coord = Tuple[int, int]

with open ("./input.txt", "r") as input_file:
    world = list(map(lambda row: list(map(lambda char: int(char), row)), input_file.read().split()))

# Determine every position in the world with an elevation of 0
start_candidates: List[Coord] = []
for world_y, row in enumerate(world):
    start_candidates += [(world_x, world_y) for world_x, num in enumerate(row) if num == 0]

# For Part 1
total_score = 0
# For Part 2
total_rating = 0
for start_candidate in start_candidates:
    # Keep track of unique elevations of 9 which are reachable from `start_candidate`
    reachable_nines = set()

    # Maintain a collection of paths which we are exploring along
    paths = [[start_candidate]]

    while paths != []:
        path_to_expand = paths.pop()
        current_location = path_to_expand[-1]
        current_elevation = world[current_location[1]][current_location[0]]
        if current_elevation == 9:
            total_rating += 1
            reachable_nines.add(current_location)
            continue

        # Consider the locations where the hiker could move to next, ensuring that they
        # also do not move outside the world border
        next_location_candidates = []
        # Move left
        if current_location[0] > 0:
            next_location_candidates.append((current_location[0] - 1, current_location[1]))
        # Move right
        if current_location[0] < len(world[0]) - 1:
            next_location_candidates.append((current_location[0] + 1, current_location[1]))
        # Move up
        if current_location[1] > 0:
            next_location_candidates.append((current_location[0], current_location[1] - 1))
        # Move down
        if current_location[1] < len(world) - 1:
            next_location_candidates.append((current_location[0], current_location[1] + 1))

        # Determine only the candidates which are within one elevation difference
        next_location_candidates = filter(
            lambda candidate: world[candidate[1]][candidate[0]] == current_elevation + 1,
            next_location_candidates
        )

        # Generate new paths with each new location
        for location in next_location_candidates:
            new_path = path_to_expand.copy()
            new_path.append(location)
            paths.append(new_path)

    total_score += len(reachable_nines)

print(f"(Part 1) {total_score}")
print(f"(Part 2) {total_rating}")

from collections import defaultdict
from typing import List


def update_stone(stone: int) -> List[int]:
    if stone == 0:
        return [1]
    else:
        digit_length = len(str(stone))
        if digit_length % 2 == 0:
            return [int(str(stone)[:int(digit_length / 2)]), int(str(stone)[int(digit_length / 2):])]
        else:
            return [stone * 2024]


def blink_for_all_stones(stones: List[int]) -> List[int]:
    ret = []
    for stone in stones:
        ret += update_stone(stone)
    return ret


#########
# Part 1
#########
with open("./input.txt", "r") as input_file:
    stones = list(map(lambda s: int(s), input_file.read().split()))

for _ in range(25):
    stones = blink_for_all_stones(stones)

print(f"(Part 1) Number of stones is {len(stones)}")


#########
# Part 2
#########
with open("./input.txt", "r") as input_file:
    stones = list(map(lambda s: int(s), input_file.read().split()))

# Build the initial mapping of stones to the number of times they appear in the corridor
# (which at the start is once for each input stone)
stones_to_occurrences = defaultdict(int)
for stone in stones:
    stones_to_occurrences[stone] += 1

# Simulate blinking 75 times
for _ in range(75):
    new_stones_to_occurrences = defaultdict(int)
    for stone, occurrences in stones_to_occurrences.items():
        new_stones = update_stone(stone)
        for stone in new_stones:
            new_stones_to_occurrences[stone] += occurrences

    stones_to_occurrences = new_stones_to_occurrences

print(f"(Part 2) Number of stones is {sum(stones_to_occurrences.values())}")

from typing import List, Set, Tuple


Coord = Tuple[int, int]

with open("./input.txt", "r") as input_file:
    garden = list(map(lambda line: list(line), input_file.read().splitlines()))

# Keep track of all plots which have been placed into a region
regioned_plots: Set[Coord] = set()

total_price = 0
for line_index, line in enumerate(garden):
    for char_index, char in enumerate(line):
        plot_location = (char_index, line_index)
        if plot_location in regioned_plots:
            continue

        # We will greedily explore from the plot, finding its entire region
        plant_type = char
        frontier: List[Coord] = [plot_location]
        regioned_plots.add(plot_location)
        region_area = 0
        region_perimeter = 0
        while frontier != []:
            plot_to_expand = frontier.pop()

            # Determine all neighbouring coordinates of the plot
            neighbours: List[Coord] = []

            # Explore to the left (if possible)
            if plot_to_expand[0] > 0:
                neighbours.append((plot_to_expand[0] - 1, plot_to_expand[1]))

            # Explore to the right (if possible)
            if plot_to_expand[0] < len(garden[0]) - 1:
                neighbours.append((plot_to_expand[0] + 1, plot_to_expand[1]))

            # Explore below (if possible)
            if plot_to_expand[1] < len(garden) - 1:
                neighbours.append((plot_to_expand[0], plot_to_expand[1] + 1))

            # Explore above (if possible)
            if plot_to_expand[1] > 0:
                neighbours.append((plot_to_expand[0], plot_to_expand[1] - 1))

            # The plot always contributes an area of 1
            region_area += 1

            # We pretend that the plot adds a perimiter of 4, and then for each adjacent
            # neighbour of the same type and region, we decrement the contribution
            region_perimeter += 4
            for neighbour in neighbours:
                # If the neighbour is a different plant, and has already been explored,
                # then we treat the new plot as not having an exposed edge
                if (garden[neighbour[1]][neighbour[0]] == plant_type and
                        neighbour in regioned_plots
                        and neighbour not in frontier):
                    region_perimeter -= 2

            # Determine where to explore to next
            for neighbour in neighbours:
                # If the neighbour is of a different plant type, then ignore it
                if garden[neighbour[1]][neighbour[0]] != plant_type:
                    continue

                # If the neighbour has already been added to a region, then ignore it
                if neighbour in regioned_plots:
                    continue

                frontier.append(neighbour)
                regioned_plots.add(neighbour)
        total_price += region_area * region_perimeter

print(f"(Part 1) Total price is {total_price}")

from collections import defaultdict
from enum import Enum
from functools import reduce
from typing import List, Set, Tuple


# A plot coordinate has the top-left plot in place `(0,0)` and uses screen coordinates
PlotCoord = Tuple[int, int]

# A fence coordinate has the top-left corner of the top-left plot in place `(0,0)` and
# uses screen coordinates. The bottom-right corner of the top-left plot has a fence
# coordinate of `(1,1)`.
FenceCoord = Tuple[int, int]

# A fence can be viewed as an undirected edge between two fence coordinates
Fence = Tuple[FenceCoord, FenceCoord]

Direction = Enum("Direction", ["UP", "RIGHT", "DOWN", "LEFT"])

with open("./input.txt", "r") as input_file:
    garden = list(map(lambda line: list(line), input_file.read().splitlines()))

# Keep track of all plots which have been placed into a region
regioned_plots: Set[PlotCoord] = set()

total_price = 0
# Iterate through every plot in the garden
for line_index, line in enumerate(garden):
    for char_index, char in enumerate(line):
        plot_location = (char_index, line_index)

        # We have already processed a plot if it was in the same region as a previous plot
        if plot_location in regioned_plots:
            continue

        # We will greedily explore from the plot, finding its entire region
        plant_type = char
        region_area = 0
        frontier: List[PlotCoord] = [plot_location]
        regioned_plots.add(plot_location)
        region_fences: Set[Fence] = set()

        while frontier != []:
            plot_to_expand = frontier.pop()
            region_area += 1

            # Determine all neighbouring coordinates of the plot
            neighbours: List[PlotCoord] = []

            # By looking at the neighbours, we can determine the fences of this plot, as
            # well as the closed region that needs to be fenced.
            # Look at the left neighbour
            if plot_to_expand[0] > 0:
                # Get the coordinate of the left neighbour
                left_neighbour = (plot_to_expand[0] - 1, plot_to_expand[1])

                # If the plant type of the neighbour is different, then there must exist
                # a fence between the neighbours
                if garden[left_neighbour[1]][left_neighbour[0]] != plant_type:
                    region_fences.add((plot_to_expand, (plot_to_expand[0], plot_to_expand[1] + 1)))
                else:
                    # The neighbour has the same plant type, so we might need to explore
                    # to it (if we have not already)
                    if left_neighbour not in regioned_plots:
                        frontier.append(left_neighbour)
                        regioned_plots.add(left_neighbour)
            else:
                region_fences.add((plot_to_expand, (plot_to_expand[0], plot_to_expand[1] + 1)))

            # Look at the right negihbour
            if plot_to_expand[0] < len(garden[0]) - 1:
                right_neighbour = (plot_to_expand[0] + 1, plot_to_expand[1])
                if garden[right_neighbour[1]][right_neighbour[0]] != plant_type:
                    region_fences.add(
                        (
                            (plot_to_expand[0] + 1, plot_to_expand[1]),
                            (plot_to_expand[0] + 1, plot_to_expand[1] + 1)
                        )
                    )
                else:
                    if right_neighbour not in regioned_plots:
                        frontier.append(right_neighbour)
                        regioned_plots.add(right_neighbour)
            else:
                region_fences.add(
                    (
                        (plot_to_expand[0] + 1, plot_to_expand[1]),
                        (plot_to_expand[0] + 1, plot_to_expand[1] + 1)
                    )
                )

            # Look at the below neighbour
            if plot_to_expand[1] < len(garden) - 1:
                below_neighbour = (plot_to_expand[0], plot_to_expand[1] + 1)
                if garden[below_neighbour[1]][below_neighbour[0]] != plant_type:
                    region_fences.add(
                        (
                            (plot_to_expand[0], plot_to_expand[1] + 1),
                            (plot_to_expand[0] + 1, plot_to_expand[1] + 1)
                        )
                    )
                else:
                    if below_neighbour not in regioned_plots:
                        frontier.append(below_neighbour)
                        regioned_plots.add(below_neighbour)
            else:
                region_fences.add(
                    (
                        (plot_to_expand[0], plot_to_expand[1] + 1),
                        (plot_to_expand[0] + 1, plot_to_expand[1] + 1)
                    )
                )

            # Look at the above neighbour
            if plot_to_expand[1] > 0:
                above_neighbour = (plot_to_expand[0], plot_to_expand[1] - 1)
                if garden[above_neighbour[1]][above_neighbour[0]] != plant_type:
                    region_fences.add(
                        (
                            (plot_to_expand[0], plot_to_expand[1]),
                            (plot_to_expand[0] + 1, plot_to_expand[1])
                        )
                    )
                else:
                    if above_neighbour not in regioned_plots:
                        frontier.append(above_neighbour)
                        regioned_plots.add(above_neighbour)
            else:
                region_fences.add(
                    (
                        (plot_to_expand[0], plot_to_expand[1]),
                        (plot_to_expand[0] + 1, plot_to_expand[1])
                    )
                )

        # We imagine going 'clockwise' around the fences, starting at an arbitrary fence
        # of the region
        current_fence = list(region_fences)[0]

        # Edges are either horizontal of vertical. Arbitrarily, if we are on a horizontal
        # edge, we start with going right, and if we are on a vertical edge, we start
        # with going up.
        current_direction = Direction.UP if current_fence[0][0] == current_fence[1][0] else Direction.RIGHT

        visited_fences: Set[Fence] = set()

        # Keep track of the number of edges used
        edge_count = 0

        while True:
            # Determine the source vertex (i.e. the fence coordinate that we are
            # leaving) based on the direction of travel we are in
            if current_direction == Direction.RIGHT:
                source_vertex = current_fence[0] if current_fence[0][0] > current_fence[1][0] else current_fence[1]
            elif current_direction == Direction.LEFT:
                source_vertex = current_fence[0] if current_fence[0][0] < current_fence[1][0] else current_fence[1]
            elif current_direction == Direction.DOWN:
                source_vertex = current_fence[0] if current_fence[0][1] > current_fence[1][1] else current_fence[1]
            else:
                source_vertex = current_fence[0] if current_fence[0][1] < current_fence[1][1] else current_fence[1]

            # If the source vertex is containd within any fences that we have visited,
            # then we have a loop within `visited_fences`
            if source_vertex in reduce(lambda acc, f: acc + [f[0], f[1]], visited_fences, []):
                visited_fences.add(current_fence)

                # At this point, we have a loop, but there might be some fences within
                # `visited_fences` which are not used within the loop.
                # Until there's only a loop, there will be at least one vertex which is
                # present only once in the set, so we can remove all edges containing
                # that vertex to get closer to having just a loop.
                while True:
                    appearing_vertices = defaultdict(int)
                    for fence in visited_fences:
                        appearing_vertices[fence[0]] += 1
                        appearing_vertices[fence[1]] += 1

                    # Use a flag for determining if the visited fences are just a loop
                    is_just_loop = True
                    for vertex, count in appearing_vertices.items():
                        # If there's a vertex which appears just once, then remove all
                        # edges that it is involved in
                        if count == 1:
                            visited_fences = set(filter(lambda f: vertex not in f, visited_fences))
                            is_just_loop = False
                            break

                    # Once we've been through an entire iteration of `appearing_vertices`
                    # without finding one with just one occurrence, `visited_fences`
                    # contains only edges that form a single loop.
                    if is_just_loop:
                        break

                # Now, we have just one loop. We can start somewhere in that loop and
                # determine how many times the direction changes to get the edge count
                loop_edge_count = 0
                loop_edge = list(visited_fences)[0]
                loop_direction = Direction.UP if loop_edge[0][0] == loop_edge[1][0] else Direction.RIGHT
                visited_vertices = set()

                # Keep track of whether we have been to a corner yet (i.e. a point when
                # we change direction). This makes us start counting visited vertices once
                # we change direction, which helps with reasoning about the loop.
                has_been_at_corner = False
                while True:
                    # Determine the source vertex of the current edge
                    if loop_direction == Direction.RIGHT:
                        source_vertex = loop_edge[0] if loop_edge[0][0] > loop_edge[1][0] else loop_edge[1]
                    elif loop_direction == Direction.LEFT:
                        source_vertex = loop_edge[0] if loop_edge[0][0] < loop_edge[1][0] else loop_edge[1]
                    elif loop_direction == Direction.DOWN:
                        source_vertex = loop_edge[0] if loop_edge[0][1] > loop_edge[1][1] else loop_edge[1]
                    else:
                        source_vertex = loop_edge[0] if loop_edge[0][1] < loop_edge[1][1] else loop_edge[1]

                    # As we have only a single loop, we expect the number of incident
                    # edges to be exactly `1`.
                    incident_edges = [f for f in visited_fences if source_vertex in f and f != loop_edge]
                    assert len(incident_edges) == 1

                    next_edge = incident_edges[0]
                    destination_vertex = next_edge[1] if next_edge[0] == source_vertex else next_edge[0]

                    # If the destination vertex has been visited before, then we've
                    # finished the single loop
                    if destination_vertex in visited_vertices:
                        break

                    # Determine the direction of the new edge
                    movement = (destination_vertex[0] - source_vertex[0], destination_vertex[1] - source_vertex[1])
                    if movement == (1, 0):
                        new_direction = Direction.RIGHT
                    elif movement == (-1, 0):
                        new_direction = Direction.LEFT
                    elif movement == (0, 1):
                        new_direction = Direction.DOWN
                    else:
                        new_direction = Direction.UP

                    if has_been_at_corner:
                        visited_vertices.add(source_vertex)

                    # Changing direction implies that another edge is used
                    if new_direction != loop_direction:
                        loop_edge_count += 1
                        has_been_at_corner = True

                    loop_edge = next_edge
                    loop_direction = new_direction

                # The loop has finished being processed, and we know the edges that are
                # needed to create it
                edge_count += loop_edge_count

                # Now, we need only consider all fences of the region which were not
                # involved with that loop
                unvisited_fences = region_fences - visited_fences

                # If there are no such fences, determining the region's edge count is
                # complete
                if unvisited_fences == set():
                    break

                # Otherwise, there might be (e.g.) 'inside fences' that we need to look
                # for, so we reset all state and iterate again
                visited_fences = set()
                region_fences = unvisited_fences
                current_fence = list(region_fences)[0]
                current_direction = Direction.UP if current_fence[0][0] == current_fence[1][0] else Direction.RIGHT
                continue

            # We have not yet found a loop within `visited_fences`, so we continue
            # exploring and determine all fences incident to the source vertex
            incident_fences = [f for f in region_fences if source_vertex in f and f != current_fence]

            # Arbitrarily choose the first incident fence. We can choose any fence as
            # we will still get a loop, and trim off any excess fences (see the code above
            # for when a loop is present)
            incident_fence = incident_fences[0]

            # Determine the fence coordinate that we will be moving to from the source
            # vertex
            destination_vertex = incident_fence[1] if incident_fence[0] == source_vertex else incident_fence[0]

            # Determine the new direction of movement
            movement = (destination_vertex[0] - source_vertex[0], destination_vertex[1] - source_vertex[1])
            if movement == (1, 0):
                new_direction = Direction.RIGHT
            elif movement == (-1, 0):
                new_direction = Direction.LEFT
            elif movement == (0, 1):
                new_direction = Direction.DOWN
            else:
                new_direction = Direction.UP

            # Update the state for the next iteration
            visited_fences.add(current_fence)
            current_fence = incident_fence
            current_direction = new_direction

        # We have finished finding all edges of the region, so can determine its
        # contribution to the price
        total_price += edge_count * region_area

print(f"(Part 2) Total price is {total_price}")

from functools import reduce
from typing import List, Tuple
import re


def parse_problem_block(block: str) -> Tuple[Tuple[int, int], Tuple[int, int], Tuple[int, int]]:
    lines = block.splitlines()

    button_a_match = re.search(r"Button A: X\+(\d*), Y\+(\d*)", lines[0])
    assert button_a_match is not None
    button_a_info = (int(button_a_match.group(1)), int(button_a_match.group(2)))

    button_b_match = re.search(r"Button B: X\+(\d*), Y\+(\d*)", lines[1])
    assert button_b_match is not None
    button_b_info = (int(button_b_match.group(1)), int(button_b_match.group(2)))

    prize_match = re.search(r"Prize: X=(\d*), Y=(\d*)", lines[2])
    assert prize_match is not None
    prize_match_info = (int(prize_match.group(1)), int(prize_match.group(2)))

    return (button_a_info, button_b_info, prize_match_info)


#########
# Part 1
#########
with open("./input.txt", "r") as input_file:
    blocks = input_file.read().split("\n\n")

total_token_cost = 0
for block in blocks:
    (x_A, y_A), (x_B, y_B), (prize_x_coord, prize_y_coord) = parse_problem_block(block)

    # Consider every value of n_{A} and whether the problem is solvable, storing each
    # solution as a tuple of (n_{A}, n_{B})
    solutions: List[Tuple[int, int]] = []
    for n_A in range(101):
        needed_x_change = prize_x_coord - (n_A * x_A)

        # Button B can only contribute positive values, so we have no more solutions if
        # we need a negative number from button B presses
        if needed_x_change < 0:
            break

        # If button B's contribution does not evenly fit into the needed coordinate, then
        # we cannot use it
        if needed_x_change % x_B:
            continue

        # There's some number of presses to button B that takes the claw to the exact X
        # location needed
        n_B = int(needed_x_change / x_B)

        # Each button can be pressed no more than 100 times
        if n_B > 100:
            continue

        # Check that the claw's y-coordinate is correct
        if (n_A * y_A) + (n_B * y_B) != prize_y_coord:
            continue

        # We have found a solution
        solutions.append((n_A, n_B))

    # Determine the lowest-cost solution. HACK: No cost goes over 1000, so we use it as
    # an initial value (and default).
    lowest_cost = reduce(lambda acc, presses: min(acc, (presses[0] * 3) + presses[1]), solutions, 1000)
    if lowest_cost == 1000:
        continue

    total_token_cost += lowest_cost

print(f"(Part 1) Total token cost is {total_token_cost}")

#########
# Part 2
#########
with open("./input.txt", "r") as input_file:
    blocks = input_file.read().split("\n\n")

total_token_cost = 0
for block in blocks:
    (x_A, y_A), (x_B, y_B), (prize_x_coord, prize_y_coord) = parse_problem_block(block)
    prize_x_coord += 10000000000000
    prize_y_coord += 10000000000000

    # We have two equations:
    #   n_A * x_A + n_B * x_B = prize_x_coord
    #   n_A * y_A + n_B * y_B = prize_y_coord
    #
    # Using substitution, we can find the following:
    n_B = ((prize_y_coord * x_A) - (prize_x_coord * y_A)) / ((x_A * y_B) - (x_B * y_A))

    if int(n_B) == n_B:
        n_A = (prize_x_coord - (x_B * n_B)) / x_A
        if int(n_A) == n_A:
            total_token_cost += int((n_A * 3) + n_B)

print(f"(Part 2) Total token cost is {total_token_cost}")

from math import prod
import re
from typing import List, Tuple


WORLD_DIMENSIONS = (101, 103)


class Robot:
    def __init__(self, position: Tuple[int, int], velocity: Tuple[int, int]) -> None:
        self.position = position
        self.velocity = velocity

    def move(self, seconds: int) -> None:
        self.position = (
            self.position[0] + (seconds * self.velocity[0]),
            self.position[1] + (seconds * self.velocity[1]),
        )

        # Adjust the position based on the wrap-around
        self.position = (self.position[0] % WORLD_DIMENSIONS[0], self.position[1] % WORLD_DIMENSIONS[1])


#########
# Part 1
#########
with open("./input.txt", "r") as input_file:
    lines = input_file.read().splitlines()

robots: List[Robot] = []
for line in lines:
    search_match = re.search(r"p=(\d*),(\d*) v=(-?\d*),(-?\d*)", line)
    assert search_match is not None
    robots.append(Robot(
        (int(search_match.group(1)), int(search_match.group(2))),
        (int(search_match.group(3)), int(search_match.group(4)))
    ))

# Simulate all robots moving for 100 seconds
for robot in robots:
    robot.move(100)

# Determine how many robots are in each quadrant
quadrant_counts = [0, 0, 0, 0]
for robot in robots:
    # Determine the quadrant that the robot is in
    if robot.position[1] < (WORLD_DIMENSIONS[1] - 1) / 2:
        if robot.position[0] < (WORLD_DIMENSIONS[0] - 1) / 2:
            quadrant_counts[0] += 1
        elif robot.position[0] > (WORLD_DIMENSIONS[0] - 1) / 2:
            quadrant_counts[1] += 1
    elif robot.position[1] > (WORLD_DIMENSIONS[1] - 1) / 2:
        if robot.position[0] < (WORLD_DIMENSIONS[0] - 1) / 2:
            quadrant_counts[2] += 1
        elif robot.position[0] > (WORLD_DIMENSIONS[0] - 1) / 2:
            quadrant_counts[3] += 1

print(f"(Part 1) Safety factor is {prod(quadrant_counts)}")


#########
# Part 2
#########
with open("./input.txt", "r") as input_file:
    lines = input_file.read().splitlines()

robots: List[Robot] = []
for line in lines:
    search_match = re.search(r"p=(\d*),(\d*) v=(-?\d*),(-?\d*)", line)
    assert search_match is not None
    robots.append(Robot(
        (int(search_match.group(1)), int(search_match.group(2))),
        (int(search_match.group(3)), int(search_match.group(4)))
    ))

seconds_elapsed = 0
seen_states = set()
while True:
    char_grid = [[" " for _ in range(WORLD_DIMENSIONS[0])] for _ in range(WORLD_DIMENSIONS[1])]

    for robot in robots:
        robot.move(1)
        char_grid[robot.position[1]][robot.position[0]] = "#"

    seconds_elapsed += 1
    print(f"Seconds elapsed: {seconds_elapsed}")

    char_grid_str = ""
    should_print = False
    for line in char_grid:
        char_grid_str += "".join(line) + "\n"
        if line.count("#") > 0.2 * len(line):
            should_print = True

    if should_print:
        print(char_grid_str)
        input()

    state_hash = frozenset({(i, robots[i].position) for i in range(len(robots))})
    if state_hash not in seen_states:
        seen_states.add(state_hash)
    else:
        print("Repetition")
        input()

from typing import List, Tuple


Coord = Tuple[int, int]

class World:
    def __init__(self, world: List[List[str]]) -> None:
        self.world = world

    def at(self, coord: Coord) -> str:
        return self.world[coord[1]][coord[0]]

    def set(self, coord: Coord, char: str) -> None:
        self.world[coord[1]][coord[0]] = char

    def get_score(self) -> bool:
        score = 0
        for line_index, line in enumerate(world.world):
            for char_index, char in enumerate(line):
                if char == "O":
                    score += (line_index * 100) + char_index

        return score


with open("./input_map.txt", "r") as input_file:
    world = World(list(map(lambda line: list(line), input_file.read().splitlines())))

with open("./input_move_sequence.txt", "r") as input_file:
    moves = input_file.read()

# Determine the robot's starting position
starting_pos = None
for line_index, line in enumerate(world.world):
    if "@" in line:
        starting_pos = (line.index("@"), line_index)

assert starting_pos
current_pos = starting_pos

for move in moves:
    if move == "\n":
        continue

    if move == "^":
        intended_move = (current_pos[0], current_pos[1] - 1)
    elif move == ">":
        intended_move = (current_pos[0] + 1, current_pos[1])
    elif move == "v":
        intended_move = (current_pos[0], current_pos[1] + 1)
    else:
        intended_move = (current_pos[0] - 1, current_pos[1])

    # If we would move into a wall, then do not move
    if world.at(intended_move) == "#":
        continue

    # If there is empty space, then the robot can immediately move into it
    if world.at(intended_move) == ".":
        world.set(current_pos, ".")
        current_pos = intended_move
        world.set(current_pos, "@")
        continue

    # Otherwise, there is a box, so determine if the box can be moved, and if so, move it
    furthest_known_box_coord = intended_move
    can_move = False
    if move == "^":
        while True:
            next_box_coord = (furthest_known_box_coord[0], furthest_known_box_coord[1] - 1)
            if world.at(next_box_coord) == ".":
                can_move = True
                break
            elif world.at(next_box_coord) == "#":
                break
            else:
                # We have another box
                furthest_known_box_coord = next_box_coord
    elif move == ">":
        while True:
            next_box_coord = (furthest_known_box_coord[0] + 1, furthest_known_box_coord[1])
            if world.at(next_box_coord) == ".":
                can_move = True
                break
            elif world.at(next_box_coord) == "#":
                break
            else:
                # We have another box
                furthest_known_box_coord = next_box_coord
    elif move == "v":
        while True:
            next_box_coord = (furthest_known_box_coord[0], furthest_known_box_coord[1] + 1)
            if world.at(next_box_coord) == ".":
                can_move = True
                break
            elif world.at(next_box_coord) == "#":
                break
            else:
                # We have another box
                furthest_known_box_coord = next_box_coord
    else:
        while True:
            next_box_coord = (furthest_known_box_coord[0] - 1, furthest_known_box_coord[1])
            if world.at(next_box_coord) == ".":
                can_move = True
                break
            elif world.at(next_box_coord) == "#":
                break
            else:
                # We have another box
                furthest_known_box_coord = next_box_coord

    if can_move:
        world.set(current_pos, ".")
        current_pos = intended_move
        world.set(current_pos, "@")

        if move == "^":
            world.set((furthest_known_box_coord[0], furthest_known_box_coord[1] - 1), "O")
        elif move == ">":
            world.set((furthest_known_box_coord[0] + 1, furthest_known_box_coord[1]), "O")
        elif move == "v":
            world.set((furthest_known_box_coord[0], furthest_known_box_coord[1] + 1), "O")
        else:
            world.set((furthest_known_box_coord[0] - 1, furthest_known_box_coord[1]), "O")

print(f"(Part 1) Score is {world.get_score()}")

from typing import List, Tuple


Coord = Tuple[int, int]

class World:
    def __init__(self, world: List[List[str]]) -> None:
        # Expand the world
        expanded_world = []
        for line in world:
            expanded_line = []
            for char in line:
                if char == "#":
                    expanded_line += ["#", "#"]
                elif char == "O":
                    expanded_line += ["[", "]"]
                elif char == ".":
                    expanded_line += [".", "."]
                elif char == "@":
                    expanded_line += ["@", "."]
            expanded_world.append(expanded_line)
        self.world = expanded_world

    def at(self, coord: Coord) -> str:
        return self.world[coord[1]][coord[0]]

    def set(self, coord: Coord, char: str) -> None:
        self.world[coord[1]][coord[0]] = char

    def get_score(self) -> bool:
        score = 0
        for line_index, line in enumerate(world.world):
            for char_index, char in enumerate(line):
                if char == "[":
                    score += (line_index * 100) + char_index

        return score

    def __str__(self) -> str:
        ret = ""
        for line in self.world:
            ret += "".join(line) + "\n"
        return ret


with open("./input_map.txt", "r") as input_file:
    world = World(list(map(lambda line: list(line), input_file.read().splitlines())))

with open("./input_move_sequence.txt", "r") as input_file:
    moves = input_file.read()

# Determine the robot's starting position
starting_pos = None
for line_index, line in enumerate(world.world):
    if "@" in line:
        starting_pos = (line.index("@"), line_index)

assert starting_pos
current_pos = starting_pos

for move in moves:
    if move == "\n":
        continue

    if move == "^":
        intended_move = (current_pos[0], current_pos[1] - 1)
    elif move == ">":
        intended_move = (current_pos[0] + 1, current_pos[1])
    elif move == "v":
        intended_move = (current_pos[0], current_pos[1] + 1)
    else:
        intended_move = (current_pos[0] - 1, current_pos[1])

    # If we would move into a wall, then do not move
    if world.at(intended_move) == "#":
        continue

    # If there is empty space, then the robot can immediately move into it
    if world.at(intended_move) == ".":
        world.set(current_pos, ".")
        current_pos = intended_move
        world.set(current_pos, "@")
        continue

    # Otherwise, there is a box, so determine if the box can be moved, and if so, move it
    if move == "^":
        intended_move = (current_pos[0], current_pos[1] - 1)

        # Maintain a frontier of boxes, which we explore vertically, layer by layer.
        # Frontier contains the left-coordinate of each box.
        frontier = set()
        # Track all boxes which need to be moved.
        boxes_to_move = set()
        if world.at(intended_move) == "[":
            frontier.add(intended_move)
            boxes_to_move.add(intended_move)
        else:
            frontier.add((intended_move[0] - 1, intended_move[1]))
            boxes_to_move.add((intended_move[0] - 1, intended_move[1]))
        while True:
            # Determine everything above the boxes
            boxes_above = set()
            definitely_cannot_move = False
            for box in frontier:
                # See what is above the "[" of the box
                above_left = world.at((box[0], box[1] - 1))
                if above_left == "#":
                    definitely_cannot_move = True
                    break
                if above_left == "[":
                    boxes_above.add((box[0], box[1] - 1))
                elif above_left == "]":
                    boxes_above.add((box[0] - 1, box[1] - 1))

                # See what is above the "]" of the box
                above_right = world.at((box[0] + 1, box[1] - 1))
                if above_right == "#":
                    definitely_cannot_move = True
                    break
                if above_right == "[":
                    boxes_above.add((box[0] + 1, box[1] - 1))
                elif above_right == "]":
                    boxes_above.add((box[0], box[1] - 1))

            boxes_to_move |= boxes_above

            # If we cannot move, then we are done considering this instruction, as we
            # know the robot cannot move this direction
            if definitely_cannot_move:
                break

            # If there are no boxes above, then there is just empty space, so the robot
            # can complete the move
            if boxes_above == set():
                # If there are no boxes above and we can move, then the robot is able
                # to complete a move and push all the boxes in its direction. For the sake
                # of simplicity and not overriding previous moves, it is easiest to
                # consider moving the boxes which are furthest away first
                boxes_to_move = list(boxes_to_move)
                boxes_to_move.sort(key=lambda box: box[1])
                for box_to_move in boxes_to_move:
                    world.set((box_to_move[0], box_to_move[1]), ".")
                    world.set((box_to_move[0] + 1, box_to_move[1]), ".")

                    world.set((box_to_move[0], box_to_move[1] - 1), "[")
                    world.set((box_to_move[0] + 1, box_to_move[1] - 1), "]")

                # The boxes have all been moved, so move the player now
                world.set(current_pos, ".")
                current_pos = intended_move
                world.set(current_pos, "@")
                break
            else:
                # There are boxes above which still need exploring
                frontier = boxes_above
    elif move == ">":
        intended_move = (current_pos[0] + 1, current_pos[1])
        furthest_known_box_coord = intended_move
        can_move = False
        while True:
            next_box_coord = (furthest_known_box_coord[0] + 2, furthest_known_box_coord[1])
            if world.at(next_box_coord) == ".":
                can_move = True
                break
            elif world.at(next_box_coord) == "#":
                break
            else:
                # We have another box
                furthest_known_box_coord = next_box_coord
        if can_move:
            # Move the robot
            world.set(current_pos, ".")
            current_pos = intended_move
            world.set(current_pos, "@")

            # Move the boxes, essentially by inverting each box side, and then adding
            # a final box side at the end
            for x in range(current_pos[0] + 1, furthest_known_box_coord[0] + 2):
                if world.at((x, current_pos[1])) == "[":
                    world.set((x, current_pos[1]), "]")
                else:
                    world.set((x, current_pos[1]), "[")
            world.set((furthest_known_box_coord[0] + 2, furthest_known_box_coord[1]), "]")
    elif move == "v":
        intended_move = (current_pos[0], current_pos[1] + 1)

        # Maintain a frontier of boxes, which we explore vertically, layer by layer.
        # Frontier contains the left-coordinate of each box.
        frontier = set()
        # Track all boxes which need to be moved.
        boxes_to_move = set()
        if world.at(intended_move) == "[":
            frontier.add(intended_move)
            boxes_to_move.add(intended_move)
        else:
            frontier.add((intended_move[0] - 1, intended_move[1]))
            boxes_to_move.add((intended_move[0] - 1, intended_move[1]))
        while True:
            # Determine everything below the boxes
            boxes_below = set()
            definitely_cannot_move = False
            for box in frontier:
                # See what is above the "[" of the box
                below_left = world.at((box[0], box[1] + 1))
                if below_left == "#":
                    definitely_cannot_move = True
                    break
                if below_left == "[":
                    boxes_below.add((box[0], box[1] + 1))
                elif below_left == "]":
                    boxes_below.add((box[0] - 1, box[1] + 1))

                # See what is above the "]" of the box
                below_right = world.at((box[0] + 1, box[1] + 1))
                if below_right == "#":
                    definitely_cannot_move = True
                    break
                if below_right == "[":
                    boxes_below.add((box[0] + 1, box[1] + 1))
                elif below_right == "]":
                    boxes_below.add((box[0], box[1] + 1))

            boxes_to_move |= boxes_below

            # If we cannot move, then we are done considering this instruction, as we
            # know the robot cannot move this direction
            if definitely_cannot_move:
                break

            # If there are no boxes above, then there is just empty space, so the robot
            # can complete the move
            if boxes_below == set():
                # If there are no boxes above and we can move, then the robot is able
                # to complete a move and push all the boxes in its direction. For the sake
                # of simplicity and not overriding previous moves, it is easiest to
                # consider moving the boxes which are furthest away first
                boxes_to_move = list(boxes_to_move)
                boxes_to_move.sort(key=lambda box: -box[1])
                for box_to_move in boxes_to_move:
                    world.set((box_to_move[0], box_to_move[1]), ".")
                    world.set((box_to_move[0] + 1, box_to_move[1]), ".")

                    world.set((box_to_move[0], box_to_move[1] + 1), "[")
                    world.set((box_to_move[0] + 1, box_to_move[1] + 1), "]")

                # The boxes have all been moved, so move the player now
                world.set(current_pos, ".")
                current_pos = intended_move
                world.set(current_pos, "@")
                break
            else:
                # There are boxes below which still need exploring
                frontier = boxes_below
    else:
        intended_move = (current_pos[0] - 1, current_pos[1])
        furthest_known_box_coord = intended_move
        can_move = False
        while True:
            next_box_coord = (furthest_known_box_coord[0] - 2, furthest_known_box_coord[1])
            if world.at(next_box_coord) == ".":
                can_move = True
                break
            elif world.at(next_box_coord) == "#":
                break
            else:
                # We have another box
                furthest_known_box_coord = next_box_coord
        if can_move:
            # Move the robot
            world.set(current_pos, ".")
            current_pos = intended_move
            world.set(current_pos, "@")

            # Move the boxes, essentially by inverting each box side, and then adding
            # a final box side at the end
            for x in range(current_pos[0] - 1, furthest_known_box_coord[0] - 2, -1):
                if world.at((x, current_pos[1])) == "[":
                    world.set((x, current_pos[1]), "]")
                else:
                    world.set((x, current_pos[1]), "[")
            world.set((furthest_known_box_coord[0] - 2, furthest_known_box_coord[1]), "[")

print(f"(Part 2) Score is {world.get_score()}")

from collections import namedtuple
from enum import Enum
from queue import PriorityQueue
from typing import Dict, List, Set, Tuple, cast


Coord = Tuple[int, int]


class Direction(Enum):
    NORTH = 0
    EAST = 1
    SOUTH = 2
    WEST = 3

    def __lt__(self, other):
        if self.__class__ is other.__class__:
            return self.value < other.value
        return NotImplemented


def turn_right(direction: Direction) -> Direction:
    if direction == Direction.NORTH:
        return Direction.EAST
    elif direction == Direction.EAST:
        return Direction.SOUTH
    elif direction == Direction.SOUTH:
        return Direction.WEST
    else:
        return Direction.NORTH


def turn_left(direction: Direction) -> Direction:
    if direction == Direction.NORTH:
        return Direction.WEST
    elif direction == Direction.EAST:
        return Direction.NORTH
    elif direction == Direction.SOUTH:
        return Direction.EAST
    else:
        return Direction.SOUTH


class World:
    def __init__(self, world: List[List[str]]) -> None:
        self.world = world

    def at(self, coord: Coord) -> str:
        return self.world[coord[1]][coord[0]]


with open("./input.txt", "r") as input_file:
    world = World(list(map(lambda line: list(line), input_file.read().splitlines())))

# Determine the Reindeer's starting position
starting_pos = None
for line_index, line in enumerate(world.world):
    if "S" in line:
        starting_pos = (line.index("S"), line_index)
assert starting_pos is not None

# Determine the End Tile's position
end_tile_position = None
for line_index, line in enumerate(world.world):
    if "E" in line:
        end_tile_position = (line.index("E"), line_index)
assert end_tile_position is not None

starting_direction = Direction.EAST

VisitState = namedtuple("VisitState", "pos direction")
class Path:
    def __init__(
        self,
        cost: int,
        current_state: VisitState,

        # Maintain a set of every state that this path has visited, including the current
        all_visited_states: Set[VisitState]
    ) -> None:
        self.cost = cost
        self.current_state = current_state
        self.all_visited_states = all_visited_states

    def __lt__(self, other):
        return self.cost < other.cost

paths: PriorityQueue[Path] = PriorityQueue()
paths.put(Path(
    0,
    VisitState(starting_pos, starting_direction),
    {VisitState(starting_pos, starting_direction)}
))

# Maintain a map from states in the map to the shortest paths found to get to that state.
# We allow for multiple shortest paths of the same cost. To find the cost of the path,
# the first object can be indexed.
shortest_paths: Dict[VisitState, List[Path]] = {}

lowest_cost_path = -1
while not paths.empty():
    path_to_expand = paths.get()

    # Check whether the Reindeer has been to this state before
    if path_to_expand.current_state in shortest_paths:
        # If the Reindeer has previously reached this state with a strictly lower cost,
        # then there exists a strictly better path than this one, so we need not process
        # this one anymore.
        if shortest_paths[path_to_expand.current_state][0].cost < path_to_expand.cost:
            continue

        if shortest_paths[path_to_expand.current_state][0].cost == path_to_expand.cost:
            shortest_paths[path_to_expand.current_state].append(path_to_expand)
            continue
        else:
            # We have found a new path with a lower cost, then any existing, so we replace
            shortest_paths[path_to_expand.current_state] = [path_to_expand]
    else:
        shortest_paths[path_to_expand.current_state] = [path_to_expand]

    # Determine if the path has reached the destination
    if path_to_expand.current_state.pos == end_tile_position:
        if lowest_cost_path == -1:
            lowest_cost_path = path_to_expand.cost
            print(f"(Part 1) Cost is {path_to_expand.cost}")
        elif path_to_expand.cost != lowest_cost_path:
            # We have found a path with higher cost than any lowest-cost path, so we have
            # finished finding all the best paths
            break

    # Determine where the Reindeer would move to if it keeps the same direction
    if path_to_expand.current_state.direction == Direction.NORTH:
        intended_move = (path_to_expand.current_state.pos[0], path_to_expand.current_state.pos[1] - 1)
    elif path_to_expand.current_state.direction == Direction.EAST:
        intended_move = (path_to_expand.current_state.pos[0] + 1, path_to_expand.current_state.pos[1])
    elif path_to_expand.current_state.direction == Direction.SOUTH:
        intended_move = (path_to_expand.current_state.pos[0], path_to_expand.current_state.pos[1] + 1)
    else:
        intended_move = (path_to_expand.current_state.pos[0] - 1, path_to_expand.current_state.pos[1])

    # If the Reindeer can move in that direction, then it's a valid path
    if world.at(intended_move) != "#":
        # Fact: There is no shortest path where the Reindeer moves into a location
        # which it has already been to
        if {
            VisitState(intended_move, Direction.NORTH),
            VisitState(intended_move, Direction.EAST),
            VisitState(intended_move, Direction.SOUTH),
            VisitState(intended_move, Direction.WEST)
        } & path_to_expand.all_visited_states == set():
            new_visited_states = path_to_expand.all_visited_states.copy()
            new_visited_states.add(VisitState(intended_move, path_to_expand.current_state.direction))
            paths.put(Path(
                path_to_expand.cost + 1,
                VisitState(intended_move, path_to_expand.current_state.direction),
                new_visited_states)
            )

    # Determine if the Reindeer could turn 90 degrees and then move. Note that we do not
    # check if the Reindeer could turn 180 degrees, as this will never be a lowest-cost
    # path (unless the Reindeer starts in a dead-end, but this is an edgecase which I
    # manually check)
    if path_to_expand.current_state.direction == Direction.NORTH:
        ahead_of_turn_right = (path_to_expand.current_state.pos[0] + 1, path_to_expand.current_state.pos[1])
        ahead_of_turn_left = (path_to_expand.current_state.pos[0] - 1, path_to_expand.current_state.pos[1])
    elif path_to_expand.current_state.direction == Direction.EAST:
        ahead_of_turn_right = (path_to_expand.current_state.pos[0], path_to_expand.current_state.pos[1] + 1)
        ahead_of_turn_left = (path_to_expand.current_state.pos[0], path_to_expand.current_state.pos[1] - 1)
    elif path_to_expand.current_state.direction == Direction.SOUTH:
        ahead_of_turn_right = (path_to_expand.current_state.pos[0] - 1, path_to_expand.current_state.pos[1])
        ahead_of_turn_left = (path_to_expand.current_state.pos[0] + 1, path_to_expand.current_state.pos[1])
    else:
        ahead_of_turn_right = (path_to_expand.current_state.pos[0], path_to_expand.current_state.pos[1] - 1)
        ahead_of_turn_left = (path_to_expand.current_state.pos[0], path_to_expand.current_state.pos[1] + 1)

    if world.at(ahead_of_turn_left) != "#":
        new_current_state = VisitState(
            path_to_expand.current_state.pos,
            turn_left(path_to_expand.current_state.direction)
        )
        if new_current_state not in path_to_expand.all_visited_states:
            new_visited_states = path_to_expand.all_visited_states.copy()
            new_visited_states.add(new_current_state)
            paths.put(Path(
                path_to_expand.cost + 1000,
                new_current_state,
                new_visited_states
            ))
    if world.at(ahead_of_turn_right) != "#":
        new_current_state = VisitState(
            path_to_expand.current_state.pos,
            turn_right(path_to_expand.current_state.direction)
        )
        if new_current_state not in path_to_expand.all_visited_states:
            new_visited_states = path_to_expand.all_visited_states.copy()
            new_visited_states.add(new_current_state)
            paths.put(Path(
                path_to_expand.cost + 1000,
                new_current_state,
                new_visited_states
            ))

# We have some shortest paths which get to the target. We also have shortest paths that
# get to each location within any of those shortest paths. We need to put them all
# together to get every possible path.
# Get all the lowest-cost found paths that went directly to the target
shortest_paths_to_target_any_direction: List[List[Path]] = cast(List[List[Path]], list(filter(
    lambda paths: paths is not None and paths[0] != lowest_cost_path,
    [
        shortest_paths.get(VisitState(end_tile_position, Direction.NORTH)),
        shortest_paths.get(VisitState(end_tile_position, Direction.EAST)),
        shortest_paths.get(VisitState(end_tile_position, Direction.SOUTH)),
        shortest_paths.get(VisitState(end_tile_position, Direction.WEST)),
    ]
)))

all_shortest_cost_path_visit_states = set()

for shortest_paths_to_target_some_direction in shortest_paths_to_target_any_direction:
    for shortest_path_to_target_some_direction in shortest_paths_to_target_some_direction:
        for visited_state in shortest_path_to_target_some_direction.all_visited_states:
            for sub_path in shortest_paths[visited_state]:
                all_shortest_cost_path_visit_states |= sub_path.all_visited_states

before_pass_length = len(all_shortest_cost_path_visit_states)
while True:
    other_visit_states: Set[VisitState] = set()
    for visit_state in all_shortest_cost_path_visit_states:
        for sub_path in shortest_paths[visit_state]:
            other_visit_states |= sub_path.all_visited_states
    all_shortest_cost_path_visit_states |= other_visit_states

    if before_pass_length == len(all_shortest_cost_path_visit_states):
        break
    before_pass_length = len(all_shortest_cost_path_visit_states)

all_unique_locations = set(map(lambda visit_state: visit_state.pos, all_shortest_cost_path_visit_states))
print(f"(Part 2) Number of tiles belonging to at least one best path is {len(all_unique_locations)}")

from typing import List


class Computer:
    def __init__(self, register_a: int, register_b: int, register_c: int, program: List[int]) -> None:
        self.register_a = register_a
        self.register_b = register_b
        self.register_c = register_c
        self.program = program
        self.instr_ptr = 0
        self.output: List[int] = []

    def compute(self) -> List[int]:
        while self.instr_ptr < len(self.program):
            current_opcode = self.program[self.instr_ptr]
            match current_opcode:
                case 0:
                    self._adv()
                case 1:
                    self._bxl()
                case 2:
                    self._bst()
                case 3:
                    self._jnz()
                case 4:
                    self._bxc()
                case 5:
                    self._out()
                case 6:
                    self._bdv()
                case 7:
                    self._cdv()
                case _:
                    raise Exception(f"Unrecognised opcode {current_opcode}")

        return self.output

    def _combo(self, operand: int) -> bool:
        match operand:
            case 0 | 1 | 2 | 3:
                return operand
            case 4:
                return self.register_a
            case 5:
                return self.register_b
            case 6:
                return self.register_c
            case _:
                raise Exception(f"Unrecognised operand {operand}")

    def _adv(self) -> None:
        numerator = self.register_a
        denominator = 2 ** self._combo(self.program[self.instr_ptr + 1])
        self.register_a = int(numerator / denominator)
        self.instr_ptr += 2

    def _bxl(self) -> None:
        self.register_b = self.register_b ^ self.program[self.instr_ptr + 1]
        self.instr_ptr += 2

    def _bst(self) -> None:
        self.register_b = self._combo(self.program[self.instr_ptr + 1]) % 8
        self.instr_ptr += 2

    def _jnz(self) -> None:
        if self.register_a == 0:
            self.instr_ptr += 2
            return

        self.instr_ptr = self.program[self.instr_ptr + 1]

    def _bxc(self) -> None:
        self.register_b = self.register_b ^ self.register_c
        self.instr_ptr += 2

    def _out(self) -> None:
        self.output.append(self._combo(self.program[self.instr_ptr + 1]) % 8)
        self.instr_ptr += 2

    def _bdv(self) -> None:
        numerator = self.register_a
        denominator = 2 ** self._combo(self.program[self.instr_ptr + 1])
        self.register_b = int(numerator / denominator)
        self.instr_ptr += 2

    def _cdv(self) -> None:
        numerator = self.register_a
        denominator = 2 ** self._combo(self.program[self.instr_ptr + 1])
        self.register_c = int(numerator / denominator)
        self.instr_ptr += 2


with open("./input.txt", "r") as input_file:
    lines = input_file.read().splitlines()

initial_register_a = int(lines[0][len("Register A: "):])
initial_register_b = int(lines[1][len("Register B: "):])
initial_register_c = int(lines[2][len("Register C: "):])
program = list(map(lambda s: int(s), lines[4][len("Program: "):].split(",")))

# (Part 1)
computer = Computer(initial_register_a, initial_register_b, initial_register_c, program)
part_1_output = computer.compute()
print(f"(Part 1): {','.join(map(lambda i: str(i), part_1_output))}")

# (Part 2)
# The program has a length of 16, so we need an initial register value which has at least
# 15 outputs. By clock observations, this starts at 8 ** (16 - 1).
PROGRAM_LENGTH = 16
initial_register_a = 8 ** (16 - 1)

target_output_number_idx = 15
while target_output_number_idx >= 0:
    computer = Computer(initial_register_a, initial_register_b, initial_register_c, program)
    output = computer.compute()

    if output[target_output_number_idx] == program[target_output_number_idx]:
        target_output_number_idx -= 1
        continue

    initial_register_a += 8 ** (PROGRAM_LENGTH - (len(program) - target_output_number_idx))

print(f"(Part 2) Register A should be set to {initial_register_a}")

from queue import PriorityQueue
from typing import Dict, Set, Tuple


Coord = Tuple[int, int]


class World:
    def __init__(self, world_dims_wh: Tuple[int, int]) -> None:
        self.world = [["." for _ in range(world_dims_wh[0])] for _ in range(world_dims_wh[1])]

    def at(self, coord: Coord) -> str:
        return self.world[coord[1]][coord[0]]

    def set(self, coord: Coord, char: str) -> None:
        self.world[coord[1]][coord[0]] = char

    def __str__(self) -> str:
        ret = ""
        for line in self.world:
            ret += "".join(line) + "\n"
        return ret


class Path:
    def __init__(self, current_position: Coord, all_visited_positions: Set[Coord]) -> None:
        self.current_position = current_position
        self.all_visited_positions = all_visited_positions

        # The cost is determined via the number of steps in the path, as well as the
        # Manhattan Distance to the target
        total_cost = len(all_visited_positions) - 1
        total_cost += (WORLD_DIMS[0] - 1) - current_position[0]
        total_cost += (WORLD_DIMS[1] - 1) - current_position[1]
        self.cost = total_cost

    def __lt__(self, other):
        return self.cost < other.cost


WORLD_DIMS = (71, 71)
NUMBER_OF_FALLING_BYTES = 1024
world = World(WORLD_DIMS)

with open("./input.txt", "r") as input_file:
    falling_bytes = list(map(
        lambda line: (int(line.split(",")[0]), int(line.split(",")[1])),
        input_file.read().splitlines()
    ))

for i in range(NUMBER_OF_FALLING_BYTES):
    world.set(falling_bytes[i], "#")

current_position = (0, 0)
target_position = (WORLD_DIMS[0] - 1, WORLD_DIMS[1] - 1)
frontier: PriorityQueue[Path] = PriorityQueue()
frontier.put(Path(current_position, {current_position}))
shortest_costs: Dict[Coord, int] = {}

while True:
    path_to_expand = frontier.get()
    current_position = path_to_expand.current_position

    if current_position in shortest_costs:
        if path_to_expand.cost >= shortest_costs[current_position]:
            continue

    shortest_costs[current_position] = path_to_expand.cost

    if current_position == (WORLD_DIMS[0] - 1, WORLD_DIMS[1] - 1):
        print(f"(Part 1) Shortest path has length {len(path_to_expand.all_visited_positions) - 1} steps")
        break

    # Attempt moving up
    if current_position[1] > 0:
        move_up = (current_position[0], current_position[1] - 1)
        if move_up not in path_to_expand.all_visited_positions and world.at(move_up) == ".":
            new_all_visited_positions = path_to_expand.all_visited_positions.copy()
            new_all_visited_positions.add(move_up)
            frontier.put(Path(move_up, new_all_visited_positions))

    # Attempt moving right
    if current_position[0] < WORLD_DIMS[0] - 1:
        move_right = (current_position[0] + 1, current_position[1])
        if move_right not in path_to_expand.all_visited_positions and world.at(move_right) == ".":
            new_all_visited_positions = path_to_expand.all_visited_positions.copy()
            new_all_visited_positions.add(move_right)
            frontier.put(Path(move_right, new_all_visited_positions))

    # Attempt moving down
    if current_position[1] < WORLD_DIMS[1] - 1:
        move_down = (current_position[0], current_position[1] + 1)
        if move_down not in path_to_expand.all_visited_positions and world.at(move_down) == ".":
            new_all_visited_positions = path_to_expand.all_visited_positions.copy()
            new_all_visited_positions.add(move_down)
            frontier.put(Path(move_down, new_all_visited_positions))

    # Attempt moving left
    if current_position[0] > 0:
        move_left = (current_position[0] - 1, current_position[1])
        if move_left not in path_to_expand.all_visited_positions and world.at(move_left) == ".":
            new_all_visited_positions = path_to_expand.all_visited_positions.copy()
            new_all_visited_positions.add(move_left)
            frontier.put(Path(move_left, new_all_visited_positions))

from queue import PriorityQueue
from typing import Dict, Set, Tuple


Coord = Tuple[int, int]


class World:
    def __init__(self, world_dims_wh: Tuple[int, int]) -> None:
        self.world = [["." for _ in range(world_dims_wh[0])] for _ in range(world_dims_wh[1])]

    def at(self, coord: Coord) -> str:
        return self.world[coord[1]][coord[0]]

    def set(self, coord: Coord, char: str) -> None:
        self.world[coord[1]][coord[0]] = char

    def __str__(self) -> str:
        ret = ""
        for line in self.world:
            ret += "".join(line) + "\n"
        return ret


class Path:
    def __init__(self, current_position: Coord, all_visited_positions: Set[Coord]) -> None:
        self.current_position = current_position
        self.all_visited_positions = all_visited_positions

        # The cost is determined via the number of steps in the path, as well as the
        # Manhattan Distance to the target
        total_cost = len(all_visited_positions) - 1
        total_cost += (WORLD_DIMS[0] - 1) - current_position[0]
        total_cost += (WORLD_DIMS[1] - 1) - current_position[1]
        self.cost = total_cost

    def __lt__(self, other):
        return self.cost < other.cost


WORLD_DIMS = (71, 71)
INITIAL_NUMBER_OF_FALLING_BYTES = 1024
with open("./input.txt", "r") as input_file:
    falling_bytes = list(map(
        lambda line: (int(line.split(",")[0]), int(line.split(",")[1])),
        input_file.read().splitlines()
    ))

world = World(WORLD_DIMS)
for i in range(INITIAL_NUMBER_OF_FALLING_BYTES):
    world.set(falling_bytes[i], "#")

previous_path = None
for falling_byte in falling_bytes[INITIAL_NUMBER_OF_FALLING_BYTES:]:
    world.set(falling_byte, "#")

    current_position = (0, 0)
    target_position = (WORLD_DIMS[0] - 1, WORLD_DIMS[1] - 1)
    frontier: PriorityQueue[Path] = PriorityQueue()
    frontier.put(Path(current_position, {current_position}))
    shortest_costs: Dict[Coord, int] = {}

    if previous_path is not None and falling_byte not in previous_path.all_visited_positions:
        continue

    path_found = False

    while not frontier.empty():
        path_to_expand = frontier.get()
        current_position = path_to_expand.current_position

        if current_position in shortest_costs:
            if path_to_expand.cost >= shortest_costs[current_position]:
                continue

        shortest_costs[current_position] = path_to_expand.cost

        if current_position == (WORLD_DIMS[0] - 1, WORLD_DIMS[1] - 1):
            path_found = True
            previous_path = path_to_expand
            break

        # Attempt moving up
        if current_position[1] > 0:
            move_up = (current_position[0], current_position[1] - 1)
            if move_up not in path_to_expand.all_visited_positions and world.at(move_up) == ".":
                new_all_visited_positions = path_to_expand.all_visited_positions.copy()
                new_all_visited_positions.add(move_up)
                frontier.put(Path(move_up, new_all_visited_positions))

        # Attempt moving right
        if current_position[0] < WORLD_DIMS[0] - 1:
            move_right = (current_position[0] + 1, current_position[1])
            if move_right not in path_to_expand.all_visited_positions and world.at(move_right) == ".":
                new_all_visited_positions = path_to_expand.all_visited_positions.copy()
                new_all_visited_positions.add(move_right)
                frontier.put(Path(move_right, new_all_visited_positions))

        # Attempt moving down
        if current_position[1] < WORLD_DIMS[1] - 1:
            move_down = (current_position[0], current_position[1] + 1)
            if move_down not in path_to_expand.all_visited_positions and world.at(move_down) == ".":
                new_all_visited_positions = path_to_expand.all_visited_positions.copy()
                new_all_visited_positions.add(move_down)
                frontier.put(Path(move_down, new_all_visited_positions))

        # Attempt moving left
        if current_position[0] > 0:
            move_left = (current_position[0] - 1, current_position[1])
            if move_left not in path_to_expand.all_visited_positions and world.at(move_left) == ".":
                new_all_visited_positions = path_to_expand.all_visited_positions.copy()
                new_all_visited_positions.add(move_left)
                frontier.put(Path(move_left, new_all_visited_positions))

    if path_found:
        continue

    print(f"(Part 2) Byte that closes the exit is {falling_byte}")
    break

from collections import defaultdict
from queue import PriorityQueue
from typing import Set, Tuple


with open("./input.txt", "r") as input_file:
    towel_patterns, designs = input_file.read().split("\n\n")

    towel_patterns = towel_patterns.split(", ")
    designs = designs.splitlines()


#########
# Part 1
#########
# Keep track of every sub-design (i.e. a portion of any design) that we know to be
# solvable
number_of_solvable_designs = 0
for design in designs:
    # Maintain a Priority Queue (ordered by length), such that any design within that
    # queue which can be solved means that `design` can be solved. We also maintain a
    # set of designs that have been seen within the queue, to stop needless repetition.
    designs_to_solve: PriorityQueue[Tuple[int, str]] = PriorityQueue()
    seen_designs: Set[str] = set()
    designs_to_solve.put((len(design), design))

    is_solvable = False
    while not designs_to_solve.empty():
        length, design_to_solve = designs_to_solve.get()

        if design_to_solve == "":
            is_solvable = True
            break

        for towel_pattern in towel_patterns:
            if design_to_solve.startswith(towel_pattern):
                # The design to solve is the rest of the desired towel pattern, without
                # the candidate
                remaining_pattern = design_to_solve[len(towel_pattern):]
                if remaining_pattern not in seen_designs:
                    designs_to_solve.put((length - len(towel_pattern), remaining_pattern))
                    seen_designs.add(remaining_pattern)

    if is_solvable:
        number_of_solvable_designs += 1

print(f"(Part 1) There are {number_of_solvable_designs} solvable designs")


#########
# Part 2
#########
length_to_towel_patterns = defaultdict(set)
for towel_pattern in towel_patterns:
    length_to_towel_patterns[len(towel_pattern)].add(towel_pattern)

longest_towel_pattern = max(length_to_towel_patterns.keys())

# Keep track of patterns and the number of solutions that they have
unique_solution_cache = {}


def get_unique_solutions(design: str) -> bool:
    # Base case --- if there is no more design, then this represents a single solution
    if design == "":
        return 1

    # Recursive case --- we consider each pattern that could be at the start of the
    # design (i.e. consider each towel that could come first). We then consider the
    # remaining pattern(s) and recursively apply `get_unique_solutions`.
    candidates = []
    for pattern_length in range(1, 1 + min(len(design), longest_towel_pattern)):
        starting_pattern = design[:pattern_length]
        if starting_pattern in length_to_towel_patterns[pattern_length]:
            remaining_pattern = design[pattern_length:]
            candidates.append(remaining_pattern)

    ret = 0
    for candidate in candidates:
        if candidate in unique_solution_cache:
            ret += unique_solution_cache[candidate]
        else:
            candidate_result = get_unique_solutions(candidate)
            unique_solution_cache[candidate] = candidate_result
            ret += candidate_result

    return ret


total = 0
for design in designs:
    total += get_unique_solutions(design)

print(f"(Part 2) Total is {total}")

from collections import defaultdict
from typing import Iterable, List, Tuple


Coord = Tuple[int, int]


class World:
    def __init__(self, world: List[List[str]]) -> None:
        self.world = world

        self.dimensions = (len(world[0]), len(world))

    def at(self, coord: Coord) -> str:
        return self.world[coord[1]][coord[0]]

    def is_in_bounds(self, c: Coord) -> bool:
        return c[0] >= 0 and c[0] < self.dimensions[0] and c[1] >= 0 and c[1] < self.dimensions[1]

    def __str__(self) -> str:
        ret = ""
        for line in self.world:
            ret += "".join(line) + "\n"
        return ret


with open("./input.txt", "r") as input_file:
    world = World(list(map(lambda line: list(line), input_file.read().splitlines())))

# Determine the starting position
starting_pos = None
for line_index, line in enumerate(world.world):
    if "S" in line:
        starting_pos = (line.index("S"), line_index)
assert starting_pos is not None

# Determine the ending position
ending_pos = None
for line_index, line in enumerate(world.world):
    if "E" in line:
        ending_pos = (line.index("E"), line_index)
assert ending_pos is not None

current_pos = starting_pos
path = []
while current_pos != ending_pos:
    # There should be exactly one '.' next to the current position (apart from the
    # previous position)
    previous_position = None if len(path) == 0 else path[-1]

    move_up = (current_pos[0], current_pos[1] - 1)
    move_down = (current_pos[0], current_pos[1] + 1)
    move_left = (current_pos[0] - 1, current_pos[1])
    move_right = (current_pos[0] + 1, current_pos[1])

    for move in [move_up, move_down, move_left, move_right]:
        if move != previous_position and world.at(move) in [".", "E"]:
            path.append(current_pos)
            current_pos = move
            break

path.append(ending_pos)


#########
# Part 1
#########
time_saves = defaultdict(int)
for position_index, position in enumerate(path):
    # There are 8 coordinates that could be moved to --- these are all coordinates which
    # require 2 movements. We ignore 1 movement cheats, as they either keep on track or
    # end in a wall.
    candidates = [
        (position[0] - 2, position[1]),
        (position[0] - 1, position[1] - 1),
        (position[0] - 1, position[1] + 1),
        (position[0]    , position[1] - 2),
        (position[0]    , position[1] + 2),
        (position[0] + 1, position[1] - 1),
        (position[0] + 1, position[1] + 1),
        (position[0] + 2, position[1]),
    ]

    # Some of these coordinates might be out of bounds
    candidates = list(filter(world.is_in_bounds, candidates))

    # We must finish moving at a path
    candidates = list(filter(lambda c: world.at(c) in [".", "E", "S"], candidates))

    # Determine the time gain of performing the cheat for each potential move
    for candidate in candidates:
        destination_index = path.index(candidate)

        # We subtract 2 from the time save, as each cheat takes 2 movement
        time_save = destination_index - position_index - 2
        if time_save > 0:
            time_saves[time_save] += 1

total = 0
for key, value in time_saves.items():
    if key >= 100:
        total += value

print(f"(Part 1) Cheats saving at least 100 picoseconds: {total}")


#########
# Part 2
#########
TRACK_CHARS = {".", "E", "S"}
def get_candidates(c: Coord, picoseconds: int) -> Iterable[Coord]:
    # Return every possible track position that can be moved to within `picoseconds` from
    # `c`, given inclusion within the world (via the bounds used).
    return iter([
        (x,y)
        for x in range(
            max(0, c[0] - picoseconds),
            min(c[0] + picoseconds + 1, world.dimensions[0])
        )
        for y in range(
            max(0, c[1] - (picoseconds - abs(x - c[0]))),
            min(c[1] + (picoseconds - abs(x - c[0])) + 1, world.dimensions[1])
        )
        if world.at((x,y)) in TRACK_CHARS
    ])


# Create a map of each path's position to its index within the path
path_position_to_index = {}
for position_index, position in enumerate(path):
    path_position_to_index[position] = position_index

time_saves = defaultdict(int)
CHEAT_PICOSECONDS = 20
total = 0

# We can immediately trim (at least roughly) the last 100 positions in the path as for a
# cheat to save at least 100 seconds, it must be more than 100 positions from the end.
for position_index, position in enumerate(path[:-100]):
    # Determine the time gain of performing the cheat for each potential move
    for candidate in get_candidates(position, CHEAT_PICOSECONDS):
        destination_index = path_position_to_index[candidate]

        # The cheat cost is the Manhattan distance between the two coordinates
        cheat_cost = abs(position[0] - candidate[0]) + abs(position[1] - candidate[1])

        time_save = destination_index - position_index - cheat_cost
        if time_save >= 100:
            total += 1

print(f"(Part 2) Cheats saving at least 100 picoseconds: {total}")

from typing import List, Tuple
import itertools


Coord = Tuple[int, int]


def get_key_coord(key: str, keypad) -> Coord:
    for line_index, line in enumerate(keypad):
        if key in line:
            return (line.index(key), line_index)

    raise Exception(f"Key not found")


def instruction_to_subinstructions(instruction: str, isDirectionalKeypad: bool) -> List[str]:
    keypad = DIRECTIONAL_KEYPAD if isDirectionalKeypad else NUMERIC_KEYPAD
    cache = move_option_cache_directional if isDirectionalKeypad else move_option_cache_numeric

    # Begin at the 'A'. All robots will start at 'A', due to how entering an instruction
    # essentially ends with pressing an 'A'.
    current_pos: Coord = get_key_coord("A", keypad)

    path_segments = []
    while instruction:
        next_key = instruction[0]
        next_key_coord = get_key_coord(next_key, keypad)

        # Determine if we already have this path in the cache
        if (current_pos, next_key_coord) in cache:
            movements_to_cover_coord_diff = cache[(current_pos, next_key_coord)]
        else:
            # Determine the smallest vector that the arm needs to move by
            coord_diff = (next_key_coord[0] - current_pos[0], next_key_coord[1] - current_pos[1])

            # If the vector has two components, then there's potentially more than one way it can
            # be performed
            if coord_diff[0] != 0 and coord_diff[1] != 0:
                # Visualise the movement vector as a list of horizontal movements and vertical
                # movements
                movements_required = (
                    list(("<" if coord_diff[0] < 0 else ">") * abs(coord_diff[0])) +
                    list(("^" if coord_diff[1] < 0 else "v") * abs(coord_diff[1]))
                )

                # Determine every unique permutation of that list
                moves_candidates = set(itertools.permutations(movements_required))

                # Filter-out any candidates which are impossible, i.e. simulate moving them and
                # determine if we get out of bounds
                possible_candidates = []
                for moves_candidate in moves_candidates:
                    move_pos = current_pos
                    is_possible = True
                    for move in moves_candidate:
                        if move == ">":
                            move_pos = (move_pos[0] + 1, move_pos[1]    )
                        elif move == "<":
                            move_pos = (move_pos[0] - 1, move_pos[1]    )
                        elif move == "v":
                            move_pos = (move_pos[0]    , move_pos[1] + 1)
                        else:
                            move_pos = (move_pos[0]    , move_pos[1] - 1)

                        if keypad[move_pos[1]][move_pos[0]] == None:
                            is_possible = False
                            break

                    if is_possible:
                        possible_candidates.append("".join(moves_candidate))

                movements_to_cover_coord_diff = possible_candidates

                cache[(current_pos, next_key_coord)] = movements_to_cover_coord_diff
            else:
                # We are moving only in one direction, and so there is only one combination of
                # moves available
                if coord_diff[0] == 0:
                    # We are moving vertically
                    if coord_diff[1] > 0:
                        movements_to_cover_coord_diff = ["v" * coord_diff[1]]
                    else:
                        movements_to_cover_coord_diff = ["^" * -coord_diff[1]]
                else:
                    # We are moving horizontally
                    if coord_diff[0] > 0:
                        movements_to_cover_coord_diff = [">" * coord_diff[0]]
                    else:
                        movements_to_cover_coord_diff = ["<" * -coord_diff[0]]
                cache[(current_pos, next_key_coord)] = movements_to_cover_coord_diff

        path_segments.append(movements_to_cover_coord_diff)
        path_segments.append(["A"])

        current_pos = next_key_coord

        instruction = instruction[1:]

    path_strings = [""]
    for path_segment in path_segments:
        if len(path_segment) == 1:
            path_strings = list(map(lambda s: s + path_segment[0], path_strings))
        else:
            new_path_strings = []
            for option in path_segment:
                new_path_strings += list(map(lambda s: s + option, path_strings))
            path_strings = new_path_strings

    return path_strings


NUMERIC_KEYPAD = [
    ["7" , "8", "9"],
    ["4" , "5", "6"],
    ["1" , "2", "3"],
    [None, "0", "A"],
]

DIRECTIONAL_KEYPAD = [
    [None, "^", "A"],
    ["<" , "v", ">"],
]

move_option_cache_numeric = {}
move_option_cache_directional = {}

with open("./input.txt", "r") as input_file:
    instructions_for_robot1 = input_file.read().splitlines()

total = 0
for instruction_for_robot1 in instructions_for_robot1:
    # Get the instructions for the robot at the numeric keypad
    current_instructions = instruction_to_subinstructions(instruction_for_robot1, False)

    # Get the instructions for the chain of robots
    for _ in range(2):
        next_instructions = []
        for instruction in current_instructions:
            next_instructions += instruction_to_subinstructions(instruction, True)

        current_instructions = next_instructions

    shortest_length = min(map(len, current_instructions))
    total += shortest_length * int(instruction_for_robot1[:-1])

print(f"(Part 1) Total is {total}")

Coord = Tuple[int, int]


def get_key_coord(key: str, keypad) -> Coord:
    for line_index, line in enumerate(keypad):
        if key in line:
            return (line.index(key), line_index)

    raise Exception(f"Key not found")


NUMERIC_KEYPAD = [
    ["7" , "8", "9"],
    ["4" , "5", "6"],
    ["1" , "2", "3"],
    [None, "0", "A"],
]

DIRECTIONAL_KEYPAD = [
    [None, "^", "A"],
    ["<" , "v", ">"],
]

###################################
# Bulid the numeric movement cache
###################################
numeric_movement_cache = {}
potential_locations = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A"]
every_pair = itertools.combinations(potential_locations, 2)

# Consider the reverse of pairs
new_every_pair = []
for pair in every_pair:
    new_every_pair.append(pair)
    new_every_pair.append(tuple(reversed(pair)))
every_pair = new_every_pair

# Also consider every pair that does not move
for location in potential_locations:
    every_pair.append((location, location))

for pair in every_pair:
    source_coord = get_key_coord(pair[0], NUMERIC_KEYPAD)
    dest_coord = get_key_coord(pair[1], NUMERIC_KEYPAD)

    coord_diff = (dest_coord[0] - source_coord[0], dest_coord[1] - source_coord[1])
    movements_required = (
        list(("<" if coord_diff[0] < 0 else ">") * abs(coord_diff[0])) +
        list(("^" if coord_diff[1] < 0 else "v") * abs(coord_diff[1]))
    )
    potential_movements = set(itertools.permutations(movements_required))

    # Filter-out any candidates which are impossible, i.e. simulate moving them and
    # determine if we get out of bounds
    non_impossible_movements = []
    for possible_candidate in potential_movements:
        current_pos = source_coord
        is_possible = True
        for move in possible_candidate:
            if move == ">":
                current_pos = (current_pos[0] + 1, current_pos[1]    )
            elif move == "<":
                current_pos = (current_pos[0] - 1, current_pos[1]    )
            elif move == "v":
                current_pos = (current_pos[0]    , current_pos[1] + 1)
            else:
                current_pos = (current_pos[0]    , current_pos[1] - 1)

            if NUMERIC_KEYPAD[current_pos[1]][current_pos[0]] == None:
                is_possible = False
                break

        if is_possible:
            non_impossible_movements.append("".join(possible_candidate) + "A")

    numeric_movement_cache[pair] = non_impossible_movements


#######################################
# Bulid the directional movement cache
#######################################
directional_movement_cache = {}
potential_locations = ["<", "^", ">", "v", "A"]
every_pair = itertools.combinations(potential_locations, 2)

# Consider the reverse of pairs
new_every_pair = []
for pair in every_pair:
    new_every_pair.append(pair)
    new_every_pair.append(tuple(reversed(pair)))
every_pair = new_every_pair

# Also consider every pair that does not move
for location in potential_locations:
    every_pair.append((location, location))

for pair in every_pair:
    source_coord = get_key_coord(pair[0], DIRECTIONAL_KEYPAD)
    dest_coord = get_key_coord(pair[1], DIRECTIONAL_KEYPAD)

    coord_diff = (dest_coord[0] - source_coord[0], dest_coord[1] - source_coord[1])
    movements_required = (
        list(("<" if coord_diff[0] < 0 else ">") * abs(coord_diff[0])) +
        list(("^" if coord_diff[1] < 0 else "v") * abs(coord_diff[1]))
    )
    potential_movements = set(itertools.permutations(movements_required))

    # Filter-out any candidates which are impossible, i.e. simulate moving them and
    # determine if we get out of bounds
    non_impossible_movements = []
    for possible_candidate in potential_movements:
        current_pos = source_coord
        is_possible = True
        for move in possible_candidate:
            if move == ">":
                current_pos = (current_pos[0] + 1, current_pos[1]    )
            elif move == "<":
                current_pos = (current_pos[0] - 1, current_pos[1]    )
            elif move == "v":
                current_pos = (current_pos[0]    , current_pos[1] + 1)
            else:
                current_pos = (current_pos[0]    , current_pos[1] - 1)

            if DIRECTIONAL_KEYPAD[current_pos[1]][current_pos[0]] == None:
                is_possible = False
                break

        if is_possible:
            non_impossible_movements.append("".join(possible_candidate) + "A")

    directional_movement_cache[pair] = non_impossible_movements


MAX_KEYPADS = 27
cost_cache = {}


def cost(state_number: int, move_sequence: str) -> bool:
    if (state_number, move_sequence) in cost_cache:
        return cost_cache[(state_number, move_sequence)]

    # Base case
    if state_number == MAX_KEYPADS:
        return len(move_sequence)

    # Recursive case
    if state_number == 1:
        total_cost = 0
        initial_source = "A"
        for move in move_sequence:
            sub_movement_options = numeric_movement_cache[(initial_source, move)]
            if len(sub_movement_options) == 1:
                total_cost += cost(state_number + 1, sub_movement_options[0])
            else:
                sub_movement_costs = []
                for sub_movement_option in sub_movement_options:
                    sub_movement_costs.append(cost(state_number + 1, sub_movement_option))
                total_cost += min(sub_movement_costs)

            initial_source = move

        cost_cache[(state_number, move_sequence)] = total_cost
        return total_cost
    else:
        total_cost = 0
        initial_source = "A"
        for move in move_sequence:
            sub_movement_options = directional_movement_cache[(initial_source, move)]
            if len(sub_movement_options) == 1:
                total_cost += cost(state_number + 1, sub_movement_options[0])
            else:
                sub_movement_costs = []
                for sub_movement_option in sub_movement_options:
                    sub_movement_costs.append(cost(state_number + 1, sub_movement_option))
                total_cost += min(sub_movement_costs)

            initial_source = move

        cost_cache[(state_number, move_sequence)] = total_cost
        return total_cost


with open("./input.txt", "r") as input_file:
    instructions_for_robot1 = input_file.read().splitlines()

total = 0
for instruction_for_robot1 in instructions_for_robot1:
    total += cost(1, instruction_for_robot1) * int(instruction_for_robot1[:-1])

print(f"(Part 2) Total is {total}")

def evolve_secret_number(n: int) -> bool:
    temp = n * (2 ** 6)
    n = n ^ temp
    n = n % (2 ** 24)

    temp = n  / (2 ** 5)
    temp = int(temp)
    n = n ^ temp
    n = n % (2 ** 24)

    temp = n * (2 ** 11)
    n = n ^ temp
    n = n % (2 ** 24)

    return n


with open("./input.txt", "r") as input_file:
    initial_numbers = list(map(int, input_file.read().splitlines()))


total = 0
for initial_number in initial_numbers:
    number = initial_number
    for _ in range(2000):
        number = evolve_secret_number(number)
    total += number

print(f"(Part 1) Total is {total}")

from collections import defaultdict
from typing import List, Tuple, cast


class PriceInfo:
    def __init__(self, prices: List[int]) -> None:
        self.prices = prices

        self.price_changes = []
        for x in range(len(self.prices) - 1):
            self.price_changes.append(self.prices[x + 1] - self.prices[x])

        self.price_change_to_sell_price = {}
        for x in range(len(self.price_changes) - 3):
            change_starting_at_x = tuple(self.price_changes[x:x+4])
            if change_starting_at_x not in self.price_change_to_sell_price:
                self.price_change_to_sell_price[change_starting_at_x] = self.prices[x + 4]


def evolve_secret_number(n: int) -> bool:
    temp = n << 6
    n = n ^ temp
    n = n & (16777216 - 1)

    temp = n >> 5
    n = n ^ temp
    n = n & (16777216 - 1)

    temp = n << 11
    n = n ^ temp
    n = n & (16777216 - 1)

    return n


def buy_at_sequence(price_info: PriceInfo, sequence: Tuple[int, int, int, int]) -> bool:
    if sequence in price_info.price_change_to_sell_price:
        return price_info.price_change_to_sell_price[sequence]

    return 0


with open("./input.txt", "r") as input_file:
    initial_numbers = list(map(int, input_file.read().splitlines()))

all_price_info: List[PriceInfo] = []
for initial_number in initial_numbers:
    number = initial_number
    prices = [number % 10]
    for _ in range(2000):
        new_number = evolve_secret_number(number)
        prices.append(new_number % 10)
        number = new_number
    all_price_info.append(PriceInfo(prices))

sequence_occurrences = defaultdict(int)
for price_info in all_price_info:
    for sequence_occurrence in price_info.price_change_to_sell_price.keys():
        sequence_occurrences[sequence_occurrence] += 1

sequence_occurrence_pairs = list(sequence_occurrences.items())
sequence_occurrence_pairs.sort(key=lambda item: item[1], reverse=True)

best_price = 0
for sequence, occurrence in sequence_occurrence_pairs:
    if occurrence * 9 < best_price:
        break

    total = 0
    for price_info in all_price_info:
        total += buy_at_sequence(price_info, cast(Tuple[int, int, int, int], sequence))

    if total > best_price:
        best_price = total

print(f"(Part 2) {best_price}")

from collections import defaultdict
from copy import deepcopy
from itertools import combinations


connections = defaultdict(set)
with open("./input.txt", "r") as input_file:
    lines = input_file.read().splitlines()
    for line in lines:
        computer1, computer2 = line.split("-")
        connections[computer1].add(computer2)
        connections[computer2].add(computer1)

fully_connected_trios = []
for trio in combinations(connections.keys(), 3):
    if not trio[0].startswith("t") and not trio[1].startswith("t") and not trio[2].startswith("t"):
        continue
    if (
        (trio[2] in connections[trio[0]] and trio[1] in connections[trio[0]]) and
        (trio[2] in connections[trio[1]] and trio[0] in connections[trio[1]]) and
        (trio[1] in connections[trio[2]] and trio[0] in connections[trio[2]])
    ):
        fully_connected_trios.append(trio)

print(f"(Part 1) {len(fully_connected_trios)}")


largest_fully_connected = set()
for src_computer, dst_computers in connections.items():
    for dst_computer in dst_computers:
        largest_fully_connected.add(tuple(sorted([src_computer, dst_computer])))

while True:
    new_largest_fully_connected = set()
    for fully_connected in largest_fully_connected:
        # Determine all computers for which every computer in the current component has an
        # outgoing edge to that computer
        computers_to_add = connections[fully_connected[0]].copy()
        for src_computer in fully_connected[1:]:
            computers_to_add &= connections[src_computer]

        for computer in computers_to_add:
            new_fully_connected = list(deepcopy(fully_connected))
            new_fully_connected.append(computer)
            new_largest_fully_connected.add(tuple(sorted(new_fully_connected)))

    # If we failed to expand any of the existing sets, then we have a largest one
    if new_largest_fully_connected == set():
        break

    # Otherwise, we have a new collection of fully-connected components
    largest_fully_connected = new_largest_fully_connected

print(f"(Part 2) {','.join(list(list(largest_fully_connected)[0]))}")

from typing import Dict, List, Literal, Tuple, cast


class Gate:
    def __init__(self, inputs: Tuple[str, str], operator: Literal["AND", "OR", "XOR"], output: str) -> None:
        self.inputs = inputs
        self.operator = operator
        self.output = output

    def execute(self, input1: int, input2: int) -> bool:
        if self.operator == "AND":
            return input1 & input2
        elif self.operator == "OR":
            return input1 | input2
        else:
            return input1 ^ input2

    def __repr__(self) -> str:
        return f"{self.inputs[0]} {self.operator} {self.inputs[1]} -> {self.output}"


gates: List[Gate] = []
values: Dict[str, int] = {}


with open("./input.txt", "r") as input_file:
    initial_values_input, gate_input = input_file.read().split("\n\n")

    for line in initial_values_input.splitlines():
        wire, value = line.split(": ")
        values[wire] = int(value)

    for line in gate_input.splitlines():
        input1, operator, input2, _, output = line.split(" ")
        gates.append(Gate((input1, input2), cast(Literal["AND", "OR", "XOR"], operator), output))


#########
# Part 1
#########
while True:
    unsolved_gates = []
    for gate in gates:
        if gate.inputs[0] in values and gate.inputs[1] in values:
            values[gate.output] = gate.execute(values[gate.inputs[0]], values[gate.inputs[1]])
        else:
            unsolved_gates.append(gate)

    if unsolved_gates == []:
        break

ordered_z_bits = sorted(filter(lambda wire: wire.startswith("z"), values.keys()))
final_value = 0
for z_bit_index, z_bit in enumerate(ordered_z_bits):
    final_value += (2 ** z_bit_index) * values[z_bit]
print(f"(Part 1) Final value is {final_value}")


#########
# Part 2
#########
class TreeNode:
    def __init__(self, symbol: str) -> None:
        self.symbol = symbol
        self.children = []

    def add_child(self, child: "TreeNode") -> None:
        self.children.append(child)

    def __repr__(self) -> str:
        if self.symbol in ["AND", "OR", "XOR"]:
            ret = ""
            ret += f"({repr(self.children[0])})"
            ret += f" {self.symbol} "
            ret += f"({repr(self.children[1])})"
            return ret
        else:
            return f"{self.symbol}"

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, TreeNode):
            return False

        if self.symbol != other.symbol:
            return False

        if not self.children:
            return True

        return (
            (self.children[0] == other.children[0] and self.children[1] == other.children[1]) or
            (self.children[0] == other.children[1] and self.children[1] == other.children[0])
        )


def get_expected_c_n_equality(n) -> TreeNode:
    if n == 0:
        ret = TreeNode("AND")
        ret.add_child(TreeNode("x00"))
        ret.add_child(TreeNode("y00"))
        return ret
    else:
        ret = TreeNode("OR")
        left_child = TreeNode("AND")

        left_grandchild = TreeNode("XOR")
        left_grandchild.add_child(TreeNode(f"x{n:02}"))
        left_grandchild.add_child(TreeNode(f"y{n:02}"))

        left_child.add_child(left_grandchild)
        left_child.add_child(get_expected_c_n_equality(n - 1))

        right_child = TreeNode("AND")
        right_child.add_child(TreeNode(f"x{n:02}"))
        right_child.add_child(TreeNode(f"y{n:02}"))

        ret.add_child(left_child)
        ret.add_child(right_child)
        return ret


def get_expected_z_n_equality(n):
    if n == 0:
        ret = TreeNode("XOR")
        ret.add_child(TreeNode("x00"))
        ret.add_child(TreeNode("y00"))
        return ret
    else:
        ret = TreeNode("XOR")
        left_child = TreeNode("XOR")
        left_child.add_child(TreeNode(f"x{n:02}"))
        left_child.add_child(TreeNode(f"y{n:02}"))

        ret.add_child(left_child)
        ret.add_child(get_expected_c_n_equality(n - 1))
        return ret


def get_variable_name_tree(variable_name: str) -> TreeNode:
    if variable_name.startswith(("x", "y")):
        return TreeNode(variable_name)

    for gate in gates:
        if gate.output == variable_name:
            ret = TreeNode(gate.operator)
            ret.add_child(get_variable_name_tree(gate.inputs[0]))
            ret.add_child(get_variable_name_tree(gate.inputs[1]))
            return ret

    assert False


swap_count = 0
while True:
    z_bit_index_wrong_shape = None
    for x in range(43):
        if get_variable_name_tree(f"z{x:02}") != get_expected_z_n_equality(x):
            print(f"z{x:02} is wrong shape")
            z_bit_index_wrong_shape = x
            break

    # If there is no z bit that has the wrong shape, then we are finished, as the adder is
    # working correctly
    if z_bit_index_wrong_shape is None:
        break

    # Otherwise, a gate with z-output (with bit number `z_bit_index_wrong_shape`) is
    # wrong, so try to fix it
    gate_with_bad_output = None
    for gate in gates:
        if gate.output == f"z{z_bit_index_wrong_shape:02}":
            gate_with_bad_output = gate
    assert gate_with_bad_output

    # Try swapping the output wire with every wire (including itself, but this does
    # nothing useful)
    swap_found = False
    for gate in gates:
        temp_output = gate.output
        gate.output = gate_with_bad_output.output
        gate_with_bad_output.output = temp_output

        # Determine if the swap improved the situation
        first_bad_gate = None
        for x in range(43):
            try:
                variable_name_tree = get_variable_name_tree(f"z{x:02}")
            except RecursionError:
                first_bad_gate = 0
                break

            expected_tree = get_expected_z_n_equality(x)
            if variable_name_tree != expected_tree:
                first_bad_gate = x
                break

        # If the first bad gate is not higher, then the swap has helped
        if first_bad_gate is None or first_bad_gate > z_bit_index_wrong_shape:
            swap_count += 1
            swap_found = True
            print(f"Found swap {swap_count} ({temp_output} with {gate.output})")
            break

        # Swap back
        gate_with_bad_output.output = gate.output
        gate.output = temp_output

    if swap_found:
        continue

    # Try instead swapping the first input label
    swap_found = False
    gate_with_first_input = None
    for gate in gates:
        if gate.output == gate_with_bad_output.inputs[0]:
            gate_with_first_input = gate
    assert gate_with_first_input

    for gate in gates:
        temp_output = gate.output
        gate.output = gate_with_first_input.output
        gate_with_first_input.output = temp_output

        # Determine if the swap improved the situation
        first_bad_gate = 0
        for x in range(43):
            try:
                variable_name_tree = get_variable_name_tree(f"z{x:02}")
            except RecursionError:
                x = 0
                break

            expected_tree = get_expected_z_n_equality(x)
            if variable_name_tree != expected_tree:
                first_bad_gate = x
                break

        # If the first bad gate is not higher, then the swap has helped
        if first_bad_gate > z_bit_index_wrong_shape:
            swap_count += 1
            swap_found = True
            print(f"Found swap {swap_count} ({temp_output} with {gate.output})")
            break

        # Swap back
        gate_with_first_input.output = gate.output
        gate.output = temp_output

    if swap_found:
        continue

    # Try instead swapping the second input label
    swap_found = False
    gate_with_second_input = None
    for gate in gates:
        if gate.output == gate_with_bad_output.inputs[1]:
            gate_with_second_input = gate
    assert gate_with_second_input

    for gate in gates:
        temp_output = gate.output
        gate.output = gate_with_second_input.output
        gate_with_second_input.output = temp_output

        # Determine if the swap improved the situation
        first_bad_gate = 0
        for x in range(43):
            try:
                variable_name_tree = get_variable_name_tree(f"z{x:02}")
            except RecursionError:
                x = 0
                break

            expected_tree = get_expected_z_n_equality(x)
            if variable_name_tree != expected_tree:
                first_bad_gate = x
                break

        # If the first bad gate is not higher, then the swap has helped
        if first_bad_gate > z_bit_index_wrong_shape:
            swap_count += 1
            swap_found = True
            print(f"Found swap {swap_count} ({temp_output} with {gate.output})")
            break

        # Swap back
        gate_with_second_input.output = gate.output
        gate.output = temp_output

    if not swap_found:
        print(f"No swap was found")

locks = []
keys = []


with open("./input.txt", "r") as input_file:
    blocks = input_file.read().split("\n\n")

    for block in blocks:
        lines = block.splitlines()

        if lines[0] == "#####":
            # We have a lock
            lock = []
            for x in range(0, 5):
                highest = 0
                for y in range(1, 6):
                    if lines[y][x] != "#":
                        break
                    highest += 1
                lock.append(highest)
            locks.append(lock)
        else:
            # We have a key
            key = []
            for x in range(0, 5):
                highest = 0
                for y in range(5, 0, -1):
                    if lines[y][x] != "#":
                        break
                    highest += 1
                key.append(highest)
            keys.append(key)


def does_key_fit_in_lock(lock, key) -> bool:
    for x in range(0, 5):
        if lock[x] + key[x] > 5:
            return False
    return True


matches = 0
for lock in locks:
    for key in keys:
        matches += 1 if does_key_fit_in_lock(lock, key) else 0

print(f"(Part 1) {matches}")