# AoC 12¶

In [214]:
test="""<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>"""

test_posns = [[-1, 0, 2], [2, -10, -7], [4, -8, 8], [3, 5, -1]]

actual="""<x=5, y=13, z=-3>
<x=18, y=-7, z=13>
<x=16, y=3, z=4>
<x=0, y=8, z=8>
"""
posns = [[5, 13, -3], [18, -7, 13], [16, 3, 4], [0, 8, 8]]

test2="""<x=-8, y=-10, z=0>
<x=5, y=5, z=10>
<x=2, y=-7, z=3>
<x=9, y=-8, z=-3>"""
test2_posns= [[-8,-10,0], [5,5,10], [2,-7,3], [9,-8,-3]]

In [72]:
def eval_moons(arg_moons, steps=10):
moons = []
moons_v = []
for i in range(4):
moons.append(arg_moons[i][:])
moons_v.append([0] * 3)

for step in range(steps + 1):
# print(f"After {step} steps")
# for i, moon in enumerate(moons):
#     moon_v = moons_v[i]
#     print(f"pos=<x={moon[0]}, y={moon[1]}, z={moon[2]}, vel=<x={moon_v[0]}, y={moon_v[1]}, z={moon_v[2]}")

for i, moon in enumerate(moons):
for j, moon in enumerate(moons):
if i >= j:
continue
for k in range(3):
if moons[i][k] == moons[j][k]:
continue
moons_v[i][k] += 1 if moons[i][k] < moons[j][k] else -1
moons_v[j][k] += 1 if moons[j][k] < moons[i][k] else -1

for i, moon in enumerate(moons):
for k in range(3):
moons[i][k] += moons_v[i][k]

# print()
return moons, moons_v


In [79]:
newmoons = eval_moons(posns, 999)

In [76]:
def energy(moons, moons_v):
total = 0
for i in range(4):
total += sum(map(abs, moons[i])) * sum(map(abs, moons_v[i]))

In [81]:
energy(*newmoons)

Out[81]:
10198
In [227]:
from copy import deepcopy

def sim(arg_moons):
moons = []
moons_v = []
for i in range(4):
moons.append(arg_moons[i][:])
moons_v.append([0] * 3)

while True:
for i, moon in enumerate(moons):
for j, moon in enumerate(moons):
if i >= j:
continue
for k in range(3):
if moons[i][k] == moons[j][k]:
continue
moons_v[i][k] += 1 if moons[i][k] < moons[j][k] else -1
moons_v[j][k] += 1 if moons[j][k] < moons[i][k] else -1

for i, moon in enumerate(moons):
for k in range(3):
moons[i][k] += moons_v[i][k]

yield deepcopy(moons), None

In [210]:
def find_cycle(v, start=1):
l = len(v)
for i in range(start, l // 2):
if all(v[i + j] == v[j] for j in range(i)):
return i
return None

In [201]:
from math import gcd

def lcm(l):
lcm = l[0]
for a in l[1:]:
lcm = lcm * a // gcd(lcm, a)
return lcm

In [228]:
%%time
testsim = sim(posns)
coords = []
cycles = [None] * 12

for _ in range(4):
coords.append([])
for _ in range(3):
coords[-1].append([])

steps = 0

while not all(cycles):
steps += 1

if steps % 50000 == 0:
print(steps, cycles)

n = next(testsim)
for i in range(4):
for j in range(3):
coords[i][j].append(n[0][i][j])
index = i * 3 + j
if not cycles[index]:
cycles[index] = find_cycle(coords[i][j], start=max(1, (steps - 1) // 2))

print(cycles)
print(lcm(cycles))

50000 [None, None, None, None, None, None, None, None, None, None, None, None]
100000 [None, None, None, None, None, None, None, None, None, None, None, None]
150000 [None, None, None, None, None, None, None, None, None, None, None, None]
200000 [None, None, None, None, None, None, None, None, None, None, None, None]
250000 [None, None, None, None, None, None, None, None, None, None, None, None]
300000 [None, None, 144624, None, None, 144624, None, None, 144624, None, None, 144624]
350000 [None, 161428, 144624, None, 161428, 144624, None, 161428, 144624, None, 161428, 144624]
[186028, 161428, 144624, 186028, 161428, 144624, 186028, 161428, 144624, 186028, 161428, 144624]
271442326847376
CPU times: user 28.5 s, sys: 120 ms, total: 28.6 s
Wall time: 28.7 s


TODO: Come back and have fun optimizing this a little; removing one of the deep-copies cut runtime by 10%, there's a lot i could speed up here.

In [ ]: