diff options
| -rw-r--r-- | input10 | 100 | ||||
| -rw-r--r-- | src/main.rs | 106 |
2 files changed, 205 insertions, 1 deletions
@@ -0,0 +1,100 @@ +30 +73 +84 +136 +132 +117 +65 +161 +49 +68 +139 +46 +21 +127 +109 +153 +163 +160 +18 +22 +131 +146 +62 +113 +172 +150 +171 +98 +93 +130 +170 +59 +1 +110 +2 +55 +37 +44 +148 +102 +40 +28 +35 +43 +56 +169 +33 +5 +141 +83 +15 +105 +142 +36 +116 +11 +45 +82 +10 +17 +159 +140 +12 +108 +29 +72 +121 +52 +91 +166 +88 +97 +118 +99 +124 +149 +16 +9 +143 +104 +57 +79 +123 +58 +96 +24 +162 +23 +92 +69 +147 +156 +25 +133 +34 +8 +85 +76 +103 +122 diff --git a/src/main.rs b/src/main.rs index ff4ac74..7dd441b 100644 --- a/src/main.rs +++ b/src/main.rs @@ -629,8 +629,91 @@ fn day9() { println!("9b: {}", find_xmas_weakness(&input, number)); } +fn count_jolt_differences(input: &[i32]) -> (i32, i32) { + let mut adapters = HashSet::new(); + for i in input { + adapters.insert(*i); + } + let mut diff1 = 0; + let mut diff3 = 0; + let max_jolts = *adapters.iter().max().unwrap(); + + let mut adapter = 0; + loop { + if adapters.contains(&(adapter + 1)) { + diff1 += 1; + adapter += 1; + continue; + } + if adapters.contains(&(adapter + 2)) { + adapter += 2; + continue; + } + if adapters.contains(&(adapter + 3)) { + diff3 += 1; + adapter += 3; + continue; + } + if adapter >= max_jolts { + break; + } + adapter += 1; + } + diff3 += 1; /* difference to device adapter */ + (diff1, diff3) +} + +fn count_jolt_paths(map: &HashMap::<i32, Vec<i32>>, path_cache: &mut HashMap::<i32, i64>, from: i32, goal: i32) -> i64 { + if from == goal { + return 1; + } + if path_cache.contains_key(&from) { + return path_cache[&from]; + } + + let mut count = 0; + for next in &map[&from] { + count += count_jolt_paths(map, path_cache, *next, goal); + } + + path_cache.insert(from, count); + + count +} + +fn build_jolt_map(input: &[i32]) -> HashMap::<i32, Vec<i32>> { + let mut joltmap = HashMap::new(); + let mut input = Vec::from_iter(input.iter().copied()); + input.push(0); + for i in &input { + if input.contains(&(i+1)) { + joltmap.entry(*i).or_insert(Vec::new()).push(*i+1); + } + if input.contains(&(i+2)) { + joltmap.entry(*i).or_insert(Vec::new()).push(*i+2); + } + if input.contains(&(i+3)) { + joltmap.entry(*i).or_insert(Vec::new()).push(*i+3); + } + } + joltmap +} + +fn day10() { + let input = read_numbers("input10"); + + let (diff1, diff3) = count_jolt_differences(&input); + println!("10a: {}", diff1 * diff3); + + let max_jolts = *input.iter().max().unwrap(); + let map = build_jolt_map(&input); + let mut path_cache = HashMap::new(); + let paths = count_jolt_paths(&map, &mut path_cache, 0, max_jolts); + println!("10b: {}", paths); +} + fn main() { - day9(); + day10(); } #[cfg(test)] @@ -818,4 +901,25 @@ mod tests { assert_eq!(find_xmas_weakness(&input, number), 62); } + + #[test] + fn test_day10() { + let input = [16, 10, 15, 5, 1, 11, 7, 19, 6, 12, 4]; + assert_eq!(count_jolt_differences(&input), (7, 5)); + + let max_jolts = *input.iter().max().unwrap(); + let map = build_jolt_map(&input); + let mut path_cache = HashMap::new(); + assert_eq!(count_jolt_paths(&map, &mut path_cache, 0, max_jolts), 8); + + let input = [28, 33, 18, 42, 31, 14, 46, 20, 48, 47, 24, + 23, 49, 45, 19, 38, 39, 11, 1, 32, 25, 35, + 8, 17, 7, 9, 4, 2, 34, 10, 3]; + assert_eq!(count_jolt_differences(&input), (22, 10)); + + let max_jolts = *input.iter().max().unwrap(); + let map = build_jolt_map(&input); + let mut path_cache = HashMap::new(); + assert_eq!(count_jolt_paths(&map, &mut path_cache, 0, max_jolts), 19208); + } } |