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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
# -*- coding: utf-8 -*-
from abc import ABC
from functools import lru_cache
from typing import Tuple, Iterator, Set, Any, Optional
from aoc import BaseAssignment
from aoc.datastructures import Coordinate
class Assignment(BaseAssignment, ABC):
def __init__(self, path):
super().__init__(path)
self.cave_depth = None
def coordinate_ranges(
self, input: Iterator[str]
) -> Iterator[Tuple[Coordinate, Coordinate]]:
for item in input:
last = None
for i in item.split(" -> "):
x, y = i.split(",")
coordinate = int(x), int(y)
if last is not None:
yield last, coordinate
last = coordinate
def coordinates(self, a: Coordinate, b: Coordinate) -> Iterator[Coordinate]:
for x in range(min(a[0], b[0]), max(a[0], b[0]) + 1):
for y in range(min(a[1], b[1]), max(a[1], b[1]) + 1):
yield x, y
def generate_rocks(self, input: Iterator[str]) -> Set[Coordinate]:
rocks = set(
coordinate
for coordinates in self.coordinate_ranges(input)
for coordinate in self.coordinates(*coordinates)
)
self.cave_depth = self.get_cave_depth(rocks)
return rocks
def get_cave_depth(self, cave: Set[Coordinate]):
return max([item[1] for item in cave])
def invalid_position(self, sand: Coordinate, cave: set[Coordinate]):
raise NotImplementedError()
def blocking(self, sand: Coordinate, cave: set[Coordinate]):
raise NotImplementedError()
def drop_sand(
self, sand: Coordinate, cave: Set[Coordinate]
) -> Optional[Coordinate]:
if self.invalid_position(sand, cave):
return None
next_positions = [
(sand[0], sand[1] + 1),
(sand[0] - 1, sand[1] + 1),
(sand[0] + 1, sand[1] + 1),
]
non_blocking = [
next_position
for next_position in next_positions
if not self.blocking(next_position, cave)
]
if len(non_blocking) == 0:
return sand
return self.drop_sand(non_blocking[0], cave)
def generate_sand(self, cave: set[Coordinate]) -> Iterator[Coordinate]:
cave_copy = set(cave)
sand = (500, 0)
while True:
coordinate = self.drop_sand(sand, cave_copy)
if coordinate is None:
return
cave_copy.add(coordinate)
yield coordinate
def run(self, input: Iterator) -> Any:
cave = self.generate_rocks(input)
coordinates = set()
for sand in self.generate_sand(cave):
coordinates.add(sand)
return len(coordinates)
class AssignmentOne(Assignment):
example_result = 24
def invalid_position(self, sand: Coordinate, cave: set[Coordinate]):
return sand[1] > self.cave_depth
def blocking(self, sand: Coordinate, cave: set[Coordinate]):
return sand in cave
class AssignmentTwo(Assignment):
example_result = 93
def invalid_position(self, sand: Coordinate, cave: set[Coordinate]):
return False
def blocking(self, sand: Coordinate, cave: set[Coordinate]):
return sand in cave or sand[1] >= self.cave_depth + 2
def run(self, input: Iterator) -> Any:
cave = self.generate_rocks(input)
coordinates = set()
for sand in self.generate_sand(cave):
coordinates.add(sand)
if sand == (500, 0):
break
return len(coordinates)
|
