the n-body problem

approach

moons are read from stdin as [x, y, z] lists, with a matching list of velocities. a step applies gravity to every pair of moons along one axis and then moves them, axis by axis. part 1 runs 1000 steps and sums potential times kinetic energy.

part 2 relies on the axes being independent. frequency simulates one axis at a time, storing the positions and velocities of all moons on that axis in a set, until a state repeats. the answer is the lcm of the three cycle lengths, computed with a hand-written gcd and lcm.

the trick

x, y and z never affect each other, so find each axis's period separately and combine them with lcm.

def part2(moons):
    velocities = [[0] * len(moon) for moon in moons]
    freqs = []
    for axis in range(len(moons[0])):
        freqs.append(frequency(moons, velocities, axis))
    return lcm(*freqs)