1from __future__ import annotations
2
3import dataclasses
4
5
6@dataclasses.dataclass(frozen=True)
7class Vector:
8 y: int
9 x: int
10
11 def __add__(self, b):
12 return Vector(self.y + b.y, self.x + b.x)
13
14 def is_valid(self, grid: list[list[int]]) -> bool:
15 if self.x < 0:
16 return False
17 elif self.y < 0:
18 return False
19 elif self.x >= len(grid[0]):
20 return False
21 elif self.y >= len(grid):
22 return False
23 else:
24 return True
25
26
27def get_data(path: str) -> list[str]:
28 output = []
29 with open(path) as f:
30 for line in f:
31 output.append(line.strip())
32 return output
33
34
35def region_search(grid, starting_point: Vector) -> tuple[int, int, set[Vector]]:
36 """
37 A function that flows through a given region and returns the
38 region's area, perimeter, and the (y,x) positions of all plots in
39 it.
40 """
41 area = 0
42 perimeter = 0
43
44 crop = grid[starting_point.y][starting_point.x]
45
46 stack = [starting_point]
47 counted_plots = set()
48 while stack:
49 pos = stack.pop()
50
51 if pos in counted_plots:
52 continue
53
54 counted_plots.add(pos)
55
56 area += 1
57 perimeter += 4
58
59 for delta in [
60 Vector(1, 0),
61 Vector(-1, 0),
62 Vector(0, 1),
63 Vector(0, -1),
64 ]:
65 next_position = pos + delta
66 if not next_position.is_valid(grid):
67 continue
68
69 if grid[next_position.y][next_position.x] == crop:
70 perimeter -= 1
71 stack.append(next_position)
72
73 return area, perimeter, counted_plots
74
75
76def main(grid: list[str]) -> int:
77 checked_plots = set()
78
79 area_perimeter = 0
80 for y, row in enumerate(grid):
81 for x, _ in enumerate(row):
82 starting_point = Vector(y, x)
83 if starting_point in checked_plots:
84 # If this plot was already contained in a previously
85 # checked region then skip it.
86 continue
87
88 #
89 # Find the data about the region starting at this point
90 #
91 area, perimeter, region_plots = region_search(grid, starting_point)
92 area_perimeter += area * perimeter
93 checked_plots |= region_plots
94
95 return area_perimeter
96
97
98if __name__ == "__main__":
99 # print(main(get_data("day_12_input_test.txt")))
100 print(main(get_data("day_12_input.txt")))
1from __future__ import annotations
2
3import dataclasses
4
5
6@dataclasses.dataclass(frozen=True)
7class Vector:
8 y: int
9 x: int
10
11 def __add__(self, b):
12 return Vector(self.y + b.y, self.x + b.x)
13
14 def is_valid(self, grid: list[list[int]]) -> bool:
15 if self.x < 0:
16 return False
17 elif self.y < 0:
18 return False
19 elif self.x >= len(grid[0]):
20 return False
21 elif self.y >= len(grid):
22 return False
23 else:
24 return True
25
26
27DELTAS = [
28 Vector(1, 0),
29 Vector(0, 1),
30 Vector(-1, 0),
31 Vector(0, -1)
32]
33
34
35def rotate(vector):
36 return DELTAS[(DELTAS.index(vector) + 1) % len(DELTAS)]
37
38
39def get_data(path: str) -> list[str]:
40 output = []
41 with open(path) as f:
42 for line in f:
43 output.append(line.strip())
44 return output
45
46
47def region_search(grid, starting_point) -> tuple[int, int, set[Vector]]:
48 counted_plots = set()
49 area = 0
50 sides = set()
51
52 stack = [starting_point]
53 while stack:
54 pos = stack.pop()
55 crop = grid[pos.y][pos.x]
56
57 if pos in counted_plots:
58 continue
59
60 counted_plots.add(pos)
61
62 area += 1
63
64 potential_sides = {(pos, delta) for delta in DELTAS}
65 for delta in DELTAS:
66 next_position = pos + delta
67 if not next_position.is_valid(grid):
68 continue
69
70 if grid[next_position.y][next_position.x] == crop:
71 stack.append(next_position)
72 if delta.x:
73 potential_sides.remove((pos, delta))
74 else:
75 potential_sides.remove((pos, delta))
76
77
78 sides |= potential_sides
79
80 bad_sides = set()
81 for side in sides:
82 pos, direction = side
83 if (pos + rotate(direction), direction) in sides:
84 bad_sides.add(side)
85
86 return area, len(sides - bad_sides), counted_plots
87
88
89def main(grid: list[str]) -> int:
90 checked_plots = set()
91
92 area_perimeter = 0
93 for y, row in enumerate(grid):
94 for x, _ in enumerate(row):
95 starting_point = Vector(y, x)
96 if starting_point in checked_plots:
97 # If this plot was already contained in a previously
98 # checked region then skip it.
99 continue
100
101 # Find the data about the region starting at this point
102 #
103 area, sides, region_plots = region_search(grid, starting_point)
104 area_perimeter += area * sides
105 checked_plots |= region_plots
106
107 return area_perimeter
108
109
110if __name__ == "__main__":
111 # print(main(get_data("day_12_input_test.txt")))
112 print(main(get_data("day_12_input.txt")))