-
-
Save QuinnWilton/bb8a1d6d7a3c1e3807d203fe62ec8d12 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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