zerosleeps

from itertools import pairwise
from unittest import TestCase
from utils import get_raw_input


class Cave:
    def __init__(self, raw_input):
        self.build(raw_input)
        self.sand = set()
        self.overflowing = False

    def plot_rocks(self, x1, y1, x2, y2):
        if y1 == y2:
            return [(i, y1) for i in range(min([x1, x2]), max([x1, x2]) + 1)]
        else:
            return [(x1, i) for i in range(min([y1, y2]), max([y1, y2]) + 1)]

    def build(self, raw_input):
        self.rocks = set()
        for line in raw_input:
            for pair in pairwise(line.split(" -> ")):
                self.rocks.update(
                    self.plot_rocks(
                        int(pair[0].split(",")[0]),
                        int(pair[0].split(",")[1]),
                        int(pair[1].split(",")[0]),
                        int(pair[1].split(",")[1]),
                    )
                )

    @property
    def boundaries(self):
        # y_min is highest rock, y_max is lowest rock
        return {
            "x_min": min([rock[0] for rock in self.rocks]),
            "x_max": max([rock[0] for rock in self.rocks]),
            "y_min": min([rock[1] for rock in self.rocks]),
            "y_max": max([rock[1] for rock in self.rocks]),
        }

    def drop_sand(self, floor=False):
        sand_position = (500, 0)
        while True:
            if (
                not floor
                and (
                    sand_position[1] > self.boundaries["y_max"]
                    or sand_position[0] < self.boundaries["x_min"]
                    or sand_position[0] > self.boundaries["x_max"]
                )
            ) or (floor and (500, 0) in self.sand):
                # Out of bounds
                self.overflowing = True
                return
            elif (
                (sand_position[0], sand_position[1] + 1) not in self.rocks
                and (sand_position[0], sand_position[1] + 1) not in self.sand
                and (
                    not floor
                    or (floor and sand_position[1] + 1 < self.boundaries["y_max"] + 2)
                )
            ):
                # Can fall straight down
                sand_position = (sand_position[0], sand_position[1] + 1)
            elif (
                (sand_position[0] - 1, sand_position[1] + 1) not in self.rocks
                and (sand_position[0] - 1, sand_position[1] + 1) not in self.sand
                and (
                    (not floor)
                    or (floor and sand_position[1] + 1 < self.boundaries["y_max"] + 2)
                )
            ):
                # Can fall down-and-left
                sand_position = (sand_position[0] - 1, sand_position[1] + 1)
            elif (
                (sand_position[0] + 1, sand_position[1] + 1) not in self.rocks
                and (sand_position[0] + 1, sand_position[1] + 1) not in self.sand
                and (
                    (not floor)
                    or (floor and sand_position[1] + 1 < self.boundaries["y_max"] + 2)
                )
            ):
                # Can fall down-and-right
                sand_position = (sand_position[0] + 1, sand_position[1] + 1)
            else:
                # Can't move
                self.sand.add(sand_position)
                return


class TestExamples(TestCase):
    def setUp(self):
        self.example_input = [
            "498,4 -> 498,6 -> 496,6",
            "503,4 -> 502,4 -> 502,9 -> 494,9",
        ]
        self.cave = Cave(self.example_input)

    def test_part_one(self):
        self.assertEqual(run(self.cave), 24)

    def test_part_two(self):
        self.assertEqual(run(self.cave, True), 93)


def run(cave, floor=False):
    while not cave.overflowing:
        cave.drop_sand(floor)
    return len(cave.sand)


if __name__ == "__main__":
    print(f"Part one: {run(Cave(get_raw_input('day_14_input.txt')))}")
    print(f"Part two: {run(Cave(get_raw_input('day_14_input.txt')), True)}")

from functools import cmp_to_key
from utils import get_raw_input_as_str

def parse_raw_input(raw_input):
    return [[eval(packet) for packet in pair.splitlines()] for pair in raw_input.split("\n\n")]

def compare(left, right):
    if type(left) == type(right) == list:
        result = None
        i = 0
        while result is None:
            if len(left) != len(right) and len(left) <= i:
                return 1
            elif len(left) != len(right) and len(right) <= i:
                return -1
            elif len(left) == i and len(right) == i:
                return None
            else:
                result = compare(left[i], right[i])
                i += 1
        return result
    elif type(left) == type(right) == int:
        if left < right:
            return 1
        elif left > right:
            return -1
        else:
            return None
    elif type(left) == int and type(right) != int:
        return compare([left], right)
    elif type(right) == int and type(left) != int:
        return compare(left, [right])
    else:
        raise Exception

def part_one(input):
    return sum([i + 1 for i, pair in enumerate(input) if compare(pair[0], pair[1]) == 1])

def part_two(input):
    flattened_input = [packet for pair in input for packet in pair] + [[[2]]] + [[[6]]]
    sorted_packets = sorted(flattened_input, key=cmp_to_key(compare), reverse=True)
    return (sorted_packets.index([[2]]) + 1) * (sorted_packets.index([[6]]) + 1)

if __name__ == '__main__':
    print(f"Part one: {part_one(parse_raw_input(get_raw_input_as_str('day_13_input.txt')))}")
    print(f"Part one: {part_two(parse_raw_input(get_raw_input_as_str('day_13_input.txt')))}")

from functools import cmp_to_key
from utils import get_raw_input_as_str

def parse_raw_input(raw_input):
    return [[eval(packet) for packet in pair.splitlines()] for pair in raw_input.split("\n\n")]

def compare(left, right):
    if type(left) == type(right) == int:
        if left < right:
            return 1
        elif left > right:
            return -1
        else:
            return None
    elif type(left) == type(right) == list:
        result = None
        i = 0
        while result is None:
            if len(left) <= i and len(right) >= i:
                return 1
            elif len(right) <= i and len(left) >= i:
                return -1
            else:
                result = compare(left[i], right[i])
                i += 1
        return result
    elif type(left) == int and type(right) != int:
        return compare([left], right)
    elif type(right) == int and type(left) != int:
        return compare(left, [right])
    else:
        return None

def part_one(input):
    return sum([i + 1 for i, pair in enumerate(input) if compare(pair[0], pair[1]) == 1])

def part_two(input):
    flattened_input = [packet for pair in input for packet in pair] + [[[2]]] + [[[6]]]
    sorted_packets = sorted(flattened_input, key=cmp_to_key(compare), reverse=True)
    return (sorted_packets.index([[2]]) + 1) * (sorted_packets.index([[6]]) + 1)

if __name__ == '__main__':
    print(part_one(parse_raw_input(get_raw_input_as_str("day_13_input.txt"))))
    print(part_two(parse_raw_input(get_raw_input_as_str("day_13_input.txt"))))

import heapq
from string import ascii_lowercase
from utils import get_raw_input


class Heightmap:
    def __init__(self, raw_input):
        self.input_to_heightmap(raw_input)

    def input_to_heightmap(self, raw_input):
        self.heightmap = []
        for y, line in enumerate(raw_input):
            row = []
            for x, char in enumerate(line):
                if char == "S":
                    self.start = (x, y)
                    row.append(0)
                elif char == "E":
                    self.goal = (x, y)
                    row.append(25)
                else:
                    row.append(ascii_lowercase.index(char))
            self.heightmap.append(row)

    @property
    def node_keys(self):
        return [
            (x, y)
            for y in range(len(self.heightmap))
            for x in range(len(self.heightmap[y]))
        ]

    def node_value(self, node_key):
        if node_key in self.node_keys:
            return self.heightmap[node_key[1]][node_key[0]]
        return None

    def get_neighboring_nodes(self, node):
        candidates = [
            (node[0], node[1] - 1),
            (node[0] + 1, node[1]),
            (node[0], node[1] + 1),
            (node[0] - 1, node[1]),
        ]
        return [
            candidate
            for candidate in candidates
            if candidate in self.node_keys
            and self.node_value(candidate) - self.node_value(node) <= 1
        ]

    def manhattan_distance(self, current, neighbor):
        return abs(current[0] - neighbor[0]) + abs(current[1] - neighbor[1])

    def reconstruct_path(self, came_from, current):
        final_path = [current]
        while current in came_from.keys():
            current = came_from[current]
            final_path.insert(0, current)
        return final_path

    def a_star(self):
        open_set = [(0, self.start)]
        came_from = {}
        g_score = {self.start: 0}
        while open_set:
            current = heapq.heappop(open_set)[1]
            if current == self.goal:
                return self.reconstruct_path(came_from, current)
            for neighbor in self.get_neighboring_nodes(current):
                tentative_g_score = g_score[current] + 1
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    heapq.heappush(
                        open_set,
                        (
                            tentative_g_score
                            + self.manhattan_distance(current, neighbor),
                            neighbor,
                        ),
                    )


if __name__ == "__main__":
    heightmap = Heightmap(get_raw_input("day_12_input.txt"))
    print(f"{len(heightmap.a_star())=}")