1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
# -*- coding: utf-8 -*-
import re
from abc import ABC
from dataclasses import dataclass, field
from typing import Union
from typing import Tuple, Iterator, Set, List
from aoc import BaseAssignment
from aoc.datastructures import Coordinate
@dataclass
class Sensor:
coordinate: Coordinate
nearest: Coordinate
radius: int = None
def __hash__(self):
return hash(self.coordinate)
def __post_init__(self):
self.radius = self.coordinate.manhattan_distance(self.nearest)
def within_radius(self, coordinate: Coordinate) -> bool:
distance = self.coordinate.manhattan_distance(coordinate)
return distance <= self.radius
def x_coordinates_within_radius_at(self, y: int, map: "Map") -> Union[range, list]:
coordinate = Coordinate(self.coordinate.x, y)
if not self.within_radius(coordinate):
return []
dy = abs(self.coordinate.y - y)
left_over = self.radius - dy
return range(
max(self.coordinate.x - left_over, map.width[0]),
min(self.coordinate.x + left_over + 1, map.width[-1]),
)
@dataclass
class Map:
sensors: List[Sensor] = field(default_factory=list)
beacons: Set[Coordinate] = field(default_factory=set)
def __post_init__(self):
all_coordinates = self.beacons | {sensor.coordinate for sensor in self.sensors}
min_x = min(c.x for c in all_coordinates)
max_x = max(c.x for c in all_coordinates)
min_y = min(c.y for c in all_coordinates)
max_y = max(c.y for c in all_coordinates)
self.width = list(range(min_x, max_x + 1))
self.height = list(range(min_y, max_y + 1))
input_pattern = re.compile("x=(-?[-0-9]+), y=(-?[0-9]+)")
class Assignment(BaseAssignment[int, Tuple[Sensor, Coordinate]], ABC):
def parse_item(self, line: str) -> Tuple[Sensor, Coordinate]:
match = input_pattern.findall(line)
if len(match) != 2:
raise RuntimeError()
sensor_match, beacon_match = match
beacon = Coordinate(int(beacon_match[0]), int(beacon_match[1]))
sensor = Sensor(Coordinate(int(sensor_match[0]), int(sensor_match[1])), beacon)
return sensor, beacon
def create_map(self, input: Iterator[Tuple[Sensor, Coordinate]]) -> Map:
sensors = list()
beacons = set()
for sensor, beacon in input:
sensors.append(sensor)
beacons.add(beacon)
return Map(sensors, beacons)
class AssignmentOne(Assignment):
example_result = 26
example_kwargs = {"y": 10}
# Wrong: 4062163
def run(self, input: Iterator[Tuple[Sensor, Coordinate]], y=2000000):
map = self.create_map(input)
x_coordinates = {
x
for sensor in map.sensors
for x in sensor.x_coordinates_within_radius_at(y, map)
}
return len(x_coordinates) - len(
[beacon.x for beacon in map.beacons if beacon.y == y]
)
class AssignmentTwo(Assignment):
pass
|
