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()}")