diff options
| author | Botond Hende <nettingman@gmail.com> | 2024-12-13 20:52:55 +0100 |
|---|---|---|
| committer | Botond Hende <nettingman@gmail.com> | 2024-12-13 20:52:55 +0100 |
| commit | 1ffc2556d4ae91a6a568def1fb79410cf70eb795 (patch) | |
| tree | 0c60a0eaa603edfcaf34a6979177a577388bbd50 /2024/day12/solve.py | |
| parent | 1d3fff4219458283ce7919c3fb5c94951a66dac7 (diff) | |
2024 day 12-13
Diffstat (limited to '2024/day12/solve.py')
| -rw-r--r-- | 2024/day12/solve.py | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/2024/day12/solve.py b/2024/day12/solve.py new file mode 100644 index 0000000..e7a6b7b --- /dev/null +++ b/2024/day12/solve.py @@ -0,0 +1,92 @@ +from typing import Optional
+from functools import cmp_to_key
+
+
+def chart_region(plots: list[list[Optional[str]]], current_pos: tuple[int, int],
+ charted_positions: list[tuple[int, int]], fence_positions: list[list[tuple[int, int]]]) -> tuple[int, int]:
+ charted_positions.append(current_pos)
+ current_plot = plots[current_pos[0]][current_pos[1]]
+
+ plot_count = 1
+ fence_count = 0
+
+ row_cnt = len(data)
+ col_cnt = len(data[0])
+ for dir_idx, direct in enumerate(((-1, 0), (1, 0), (0, -1), (0, 1))):
+ new_pos = (current_pos[0] + direct[0], current_pos[1] + direct[1])
+ if 0 <= new_pos[0] < row_cnt and 0 <= new_pos[1] < col_cnt and plots[new_pos[0]][new_pos[1]] == current_plot:
+ if new_pos not in charted_positions:
+ result = chart_region(plots, new_pos, charted_positions, fence_positions)
+ plot_count += result[0]
+ fence_count += result[1]
+ else:
+ fence_positions[dir_idx].append(current_pos)
+ fence_count += 1
+
+ return plot_count, fence_count
+
+
+def compare_row_first(item1: tuple[int, int], item2: tuple[int, int]):
+ row_diff = item1[0] - item2[0]
+ if row_diff != 0:
+ return row_diff
+
+ return item1[1] - item2[1]
+
+
+def compare_col_first(item1: tuple[int, int], item2: tuple[int, int]):
+ col_diff = item1[1] - item2[1]
+ if col_diff != 0:
+ return col_diff
+
+ return item1[0] - item2[0]
+
+
+def calculate_discount(fence_positions: list[list[tuple[int, int]]]) -> int:
+ adjacents = 0
+ for charted_positions in fence_positions:
+ charted_positions.sort(key=cmp_to_key(compare_row_first))
+ last_pos = None
+ for current_pos in charted_positions:
+ if last_pos is not None and last_pos[0] == current_pos[0] and last_pos[1] + 1 == current_pos[1]:
+ adjacents += 1
+
+ last_pos = current_pos
+
+ charted_positions.sort(key=cmp_to_key(compare_col_first))
+ last_pos = None
+ for current_pos in charted_positions:
+ if last_pos is not None and last_pos[1] == current_pos[1] and last_pos[0] + 1 == current_pos[0]:
+ adjacents += 1
+
+ last_pos = current_pos
+
+ return adjacents
+
+
+use_discount = True # for part two
+
+data = []
+with open("input") as f:
+ for line in f:
+ data.append(list(line.strip()))
+
+row_count = len(data)
+col_count = len(data[0])
+
+final_sum = 0
+
+for row in range(row_count):
+ for col in range(col_count):
+ if data[row][col] is not None:
+ charted_pos: list[tuple[int, int]] = []
+ fence_pos: list[list[tuple[int, int]]] = [[], [], [], []]
+ chart_result = chart_region(data, (row, col), charted_pos, fence_pos)
+ fences = chart_result[1]
+ if use_discount:
+ fences -= calculate_discount(fence_pos)
+ final_sum += chart_result[0] * fences
+ for pos in charted_pos:
+ data[pos[0]][pos[1]] = None
+
+print(final_sum)
|