2018-12-25 - Four-Dimensional Adventure
(original .ipynb)
test_input_str_1 = """0,0,0,0
3,0,0,0
0,3,0,0
0,0,3,0
0,0,0,3
0,0,0,6
9,0,0,0
12,0,0,0"""
test_input_str_2 = """-1,2,2,0
0,0,2,-2
0,0,0,-2
-1,2,0,0
-2,-2,-2,2
3,0,2,-1
-1,3,2,2
-1,0,-1,0
0,2,1,-2
3,0,0,0"""
test_input_str_3 = """1,-1,0,1
2,0,-1,0
3,2,-1,0
0,0,3,1
0,0,-1,-1
2,3,-2,0
-2,2,0,0
2,-2,0,-1
1,-1,0,-1
3,2,0,2"""
test_input_str_4 = """1,-1,-1,-2
-2,-2,0,1
0,2,1,3
-2,3,-2,1
0,2,3,-2
-1,-1,1,-2
0,-2,-1,0
-2,2,3,-1
1,2,2,0
-1,-2,0,-2"""
puzzle_input_str = open("puzzle_input/day25.txt").read()
def parse_input(input_str):
points = []
for line in input_str.split("\n"):
point = [int(s) for s in line.split(",")]
points.append(point)
return points
def distance(p1, p2):
x1, y1, z1, w1 = p1
x2, y2, z2, w2 = p2
return abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2) + abs(w1 - w2)
def should_join(c1, c2):
for p1 in c1:
for p2 in c2:
if distance(p1, p2) <= 3:
return True
return False
def find_constellations(input_str):
points = parse_input(input_str)
# build a naive list of constellations
semi_constellations = []
while any(points):
point = points.pop(0)
was_inserted = False
for constellation in semi_constellations:
for other_point in constellation:
if distance(point, other_point) <= 3:
constellation.append(point)
was_inserted = True
break
if was_inserted:
break
if not was_inserted:
semi_constellations.append([point])
# see if any can be jammed together
constellations = []
constellation = None
while any(semi_constellations):
if constellation is None:
constellation = semi_constellations.pop()
joined = False
for i, c in enumerate(constellations):
if should_join(constellation, c):
c = constellations.pop(i)
constellation += c
joined = True
break
if not joined:
constellations.append(constellation)
constellation = None
return len(constellations)
assert 2 == find_constellations(test_input_str_1)
assert 4 == find_constellations(test_input_str_2)
assert 3 == find_constellations(test_input_str_3)
assert 8 == find_constellations(test_input_str_4)
print(find_constellations(puzzle_input_str))
367