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

1from typing import List, Optional, Tuple 

2 

3from src.aoc2022 import utils 

4 

5 

6def parse_data_to_array( 

7 raw_data: str, 

8) -> List[Tuple[int, int, int, int]]: 

9 """ 

10 Parse raw data into a list of sensor/closest beacon locations 

11 

12 :param raw_data: Raw data to parse into sensor/beacon locations 

13 :type raw_data: str 

14 

15 :return: the parsed sensor/beacon locations 

16 :rtype: List[Tuple[int, int]] 

17 """ 

18 

19 coordinate_pairs = [] 

20 

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

22 sensor_str, beacon_str = line.split(": ") 

23 

24 sensor_prefix = "Sensor at " 

25 x_str, y_str = sensor_str.replace(sensor_prefix, "").split(", ") 

26 sensor_location = int(x_str[2:]), int(y_str[2:]) 

27 

28 beacon_prefix = "closest beacon is at " 

29 x_str, y_str = beacon_str.replace(beacon_prefix, "").split(", ") 

30 beacon_location = int(x_str[2:]), int(y_str[2:]) 

31 

32 coordinate_pairs.append((*sensor_location, *beacon_location)) 

33 

34 return coordinate_pairs 

35 

36 

37def count_scanned_location( 

38 beacon_sensor_locations: List[Tuple[int, int, int, int]], 

39 row_number: int, 

40 bounding_range: Optional[Tuple[int, int]] = None, 

41) -> Tuple[List[Tuple[int, int]], int]: 

42 """ 

43 Count how many locations have been scanned given the beacon/sensor 

44 locations and the row number 

45 

46 :param beacon_sensor_locations: List of sensor/beacon locations 

47 :type beacon_sensor_locations: List[Tuple[int, int, int, int]] 

48 

49 :param row_number: The row for which to count the scan locations 

50 :type row_number: int 

51 

52 :param bounding_range: an optional bounding range for scan range 

53 :type bounding_range: Optional[Tuple[int, int]] 

54 

55 :return: the ranges scanned as well as the total number of scanned cells 

56 :rtype: Tuple[List[Tuple[int, int]], int] 

57 """ 

58 

59 ranges = [] 

60 

61 # note this is not optimal, this is O(nm), where n = num beacons, m = size 

62 # could do an O(n^2) solution by checking each pair of beacons, would be 

63 # faster in the case that n << m 

64 for sensor_x, sensor_y, beacon_x, beacon_y in beacon_sensor_locations: 

65 

66 L1_dist = abs(beacon_x - sensor_x) + abs(beacon_y - sensor_y) 

67 

68 width = (2 * L1_dist + 1) - (2 * abs(sensor_y - row_number)) 

69 

70 if width > 0: 

71 left = sensor_x - width // 2 

72 right = sensor_x + width // 2 

73 if bounding_range is not None: 

74 left = max(bounding_range[0], min(bounding_range[1], left)) 

75 right = max(bounding_range[0], min(bounding_range[1], right)) 

76 

77 range_ = (left, right) 

78 ranges.append(range_) 

79 

80 potential_beacons = set( 

81 [t[2] for t in beacon_sensor_locations if t[3] == row_number] 

82 ) 

83 

84 sorted_ranges = sorted(ranges, key=lambda t: t[0]) 

85 range_stack = [sorted_ranges[0]] 

86 

87 for start, end in sorted_ranges[1:]: 

88 stack_start, stack_end = range_stack[-1] 

89 

90 if stack_start <= start <= stack_end: 

91 range_stack[-1] = (stack_start, max(stack_end, end)) 

92 else: 

93 range_stack.append((start, end)) 

94 

95 total_count = 0 

96 for start, end in range_stack: 

97 for x in potential_beacons: 

98 if start <= x <= end: 

99 total_count -= 1 

100 

101 total_count += end - start + 1 

102 

103 return range_stack, total_count 

104 

105 

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

107 

108 row_to_analyze = 2_000_000 

109 

110 raw_data = utils.get_raw_data("./src/aoc2022/data/day15.txt") 

111 sensor_beacon_coordinates = parse_data_to_array(raw_data) 

112 

113 ranges, location_count = count_scanned_location( 

114 sensor_beacon_coordinates, row_to_analyze 

115 ) 

116 print(f"{location_count} locations are sure to not contain a beacon") 

117 

118 min_x, max_x = 0, 4_000_000 

119 

120 for i in range(min_x, max_x): 

121 ranges, location_count = count_scanned_location( 

122 sensor_beacon_coordinates, i, bounding_range=(min_x, max_x) 

123 ) 

124 

125 if len(ranges) != 1: 

126 x_coord = ranges[0][1] + 1 

127 print(f"The tuning frequence is {x_coord * 4_000_000 + i}") 

128 break