Day 12

4 files changed, 221 insertions, 0 deletions

diff --git a/day12/__init__.py b/day12/__init__.py
new file mode 100644
index 0000000..aad531d
--- /dev/null
+++ b/day12/__init__.py
@@ -0,0 +1,116 @@
+from abc import ABC
+from collections import Counter
+from dataclasses import dataclass, field
+from typing import List, Tuple, Dict, Set
+
+from aoc import BaseAssignment
+
+Coordinate = Tuple[int, int]
+Field = List[List[int]]
+
+
+@dataclass
+class Node:
+    id: str
+    big: bool = False
+    nodes: Set['Node'] = field(default_factory=set)
+
+    def __eq__(self, other: 'Node'):
+        return self.id == other.id
+
+    def __hash__(self):
+        return hash(self.id)
+
+    def __repr__(self):
+        return f'Node(id={self.id})'
+
+    def __lt__(self, other):
+        return self.id < other.id
+
+class Assignment(BaseAssignment, ABC):
+    def parse_item(self, item: str) -> Tuple[str, str]:
+        return tuple(item.split('-'))
+
+    @classmethod
+    def get_or_create_node(cls, nodes: Dict[str, Node], id) -> Node:
+        if id not in nodes:
+             nodes[id] = Node(id=id, big=id.upper() == id)
+        return nodes[id]
+
+    def read_input(self, example = False) -> Dict[str, Node]:
+        nodes = {}
+        for a, b in super().read_input(example):
+            node_a = self.get_or_create_node(nodes, a)
+            node_b = self.get_or_create_node(nodes, b)
+
+            node_a.nodes.add(node_b)
+            node_b.nodes.add(node_a)
+
+        return nodes
+
+    @classmethod
+    def calculate_all_paths(cls, start: Node, end: Node, visited: List[Node] = []) -> List[List[Node]]:
+        raise NotImplementedError
+
+    def run(self, input: Dict[str, Node]) -> int:
+        return len(self.calculate_all_paths(input['start'], input['end']))
+
+
+class AssignmentOne(Assignment):
+    example_result = 19
+
+    @classmethod
+    def calculate_all_paths(cls, start: Node, end: Node, visited: List[Node] = []) -> List[List[Node]]:
+        if start == end:
+            return [[end]]
+
+        return [
+            [start, *path]
+            for node in start.nodes
+            if node.big or node not in visited
+            for path in cls.calculate_all_paths(node, end, visited=[*visited, start])
+        ]
+
+
+class AssignmentTwo(Assignment):
+    example_result =  103
+
+    @classmethod
+    def can_be_visited(cls, node: Node, visited: List[Node]) -> bool:
+        if node.big:
+            return True
+
+        visited_counter = Counter([node for node in visited if not node.big])
+
+        if node.id in ['start', 'end']:
+            return visited_counter.get(node, 0) < 1
+
+        small_node_visited_twice = any(
+            v == 2
+            for n, v
+            in visited_counter.items()
+        )
+
+        return  visited_counter.get(node, 0) < 1 if small_node_visited_twice else 2
+
+
+    @classmethod
+    def calculate_all_paths(cls, start: Node, end: Node, visited: List[Node] = []) -> List[List[Node]]:
+        if start == end:
+            return [[end]]
+
+        return [
+            [start, *path]
+            for node in start.nodes
+            if cls.can_be_visited(node, [*visited, start])
+            for path in cls.calculate_all_paths(node, end, visited=[*visited, start])
+        ]
+
+    def run(self, input: Dict[str, Node]) -> int:
+        paths = sorted(self.calculate_all_paths(input['start'], input['end']))
+
+        print()
+        for path in paths:
+            print(','.join([ n.id for n in path ]))
+
+        return len(paths)
diff --git a/day12/example.txt b/day12/example.txt
new file mode 100644
index 0000000..62cc714
--- /dev/null
+++ b/day12/example.txt
@@ -0,0 +1,10 @@
+dc-end
+HN-start
+start-kj
+dc-start
+dc-HN
+LN-dc
+HN-end
+kj-sa
+kj-HN
+kj-dc
diff --git a/day12/input.txt b/day12/input.txt
new file mode 100644
index 0000000..96b504b
--- /dev/null
+++ b/day12/input.txt
@@ -0,0 +1,23 @@
+vn-DD
+qm-DD
+MV-xy
+end-xy
+KG-end
+end-kw
+qm-xy
+start-vn
+MV-vn
+vn-ko
+lj-KG
+DD-xy
+lj-kh
+lj-MV
+ko-MV
+kw-qm
+qm-MV
+lj-kw
+VH-lj
+ko-qm
+ko-start
+MV-start
+DD-ko
diff --git a/day12/test_init.py b/day12/test_init.py
new file mode 100644
index 0000000..f6e78e1
--- /dev/null
+++ b/day12/test_init.py
@@ -0,0 +1,72 @@
+from day12 import Node, AssignmentOne, AssignmentTwo
+
+
+def test_calculate_all_paths_assignment_one():
+    start = Node(id='start')
+    end = Node(id='end')
+
+    start.nodes.add(end)
+    end.nodes.add(start)
+
+    assert AssignmentOne.calculate_all_paths(start, end) == [
+        [start, end]
+    ]
+
+    a = Node(id='a')
+    start.nodes = { a }
+    a.nodes = { start, end }
+    end.nodes = { end }
+
+    assert AssignmentOne.calculate_all_paths(start, end) == [
+        [start, a, end]
+    ]
+
+    b = Node(id='b')
+    start.nodes = { a, b }
+    b.nodes = { start, end }
+    a.nodes = { start, end }
+    end.nodes = { a, b }
+
+    assert sorted(AssignmentOne.calculate_all_paths(start, end)) == sorted([
+        [start, a, end],
+        [start, b, end]
+    ])
+
+    a.nodes.add(b)
+    b.nodes.add(a)
+
+    assert sorted(AssignmentOne.calculate_all_paths(start, end)) == sorted([
+        [start, a, end],
+        [start, a, b, end],
+        [start, b, end],
+        [start, b, a, end]
+    ])
+
+    a.big = True
+
+    assert sorted(AssignmentOne.calculate_all_paths(start, end)) == sorted([
+        [start, a, end],
+        [start, a, b, end],
+        [start, a, b, a, end],
+        [start, b, end],
+        [start, b, a, end],
+    ])
+
+
+def test_calculate_all_paths_assignment_two():
+    start = Node(id='start')
+    end = Node(id='end')
+
+    a = Node(id='a')
+    b = Node(id='b')
+
+    start.nodes.add(a)
+    a.nodes.add(b)
+    a.nodes.add(start)
+    b.nodes.add(a)
+    b.nodes.add(end)
+    end.nodes.add(b)
+
+    assert sorted(AssignmentTwo.calculate_all_paths(start, end)) == sorted([
+        [start, a, b, end]
+    ])