From 4147da1317c19fa61d6aa265e8370e63231f9207 Mon Sep 17 00:00:00 2001 From: Tom van der Lee Date: Sun, 19 Nov 2023 16:55:03 +0100 Subject: Initial commit --- .gitignore | 234 +++++++++++++++++++++++++++++++++++++++ .pre-commit-config.yaml | 15 +++ aoc/__init__.py | 43 +++++++ aoc/__main__.py | 66 +++++++++++ aoc/datastructures.py | 98 ++++++++++++++++ aoc/decorators.py | 30 +++++ 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 | 79 +++++++++++++ aoc/utils.py | 6 + conftest.py | 36 ++++++ requirements.txt | 3 + 16 files changed, 711 insertions(+) create mode 100644 .gitignore create mode 100644 .pre-commit-config.yaml 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 create mode 100644 conftest.py create mode 100644 requirements.txt diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..f402d03 --- /dev/null +++ b/.gitignore @@ -0,0 +1,234 @@ + +# Created by https://www.toptal.com/developers/gitignore/api/python,pycharm+all +# Edit at https://www.toptal.com/developers/gitignore?templates=python,pycharm+all + +### PyCharm+all ### +# Covers JetBrains IDEs: IntelliJ, RubyMine, PhpStorm, AppCode, PyCharm, CLion, Android Studio, WebStorm and Rider +# Reference: https://intellij-support.jetbrains.com/hc/en-us/articles/206544839 + +# User-specific stuff +.idea/**/workspace.xml +.idea/**/tasks.xml +.idea/**/usage.statistics.xml +.idea/**/dictionaries +.idea/**/shelf + +# Generated files +.idea/**/contentModel.xml + +# Sensitive or high-churn files +.idea/**/dataSources/ +.idea/**/dataSources.ids +.idea/**/dataSources.local.xml +.idea/**/sqlDataSources.xml +.idea/**/dynamic.xml +.idea/**/uiDesigner.xml +.idea/**/dbnavigator.xml + +# Gradle +.idea/**/gradle.xml +.idea/**/libraries + +# Gradle and Maven with auto-import +# When using Gradle or Maven with auto-import, you should exclude module files, +# since they will be recreated, and may cause churn. Uncomment if using +# auto-import. +# .idea/artifacts +# .idea/compiler.xml +# .idea/jarRepositories.xml +# .idea/modules.xml +# .idea/*.iml +# .idea/modules +# *.iml +# *.ipr + +# CMake +cmake-build-*/ + +# Mongo Explorer plugin +.idea/**/mongoSettings.xml + +# File-based project format +*.iws + +# IntelliJ +out/ + +# mpeltonen/sbt-idea plugin +.idea_modules/ + +# JIRA plugin +atlassian-ide-plugin.xml + +# Cursive Clojure plugin +.idea/replstate.xml + +# Crashlytics plugin (for Android Studio and IntelliJ) +com_crashlytics_export_strings.xml +crashlytics.properties +crashlytics-build.properties +fabric.properties + +# Editor-based Rest Client +.idea/httpRequests + +# Android studio 3.1+ serialized cache file +.idea/caches/build_file_checksums.ser + +### PyCharm+all Patch ### +# Ignores the whole .idea folder and all .iml files +# See https://github.com/joeblau/gitignore.io/issues/186 and https://github.com/joeblau/gitignore.io/issues/360 + +.idea/ + +# Reason: https://github.com/joeblau/gitignore.io/issues/186#issuecomment-249601023 + +*.iml +modules.xml +.idea/misc.xml +*.ipr + +# Sonarlint plugin +.idea/sonarlint + +### Python ### +# Byte-compiled / optimized / DLL files +__pycache__/ +*.py[cod] +*$py.class + +# C extensions +*.so + +# Distribution / packaging +.Python +build/ +develop-eggs/ +dist/ +downloads/ +eggs/ +.eggs/ +lib/ +lib64/ +parts/ +sdist/ +var/ +wheels/ +pip-wheel-metadata/ +share/python-wheels/ +*.egg-info/ +.installed.cfg +*.egg +MANIFEST + +# PyInstaller +# Usually these files are written by a python script from a template +# before PyInstaller builds the exe, so as to inject date/other infos into it. +*.manifest +*.spec + +# Installer logs +pip-log.txt +pip-delete-this-directory.txt + +# Unit test / coverage reports +htmlcov/ +.tox/ +.nox/ +.coverage +.coverage.* +.cache +nosetests.xml +coverage.xml +*.cover +*.py,cover +.hypothesis/ +.pytest_cache/ +pytestdebug.log + +# Translations +*.mo +*.pot + +# Django stuff: +*.log +local_settings.py +db.sqlite3 +db.sqlite3-journal + +# Flask stuff: +instance/ +.webassets-cache + +# Scrapy stuff: +.scrapy + +# Sphinx documentation +docs/_build/ +doc/_build/ + +# PyBuilder +target/ + +# Jupyter Notebook +.ipynb_checkpoints + +# IPython +profile_default/ +ipython_config.py + +# pyenv +.python-version + +# pipenv +# According to pypa/pipenv#598, it is recommended to include Pipfile.lock in version control. +# However, in case of collaboration, if having platform-specific dependencies or dependencies +# having no cross-platform support, pipenv may install dependencies that don't work, or not +# install all needed dependencies. +#Pipfile.lock + +# PEP 582; used by e.g. github.com/David-OConnor/pyflow +__pypackages__/ + +# Celery stuff +celerybeat-schedule +celerybeat.pid + +# SageMath parsed files +*.sage.py + +# Environments +.env +.venv +env/ +venv/ +ENV/ +env.bak/ +venv.bak/ +pythonenv* + +# Spyder project settings +.spyderproject +.spyproject + +# Rope project settings +.ropeproject + +# mkdocs documentation +/site + +# mypy +.mypy_cache/ +.dmypy.json +dmypy.json + +# Pyre type checker +.pyre/ + +# pytype static type analyzer +.pytype/ + +# profiling data +.prof + +# End of https://www.toptal.com/developers/gitignore/api/python,pycharm+all diff --git a/.pre-commit-config.yaml b/.pre-commit-config.yaml new file mode 100644 index 0000000..1232470 --- /dev/null +++ b/.pre-commit-config.yaml @@ -0,0 +1,15 @@ +# See https://pre-commit.com for more information +# See https://pre-commit.com/hooks.html for more hooks +repos: + - repo: https://github.com/pre-commit/pre-commit-hooks + rev: v4.3.0 + hooks: + - id: trailing-whitespace + - id: end-of-file-fixer + - id: check-merge-conflict + - id: debug-statements + - id: fix-encoding-pragma + - repo: https://github.com/psf/black + rev: 22.10.0 + hooks: + - id: black 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..9bbaed9 --- /dev/null +++ b/aoc/__main__.py @@ -0,0 +1,66 @@ +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 assignment_part + + +def kwargs(kwarg: str) -> List: + return kwarg.split("=") + + +@app.command() +def run(day: str, + part: str = typer.Option("One", '--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{part}") + 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..42603c2 --- /dev/null +++ b/aoc/decorators.py @@ -0,0 +1,30 @@ +# -*- 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..42cc44d --- /dev/null +++ b/aoc/tests/test_datastructures.py @@ -0,0 +1,79 @@ +# -*- 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 diff --git a/conftest.py b/conftest.py new file mode 100644 index 0000000..1c0a8e4 --- /dev/null +++ b/conftest.py @@ -0,0 +1,36 @@ +# -*- coding: utf-8 -*- +import importlib +import os +from pkgutil import walk_packages + +from _pytest.python import Metafunc + +from aoc.__main__ import day + +dir_path = os.path.dirname(os.path.realpath(__file__)) + + +def pytest_generate_tests(metafunc: Metafunc): + if "assignment" in metafunc.fixturenames: + packages = [ + importlib.import_module(package.name) + for package in walk_packages([dir_path]) + ] + + assignments = [ + (getattr(package, f"Assignment{day(part)}", None), package) + for package in packages + for part in ["1", "2"] + ] + + metafunc.parametrize( + argnames=f"assignment", + argvalues=[ + Assignment(path=package.__path__[0]) + for (Assignment, package) in assignments + if Assignment is not None + and hasattr(package, "__path__") + and Assignment.example_result != NotImplemented + ], + ids=lambda assignment: str(assignment), + ) diff --git a/requirements.txt b/requirements.txt new file mode 100644 index 0000000..b8ff5dc --- /dev/null +++ b/requirements.txt @@ -0,0 +1,3 @@ +pytest +coverage +typer[all] -- cgit v1.2.3