diff options
author | Justin Wernick <justin@worthe-it.co.za> | 2019-12-20 23:56:10 +0200 |
---|---|---|
committer | Justin Wernick <justin@worthe-it.co.za> | 2019-12-20 23:56:10 +0200 |
commit | 4316344e335cd69714799ed204d2448d81877b7d (patch) | |
tree | 7edb82fdfa936261d134d3118805b4e4ec3d5028 /src/bin/day_12.rs | |
parent | 8f88266bd0890ae8e238ab108d16dba9fea86bfd (diff) |
Day 12 part 2
Diffstat (limited to 'src/bin/day_12.rs')
-rw-r--r-- | src/bin/day_12.rs | 69 |
1 files changed, 59 insertions, 10 deletions
diff --git a/src/bin/day_12.rs b/src/bin/day_12.rs index 678653b..fa0db20 100644 --- a/src/bin/day_12.rs +++ b/src/bin/day_12.rs @@ -16,7 +16,7 @@ use structopt::StructOpt; /// See https://adventofcode.com/2019/day/12 for details. struct Opt { #[structopt(short = "n")] - n: usize, + n: Option<u64>, } fn main() { @@ -30,7 +30,10 @@ fn main() { .map(|x| exit_on_failed_assertion(x.parse::<Planet>(), "Input was not a valid planet")) .collect(); - println!("{}", energy(simulate_planets_n_iterations(planets, opt.n))); + match opt.n { + Some(n) => println!("{}", energy(simulate_planets_n_iterations(planets, n))), + None => println!("{}", simulate_planets_to_duplicate(planets)), + }; } fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A { @@ -47,13 +50,47 @@ fn energy(planets: Vec<Planet>) -> i32 { planets.into_iter().map(|p| p.energy()).sum() } -fn simulate_planets_n_iterations(planets: Vec<Planet>, n: usize) -> Vec<Planet> { - iter::successors(Some((0, planets)), |(i, planets)| { +fn simulate_planets_n_iterations(planets: Vec<Planet>, n: u64) -> Vec<Planet> { + simulate_planets_iter(planets) + .find(|(i, _)| *i == n) + .unwrap() + .1 +} + +fn simulate_planets_to_duplicate(planets: Vec<Planet>) -> u64 { + lowest_common_multiple( + simulate_planets_to_duplicate_1d(planets.clone(), |(p, o)| p.equal_x(o)), + simulate_planets_to_duplicate_1d(planets.clone(), |(p, o)| p.equal_y(o)), + simulate_planets_to_duplicate_1d(planets.clone(), |(p, o)| p.equal_z(o)), + ) +} + +fn simulate_planets_to_duplicate_1d( + planets: Vec<Planet>, + eq: impl FnMut((&Planet, &Planet)) -> bool + Copy, +) -> u64 { + simulate_planets_iter(planets.clone()) + .skip(1) + .find(|(_i, ps)| ps.iter().zip(planets.iter()).all(eq)) + .unwrap() + .0 +} + +fn lowest_common_multiple(x: u64, y: u64, z: u64) -> u64 { + (1..) + .map(|i| x * i) + .find(|mx| multiples(y, *mx) && multiples(z, *mx)) + .unwrap() +} + +fn multiples(x: u64, target: u64) -> bool { + target % x == 0 +} + +fn simulate_planets_iter(planets: Vec<Planet>) -> impl Iterator<Item = (u64, Vec<Planet>)> { + iter::successors(Some((0, planets.clone())), |(i, planets)| { Some((i + 1, simulate_planets(planets.clone()))) }) - .find(|(i, _)| *i == n) - .unwrap() - .1 } fn simulate_planets(planets: Vec<Planet>) -> Vec<Planet> { @@ -68,7 +105,7 @@ fn simulate_gravity(planets: Vec<Planet>) -> Vec<Planet> { vel: planets .iter() .filter(|o| p != *o) - .map(|o| p.gravity_pull(o)) + .map(|o| p.acc(o)) .fold(p.vel, |acc, next| acc + next), }) .collect() @@ -116,13 +153,13 @@ impl FromStr for Planet { }), _ => "wrong number of fields" .parse::<i32>() - .map(|x| Planet::default()), + .map(|_x| Planet::default()), }) } } impl Planet { - fn gravity_pull(&self, other: &Planet) -> Vec3d { + fn acc(&self, other: &Planet) -> Vec3d { Vec3d { x: gravity(self.pos.x, other.pos.x), y: gravity(self.pos.y, other.pos.y), @@ -134,6 +171,18 @@ impl Planet { (self.pos.x.abs() + self.pos.y.abs() + self.pos.z.abs()) * (self.vel.x.abs() + self.vel.y.abs() + self.vel.z.abs()) } + + fn equal_x(&self, other: &Planet) -> bool { + self.pos.x == other.pos.x && self.vel.x == other.vel.x + } + + fn equal_y(&self, other: &Planet) -> bool { + self.pos.y == other.pos.y && self.vel.y == other.vel.y + } + + fn equal_z(&self, other: &Planet) -> bool { + self.pos.z == other.pos.z && self.vel.z == other.vel.z + } } fn gravity(this: i32, that: i32) -> i32 { |