3 files changed, 247 insertions, 0 deletions

diff --git a/day14/__init__.py b/day14/__init__.py
new file mode 100644
index 0000000..44107de
--- /dev/null
+++ b/day14/__init__.py
@@ -0,0 +1,133 @@
+# -*- coding: utf-8 -*-
+from abc import ABC
+from functools import lru_cache
+from typing import Tuple, Iterator, Set, Any, Optional
+
+from aoc import BaseAssignment
+
+Coordinate = Tuple[int, int]
+
+
+class Assignment(BaseAssignment, ABC):
+    def __init__(self, path):
+        super().__init__(path)
+
+        self.cave_depth = None
+
+    def coordinate_ranges(
+        self, input: Iterator[str]
+    ) -> Iterator[Tuple[Coordinate, Coordinate]]:
+        for item in input:
+            last = None
+
+            for i in item.split(" -> "):
+                x, y = i.split(",")
+
+                coordinate = int(x), int(y)
+
+                if last is not None:
+                    yield last, coordinate
+
+                last = coordinate
+
+    def coordinates(self, a: Coordinate, b: Coordinate) -> Iterator[Coordinate]:
+        for x in range(min(a[0], b[0]), max(a[0], b[0]) + 1):
+            for y in range(min(a[1], b[1]), max(a[1], b[1]) + 1):
+                yield x, y
+
+    def generate_rocks(self, input: Iterator[str]) -> Set[Coordinate]:
+        rocks = set(
+            coordinate
+            for coordinates in self.coordinate_ranges(input)
+            for coordinate in self.coordinates(*coordinates)
+        )
+
+        self.cave_depth = self.get_cave_depth(rocks)
+
+        return rocks
+
+    def get_cave_depth(self, cave: Set[Coordinate]):
+        return max([item[1] for item in cave])
+
+    def invalid_position(self, sand: Coordinate, cave: set[Coordinate]):
+        raise NotImplementedError()
+
+    def blocking(self, sand: Coordinate, cave: set[Coordinate]):
+        raise NotImplementedError()
+
+    def drop_sand(
+        self, sand: Coordinate, cave: Set[Coordinate]
+    ) -> Optional[Coordinate]:
+        if self.invalid_position(sand, cave):
+            return None
+
+        next_positions = [
+            (sand[0], sand[1] + 1),
+            (sand[0] - 1, sand[1] + 1),
+            (sand[0] + 1, sand[1] + 1),
+        ]
+
+        non_blocking = [
+            next_position
+            for next_position in next_positions
+            if not self.blocking(next_position, cave)
+        ]
+
+        if len(non_blocking) == 0:
+            return sand
+
+        return self.drop_sand(non_blocking[0], cave)
+
+    def generate_sand(self, cave: set[Coordinate]) -> Iterator[Coordinate]:
+        cave_copy = set(cave)
+        sand = (500, 0)
+
+        while True:
+            coordinate = self.drop_sand(sand, cave_copy)
+
+            if coordinate is None:
+                return
+
+            cave_copy.add(coordinate)
+            yield coordinate
+
+    def run(self, input: Iterator) -> Any:
+        cave = self.generate_rocks(input)
+        coordinates = set()
+
+        for sand in self.generate_sand(cave):
+            coordinates.add(sand)
+
+        return len(coordinates)
+
+
+class AssignmentOne(Assignment):
+    example_result = 24
+
+    def invalid_position(self, sand: Coordinate, cave: set[Coordinate]):
+        return sand[1] > self.cave_depth
+
+    def blocking(self, sand: Coordinate, cave: set[Coordinate]):
+        return sand in cave
+
+
+class AssignmentTwo(Assignment):
+    example_result = 93
+
+    def invalid_position(self, sand: Coordinate, cave: set[Coordinate]):
+        return False
+
+    def blocking(self, sand: Coordinate, cave: set[Coordinate]):
+        return sand in cave or sand[1] >= self.cave_depth + 2
+
+    def run(self, input: Iterator) -> Any:
+        cave = self.generate_rocks(input)
+        coordinates = set()
+
+        for sand in self.generate_sand(cave):
+            coordinates.add(sand)
+
+            if sand == (500, 0):
+                break
+
+        return len(coordinates)
diff --git a/day14/example.txt b/day14/example.txt
new file mode 100644
index 0000000..4e87bb5
--- /dev/null
+++ b/day14/example.txt
@@ -0,0 +1,2 @@
+498,4 -> 498,6 -> 496,6
+503,4 -> 502,4 -> 502,9 -> 494,9
diff --git a/day14/input.txt b/day14/input.txt
new file mode 100644
index 0000000..9ff2c57
--- /dev/null
+++ b/day14/input.txt
@@ -0,0 +1,112 @@
+481,54 -> 481,47 -> 481,54 -> 483,54 -> 483,45 -> 483,54 -> 485,54 -> 485,52 -> 485,54
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+465,117 -> 465,120 -> 464,120 -> 464,123 -> 476,123 -> 476,120 -> 471,120 -> 471,117
+451,104 -> 451,103 -> 451,104 -> 453,104 -> 453,97 -> 453,104 -> 455,104 -> 455,100 -> 455,104
+501,15 -> 506,15
+481,54 -> 481,47 -> 481,54 -> 483,54 -> 483,45 -> 483,54 -> 485,54 -> 485,52 -> 485,54
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+474,73 -> 474,74 -> 486,74 -> 486,73
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+481,54 -> 481,47 -> 481,54 -> 483,54 -> 483,45 -> 483,54 -> 485,54 -> 485,52 -> 485,54
+491,29 -> 495,29
+491,17 -> 496,17
+474,36 -> 474,38 -> 468,38 -> 468,41 -> 482,41 -> 482,38 -> 478,38 -> 478,36
+454,107 -> 454,110 -> 450,110 -> 450,114 -> 467,114 -> 467,110 -> 459,110 -> 459,107
+462,84 -> 462,87 -> 455,87 -> 455,91 -> 469,91 -> 469,87 -> 466,87 -> 466,84
+462,84 -> 462,87 -> 455,87 -> 455,91 -> 469,91 -> 469,87 -> 466,87 -> 466,84
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+477,33 -> 482,33 -> 482,32
+485,29 -> 489,29
+481,54 -> 481,47 -> 481,54 -> 483,54 -> 483,45 -> 483,54 -> 485,54 -> 485,52 -> 485,54
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+465,117 -> 465,120 -> 464,120 -> 464,123 -> 476,123 -> 476,120 -> 471,120 -> 471,117
+462,84 -> 462,87 -> 455,87 -> 455,91 -> 469,91 -> 469,87 -> 466,87 -> 466,84
+481,54 -> 481,47 -> 481,54 -> 483,54 -> 483,45 -> 483,54 -> 485,54 -> 485,52 -> 485,54
+474,36 -> 474,38 -> 468,38 -> 468,41 -> 482,41 -> 482,38 -> 478,38 -> 478,36
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+477,59 -> 477,60 -> 495,60
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+481,54 -> 481,47 -> 481,54 -> 483,54 -> 483,45 -> 483,54 -> 485,54 -> 485,52 -> 485,54
+465,117 -> 465,120 -> 464,120 -> 464,123 -> 476,123 -> 476,120 -> 471,120 -> 471,117
+465,117 -> 465,120 -> 464,120 -> 464,123 -> 476,123 -> 476,120 -> 471,120 -> 471,117
+465,117 -> 465,120 -> 464,120 -> 464,123 -> 476,123 -> 476,120 -> 471,120 -> 471,117
+451,104 -> 451,103 -> 451,104 -> 453,104 -> 453,97 -> 453,104 -> 455,104 -> 455,100 -> 455,104
+477,140 -> 488,140
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+485,23 -> 489,23
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+497,65 -> 502,65
+488,26 -> 492,26
+451,104 -> 451,103 -> 451,104 -> 453,104 -> 453,97 -> 453,104 -> 455,104 -> 455,100 -> 455,104
+479,29 -> 483,29
+474,36 -> 474,38 -> 468,38 -> 468,41 -> 482,41 -> 482,38 -> 478,38 -> 478,36
+454,107 -> 454,110 -> 450,110 -> 450,114 -> 467,114 -> 467,110 -> 459,110 -> 459,107
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+454,107 -> 454,110 -> 450,110 -> 450,114 -> 467,114 -> 467,110 -> 459,110 -> 459,107
+474,36 -> 474,38 -> 468,38 -> 468,41 -> 482,41 -> 482,38 -> 478,38 -> 478,36
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+498,17 -> 503,17
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+474,36 -> 474,38 -> 468,38 -> 468,41 -> 482,41 -> 482,38 -> 478,38 -> 478,36
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+488,20 -> 492,20
+494,67 -> 499,67
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+462,84 -> 462,87 -> 455,87 -> 455,91 -> 469,91 -> 469,87 -> 466,87 -> 466,84
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+454,107 -> 454,110 -> 450,110 -> 450,114 -> 467,114 -> 467,110 -> 459,110 -> 459,107
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+505,17 -> 510,17
+487,67 -> 492,67
+451,104 -> 451,103 -> 451,104 -> 453,104 -> 453,97 -> 453,104 -> 455,104 -> 455,100 -> 455,104
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+474,36 -> 474,38 -> 468,38 -> 468,41 -> 482,41 -> 482,38 -> 478,38 -> 478,36
+490,65 -> 495,65
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+478,81 -> 483,81
+501,67 -> 506,67
+484,69 -> 489,69
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+454,107 -> 454,110 -> 450,110 -> 450,114 -> 467,114 -> 467,110 -> 459,110 -> 459,107
+462,84 -> 462,87 -> 455,87 -> 455,91 -> 469,91 -> 469,87 -> 466,87 -> 466,84
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153
+497,29 -> 501,29
+493,63 -> 498,63
+471,136 -> 471,130 -> 471,136 -> 473,136 -> 473,128 -> 473,136 -> 475,136 -> 475,132 -> 475,136 -> 477,136 -> 477,133 -> 477,136 -> 479,136 -> 479,133 -> 479,136 -> 481,136 -> 481,132 -> 481,136
+485,153 -> 485,145 -> 485,153 -> 487,153 -> 487,152 -> 487,153 -> 489,153 -> 489,143 -> 489,153 -> 491,153 -> 491,148 -> 491,153