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

1from typing import 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 1D list of instruction sets 

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[str]] 

17 """ 

18 

19 rows = [] 

20 

21 base_value = ord("a") 

22 

23 start_pos = None 

24 end_pos = None 

25 

26 for i, line in enumerate(raw_data.split("\n")): # row number 

27 values = [] 

28 for j, char in enumerate(line.strip()): # col number 

29 if char == "S": 

30 values.append(0) 

31 start_pos = (j, i) 

32 elif char == "E": 

33 values.append(ord("z") - base_value) 

34 end_pos = (j, i) 

35 else: 

36 values.append(ord(char) - base_value) 

37 rows.append(np.array(values)) 

38 

39 return np.array(rows).transpose(), start_pos, end_pos 

40 

41 

42def get_distance_matrix(data: np.ndarray, pos: Tuple[int, int]) -> np.ndarray: 

43 """ 

44 Compute the breadth-first distance matrix from aa starting position 

45 

46 :param data: Height map for the traversal 

47 :type data: np.ndarray 

48 

49 :param pos: starting position for the depth-first search 

50 :type pos: Tuple[int, int] 

51 

52 :return: the shortest distance from the starting pos to all other points 

53 :rtype: np.ndarray 

54 """ 

55 distances = np.full(data.shape, -1) 

56 distances[pos] = 0 

57 visited = np.full(data.shape, 0, dtype=bool) 

58 

59 visit_stack = [pos] 

60 

61 max_x, max_y = data.shape 

62 

63 deltas = [ 

64 (-1, 0), 

65 (1, 0), 

66 (0, -1), 

67 (0, 1), 

68 ] 

69 

70 while len(visit_stack) > 0: 

71 x, y = visit_stack.pop(0) 

72 

73 if visited[x, y]: 

74 pass 

75 else: 

76 

77 visited[x, y] = True 

78 

79 for dx, dy in deltas: 

80 new_x = x + dx 

81 new_y = y + dy 

82 

83 valid_x = new_x >= 0 and new_x < max_x 

84 valid_y = new_y >= 0 and new_y < max_y 

85 

86 if valid_x and valid_y: 

87 

88 valid_pos = data[x, y] - data[new_x, new_y] <= 1 

89 

90 if valid_pos and (not visited[new_x, new_y]): 

91 distances[new_x, new_y] = distances[x, y] + 1 

92 visit_stack.append((new_x, new_y)) 

93 

94 return distances 

95 

96 

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

98 

99 raw_data = utils.get_raw_data("./src/aoc2022/data/day12.txt") 

100 

101 parsed_map, start, end = parse_data_to_array(raw_data) 

102 

103 distance_matrix = get_distance_matrix(parsed_map, end) 

104 path_length = distance_matrix[start] 

105 

106 print(f"The shortest path is {path_length}") 

107 

108 values = [e for e in distance_matrix[parsed_map == 0] if e != -1] 

109 closest_start = min(*values) 

110 

111 print(f"The closest start point is {closest_start}")