115 lines
3.0 KiB
Rust
115 lines
3.0 KiB
Rust
use std::collections::HashMap;
|
|
|
|
pub fn day14() {
|
|
// let input = r#"
|
|
// NNCB
|
|
|
|
// CH -> B
|
|
// HH -> N
|
|
// CB -> H
|
|
// NH -> C
|
|
// HB -> C
|
|
// HC -> B
|
|
// HN -> C
|
|
// NN -> C
|
|
// BH -> H
|
|
// NC -> B
|
|
// NB -> B
|
|
// BN -> B
|
|
// BB -> N
|
|
// BC -> B
|
|
// CC -> N
|
|
// CN -> C
|
|
// "#;
|
|
let input = include_str!("../input/day14.txt");
|
|
let (s, rules) = parse(input);
|
|
|
|
let mut pair_counts = count_pairs(s);
|
|
// dbg!(&pair_counts);
|
|
|
|
for _step in 0..10 {
|
|
pair_counts = step(&pair_counts, &rules);
|
|
}
|
|
println!(
|
|
"{}",
|
|
frequency_diff(&pair_counts, s.chars().last().unwrap())
|
|
);
|
|
|
|
for _step in 10..40 {
|
|
pair_counts = step(&pair_counts, &rules);
|
|
}
|
|
println!(
|
|
"{}",
|
|
frequency_diff(&pair_counts, s.chars().last().unwrap())
|
|
);
|
|
}
|
|
|
|
fn parse(input: &str) -> (&str, HashMap<(char, char), char>) {
|
|
let (s, rules) = input.trim().split_once("\n\n").unwrap();
|
|
|
|
let map = rules
|
|
.lines()
|
|
.map(|l| {
|
|
let (src, insertion) = l.trim().split_once(" -> ").unwrap();
|
|
(
|
|
(src.chars().nth(0).unwrap(), src.chars().nth(1).unwrap()),
|
|
insertion.chars().nth(0).unwrap(),
|
|
)
|
|
})
|
|
.collect::<HashMap<_, _>>();
|
|
|
|
(s, map)
|
|
}
|
|
|
|
fn count_pairs(s: &str) -> HashMap<(char, char), usize> {
|
|
let mut map = HashMap::new();
|
|
for pair in s.chars().zip(s.chars().skip(1)) {
|
|
*map.entry(pair).or_insert(0) += 1;
|
|
}
|
|
map
|
|
}
|
|
|
|
// fn replace(s: &[char], rules: &HashMap<(char, char), char>) -> Vec<char> {
|
|
// let mut res = s.to_vec();
|
|
// for ((i, a), b) in s.iter().enumerate().zip(s.iter().skip(1)).rev() {
|
|
// match rules.get(&(*a, *b)) {
|
|
// Some(insertion) => {
|
|
// res.insert(i + 1, *insertion);
|
|
// }
|
|
// _ => (),
|
|
// }
|
|
// }
|
|
// res
|
|
// }
|
|
|
|
fn step(
|
|
counts: &HashMap<(char, char), usize>,
|
|
rules: &HashMap<(char, char), char>,
|
|
) -> HashMap<(char, char), usize> {
|
|
let mut new_counts = HashMap::new();
|
|
for (pair, n) in counts {
|
|
if let Some(insertion) = rules.get(pair) {
|
|
*new_counts.entry((pair.0, *insertion)).or_insert(0) += n;
|
|
*new_counts.entry((*insertion, pair.1)).or_insert(0) += n;
|
|
} else {
|
|
new_counts.insert(*pair, *n);
|
|
}
|
|
}
|
|
new_counts
|
|
}
|
|
|
|
fn frequency_diff(pair_counts: &HashMap<(char, char), usize>, last_char: char) -> usize {
|
|
let mut frequencies = HashMap::new();
|
|
for ((a, _), n) in pair_counts {
|
|
*frequencies.entry(a).or_insert(0) += n;
|
|
// each char in what would be the actual string appears in two pairs, so only count the
|
|
// first char in each pair to avoid double counting
|
|
// this means which ever char would come last in the actual string is undercounted by 1, so
|
|
// add that back at the end
|
|
}
|
|
*frequencies.entry(&last_char).or_insert(0) += 1;
|
|
let mut v = frequencies.values().collect::<Vec<_>>();
|
|
v.sort();
|
|
*v.last().unwrap() - *v.first().unwrap()
|
|
}
|