Coverage for src\aoc2022\days\day8.py: 100%

1from typing import Set, Tuple 

2 

3import numpy as np 

4 

5from src.aoc2022 import utils 

6 

7 

8def parse_data_to_array(raw_data: str) -> np.ndarray: 

9 """ 

10 Parse the raw data into a 2D list of lists 

11 

12 :param raw_data: Raw data containing numerical data 

13 :type raw_data: str 

14 

15 :return: parsed matrix of values 

16 :rtype: List[List[int]] 

17 """ 

18 outer_list = [] 

19 for line in raw_data.split("\n"): 

20 inner_list = [int(e) for e in line] 

21 outer_list.append(inner_list) 

22 

23 return np.array(outer_list) 

24 

25 

26def scan_height_row(height_map: np.ndarray) -> Set[int]: 

27 """ 

28 Scan a list of heights to determine which trees are visible from either 

29 side 

30 

31 :param height_map: 1D array of heights 

32 :type height_map: np.ndarray 

33 

34 :return: Set of positions that are visible from either side 

35 :rtype: Set[int] 

36 """ 

37 left_max = -1 

38 right_max = -1 

39 n = len(height_map) 

40 

41 visible_positions = set() 

42 

43 for i in range(n): 

44 left_idx = i 

45 right_idx = n - (1 + i) 

46 

47 left_val = height_map[left_idx] 

48 right_val = height_map[right_idx] 

49 

50 if left_val > left_max: 

51 left_max = left_val 

52 visible_positions.add(left_idx) 

53 if right_val > right_max: 

54 right_max = right_val 

55 visible_positions.add(right_idx) 

56 return visible_positions 

57 

58 

59def count_visible_trees(height_map: np.ndarray) -> int: 

60 """ 

61 Count number of trees visible from perimeter 

62 

63 :param height_map: 2D array of heights 

64 :type height_map: np.ndarray 

65 

66 :return: Total count of trees visible from perimeter 

67 :rtype: int 

68 """ 

69 visible_positions: Set[Tuple[int, int]] = set() 

70 

71 height, width = height_map.shape 

72 

73 for row in range(height): 

74 row_data = height_map[row, :] 

75 visible_in_row = scan_height_row(row_data) 

76 for pos in visible_in_row: 

77 visible_positions.add((row, pos)) 

78 

79 for col in range(width): 

80 col_data = height_map[:, col] 

81 visible_in_col = scan_height_row(col_data) 

82 for pos in visible_in_col: 

83 visible_positions.add((pos, col)) 

84 

85 return len(visible_positions) 

86 

87 

88def compute_scenic_score(height_map: np.ndarray, pos: Tuple[int, int]) -> int: 

89 """ 

90 Compute the scenic view given a starting position 

91 

92 :param height_map: 2D array of heights 

93 :type height_map: np.ndarray 

94 

95 :param pos: tuple of (x, y) positions in the grid 

96 :type pos: Tuple[int, int] 

97 

98 :return: Scenic score of the position given 

99 :rtype: int 

100 """ 

101 height, width = height_map.shape 

102 x, y = pos 

103 start_height = height_map[y, x] 

104 

105 left_view = 0 

106 right_view = 0 

107 top_view = 0 

108 bot_view = 0 

109 

110 i = x + 1 

111 while i < width: 

112 if height_map[y, i] < start_height: 

113 right_view += 1 

114 elif height_map[y, i] >= start_height: 

115 right_view += 1 

116 break 

117 i += 1 

118 

119 i = x - 1 

120 while i >= 0: 

121 if height_map[y, i] < start_height: 

122 left_view += 1 

123 elif height_map[y, i] >= start_height: 

124 left_view += 1 

125 break 

126 i -= 1 

127 

128 j = y + 1 

129 while j < height: 

130 if height_map[j, x] < start_height: 

131 bot_view += 1 

132 elif height_map[y, x] >= start_height: 

133 bot_view += 1 

134 break 

135 j += 1 

136 

137 j = y - 1 

138 while j >= 0: 

139 if height_map[j, x] < start_height: 

140 top_view += 1 

141 elif height_map[y, x] >= start_height: 

142 top_view += 1 

143 break 

144 j -= 1 

145 

146 return top_view * bot_view * left_view * right_view 

147 

148 

149def get_max_scenic_score(height_map: np.ndarray) -> int: 

150 """ 

151 Find the maximum scenic score given the height map 

152 

153 :param height_map: 2D array of heights 

154 :type height_map: np.ndarray 

155 

156 :return: Maximum possible scenic score 

157 :rtype: int 

158 """ 

159 max_ = 0 

160 height, width = height_map.shape 

161 for x in range(width): 

162 for y in range(height): 

163 pos = (x, y) 

164 view = compute_scenic_score(height_map, pos) 

165 if view > max_: 

166 max_ = view 

167 return max_ 

168 

169 

170if __name__ == "__main__": # pragma: no cover 

171 

172 data = utils.get_raw_data("./src/aoc2022/data/day8.txt") 

173 

174 parsed_array = parse_data_to_array(data) 

175 vis_trees = count_visible_trees(parsed_array) 

176 

177 print(f"There are {vis_trees} visible trees.") 

178 

179 compute_scenic_score(parsed_array, (2, 3)) 

180 max_view = get_max_scenic_score(parsed_array) 

181 

182 print(f"The best view is {max_view}.")