day-06.rs (2737B)
1 use std::collections::HashMap;
2 use std::collections::VecDeque;
3 use std::fs::File;
4 use std::io::prelude::*;
5 use std::io::BufReader;
6
7 fn main() {
8 let input = BufReader::new(File::open("input.txt").unwrap())
9 .lines()
10 .map(|line| {
11 line.unwrap()
12 .trim()
13 .split(")")
14 .map(|x| x.to_string())
15 .collect::<Vec<String>>()
16 })
17 .collect::<Vec<Vec<String>>>();
18
19 println!("Rust:");
20 println!("Part 1: {}", part_1(&input));
21 println!("Part 2: {}", part_2(&input));
22 }
23
24 fn part_1(input: &Vec<Vec<String>>) -> usize {
25 // Map from orbiting planets to center planet.
26 let orbit_map = input
27 .iter()
28 .map(|x| (x[1].clone(), x[0].clone()))
29 .collect::<HashMap<String, String>>();
30
31 let mut orbit_count = HashMap::<String, usize>::new();
32 for (planet, mut center) in &orbit_map {
33 let mut path = VecDeque::<String>::new();
34 let mut root_count = 0;
35
36 path.push_front(planet.to_string());
37
38 loop {
39 path.push_front(center.to_string());
40 if let Some(ob_count) = orbit_count.get(center) {
41 root_count = *ob_count;
42 break;
43 } else {
44 if let Some(next) = orbit_map.get(center) {
45 center = next;
46 } else {
47 break;
48 }
49 }
50 }
51
52 while let Some(root) = path.pop_front() {
53 *orbit_count.entry(root).or_default() = root_count;
54 root_count += 1;
55 }
56 }
57
58 orbit_count.values().sum::<usize>()
59 }
60
61 fn part_2(input: &Vec<Vec<String>>) -> usize {
62 // Map from orbiting planets to center planet.
63 let orbit_map = input
64 .iter()
65 .map(|x| (x[1].clone(), x[0].clone()))
66 .collect::<HashMap<String, String>>();
67
68 // Build SAN path.
69 let mut santa_path = HashMap::<String, usize>::new();
70 {
71 let mut center = orbit_map.get("SAN").unwrap();
72 let mut orbit_count = 0;
73 loop {
74 santa_path.insert(center.clone(), orbit_count);
75 if let Some(next) = orbit_map.get(center) {
76 center = next;
77 orbit_count += 1;
78 } else {
79 break;
80 }
81 }
82 }
83 // Trace back YOU path until we get a hit.
84 {
85 let mut center = orbit_map.get("YOU").unwrap();
86 let mut orbit_count = 0;
87 loop {
88 if let Some(san_count) = santa_path.get(center) {
89 return orbit_count + san_count;
90 } else {
91 center = orbit_map.get(center).unwrap();
92 orbit_count += 1;
93 }
94 }
95 }
96 }