66 lines
2.0 KiB
Rust
66 lines
2.0 KiB
Rust
use std::collections::HashMap;
|
|
use std::error::Error;
|
|
use std::fs::File;
|
|
use std::io::{self, BufRead};
|
|
use std::vec::Vec;
|
|
|
|
fn enumerate_chains(curr_jolts: u32, rest: &[u32], cache: &mut HashMap<(u32, u32), u64>) -> u64 {
|
|
if rest.len() == 0 {
|
|
println!("Finished path");
|
|
1
|
|
} else if rest[0] - curr_jolts > 3 {
|
|
println!("Termindated chain at {}", curr_jolts);
|
|
0
|
|
} else {
|
|
let jolts = rest[0];
|
|
|
|
if cache.contains_key(&(curr_jolts, jolts)) {
|
|
println!("Chache hit for {} {}", curr_jolts, jolts);
|
|
return cache[&(curr_jolts, jolts)];
|
|
}
|
|
|
|
println!("Chache miss for {} {}", curr_jolts, jolts);
|
|
|
|
let res = if rest.len() > 3 {
|
|
enumerate_chains(jolts, &rest[1..], cache)
|
|
+ enumerate_chains(jolts, &rest[2..], cache)
|
|
+ enumerate_chains(jolts, &rest[3..], cache)
|
|
} else if rest.len() > 2 {
|
|
enumerate_chains(jolts, &rest[1..], cache) + enumerate_chains(jolts, &rest[2..], cache)
|
|
} else {
|
|
enumerate_chains(jolts, &rest[1..], cache)
|
|
};
|
|
|
|
cache.insert((curr_jolts, jolts), res);
|
|
|
|
res
|
|
}
|
|
}
|
|
|
|
fn main() -> Result<(), Box<dyn Error>> {
|
|
let file = File::open("inputs/day10.txt")?;
|
|
let lines = io::BufReader::new(file).lines().map(|l| l.unwrap());
|
|
|
|
let mut adapters: Vec<u32> = lines.map(|l| l.parse().unwrap()).collect();
|
|
adapters.sort();
|
|
adapters.insert(0, 0);
|
|
adapters.push(adapters.iter().last().unwrap() + 3);
|
|
|
|
let diff_hist: HashMap<u32, u32> =
|
|
adapters
|
|
.windows(2)
|
|
.map(|win| win[1] - win[0])
|
|
.fold(HashMap::new(), |mut map, x| {
|
|
map.entry(x).and_modify(|e| *e = *e + 1).or_insert(1);
|
|
map
|
|
});
|
|
|
|
println!("{:?}", diff_hist);
|
|
println!("Answer: {}", diff_hist[&1] * diff_hist[&3]);
|
|
|
|
let chains = enumerate_chains(0, &adapters, &mut HashMap::new());
|
|
println!("Number of possible chains: {}", chains);
|
|
|
|
Ok(())
|
|
}
|