Initial commit

16 files changed, 711 insertions, 0 deletions

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
--- /dev/null
+++ b/aoc/template/example.txt
diff --git a/aoc/template/input.txt b/aoc/template/input.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/aoc/template/input.txt
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
--- /dev/null
+++ b/aoc/tests/__init__.py
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]