109 lines
2.6 KiB
Rust
109 lines
2.6 KiB
Rust
use std::io::BufRead;
|
|
use std::collections::{HashMap, HashSet};
|
|
|
|
type Tree = HashMap<String, HashSet<String>>;
|
|
|
|
fn parse_input_part1<F: BufRead> (input: &mut F) -> Tree {
|
|
let it = input.lines()
|
|
.filter_map(|line| line.ok())
|
|
.map(|line| {
|
|
let v: Vec<_> = line.split(')').collect();
|
|
(v[0].to_string(), v[1].to_string())
|
|
});
|
|
let mut tree = HashMap::new();
|
|
for (parent, child) in it {
|
|
let children = tree.entry(parent).or_insert(HashSet::new());
|
|
children.insert(child);
|
|
}
|
|
tree
|
|
}
|
|
|
|
fn compute_checksum(tree: &Tree, root: &str, level: usize) -> usize {
|
|
if let Some(children) = tree.get(root) {
|
|
level + children.iter()
|
|
.map(|child| compute_checksum(&tree, child, level + 1))
|
|
.sum::<usize>()
|
|
} else {
|
|
level
|
|
}
|
|
}
|
|
|
|
pub fn part1<F: BufRead> (mut input: F) {
|
|
let tree = parse_input_part1(&mut input);
|
|
println!("{:?}", compute_checksum(&tree, "COM", 0));
|
|
}
|
|
|
|
fn parse_input_part2<F: BufRead> (input: F) -> HashMap<String, String>{
|
|
input.lines()
|
|
.filter_map(|line| line.ok())
|
|
.map(|line| {
|
|
let v: Vec<_> = line.split(')').collect();
|
|
(v[1].to_string(), v[0].to_string())
|
|
})
|
|
.collect()
|
|
}
|
|
|
|
fn path_to_node(haystack: &HashMap<String, String>, needle: &str, start: &str) -> HashSet<String> {
|
|
let mut current = start;
|
|
let mut path = HashSet::new();
|
|
while current != needle {
|
|
current = &haystack[current];
|
|
path.insert(current.to_string());
|
|
}
|
|
path
|
|
}
|
|
|
|
fn compute_min_hop_from_you_to_santa(invert_tree: HashMap<String, String>) -> usize {
|
|
let path_from_you = path_to_node(&invert_tree, "COM", "YOU");
|
|
let path_from_santa = path_to_node(&invert_tree, "COM", "SAN");
|
|
path_from_you.symmetric_difference(&path_from_santa).collect::<HashSet<_>>().len()
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (mut input: F) {
|
|
let invert_tree = parse_input_part2(&mut input);
|
|
let res = compute_min_hop_from_you_to_santa(invert_tree);
|
|
println!("{}", res);
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
use std::io;
|
|
|
|
#[test]
|
|
fn test_compute_checksum() {
|
|
let mut input = io::Cursor::new(r#"COM)B
|
|
B)C
|
|
C)D
|
|
D)E
|
|
E)F
|
|
B)G
|
|
G)H
|
|
D)I
|
|
E)J
|
|
J)K
|
|
K)L"#);
|
|
let tree = parse_input_part1(&mut input);
|
|
assert_eq!(42, compute_checksum(&tree, "COM", 0));
|
|
}
|
|
|
|
#[test]
|
|
fn test_compute_min_hop_from_you_to_santa() {
|
|
let mut input = io::Cursor::new(r#"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"#);
|
|
let invert_tree = parse_input_part2(&mut input);
|
|
assert_eq!(4, compute_min_hop_from_you_to_santa(invert_tree));
|
|
}
|
|
}
|