const INPUT: &str = include_str!("../../data/day10");

fn calc(input: &[u32], cache: &mut [Option<u64>], ndx: usize) -> u64 {
	if let Some(n) = cache[ndx] {
		n
	} else {
		let cur = input[ndx];
		let mut n = 0;
		for next in ndx+1..input.len() {
			if input[next] - cur > 3 { break; }
			n += calc(input, cache, next);
		}
		cache[ndx] = Some(n);
		n
	}
}

fn main() {
	let mut input: Vec<u32> = INPUT.lines().map(|s| s.parse().unwrap()).collect();
	input.sort();

	let mut prev = 0;
	let mut count = [0, 0, 0];
	{
		for &j in &input {
			count[(j - prev - 1) as usize] += 1;
			prev = j;
		}
	}
	count[2] += 1; // device always has diff of 3.
	println!("#(joltage diff 1) * #(joltage diff 3): {}", count[2] * count[0]);

	// insert outlet as first element
	input.insert(0, 0);
	let mut cache: Vec<Option<u64>> = input.iter().map(|_| None).collect();
	cache[input.len()-1] = Some(1); // always need last adapter

	println!("Combinations: {}", calc(&input, &mut cache, 0));
}