re: Advent of Code 2019 Solution Megathread - Day 12: The N-Body Problem VIEW POST

Part 1 was...not easy, exactly, but straightforward. Apply some logic, iterate 1000 times, cool.

Part 2 took me the rest of the day to work out, and the key insight turned out to be 2-pronged:

1. looking for a single satellite to repeat itself is probably faster than looking for all four to repeat at the same time. this turned out to be the wrong approach, but the idea of breaking it down into parts and then looking for a multiple turned out to be the right path...
2. satellite motion in a given direction is totally independent of the other directions, meaning that we can look for the four satellites to repeat themselves in just one axis, and they will have a consistent period of oscillation on that single axis. We can repeat on the other 2 axes to find 3 time periods and then the moment the satellites all find themselves at the starting location is the least common multiple of the 3 periods. I confess that this had me stumped for a looong time, and I went looking for hints on reddit before something jogged my brain.

Anyways, ruby code for part 2:

``````#!/usr/bin/env ruby

class Moon
attr_accessor :pos
attr_accessor :v
def initialize(pos)
@pos = Vector3D.new(pos)
@v = Vector3D.new([0,0,0])
end

def apply_gravity(other_moon)
dx = sign(@pos.x - other_moon.pos.x)
dy = sign(@pos.y - other_moon.pos.y)
dz = sign(@pos.z - other_moon.pos.z)

@v.x -= dx
@v.y -= dy
@v.z -= dz

other_moon.v.x += dx
other_moon.v.y += dy
other_moon.v.z += dz
end

def move()
@pos.x += @v.x
@pos.y += @v.y
@pos.z += @v.z
end

def potential_energy()
return @pos.x.abs + @pos.y.abs + @pos.z.abs
end

def kinetic_energy()
return @v.x.abs + @v.y.abs + @v.z.abs
end

def energy()
return potential_energy() * kinetic_energy()
end

def to_s()
return "#{@pos}|#{@v}"
end

def clone()
return Moon.new([@pos.x,@pos.y,@pos.z])
end
end

class Vector3D
attr_accessor :x
attr_accessor :y
attr_accessor :z
def initialize(coords)
@x = coords[0]
@y = coords[1]
@z = coords[2]
end
def to_s()
return "#{@x},#{@y},#{@z}"
end
end

def sign(n)
return n <=> 0
end

def parse_position(line)
stripped = line[1..-2] # get rid of <>
chunks = stripped.split(",")
nums = []
chunks.each do |c|
bits = c.split("=")
num = bits[1]
nums.push(num.to_i)
end
return nums
end

def step(moons)
for i in 0..moons.length-1
m = moons[i]
for j in i+1..moons.length-1
other = moons[j]
m.apply_gravity(other)
end
end
moons.each do |m|
m.move()
end
end

def pp(moons)
moons.each do |m|
puts "#{m.pos.x},#{m.pos.y},#{m.pos.z} || #{m.v.x},#{m.v.y},#{m.v.z}"
end
end

def state(moons)
s = ""
moons.each do |m|
s += m.to_s + "."
end
return s
end

def find_repeat_state(moons)
initial_moons = moons.map { |m| m.clone() }
periods = [nil,nil,nil]
num_steps = 0
while true
num_steps += 1
step(moons)

# x
if periods[0] == nil
xmatch = true
4.times do |idx|
current_moon = moons[idx]
initial_state = initial_moons[idx]
if !(current_moon.pos.x == initial_state.pos.x && current_moon.v.x == initial_state.v.x)
xmatch = false
end
end
if xmatch
periods[0] = num_steps
end
end

# y
if periods[1] == nil
ymatch = true
4.times do |idx|
current_moon = moons[idx]
initial_state = initial_moons[idx]
if !(current_moon.pos.y == initial_state.pos.y && current_moon.v.y == initial_state.v.y)
ymatch = false
end
end

if ymatch
periods[1] = num_steps
end
end

# z
if periods[2] == nil
zmatch = true
4.times do |idx|
current_moon = moons[idx]
initial_state = initial_moons[idx]
if !(current_moon.pos.z == initial_state.pos.z && current_moon.v.z == initial_state.v.z)
zmatch = false
end
end
if zmatch
periods[2] = num_steps
end
end

if !periods.include?(nil)
break
end
end
return periods.reduce(1, :lcm)
end

if __FILE__ == \$0
moons = []
File.open(ARGV[0], "r") do |file_handle|
file_handle.each_line do |line|
pos = parse_position(line.chomp)
moons.push(Moon.new(pos))
end
end
puts find_repeat_state(moons)
end
``````
code of conduct - report abuse