Day 18

9 files changed, 2279 insertions, 6 deletions

diff --git a/aoc/datastructures.py b/aoc/datastructures.py
index 81a68e4..244aa1e 100644
--- a/aoc/datastructures.py
+++ b/aoc/datastructures.py
@@ -1,5 +1,6 @@
 # -*- coding: utf-8 -*-
 from collections import namedtuple
+from typing import Iterator
 
 
 class Coordinate(namedtuple("Coordinate", ["x", "y"])):
@@ -28,3 +29,70 @@ class Coordinate(namedtuple("Coordinate", ["x", "y"])):
             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:
+                            continue
+
+                        yield coordinate
diff --git a/aoc/mixins.py b/aoc/mixins.py
index faeb3eb..5986b6e 100644
--- a/aoc/mixins.py
+++ b/aoc/mixins.py
@@ -55,3 +55,23 @@ class AStarMixin(Generic[Node]):
 
                     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/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..a7965f5
--- /dev/null
+++ b/aoc/tests/test_datastructures.py
@@ -0,0 +1,16 @@
+# -*- coding: utf-8 -*-
+from aoc.datastructures import Coordinate3
+
+
+class TestCoordinate3:
+    def test_neighbours_nodiagonal(self):
+        coordinate = Coordinate3(0, 0, 0)
+
+        assert set(coordinate.neighbours(True)) == {
+            Coordinate3(-1, 0, 0),
+            Coordinate3(1, 0, 0),
+            Coordinate3(0, -1, 0),
+            Coordinate3(0, 1, 0),
+            Coordinate3(0, 0, -1),
+            Coordinate3(0, 0, 1),
+        }
diff --git a/day17/__init__.py b/day17/__init__.py
index 41b25dc..03e9003 100644
--- a/day17/__init__.py
+++ b/day17/__init__.py
@@ -30,12 +30,12 @@ class AssignmentOne(Assignment):
 
         moves = self.infinite_moves(input)
 
-        for move in self.infinite_moves(next(input)):
-            i += 1
-            print(move)
-
-            if i == 100:
-                break
+        # for move in self.infinite_moves(next(input)):
+        #     i += 1
+        #     print(move)
+        #
+        #     if i == 100:
+        #         break
 
 
 class AssignmentTwo(Assignment):
diff --git a/day18/__init__.py b/day18/__init__.py
new file mode 100644
index 0000000..0500963
--- /dev/null
+++ b/day18/__init__.py
@@ -0,0 +1,75 @@
+# -*- coding: utf-8 -*-
+from abc import ABC
+from typing import Iterator, Set
+
+from aoc import BaseAssignment
+from aoc.datastructures import Coordinate3
+from aoc.mixins import BreathFirstSearchMixin
+
+
+class Assignment(BaseAssignment[int, Coordinate3], ABC):
+    def parse_item(self, item: str) -> Coordinate3:
+        x, y, z = item.split(",")
+        return Coordinate3(int(x), int(y), int(z))
+
+    @staticmethod
+    def open_sides(blocks: Set[Coordinate3]) -> int:
+        return len(
+            [
+                neighbour
+                for block in blocks
+                for neighbour in block.neighbours(True)
+                if neighbour not in blocks
+            ]
+        )
+
+
+class AssignmentOne(Assignment):
+    example_result = 64
+
+    def run(self, input: Iterator[Coordinate3]) -> int:
+        blocks = set(input)
+        return self.open_sides(blocks)
+
+
+class AssignmentTwo(Assignment, BreathFirstSearchMixin[Coordinate3]):
+    example_result = 58
+
+    def run(self, input: Iterator[Coordinate3]) -> int:
+        blocks = set(input)
+
+        lower_x = min([block.x for block in blocks]) - 1
+        higher_x = max([block.x for block in blocks]) + 1
+        lower_y = min([block.y for block in blocks]) - 1
+        higher_y = max([block.y for block in blocks]) + 1
+        lower_z = min([block.z for block in blocks]) - 1
+        higher_z = max([block.z for block in blocks]) + 1
+
+        all_coordinates = set(
+            Coordinate3(x, y, z)
+            for x in range(lower_x, higher_x + 1)
+            for y in range(lower_y, higher_y + 1)
+            for z in range(lower_z, higher_z + 1)
+        )
+
+        def nb(c):
+            for n in c.neighbours(True):
+                if n in all_coordinates and n not in blocks:
+                    yield n
+
+        outer_coordinates = {
+            coordinate
+            for coordinate in self.bfs(
+                Coordinate3(lower_x, lower_y, lower_z),
+                neighbours=nb,
+            )
+        }
+
+        return len(
+            [
+                neighbour
+                for block in blocks
+                for neighbour in block.neighbours(True)
+