Coverage for src\aoc2022\days\day14.py: 100%
86 statements
« prev ^ index » next coverage.py v7.0.0, created at 2022-12-23 05:19 +0000
1from typing import Tuple
3import numpy as np
5from src.aoc2022 import utils
8def parse_data_to_array(
9 raw_data: str, starting_point: Tuple[int, int]
10) -> Tuple[np.ndarray, Tuple[int, int]]:
11 """
12 Parse raw data into a grid of air/stone cells
14 :param raw_data: Raw data to parse into packets
15 :type raw_data: str
17 :param starting_point: Starting point from where sand is dropped
18 :type starting_point: Tuple[int, int]
20 :return: the generated map and updated starting point
21 :rtype: Tuple[np.ndarray, Tuple[int, int]]
22 """
23 min_x_value = starting_point[0]
24 min_y_value = starting_point[1]
25 max_x_value = starting_point[0]
26 max_y_value = starting_point[1]
27 paths = []
29 for line in raw_data.split("\n"):
30 coords = line.split(" -> ")
31 path = []
32 for i in range(len(coords)):
33 x, y = coords[i].split(",")
35 x_val = int(x)
36 y_val = int(y)
38 min_x_value = min(x_val, min_x_value)
39 max_x_value = max(x_val, max_x_value)
40 min_y_value = min(y_val, min_y_value)
41 max_y_value = max(y_val, max_y_value)
43 path.append((x_val, y_val))
45 paths.append(path)
47 shape = (max_x_value - min_x_value + 1, max_y_value - min_y_value + 1)
48 map_ = np.zeros(shape)
50 normalized_starting_point = (
51 starting_point[0] - min_x_value,
52 starting_point[1] - min_y_value,
53 )
55 for path in paths:
56 for i in range(len(path) - 1):
57 x1, y1 = path[i]
58 x2, y2 = path[i + 1]
60 x1 = min(path[i][0], path[i + 1][0])
61 y1 = min(path[i][1], path[i + 1][1])
62 x2 = max(path[i][0], path[i + 1][0])
63 y2 = max(path[i][1], path[i + 1][1])
65 x1 = x1 - min_x_value
66 x2 = x2 - min_x_value
68 y1 = y1 - min_y_value
69 y2 = y2 - min_y_value
71 if x1 != x2:
72 x2 += 1
73 map_[x1:x2, y1] = 1
74 elif y1 != y2:
75 y2 += 1
76 map_[x1, y1:y2] = 1
78 return map_, normalized_starting_point
81def add_floor_to_map(
82 map_: np.ndarray, starting_point: Tuple[int, int]
83) -> Tuple[np.ndarray, Tuple[int, int]]:
84 """
85 Add a floor underneath the given map
87 :param map_: The map to which the extra floor is added
88 :type map_: np.ndarray
90 :param starting_point: Starting point from where sand is dropped
91 :type starting_point: Tuple[int, int]
93 :return: the updated map and starting point
94 :rtype: Tuple[np.ndarray, Tuple[int, int]]
95 """
96 # want starting point to be in middle, need to find size of new map
97 height = map_.shape[1] + 2
98 width = 2 * height + map_.shape[0]
100 copy_left = height
101 copy_right = height + map_.shape[0]
102 copy_top = 0
103 copy_bot = map_.shape[1]
105 new_map = np.zeros((width, height))
106 new_map[copy_left:copy_right, copy_top:copy_bot] = map_
107 new_map[:, -1] = 1
109 new_starting_point = (starting_point[0] + height, 0)
111 return new_map, new_starting_point
114def simulate_grain_of_sand(
115 map_: np.ndarray, starting_point: Tuple[int, int]
116) -> Tuple[int, int]:
117 """
118 Simulate a grain of sand falling through the map
120 :param map_: The map through which the grain of sand falls
121 :type map_: np.ndarray
123 :param starting_point: Starting point from where sand is dropped
124 :type starting_point: Tuple[int, int]
126 :return: The updated cell that the grain of sand falls onto
127 :rtype: Tuple[int, int]
128 """
130 # TODO: this can be optimized with dynamic programming
131 x, y = starting_point
132 max_x, max_y = map_.shape
133 while (x >= 0) and (x < max_x) and (y >= 0) and (y < max_y - 1):
134 if map_[x, y] != 0:
135 return (-1, -1)
136 if map_[x, y + 1] == 0:
137 y += 1
138 else:
139 if map_[x - 1, y + 1] == 0:
140 x -= 1
141 y += 1
142 elif map_[x + 1, y + 1] == 0:
143 x += 1
144 y += 1
145 else:
146 return (x, y)
147 return (-1, -1)
150def render_map(map_: np.ndarray, start_point: Tuple[int, int]) -> str:
151 """
152 Render the map for visualization
154 :param map_: The map through which the grain of sand falls
155 :type map_: np.ndarray
157 :param starting_point: Starting point from where sand is dropped
158 :type starting_point: Tuple[int, int]
160 :return: A rendered representation of the map
161 :rtype: str
162 """
163 render = np.full(map_.shape, "")
164 render[map_ == 0] = "."
165 render[map_ == 1] = "#"
166 render[map_ == 2] = "o"
167 render[start_point] = "S"
169 return "\n".join(["".join(render[:, i]) for i in range(render.shape[1])])
172def simulate_sand_falling(
173 map_: np.ndarray, starting_point: Tuple[int, int]
174) -> np.ndarray:
175 """
176 Repeatedly drop grains of sand til convergence
178 :param map_: The map through which the grain of sand falls
179 :type map_: np.ndarray
181 :param starting_point: Starting point from where sand is dropped
182 :type starting_point: Tuple[int, int]
184 :return: converged map state after grain of sand fall off edge of map
185 :rtype: np.ndarray
186 """
187 map_ = map_.copy()
188 updated_point = simulate_grain_of_sand(map_, starting_point)
190 while updated_point != (-1, -1):
191 map_[updated_point] = 2
192 updated_point = simulate_grain_of_sand(map_, starting_point)
193 return map_
196if __name__ == "__main__": # pragma: no cover
198 starting_point = (500, 0)
199 verbose = False
201 raw_data = utils.get_raw_data("./src/aoc2022/data/day14.txt")
202 map_, new_start = parse_data_to_array(raw_data, starting_point)
204 sand_filled_map = simulate_sand_falling(map_, new_start)
206 print(f"{sand_filled_map[sand_filled_map == 2].shape[0]} grains fell")
208 if verbose:
209 print("Before :")
210 print(render_map(map_, new_start))
211 print("After :")
212 print(render_map(sand_filled_map, new_start))
214 map_with_floor, start_with_floor = add_floor_to_map(map_, new_start)
215 sand_filled_map = simulate_sand_falling(map_with_floor, start_with_floor)
217 print(f"{sand_filled_map[sand_filled_map == 2].shape[0]} grains fell")
219 if verbose:
220 print("Before :")
221 print(render_map(map_with_floor, start_with_floor))
222 print("After :")
223 print(render_map(sand_filled_map, start_with_floor))