aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGravatar alecdwm 2019-12-06 17:29:35 +1000
committerGravatar alecdwm 2019-12-06 17:29:35 +1000
commit77485e24488ea29b41f90dd8c8f498097c23ba96 (patch)
tree5fd429953f411b84247115e9b194a8c9c9897620
parenta79d39fc43ecd139fe3b7f9015e2a4441be17745 (diff)
added 2019 day6 part2 solution
-rw-r--r--src/main.rs1
-rw-r--r--src/year_2019/day6.rs217
2 files changed, 195 insertions, 23 deletions
diff --git a/src/main.rs b/src/main.rs
index e1c4eee..0b01276 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -30,6 +30,7 @@ fn main() {
puzzle_solutions.insert("2019::day5::part1", advent_of_code::year_2019::day5::part1);
puzzle_solutions.insert("2019::day5::part2", advent_of_code::year_2019::day5::part2);
puzzle_solutions.insert("2019::day6::part1", advent_of_code::year_2019::day6::part1);
+ puzzle_solutions.insert("2019::day6::part2", advent_of_code::year_2019::day6::part2);
let command = match env::args().nth(1) {
Some(command) => command,
diff --git a/src/year_2019/day6.rs b/src/year_2019/day6.rs
index 9aadf73..b2cc42e 100644
--- a/src/year_2019/day6.rs
+++ b/src/year_2019/day6.rs
@@ -1,6 +1,7 @@
//! --- Day 6: Universal Orbit Map ---
use std::collections::HashMap;
+use std::fmt;
/// You've landed at the Universal Orbit Map facility on Mercury. Because navigation in space often involves transferring between orbits, the orbit maps here are useful for finding efficient routes between, for example, you and Santa. You download a map of the local orbits (your puzzle input).
///
@@ -66,8 +67,66 @@ pub fn part1() {
);
}
-#[derive(Debug, Clone, Hash, Eq, PartialEq)]
-struct OrbitMapID(String);
+/// Now, you just need to figure out how many orbital transfers you (YOU) need to take to get to Santa (SAN).
+///
+/// You start at the object YOU are orbiting; your destination is the object SAN is orbiting. An orbital transfer lets you move from any object to an object orbiting or orbited by that object.
+///
+/// For example, suppose you have the following map:
+///
+/// COM)B
+/// B)C
+/// C)D
+/// D)E
+/// E)F
+/// B)G
+/// G)H
+/// D)I
+/// E)J
+/// J)K
+/// K)L
+/// K)YOU
+/// I)SAN
+///
+/// Visually, the above map of orbits looks like this:
+///
+/// YOU
+/// /
+/// G - H J - K - L
+/// / /
+/// COM - B - C - D - E - F
+/// \
+/// I - SAN
+///
+/// In this example, YOU are in orbit around K, and SAN is in orbit around I. To move from K to I, a minimum of 4 orbital transfers are required:
+///
+/// K to J
+/// J to E
+/// E to D
+/// D to I
+///
+/// Afterward, the map of orbits looks like this:
+///
+/// G - H J - K - L
+/// / /
+/// COM - B - C - D - E - F
+/// \
+/// I - SAN
+/// \
+/// YOU
+///
+/// What is the minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting? (Between the objects they are orbiting - not between YOU and SAN.libunwind
+pub fn part2() {
+ let input = crate::common::read_stdin_to_string();
+ let orbit_map = OrbitMap::from(input.as_str());
+
+ let minimum_transfers =
+ orbit_map.minimum_transfers(&OrbitMapID::from("YOU"), &OrbitMapID::from("SAN"));
+
+ println!(
+ "The minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting: {}",
+ minimum_transfers
+ );
+}
#[derive(Debug, Default)]
struct OrbitMap {
@@ -75,29 +134,87 @@ struct OrbitMap {
}
impl OrbitMap {
- fn add_orbit_relation(&mut self, target: OrbitMapID, source: OrbitMapID) {
+ fn get_body(&self, id: &OrbitMapID) -> &OrbitMapBody {
+ self.bodies
+ .get(id)
+ .unwrap_or_else(|| panic!("{} body not found in OrbitMap", id))
+ }
+
+ fn get_body_parent_id(&self, id: &OrbitMapID) -> &OrbitMapID {
+ self.get_body(id)
+ .parent
+ .as_ref()
+ .unwrap_or_else(|| panic!("{} body missing parent", id))
+ }
+
+ fn add_orbit_relation(&mut self, target: &OrbitMapID, source: &OrbitMapID) {
// insert target if it doesn't exist
- self.bodies.entry(target.clone()).or_default();
+ self.bodies
+ .entry(target.clone())
+ .or_insert_with(|| OrbitMapBody::new(target));
// insert source if it doesn't exist
- let source = self.bodies.entry(source).or_default();
+ let source = self
+ .bodies
+ .entry(source.clone())
+ .or_insert_with(|| OrbitMapBody::new(source));
// set source.parent to target
if let Some(parent) = &source.parent {
panic!(
- "Failed adding orbit relation, body already has a parent: {:?}",
- *parent
+ "Failed adding orbit relation, body already has a parent: {}",
+ parent
);
}
- source.parent = Some(target);
+ source.parent = Some(target.clone());
}
- fn orbit_count_checksum(&self) -> u32 {
+ fn orbit_count_checksum(&self) -> usize {
self.bodies
.values()
- .map(|body| body.count_parents(self))
+ .map(|body| body.parents(self).count())
.sum()
}
+
+ fn minimum_transfers(&self, source_id: &OrbitMapID, target_id: &OrbitMapID) -> usize {
+ let source = self.get_body(self.get_body_parent_id(source_id));
+ let target = self.get_body(self.get_body_parent_id(target_id));
+
+ let source_parents = source.parents(&self).collect::<Vec<_>>();
+ let target_parents = target.parents(&self).collect::<Vec<_>>();
+
+ let mut minimum_transfers = 0;
+ let mut common_parent: Option<OrbitMapID> = None;
+
+ for parent in source_parents.iter() {
+ minimum_transfers += 1;
+
+ if target_parents
+ .iter()
+ .any(|target_parent| parent.id == target_parent.id)
+ {
+ common_parent = Some(parent.id.clone());
+ break;
+ }
+ }
+
+ let common_parent_id = common_parent.unwrap_or_else(|| {
+ panic!(
+ "Failed to find common parent of {} and {}",
+ source_id, target_id
+ )
+ });
+
+ for parent in target_parents.iter() {
+ minimum_transfers += 1;
+
+ if parent.id == common_parent_id {
+ break;
+ }
+ }
+
+ minimum_transfers
+ }
}
impl From<&str> for OrbitMap {
@@ -107,10 +224,10 @@ impl From<&str> for OrbitMap {
string.trim().split('\n').for_each(|orbit| {
let mut bodies = orbit.split(')').map(|id| OrbitMapID(id.to_string()));
orbit_map.add_orbit_relation(
- bodies
+ &bodies
.next()
.unwrap_or_else(|| panic!("Failed to parse orbit relation {}", orbit)),
- bodies
+ &bodies
.next()
.unwrap_or_else(|| panic!("Failed to parse orbit relation {}", orbit)),
);
@@ -120,23 +237,63 @@ impl From<&str> for OrbitMap {
}
}
-#[derive(Debug, Default)]
+#[derive(Debug)]
struct OrbitMapBody {
+ id: OrbitMapID,
parent: Option<OrbitMapID>,
}
impl OrbitMapBody {
- fn count_parents(&self, map: &OrbitMap) -> u32 {
- let mut count = 0;
- let mut body = self;
- while let Some(parent) = &body.parent {
- count += 1;
- body = match map.bodies.get(parent) {
- Some(parent) => parent,
- None => panic!("OrbitMapBody with id {:?} not found", parent),
- }
+ fn new(id: &OrbitMapID) -> Self {
+ Self {
+ id: id.clone(),
+ parent: None,
+ }
+ }
+
+ fn parents<'a>(&self, map: &'a OrbitMap) -> OrbitMapBodyParentIterator<'a> {
+ OrbitMapBodyParentIterator {
+ map,
+ next_parent_id: self.parent.clone(),
}
- count
+ }
+}
+
+struct OrbitMapBodyParentIterator<'a> {
+ map: &'a OrbitMap,
+ next_parent_id: Option<OrbitMapID>,
+}
+
+impl<'a> Iterator for OrbitMapBodyParentIterator<'a> {
+ type Item = &'a OrbitMapBody;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ let parent = match self.next_parent_id.as_ref() {
+ Some(next_parent_id) => match self.map.bodies.get(&next_parent_id) {
+ Some(parent) => parent,
+ None => return None,
+ },
+ None => return None,
+ };
+
+ self.next_parent_id = parent.parent.clone();
+
+ Some(parent)
+ }
+}
+
+#[derive(Debug, Clone, Hash, Eq, PartialEq)]
+struct OrbitMapID(String);
+
+impl From<&str> for OrbitMapID {
+ fn from(string: &str) -> Self {
+ Self(string.to_string())
+ }
+}
+
+impl fmt::Display for OrbitMapID {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{}", self)
}
}
@@ -153,4 +310,18 @@ mod tests {
assert_eq!(OrbitMap::from(example.0).orbit_count_checksum(), example.1);
}
+
+ #[test]
+ fn test_orbital_transfers() {
+ let example = (
+ "COM)B\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L\nK)YOU\nI)SAN",
+ 4,
+ );
+
+ assert_eq!(
+ OrbitMap::from(example.0)
+ .minimum_transfers(&OrbitMapID::from("YOU"), &OrbitMapID::from("SAN")),
+ example.1
+ );
+ }
}