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]))
    return total
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 [ ]: