Skip to content

Instantly share code, notes, and snippets.

@QuinnWilton
Created December 12, 2019 08:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save QuinnWilton/bb8a1d6d7a3c1e3807d203fe62ec8d12 to your computer and use it in GitHub Desktop.
Save QuinnWilton/bb8a1d6d7a3c1e3807d203fe62ec8d12 to your computer and use it in GitHub Desktop.
defmodule Aoc.Year2019.Day12.TheNBodyProblem do
import Aoc
defmodule System do
defmodule Moon do
alias __MODULE__
defstruct [:position, velocity: {0, 0, 0}]
def apply_gravity(%Moon{} = moon, others) do
Enum.reduce(others, moon, fn %Moon{} = other, %Moon{} = moon ->
{x1, y1, z1} = moon.position
{x2, y2, z2} = other.position
{vx, vy, vz} = moon.velocity
new_velocity = {
vx + gravity_delta(x1, x2),
vy + gravity_delta(y1, y2),
vz + gravity_delta(z1, z2)
}
%Moon{moon | velocity: new_velocity}
end)
end
def apply_velocity(%Moon{} = moon) do
{x, y, z} = moon.position
{vx, vy, vz} = moon.velocity
new_position = {
x + vx,
y + vy,
z + vz
}
%Moon{moon | position: new_position}
end
def total_energy(%Moon{} = moon) do
potential_energy(moon) * kinetic_energy(moon)
end
def potential_energy(%Moon{position: {x, y, z}}) do
abs(x) + abs(y) + abs(z)
end
def kinetic_energy(%Moon{velocity: {x, y, z}}) do
abs(x) + abs(y) + abs(z)
end
defp gravity_delta(d1, d2) do
cond do
d1 == d2 -> 0
d1 < d2 -> 1
d2 < d1 -> -1
end
end
end
alias __MODULE__
defstruct [:moons]
def simulate(%System{} = system, 0), do: system
def simulate(%System{} = system, n) do
system
|> step()
|> simulate(n - 1)
end
def step(%System{} = system) do
system
|> apply_gravity()
|> apply_velocity()
end
def apply_gravity(%System{} = system) do
combinations = pairs(system.moons, [])
moons =
Enum.map(combinations, fn {moon, others} ->
Moon.apply_gravity(moon, others)
end)
%System{system | moons: moons}
end
def apply_velocity(%System{} = system) do
moons =
Enum.map(system.moons, fn %Moon{} = moon ->
Moon.apply_velocity(moon)
end)
%System{system | moons: moons}
end
def total_energy(%System{} = system) do
Enum.reduce(system.moons, 0, fn %Moon{} = moon, acc ->
acc + Moon.total_energy(moon)
end)
end
defp pairs([], _moons), do: []
defp pairs([moon | rest], moons) do
[{moon, moons ++ rest} | pairs(rest, [moon | moons])]
end
end
def part_1() do
system = %System{
moons: [
%System.Moon{position: {5, -1, 5}},
%System.Moon{position: {0, -14, 2}},
%System.Moon{position: {16, 4, 0}},
%System.Moon{position: {18, 1, 16}}
]
}
system
|> System.simulate(1000)
|> System.total_energy()
end
def part_2() do
system = %System{
moons: [
%System.Moon{position: {5, -1, 5}},
%System.Moon{position: {0, -14, 2}},
%System.Moon{position: {16, 4, 0}},
%System.Moon{position: {18, 1, 16}}
]
}
nx = find_state(system, System.step(system), {1, 0, 0}, 1)
ny = find_state(system, System.step(system), {0, 1, 0}, 1)
nz = find_state(system, System.step(system), {0, 0, 1}, 1)
lcm(nx, lcm(ny, nz))
end
defp find_state(initial, new, filter, n) do
initial_filtered = filter(initial, filter)
new_filtered = filter(new, filter)
if initial_filtered == new_filtered do
n
else
new = System.simulate(new, 1)
find_state(initial, new, filter, n + 1)
end
end
defp filter(system, {fx, fy, fz}) do
moons =
Enum.map(system.moons, fn moon ->
{x, y, z} = moon.position
{vx, vy, vz} = moon.velocity
new_position = {
x * fx,
y * fy,
z * fz
}
new_velocity = {
vx * fx,
vy * fy,
vz * fz
}
%{moon | position: new_position, velocity: new_velocity}
end)
%{system | moons: moons}
end
def gcd(a, 0), do: a
def gcd(0, b), do: b
def gcd(a, b), do: gcd(b, rem(a, b))
def lcm(0, 0), do: 0
def lcm(a, b), do: div(a * b, gcd(a, b))
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment