1from __future__ import annotations
2
3import typing
4import collections
5import dataclasses
6import itertools
7
8
9@dataclasses.dataclass(frozen=True)
10class Vector:
11 y: int
12 x: int
13
14 def __sub__(self, b):
15 return Vector(self.y - b.y, self.x - b.x)
16
17 def __add__(self, b):
18 return Vector(self.y + b.y, self.x + b.x)
19
20 def is_valid(self, grid: list[str]) -> bool:
21 if self.x < 0:
22 return False
23 elif self.y < 0:
24 return False
25 elif self.x >= len(grid[0]):
26 return False
27 elif self.y >= len(grid):
28 return False
29 else:
30 return True
31
32
33def get_data(path: str) -> typing.Iterable[str]:
34 with open(path) as f:
35 for line in f:
36 yield line.strip()
37
38
39def find_anode(node1: Vector, node2: Vector) -> typing.Iterable[Vector]:
40 difference = node1 - node2
41 yield node1 + difference
42 yield node2 - difference
43
44
45def find_anodes(nodes: set) -> typing.Iterable[Vector]:
46 for chosen_nodes in itertools.combinations(nodes, 2):
47 yield from find_anode(*chosen_nodes)
48
49def main(grid: list[str]) -> int:
50 #
51 # Find and group all similar nodes
52 #
53 nodes = collections.defaultdict(set)
54 for y, row in enumerate(grid):
55 for x, char in enumerate(row):
56 if char != ".":
57 nodes[char].add(Vector(y, x))
58
59 #
60 # Calculate all anodes
61 #
62 all_nodes = set()
63 anodes = set()
64 for _, node_positions in nodes.items():
65 all_nodes.update(node_positions)
66 for anode in find_anodes(node_positions):
67 if anode.is_valid(grid):
68 anodes.add(anode)
69
70 #
71 # Find all anodes where there is not already a node
72 #
73 return len(anodes - all_nodes | anodes)
74
75
76if __name__ == '__main__':
77 print(main(list(get_data("day_8_input.txt"))))
1from __future__ import annotations
2
3import typing
4import collections
5import dataclasses
6import itertools
7
8
9@dataclasses.dataclass(frozen=True)
10class Vector:
11 y: int
12 x: int
13
14 def __sub__(self, b):
15 return Vector(self.y - b.y, self.x - b.x)
16
17 def __add__(self, b):
18 return Vector(self.y + b.y, self.x + b.x)
19
20 def is_valid(self, grid: list[str]) -> bool:
21 if self.x < 0:
22 return False
23 elif self.y < 0:
24 return False
25 elif self.x >= len(grid[0]):
26 return False
27 elif self.y >= len(grid):
28 return False
29 else:
30 return True
31
32
33def get_data(path: str) -> typing.Iterable[str]:
34 with open(path) as f:
35 for line in f:
36 yield line.strip()
37
38
39def find_anode(grid: list[str], node1: Vector, node2: Vector) -> typing.Iterable[Vector]:
40 difference = node1 - node2
41
42 #
43 # The node itself is an anode
44 #
45 yield node1
46
47 #
48 # All nodes that are in the _positive_ line of the difference
49 #
50 new_node = node1 + difference
51 while new_node.is_valid(grid):
52 yield new_node
53 new_node += difference
54
55 #
56 # All nodes that are in the _negative_ line of the difference
57 #
58 new_node = node1 - difference
59 while new_node.is_valid(grid):
60 yield new_node
61 new_node -= difference
62
63
64def find_anodes(grid: list[str], nodes: set) -> typing.Iterable[Vector]:
65 for chosen_nodes in itertools.combinations(nodes, 2):
66 yield from find_anode(grid, *chosen_nodes)
67
68
69def main(grid: list[str]) -> int:
70 #
71 # Find and group all similar nodes
72 #
73 nodes = collections.defaultdict(set)
74 for y, row in enumerate(grid):
75 for x, char in enumerate(row):
76 if char != ".":
77 nodes[char].add(Vector(y, x))
78
79 #
80 # Calculate all anodes
81 #
82 all_nodes = set()
83 anodes = set()
84 for _, node_positions in nodes.items():
85 all_nodes.update(node_positions)
86 for anode in find_anodes(grid, node_positions):
87 anodes.add(anode)
88
89 #
90 # Count all anodes even those that are on top of existing nodes
91 #
92 return len(anodes)
93
94
95if __name__ == '__main__':
96 print(main(list(get_data("day_8_input.txt"))))