def process_input(raw_elf_calories: str) -> list[list[str]]:
    """Read the text file and read into a list of lists containing calories for each elf"""
    calories = raw_elf_calories.split("\n\n")
    elf_calories = [list(filter(None, elf.split("\n"))) for elf in calories]

    return elf_calories


def aggregate_calories(elf_calories: list[list[str]]) -> list[int]:
    """Sum the calories for all elves"""
    return [sum(int(item) for item in calories) for calories in elf_calories]


def part_1(aggregated_calories: list[int]) -> int:
    """Max calories carried by an elf"""
    return max(aggregated_calories)


def part_2(aggregated_calories: list) -> int:
    """Return sum of top three calorie carrying elves"""
    sorted_elf_calories = sorted(aggregated_calories, reverse=True)
    top_3 = sorted_elf_calories[:3]
    return sum(top_3)


if __name__ == "__main__":

    with open("input.txt", "r", encoding="utf-8") as input_values:
        raw_elf_calories = input_values.read()

    elf_calories = process_input(raw_elf_calories)
    aggregated_calories = aggregate_calories(elf_calories)

    part_1_ans = part_1(aggregated_calories)
    print(part_1_ans)

    part_2_ans = part_2(aggregated_calories)
    print(part_2_ans)

from typing import Callable

SHAPE_SCORE = {"A": 1, "B": 2, "C": 3, "X": 1, "Y": 2, "Z": 3}
ROUND_SCORE = {"L": 0, "D": 3, "W": 6, "X": 0, "Y": 3, "Z": 6}

OUTCOMES = {
    "A X": "D",
    "A Y": "W",
    "A Z": "L",
    "B X": "L",
    "B Y": "D",
    "B Z": "W",
    "C X": "W",
    "C Y": "L",
    "C Z": "D",
}

REQUIRED_SELECTION = {
    "A X": "C",
    "A Y": "A",
    "A Z": "B",
    "B X": "A",
    "B Y": "B",
    "B Z": "C",
    "C X": "B",
    "C Y": "C",
    "C Z": "A",
}

RuleFunc = Callable[[str], int]


def part_1(moves: str) -> int:
    result = OUTCOMES[moves]
    my_move = moves[-1]
    return SHAPE_SCORE[my_move] + ROUND_SCORE[result]


def part_2(moves: str) -> int:
    result = moves[-1]
    my_move = REQUIRED_SELECTION[moves]
    return SHAPE_SCORE[my_move] + ROUND_SCORE[result]


def calc_total_score(strategy_guide: list[str], rule_func: RuleFunc) -> int:
    round_scores = []
    for moves in strategy_guide:
        round_score = rule_func(moves)
        round_scores.append(round_score)

    return sum(round_scores)


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as input_file:
        raw_strategy_guide = input_file.readlines()
        strategy_guide = [line.strip() for line in raw_strategy_guide]

    part_1_ans = calc_total_score(strategy_guide, part_1)
    print(part_1_ans)

    part_2_ans = calc_total_score(strategy_guide, part_2)
    print(part_2_ans)

import string
from typing import Protocol, Any


class GroupFunc(Protocol):
    def __call__(self, lst: list[str], **kwargs: Any) -> list[list[str]]:
        ...


def find_intersection(*item_strings) -> str:
    intersection = set.intersection(*map(set, item_strings))
    return intersection.pop()


def get_priority(letter: str) -> int:
    priority_order = string.ascii_lowercase + string.ascii_uppercase
    return priority_order.index(letter) + 1


def split_into_compartments(lst):
    def midpoint(lst):
        return len(lst) // 2

    return [[i[: midpoint(i)], i[midpoint(i) :]] for i in lst]


def split_into_groups(lst: list[str], n: int) -> list[list[str]]:
    return [lst[i : i + n] for i in range(0, len(lst), n)]


def calc_total_priority(rucksacks: list[str], grouping_func: GroupFunc, **kwargs):

    groups = grouping_func(rucksacks, **kwargs)

    total = 0
    for group in groups:
        intersection = find_intersection(*group)
        priority = get_priority(intersection[0])
        total += priority

    return total


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as input_file:
        rucksacks = [rucksack.strip() for rucksack in input_file.readlines()]

    part_1_ans = calc_total_priority(rucksacks, split_into_compartments)
    print(part_1_ans)

    part_2_ans = calc_total_priority(rucksacks, split_into_groups, n=3)
    print(part_2_ans)

from typing import Callable

OverlapCondition = Callable[[int, int, int, int], int]


def part_1(l1_min: int, l1_max: int, l2_min: int, l2_max: int) -> bool:
    return ((l1_min <= l2_min) & (l1_max >= l2_max)) or (
        (l2_min <= l1_min) & (l2_max >= l1_max)
    )


def part_2(l1_min: int, l1_max: int, l2_min: int, l2_max: int) -> bool:
    return (l1_min <= l2_min <= l1_max) or (l2_min <= l1_min <= l2_max)


def calc_total(sections: list[list[int]], func: OverlapCondition) -> int:
    return sum(func(*item) for item in sections)


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as input_data:
        pairs = [pair.strip() for pair in input_data.readlines()]
        sections = [[*map(int, pair.replace("-", ",").split(","))] for pair in pairs]

    part_1_ans = calc_total(sections, part_1)
    print(part_1_ans)

    part_2_ans = calc_total(sections, part_2)
    print(part_2_ans)

import re
from collections import defaultdict, deque
from copy import deepcopy
from typing import Callable

MoveCratesFunc = Callable[
    [dict[int, deque[str]], list[tuple[int, int, int]]], dict[int, deque[str]]
]


def parse_stacks_string(stacks_string: str) -> defaultdict[int, deque[str]]:
    stack_rows = stacks_string.split("\n")[:-1]
    stacks = defaultdict(deque)

    # start from bottom up
    for row in reversed(stack_rows):
        # parse through each row to extract letters
        for stack_num, crate in enumerate(row[1::4], start=1):
            if crate.isalpha():
                stacks[stack_num].append(crate)
    return stacks


def parse_instructions_string(instructions_string: str) -> list[tuple[int, int, int]]:
    instructions = []
    for instruction in instructions_string.split("\n"):
        if instruction.strip():
            numbers = [int(number) for number in re.findall(r"\d+", instruction)]
            instructions.append(tuple(numbers))
    return instructions


def process_input(
    raw_input: str,
) -> tuple[defaultdict[int, deque[str]], list[tuple[int, int, int]]]:
    """Split raw input into starting stacks and instructions"""
    stacks_string, instructions_string = raw_input.split("\n\n")
    stacks = parse_stacks_string(stacks_string)
    instructions = parse_instructions_string(instructions_string)
    return stacks, instructions


def solve(
    stacks: defaultdict[int, deque],
    instructions: list[tuple[int, int, int]],
    move_crates: MoveCratesFunc,
) -> str:
    stacks_copy = deepcopy(stacks)
    moved_stacks = move_crates(stacks_copy, instructions)
    return "".join([stack.pop() for stack in moved_stacks.values()])


def part_1(
    stacks: defaultdict[int, deque], instructions: list[tuple[int, int, int]]
) -> defaultdict[int, deque[str]]:
    """Cratemover 9000 stacking function"""
    for move, source, target in instructions:
        for _ in range(move):
            crate = stacks[source].pop()
            stacks[target].append(crate)
    return stacks


def part_2(
    stacks: defaultdict[int, deque], instructions: list[tuple[int, int, int]]
) -> defaultdict[int, deque[str]]:
    """Cratemover 9001 stacking function"""
    for move, source, target in instructions:
        group = []
        for _ in range(move):
            crate = stacks[source].pop()
            group.append(crate)
        stacks[target].extend(group[::-1])
    return stacks


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        raw_input = puzzle_input.read()

    stacks, instructions = process_input(raw_input)

    part_1_ans = solve(stacks, instructions, part_1)
    print(part_1_ans)

    part_2_ans = solve(stacks, instructions, part_2)
    print(part_2_ans)

def get_message_marker(datastream: str, window_size: int) -> int:
    for i in range(len(datastream) - window_size + 1):
        window = datastream[i : i + window_size]
        seq_start_index = i + window_size
        if len(set(window)) == window_size:
            return seq_start_index
    raise ValueError("No sequence without repeated characters")


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        datastream = puzzle_input.read().strip()

    part_1_ans = get_message_marker(datastream, window_size=4)
    print(part_1_ans)

    part_2_ans = get_message_marker(datastream, window_size=14)
    print(part_2_ans)

from pathlib import Path


def get_dir_tree(commands: list[str]) -> dict:
    level = Path("")
    dir_tree = {}
    for entry in commands:
        if "$ cd" in entry:
            if ".." in entry:
                level = level.parent
            else:
                direc_name = entry[5:]
                level = level / direc_name
                if level not in dir_tree:
                    dir_tree[level] = []
        elif "dir" in entry:
            _, direc_name = entry.split(" ")
            dir_tree[level].append(level / direc_name)
        elif entry[0].isnumeric():
            file_size, file_name = entry.split(" ")
            dir_tree[level].append((file_name, int(file_size)))
    return dir_tree


def total_dir_size(dir_path: Path, dir_tree: dict) -> int:
    total_size = 0
    for object in dir_tree[dir_path]:
        if isinstance(object, tuple):
            total_size += object[1]
        elif isinstance(object, Path):
            total_size += total_dir_size(object, dir_tree)
    return total_size


def get_dir_sizes(dir_tree: dict) -> dict:
    return {dir: total_dir_size(dir, dir_tree) for dir in dir_tree}


def part_1(dir_sizes: dict, threshold: int) -> int:
    return sum(dir_size for dir_size in dir_sizes.values() if dir_size < threshold)


def part_2(dir_sizes: dict, max_disk_space: int, required_disk_space: int) -> None:
    total_space_used = dir_sizes[Path("/")]
    initial_free_space = max_disk_space - total_space_used
    clearable_space = required_disk_space - initial_free_space

    min_removeable_dir = (max_disk_space, Path("Random/Path"))

    for dir in dir_sizes:
        if dir_sizes[dir] >= clearable_space:
            if dir_sizes[dir] < min_removeable_dir[0]:
                min_removeable_dir = (dir_sizes[dir], dir)
    return min_removeable_dir[0]


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        commands = [line.strip() for line in puzzle_input.readlines()]

    dir_tree = get_dir_tree(commands)
    dir_sizes = get_dir_sizes(dir_tree)

    part_1_ans = part_1(dir_sizes, threshold=100_000)
    print(part_1_ans)

    part_2_ans = part_2(
        dir_sizes,
        max_disk_space=70_000_000,
        required_disk_space=30_000_000,
    )
    print(part_2_ans)

from functools import reduce

SightLines = tuple[list[int], list[int], list[int], list[int]]
Grid = list[list[int]]


def create_grid(raw_string: str) -> Grid:
    lines = list(filter(None, raw_string.split("\n")))
    return [[int(height) for height in line] for line in lines]


def count_perimiter(grid: Grid) -> int:
    return ((len(grid) + len(grid[0])) * 2) - 4


def get_sight_lines(x: int, y: int, grid: Grid) -> SightLines:
    left = grid[y][:x][::-1]
    right = grid[y][x + 1 :]
    top = [row[x] for row in grid[:y]][::-1]
    bottom = [row[x] for row in grid[y + 1 :]]
    return left, right, top, bottom


def check_visible(height: int, sight_lines: SightLines) -> bool:
    return any([height > max(line) for line in sight_lines if line])


def part_1(grid: Grid) -> int:
    # outer trees always visible
    visible_count = count_perimiter(grid)
    for x in range(1, len(grid[0]) - 1):
        for y in range(1, len(grid) - 1):
            sight_lines = get_sight_lines(x, y, grid)
            height = grid[y][x]
            if check_visible(height, sight_lines):
                visible_count += 1
    return visible_count


def calc_scenic_score(height: int, sight_lines: SightLines) -> int:
    views = []
    for line in sight_lines:
        if line:
            for i, tree in enumerate(line):
                if tree >= height:
                    break
            views.append(len(line[: i + 1]))
    return reduce(lambda x, y: x * y, views)


def part_2(grid: Grid) -> int:
    max_scenic_score = 0
    for x in range(1, len(grid[0]) - 1):
        for y in range(1, len(grid) - 1):
            sight_lines = get_sight_lines(x, y, grid)
            height = grid[y][x]
            scenic_score = calc_scenic_score(height, sight_lines)
            if scenic_score > max_scenic_score:
                max_scenic_score = scenic_score
    return max_scenic_score


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        raw_input = puzzle_input.read().strip()

    grid = create_grid(raw_input)
    part_1_ans = part_1(grid)
    print(part_1_ans)

    part_2_ans = part_2(grid)
    print(part_2_ans)

def process_input(input_string: str) -> list[tuple[str, int]]:
    instructions = [line.split(" ") for line in input_string.split("\n") if line]
    return [(d, int(n)) for [d, n] in instructions]


def move_tail(hx: int, hy: int, tx: int, ty: int) -> tuple[int, int]:
    dist = abs(hx - tx) + abs(hy - ty)
    if hx == tx and dist >= 2:
        return (tx, hy - 1 if hy > ty else hy + 1)
    if hy == ty and dist >= 2:
        return (hx - 1 if hx > tx else hx + 1, ty)
    if dist > 2:
        if hx > tx:
            return (tx + 1, ty + 1 if hy > ty else ty - 1)
        if hx < tx:
            return (tx - 1, ty + 1 if hy > ty else ty - 1)
    return tx, ty


def solve(instructions: list[tuple[str, int]], knots: int) -> int:
    history = {i: [(0, 0)] for i in range(knots + 1)}
    for direction, steps in instructions:
        for _ in range(steps):
            hx, hy = history[0][-1]
            match direction:
                case "R":
                    hx += 1
                case "L":
                    hx -= 1
                case "U":
                    hy += 1
                case "D":
                    hy -= 1
            history[0].append((hx, hy))
            for k in range(1, knots + 1):
                tx, ty = move_tail(*history[k - 1][-1], *history[k][-1])
                history[k].append((tx, ty))
    return len(set(history[knots]))


if __name__ == "__main__":

    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        data = puzzle_input.read().strip()

    instructions = process_input(data)

    part_1_ans = solve(instructions, knots=1)
    print(part_1_ans)

    part_2_ans = solve(instructions, knots=9)
    print(part_2_ans)

def run_operations(input_file: str):
    with open(input_file, "r", encoding="utf-8") as puzzle_input:
        instructions = puzzle_input.read()

    x = 1
    for line in instructions.splitlines():
        yield x
        if line != "noop":
            yield x
            x += int(line[5:])


def part_1(input_file: str, width: int):
    interesting_signal_strength = []
    for cycle, x in enumerate(run_operations(input_file), 1):
        if cycle % width == 20:
            interesting_signal_strength.append(cycle * x)
    return sum(interesting_signal_strength)


def part_2(input_file: str, width: int):
    rows = []
    row_string = ""
    for cycle, x in enumerate(run_operations(input_file)):
        row_string += ".#"[abs(cycle % width - x) < 2]
        if (cycle + 1) % width == 0:
            rows.append(row_string)
            row_string = ""

    for row in rows:
        print(row)


if __name__ == "__main__":
    part_1_ans = part_1(input_file="input.txt", width=40)
    print(part_1_ans)

    part_2(input_file="input.txt", width=40)

from collections import defaultdict, deque
from copy import deepcopy
from dataclasses import dataclass


@dataclass
class Monkey:
    items: list[int]
    operation: str
    test: int
    target: tuple[int, int]


def parse_input(input) -> list:
    monkeys = []

    monkeys_string = [monkey.strip() for monkey in input.split("\n\n")]
    for m in monkeys_string:

        name, items, operation, test, if_true, if_false = [
            line.strip() for line in m.split("\n")
        ]
        items = deque([int(item.strip()) for item in items[16:].split(",")])
        operation = operation.split("=")[-1].strip()
        test = int(test.split(" ")[-1])
        if_true = int(if_true.split(" ")[-1])
        if_false = int(if_false.split(" ")[-1])
        target = (if_false, if_true)

        monkeys.append(Monkey(items, operation, test, target))
    return monkeys


def solve(monkeys: list, part: int, rounds: int) -> int:

    monkeys = deepcopy(monkeys)

    divisor = 1
    for m in monkeys:
        divisor *= m.test

    counter = defaultdict(int)
    for _ in range(rounds):
        for i, m in enumerate(monkeys):
            while m.items:
                counter[i] += 1

                old = m.items.popleft()
                new = eval(m.operation)
                if part == 1:
                    new //= 3
                else:
                    new %= divisor
                test = (new % m.test) == 0
                target_monkey = m.target[test]
                monkeys[target_monkey].items.append(new)

    top, second = sorted(counter.values(), reverse=True)[:2]
    return top * second


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        monkeys_string = puzzle_input.read()

    monkeys = parse_input(monkeys_string)

    part_1_ans = solve(monkeys, part=1, rounds=20)
    print(part_1_ans)

    part_2_ans = solve(monkeys, part=2, rounds=10_000)
    print(part_2_ans)

import string

import networkx as nx
import numpy as np
from networkx import NetworkXNoPath


def char_to_index(char):
    if char == "S":
        return 1
    if char == "E":
        return 26
    return string.ascii_lowercase.index(char) + 1


def get_node(area, char):
    dest = np.where(area == char)
    return index_to_node(len(area[0]), int(dest[0]), int(dest[1]))


def get_starting_nodes(area):
    nodes = []
    options = np.where(area == "a")
    for i in range(len(options[0])):
        nodes.append(
            index_to_node(len(area[0]), int(options[0][i]), int(options[1][i]))
        )
    nodes.append(get_node(area, "S"))
    return nodes


def index_to_node(row_length, y, x):
    return (y * row_length) + x + 1


def get_neighbour_edges(x, y, area):
    edges = []
    current_node = index_to_node(len(area[0]), y, x)
    current_value = char_to_index(area[y][x])

    if x > 0 and char_to_index(area[y][x - 1]) <= current_value + 1:
        edges.append([current_node, index_to_node(len(area[0]), y, x - 1)])
    if x < len(area[0]) - 1 and char_to_index(area[y][x + 1]) <= current_value + 1:
        edges.append([current_node, index_to_node(len(area[0]), y, x + 1)])
    if y > 0 and char_to_index(area[y - 1][x]) <= current_value + 1:
        edges.append([current_node, index_to_node(len(area[0]), y - 1, x)])
    if y < len(area) - 1 and char_to_index(area[y + 1][x]) <= current_value + 1:
        edges.append([current_node, index_to_node(len(area[0]), y + 1, x)])
    return edges


def build_graph(area):
    graph = nx.DiGraph()
    for index_y, line in enumerate(area):
        for index_x, cell in enumerate(line):
            edges = get_neighbour_edges(index_x, index_y, area)
            for edge in edges:
                graph.add_edge(edge[0], edge[1])
    return graph


def part_1(graph, start, dest):
    return len(nx.shortest_path(graph, source=start, target=dest)) - 1


def part_2(graph, area, dest):
    options = get_starting_nodes(area)
    shortest_path = None
    for option in options:
        try:
            attempted_path = part_1(graph, option, dest)
            if not shortest_path:
                shortest_path = attempted_path
            elif attempted_path < shortest_path:
                shortest_path = attempted_path
        except NetworkXNoPath:
            pass
    return shortest_path


if __name__ == "__main__":
    area = np.genfromtxt("input.txt", delimiter=1, dtype=str)

    start = get_node(area, "S")
    dest = get_node(area, "E")
    graph = build_graph(area)

    part_1_ans = part_1(graph, start, dest)
    print(part_1_ans)

    part_2_ans = part_2(graph, area, dest)
    print(part_2_ans)

import ast
from functools import cmp_to_key
from itertools import zip_longest


def process_input(raw_input: str) -> list:
    processed_input = []
    for packet in raw_input.strip().split("\n\n"):
        processed_pair = list(map(ast.literal_eval, packet.split("\n")))
        processed_input.append(processed_pair)

    return processed_input


def compare(left, right):
    if left is None:
        return -1
    if right is None:
        return 1

    if isinstance(left, int) and isinstance(right, int):
        if left < right:
            return -1
        if left > right:
            return 1
        return
    elif isinstance(left, list) and isinstance(right, list):
        for new_left, new_right in zip_longest(left, right):
            if (result := compare(new_left, new_right)) is not None:
                return result
        return
    else:
        new_left = [left] if isinstance(left, int) else left
        new_right = [right] if isinstance(right, int) else right
        return compare(new_left, new_right)


def part_1(packets):
    results = [compare(*packet) for packet in packets]
    true_indices = [index + 1 for index, item in enumerate(results) if item == -1]
    return sum(true_indices)


def part_2(packets):
    div1, div2 = [[2]], [[6]]
    flat_list = [item for sublist in packets for item in sublist]
    sorted_packets = sorted([*flat_list, div1, div2], key=cmp_to_key(compare))
    return (sorted_packets.index(div1) + 1) * (sorted_packets.index(div2) + 1)


if __name__ == "__main__":
    with open("input.txt", "r", encoding="utf-8") as puzzle_input:
        raw_input = puzzle_input.read()

    packets = process_input(raw_input)

    part_1_ans = part_1(packets)
    print(part_1_ans)

    part_2_ans = part_2(packets)
    print(part_2_ans)