From d7e30321ae6ae4c82a8ab7455f6ce33afd719c67 Mon Sep 17 00:00:00 2001 From: Tom van der Lee Date: Sun, 19 Nov 2023 16:55:03 +0100 Subject: Initial commit --- aoc/__init__.py | 43 +++++++++++++++ aoc/__main__.py | 72 +++++++++++++++++++++++++ aoc/datastructures.py | 98 ++++++++++++++++++++++++++++++++++ aoc/decorators.py | 29 ++++++++++ aoc/mixins.py | 77 +++++++++++++++++++++++++++ aoc/template/__init__.py | 16 ++++++ aoc/template/example.txt | 0 aoc/template/input.txt | 0 aoc/test_init.py | 8 +++ aoc/tests/__init__.py | 0 aoc/tests/test_datastructures.py | 112 +++++++++++++++++++++++++++++++++++++++ aoc/utils.py | 6 +++ 12 files changed, 461 insertions(+) create mode 100644 aoc/__init__.py create mode 100644 aoc/__main__.py create mode 100644 aoc/datastructures.py create mode 100644 aoc/decorators.py create mode 100644 aoc/mixins.py create mode 100644 aoc/template/__init__.py create mode 100644 aoc/template/example.txt create mode 100644 aoc/template/input.txt create mode 100644 aoc/test_init.py create mode 100644 aoc/tests/__init__.py create mode 100644 aoc/tests/test_datastructures.py create mode 100644 aoc/utils.py (limited to 'aoc') diff --git a/aoc/__init__.py b/aoc/__init__.py new file mode 100644 index 0000000..7a089f6 --- /dev/null +++ b/aoc/__init__.py @@ -0,0 +1,43 @@ +# -*- coding: utf-8 -*- +import os +from abc import ABC +from typing import Generator, Any, Iterator, Dict, TypeVar, Generic + +T = TypeVar("T") +I = TypeVar("I") + + +class BaseAssignment(Generic[T, I], ABC): + example_result: T = NotImplemented + example_kwargs: Dict = {} + + def __init__(self, path): + self.path = path + + def __str__(self): + return f"{self.__module__}.{self.__class__.__name__}" + + def parse_item(self, item: str) -> I: + return item + + @property + def part(self) -> int: + return 1 if self.__class__.__name__.endswith("One") else 2 + + def read_input(self, example=False) -> Iterator[I]: + file = f"{self.path}/input.txt" + + if example or not os.path.isfile(file): + for file in [ + f"{self.path}/example_part_{self.part}.txt", + f"{self.path}/example.txt", + ]: + if os.path.exists(file): + break + + with open(file, "r") as input_file: + for line in input_file.readlines(): + yield self.parse_item(line.strip("\n")) + + def run(self, input: Iterator[I]) -> T: + raise NotImplementedError("Please implement run") diff --git a/aoc/__main__.py b/aoc/__main__.py new file mode 100644 index 0000000..596abee --- /dev/null +++ b/aoc/__main__.py @@ -0,0 +1,72 @@ +# -*- coding: utf-8 -*- +import enum +import typing +import importlib +import os +from pathlib import Path +from shutil import copytree +from time import perf_counter +from typing import List, Callable +import typer + +app = typer.Typer() + + +class AssignmentPart(str, enum.Enum): + One = "1" + Two = "2" + + +def day(assignment_part: str) -> str: + return AssignmentPart(assignment_part).name + + +def kwargs(kwarg: str) -> List: + return kwarg.split("=") + + +@app.command() +def run( + day: str, + part: str = typer.Option( + "1", "--part", help="Assignment part. Defaults to 'One'.", show_choices=True + ), + example: bool = typer.Option(False, "--example", help="Use an example input file"), + kwargs: List[str] = typer.Argument(None), +): + assignment_day = importlib.import_module(day) + + Assignment = getattr(assignment_day, f"Assignment{AssignmentPart(part).name}") + assignment = Assignment( + path=os.path.dirname(assignment_day.__file__), **dict(kwargs) + ) + + start = perf_counter() + typer.echo( + assignment.run( + input=assignment.read_input(example=example), + ) + ) + end = perf_counter() + delta = end - start + typer.secho( + f'\n{(delta if delta > 1 else delta * 1000):.3f}{"s" if delta > 1 else "ms"}', + fg="green", + ) + + +@app.command() +def new(day: str): + self = importlib.import_module(".", package="aoc") + path = Path(self.__file__) + template = path.parent.joinpath("template") + target = path.parent.parent.joinpath(day) + + try: + copytree(template, target) + except FileExistsError: + typer.secho(f"{day} already exists", fg="red") + + +if __name__ == "__main__": + app() diff --git a/aoc/datastructures.py b/aoc/datastructures.py new file mode 100644 index 0000000..1f141e2 --- /dev/null +++ b/aoc/datastructures.py @@ -0,0 +1,98 @@ +# -*- coding: utf-8 -*- +from collections import namedtuple +from typing import Iterator + + +class Coordinate(namedtuple("Coordinate", ["x", "y"])): + def __sub__(self, other: "Coordinate") -> "Coordinate": + return Coordinate(self.x - other.x, self.y - other.y) + + def __add__(self, other: "Coordinate") -> "Coordinate": + return Coordinate(self.x + other.x, self.y + other.y) + + def manhattan_distance(self, other: "Coordinate") -> int: + return abs(self.x - other.x) + abs(self.y - other.y) + + @property + def polarity(self) -> "Coordinate": + try: + px = abs(self.x) / self.x + except ZeroDivisionError: + px = 0 + + try: + py = abs(self.y) / self.y + except ZeroDivisionError: + py = 0 + + return Coordinate( + px, + py, + ) + + def neighbours(self, no_diagonal: bool = False) -> Iterator["Coordinate"]: + if no_diagonal: + yield self + Coordinate(-1, 0) + yield self + Coordinate(1, 0) + yield self + Coordinate(0, -1) + yield self + Coordinate(0, 1) + else: + for dy in range(self.y - 1, self.y + 2): + for dx in range(self.x - 1, self.x + 2): + if dy == self.y and dx == self.x: + continue + + yield Coordinate(dx, dy) + + +class Coordinate3(namedtuple("Coordinate3", ["x", "y", "z"])): + def __sub__(self, other: "Coordinate3") -> "Coordinate3": + return Coordinate3(self.x - other.x, self.y - other.y, self.z - other.z) + + def __add__(self, other: "Coordinate3") -> "Coordinate3": + return Coordinate3(self.x + other.x, self.y + other.y, self.z + other.z) + + def manhattan_distance(self, other: "Coordinate3") -> int: + return abs(self.x - other.x) + abs(self.y - other.y) + abs(self.z - other.z) + + @property + def polarity(self) -> "Coordinate3": + try: + px = abs(self.x) / self.x + except ZeroDivisionError: + px = 0 + + try: + py = abs(self.y) / self.y + except ZeroDivisionError: + py = 0 + + try: + pz = abs(self.z) / self.z + except ZeroDivisionError: + pz = 0 + + return Coordinate3( + px, + py, + pz, + ) + + def neighbours(self, no_diagonal: bool = False) -> Iterator["Coordinate3"]: + if no_diagonal: + yield self + Coordinate3(-1, 0, 0) + yield self + Coordinate3(1, 0, 0) + yield self + Coordinate3(0, -1, 0) + yield self + Coordinate3(0, 1, 0) + yield self + Coordinate3(0, 0, -1) + yield self + Coordinate3(0, 0, 1) + else: + for dz in range(self.z - 1, self.z + 2): + for dy in range(self.y - 1, self.y + 2): + for dx in range(self.x - 1, self.x + 2): + coordinate = Coordinate3(dx, dy, dz) + + if dy == self.y and dx == self.x and dz == self.z: + continue + + yield coordinate diff --git a/aoc/decorators.py b/aoc/decorators.py new file mode 100644 index 0000000..98246e6 --- /dev/null +++ b/aoc/decorators.py @@ -0,0 +1,29 @@ +# -*- coding: utf-8 -*- +from functools import wraps +from typing import Iterator, TypeVar, Callable, List + +T = TypeVar("T") +I = TypeVar("I") + +AssignmentRun = Callable[[Iterator[I], ...], Iterator[T]] +AssignmentRunList = Callable[[List[I], ...], Iterator[T]] + + +def infinite_generator(func: AssignmentRun) -> AssignmentRun: + @wraps(func) + def wrapper(*args, **kwargs): + items = list(func(*args, **kwargs)) + + while True: + for item in items: + yield item + + return wrapper + + +def list_input(func: AssignmentRun) -> AssignmentRunList: + @wraps(func) + def wrapper(self, input: Iterator, *args, **kwargs) -> T: + return func(self, list(input), *args, **kwargs) + + return wrapper diff --git a/aoc/mixins.py b/aoc/mixins.py new file mode 100644 index 0000000..5986b6e --- /dev/null +++ b/aoc/mixins.py @@ -0,0 +1,77 @@ +# -*- coding: utf-8 -*- +from math import floor, inf +from typing import Tuple, TypeVar, Generic, Callable, Iterator, List, Dict + +Node = TypeVar("Node") + + +class AStarMixin(Generic[Node]): + def _gen_path(self, current: Node, came_from: Dict[Node, Node]) -> List[Node]: + print("GENPATH") + path = [current] + + while current in came_from: + current = came_from[current] + path = [current, *path] + + return path + + def a_star( + self, + start: Node, + end: Callable[[Node, Callable[[], List[Node]]], bool], + neighbours: Callable[[Node], Iterator[Node]], + distance: Callable[[Node, Node], int] = lambda a, b: 1, + heuristic: Callable[[Node], int] = lambda a: 0, + ) -> List[Node]: + open_nodes = {start} + came_from = {} + + g_scores = {start: 0} + + f_scores = {start: heuristic(start)} + + while True: + try: + current = sorted( + [item for item in open_nodes], + key=lambda item: f_scores.get(item, inf), + )[0] + except IndexError: + raise RuntimeError("No path found") + + if end(current, lambda: self._gen_path(current, came_from)): + return self._gen_path(current, came_from) + + open_nodes.remove(current) + + for neighbour in neighbours(current): + g_score = g_scores.get(current, inf) + distance(current, neighbour) + + if g_score < g_scores.get(neighbour, inf): + came_from[neighbour] = current + g_scores[neighbour] = g_score + f_scores[neighbour] = g_score + heuristic(neighbour) + + if neighbour not in open_nodes: + open_nodes.add(neighbour) + + +class BreathFirstSearchMixin(Generic[Node]): + @staticmethod + def bfs( + start: Node, neighbours: Callable[[Node], Iterator[Node]] + ) -> Iterator[Node]: + queue = [start] + searched = set() + + while len(queue): + item = queue.pop(0) + + for neighbour in neighbours(item): + if neighbour not in searched and neighbour not in set(queue): + queue.append(neighbour) + + searched.add(item) + + yield item diff --git a/aoc/template/__init__.py b/aoc/template/__init__.py new file mode 100644 index 0000000..05b2b45 --- /dev/null +++ b/aoc/template/__init__.py @@ -0,0 +1,16 @@ +# -*- coding: utf-8 -*- +from abc import ABC + +from aoc import BaseAssignment + + +class Assignment(BaseAssignment, ABC): + pass + + +class AssignmentOne(Assignment): + pass + + +class AssignmentTwo(Assignment): + pass diff --git a/aoc/template/example.txt b/aoc/template/example.txt new file mode 100644 index 0000000..e69de29 diff --git a/aoc/template/input.txt b/aoc/template/input.txt new file mode 100644 index 0000000..e69de29 diff --git a/aoc/test_init.py b/aoc/test_init.py new file mode 100644 index 0000000..e52daf7 --- /dev/null +++ b/aoc/test_init.py @@ -0,0 +1,8 @@ +# -*- coding: utf-8 -*- +def test_assignment_examples(assignment): + assert ( + assignment.run( + input=assignment.read_input(example=True), **assignment.example_kwargs + ) + == assignment.example_result + ) diff --git a/aoc/tests/__init__.py b/aoc/tests/__init__.py new file mode 100644 index 0000000..e69de29 diff --git a/aoc/tests/test_datastructures.py b/aoc/tests/test_datastructures.py new file mode 100644 index 0000000..1c291cc --- /dev/null +++ b/aoc/tests/test_datastructures.py @@ -0,0 +1,112 @@ +# -*- coding: utf-8 -*- +from aoc.datastructures import Coordinate, Coordinate3 + + +class TestCoordinate: + def test_addition(self): + c1 = Coordinate(1, 1) + c2 = Coordinate(2, 2) + assert c1 + c2 == Coordinate(3, 3) + + def test_subtraction(self): + c1 = Coordinate(2, 2) + c2 = Coordinate(1, 1) + assert c1 - c2 == Coordinate(1, 1) + + def test_manhattan_distance(self): + c1 = Coordinate(1, 1) + c2 = Coordinate(3, 3) + assert c1.manhattan_distance(c2) == 4 + + def test_polarity(self): + c1 = Coordinate(2, -3) + assert c1.polarity == Coordinate(1, -1) + + def test_neighbours(self): + c = Coordinate(0, 0) + neighbours = { + Coordinate(-1, 0), + Coordinate(1, 0), + Coordinate(0, -1), + Coordinate(0, 1), + Coordinate(-1, -1), + Coordinate(-1, 1), + Coordinate(1, -1), + Coordinate(1, 1), + } + assert set(c.neighbours()) == neighbours + + def test_neighbours_no_diagonal(self): + c = Coordinate(0, 0) + neighbours_no_diagonal = { + Coordinate(-1, 0), + Coordinate(1, 0), + Coordinate(0, -1), + Coordinate(0, 1), + } + assert set(c.neighbours(no_diagonal=True)) == neighbours_no_diagonal + + +class TestCoordinate3: + def test_addition(self): + c1 = Coordinate3(1, 1, 1) + c2 = Coordinate3(2, 2, 2) + assert c1 + c2 == Coordinate3(3, 3, 3) + + def test_subtraction(self): + c1 = Coordinate3(2, 2, 2) + c2 = Coordinate3(1, 1, 1) + assert c1 - c2 == Coordinate3(1, 1, 1) + + def test_manhattan_distance(self): + c1 = Coordinate3(1, 1, 1) + c2 = Coordinate3(3, 3, 3) + assert c1.manhattan_distance(c2) == 6 + + def test_polarity(self): + c1 = Coordinate3(2, -3, 0) + assert c1.polarity == Coordinate3(1, -1, 0) + + def test_neighbours(self): + c = Coordinate3(0, 0, 0) + neighbours = { + Coordinate3(-1, -1, -1), + Coordinate3(-1, -1, 0), + Coordinate3(-1, -1, 1), + Coordinate3(-1, 0, -1), + Coordinate3(-1, 0, 0), + Coordinate3(-1, 0, 1), + Coordinate3(-1, 1, -1), + Coordinate3(-1, 1, 0), + Coordinate3(-1, 1, 1), + Coordinate3(0, -1, -1), + Coordinate3(0, -1, 0), + Coordinate3(0, -1, 1), + Coordinate3(0, 0, -1), + Coordinate3(0, 0, 1), + Coordinate3(0, 1, -1), + Coordinate3(0, 1, 0), + Coordinate3(0, 1, 1), + Coordinate3(1, -1, -1), + Coordinate3(1, -1, 0), + Coordinate3(1, -1, 1), + Coordinate3(1, 0, -1), + Coordinate3(1, 0, 0), + Coordinate3(1, 0, 1), + Coordinate3(1, 1, -1), + Coordinate3(1, 1, 0), + Coordinate3(1, 1, 1), + } + assert set(c.neighbours()) == neighbours + + def test_neighbours_no_diagonal(self): + c = Coordinate3(0, 0, 0) + neighbours_no_diagonal = { + Coordinate3(-1, 0, 0), + Coordinate3(1, 0, 0), + Coordinate3(0, -1, 0), + Coordinate3(0, 1, 0), + Coordinate3(0, 0, -1), + Coordinate3(0, 0, 1), + } + assert set(c.neighbours(no_diagonal=True)) == neighbours_no_diagonal diff --git a/aoc/utils.py b/aoc/utils.py new file mode 100644 index 0000000..a5de050 --- /dev/null +++ b/aoc/utils.py @@ -0,0 +1,6 @@ +# -*- coding: utf-8 -*- +from typing import Callable + + +def bold(item: str, condition: Callable[[], bool]): + return f"\033[36m{item}\033[0m" if condition() else item -- cgit v1.2.3