From 7bbeb8155521686bd9bbd28fec5cb91ffb8360af Mon Sep 17 00:00:00 2001 From: Tom van der Lee Date: Mon, 13 Dec 2021 10:20:50 +0100 Subject: Day 12 --- day12/__init__.py | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++ day12/example.txt | 10 +++++ day12/input.txt | 23 +++++++++++ day12/test_init.py | 72 +++++++++++++++++++++++++++++++++ 4 files changed, 221 insertions(+) create mode 100644 day12/__init__.py create mode 100644 day12/example.txt create mode 100644 day12/input.txt create mode 100644 day12/test_init.py (limited to 'day12') 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] + ]) -- cgit v1.2.3