2019-12-12 - The N-Body Problem
(original .ipynb)
Day 12 puzzle input is the position and velocity of a number of moons (mine is here but I didn't want to write any parsing code and it's only 4 lines so I have inlined it in my solution below). Part 1 involves calculating the movement of these moons over 1000 "steps" and applying a calculation to return the "energy" in the system. Part 2 involves attempting to find how many steps it would take for all of the moons to return to their original positions.
from itertools import combinations
axis_x = 0
axis_y = 1
axis_z = 2
def signed_unit(val):
if val == 0:
return 0
return int(abs(val)/val)
def velocity_on_axis(moon0_pos, moon1_pos, axis):
difference = signed_unit(moon0_pos[axis] - moon1_pos[axis])
return (-difference, difference)
def sum_velocity(vel1, vel2):
return [
vel1[axis_x] + vel2[axis_x],
vel1[axis_y] + vel2[axis_y],
vel1[axis_z] + vel2[axis_z]
]
def apply_velocity(moon_pos, vel):
return sum_velocity(moon_pos, vel)
# To apply gravity, consider every pair of moons. On each axis (x, y, and z), the
# velocity of each moon changes by exactly +1 or -1 to pull the moons together. For
# example, if Ganymede has an x position of 3, and Callisto has a x position of 5,
# then Ganymede's x velocity changes by +1 (because 5 > 3) and Callisto's x velocity changes
# by -1 (because 3 < 5).
assert (1, -1) == velocity_on_axis([3], [5], 0)
assert (-1, 1) == velocity_on_axis([10], [5], 0)
assert (0, 0) == velocity_on_axis([5], [5], 0)
def calculate_step(moon_positions, moon_velocity):
moon_indices = range(0, len(moon_positions))
moon_pairs = combinations(moon_indices, 2)
for (moon0, moon1) in moon_pairs:
moon0_pos = moon_positions[moon0]
moon1_pos = moon_positions[moon1]
(moon0_vel_x, moon1_vel_x) = velocity_on_axis(moon0_pos, moon1_pos, axis_x)
(moon0_vel_y, moon1_vel_y) = velocity_on_axis(moon0_pos, moon1_pos, axis_y)
(moon0_vel_z, moon1_vel_z) = velocity_on_axis(moon0_pos, moon1_pos, axis_z)
moon_velocity[moon0] = sum_velocity(moon_velocity[moon0], [ moon0_vel_x, moon0_vel_y, moon0_vel_z ])
moon_velocity[moon1] = sum_velocity(moon_velocity[moon1], [ moon1_vel_x, moon1_vel_y, moon1_vel_z ])
return (
[ apply_velocity(moon_pos, moon_velocity[moon]) for moon, moon_pos in enumerate(moon_positions) ],
moon_velocity
)
def calc_energy(values):
return sum( [ abs(v) for v in values ] )
def calc_total_energy(positions, velocities):
# A moon's potential energy is the sum of the absolute values of its x, y, and z position coordinates.
potential_energies = [ calc_energy(position) for position in positions ]
# A moon's kinetic energy is the sum of the absolute values of its velocity coordinates
kinetic_energies = [ calc_energy(velocity) for velocity in velocities ]
energies = zip(potential_energies, kinetic_energies)
# The total energy for a single moon is its potential energy multiplied by its kinetic energy.
return sum([ potential * kinetic for (potential, kinetic) in energies ])
test_positions_0 = [
[-1, 0, 2],
[2, -10, -7],
[4, -8, 8],
[3, 5, -1]
]
test_positions_1 = [
[ -8, -10, 0 ],
[ 5, 5, 10 ],
[ 2, -7, 3 ],
[ 9, -8, -3 ]
]
def all_cycles_found(cycle_times):
return cycle_times[axis_x] > 0 and cycle_times[axis_y] > 0 and cycle_times[axis_z] > 0
def perform_simulation(num_steps, positions):
original_positions = [ (x, y, z) for (x,y,z) in positions ]
current_step = 0
velocities = [ [0, 0, 0] for n in positions ]
while current_step < num_steps:
positions, velocities = calculate_step(positions, velocities)
current_step += 1
return positions, velocities
def energy_after_steps(num_steps, positions):
positions, velocities = perform_simulation(num_steps, positions)
return calc_total_energy(positions, velocities)
assert 179 == energy_after_steps(10, test_positions_0)
assert 1940 == energy_after_steps(100, test_positions_1)
puzzle_positions = [
[1, 3, -11],
[17, -10, -8],
[-1, -15, 2],
[12, -4, -4]
]
print(energy_after_steps(1000, puzzle_positions))
8310
import math
# NOTE: I had to search around for help, it clicked once someone mentioned the least-common-multiple
# so consider this slightly tainted :-(
def lcm(a, b):
return a * b // math.gcd(a, b)
def find_cycle_times(positions):
original_positions = [ [x, y, z] for x,y,z in positions ]
current_step = 0
cycle_times = [ 0, 0, 0 ]
velocities = [ [0, 0, 0] for n in positions ]
while not(all_cycles_found(cycle_times)):
positions, velocities = calculate_step(positions, velocities)
current_step += 1
for axis in [axis_x, axis_y, axis_z]:
if cycle_times[axis] == 0:
back_to_original = True
for i, position in enumerate(positions):
back_to_original = back_to_original and position[axis] == original_positions[i][axis] and velocities[i][axis] == 0
if back_to_original:
cycle_times[axis] = current_step
return lcm(lcm(cycle_times[axis_x], cycle_times[axis_y]), cycle_times[axis_z])
assert 2772 == find_cycle_times(test_positions_0)
assert 4686774924 == find_cycle_times(test_positions_1)
print(find_cycle_times(puzzle_positions))
319290382980408