-
Notifications
You must be signed in to change notification settings - Fork 0
/
11 - Cosmic Expansion.py
128 lines (90 loc) · 3.28 KB
/
11 - Cosmic Expansion.py
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
from modules import DataManager
data = DataManager(__file__).get_data_string()
# Testdata -------------------------------------------------------------------------------------
test_data_string = """
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
"""
test_data = test_data_string.strip().split("\n")
debug = [False, False, False, False]
expected = (374, 10276166, 1030, 598693078798)
# Shared ---------------------------------------------------------------------------------------
def sum_distances(input, factor) -> int:
universe = get_universe(input)
empty_rows = [all(cell == "." for cell in row) for row in universe]
empty_cols = [
all(input[row][col] == "." for row in range(len(input)))
for col in range(len(input[0]))
]
galaxy_positions = [
(i, j)
for i, row in enumerate(universe)
for j, cell in enumerate(row)
if cell == "#"
]
if debug:
print_universe(universe)
print_galaxy_positions(galaxy_positions)
return int( # cast to int since we're dealing with large numbers
sum(calculate_distances(galaxy_positions, empty_rows, empty_cols, factor))
)
def get_universe(input):
return [list(row) for row in input]
def calculate_distances(galaxy_positions, empty_rows, empty_cols, factor):
distances = []
for idx, g1 in enumerate(galaxy_positions):
for g2 in galaxy_positions[idx + 1 :]:
dist = abs(g1[0] - g2[0])
for i in bi_range(g1[0], g2[0]):
if empty_rows[i]:
dist += factor - 1
dist += abs(g1[1] - g2[1])
for j in bi_range(g1[1], g2[1]):
if empty_cols[j]:
dist += factor - 1
distances.append(dist)
if debug:
print(f"Distance between {g1} and {g2} is {dist}")
return distances
def bi_range(a, b):
if a < b:
return range(a, b)
return range(b, a)
# Part 1 ---------------------------------------------------------------------------------------
def part1(input=data) -> int:
return sum_distances(input, 2)
# Part 2 ---------------------------------------------------------------------------------------
def part2(input=data) -> int:
return sum_distances(input, 1e6)
def part2_test(input=data) -> int:
return sum_distances(input, 10)
# Debugging ------------------------------------------------------------------------------------
def print_universe(universe):
print("Universe:")
for row in universe:
print("".join(row))
def print_galaxy_positions(galaxy_positions):
print("Galaxy Positions:")
for i, pos in enumerate(galaxy_positions):
print(f"Galaxy {i+1}: Position {pos}")
# Output ---------------------------------------------------------------------------------------
results = [
("Test Part 1:", part1, test_data, expected[0], debug[0]),
("Part 1:", part1, data, expected[1], debug[1]),
("Test Part 2:", part2_test, test_data, expected[2], debug[2]),
("Part 2:", part2, data, expected[3], debug[3]),
]
for result in results:
debug = result[4]
value = result[1](result[2])
print(result[0], value)
if result[3] and value != result[3]:
print("Expected:", result[3])