first: Many thanks for sharing your solution and your very insightful webpage, explaining the thinking process. This helped me tremendously.
On my way to solve the puzzle I implemented your solution to have an oracle, and came up with different test scenarios. When I finally got it, I discovered that your solution is not correct. In particular, the hard-coded part, where based on the length of the individual chunks you derive the possible combinations.
With this input it would lead to a wrong result:
0, 2, 4, 6, 8
there is only one way to walk through these adapters.
Your solution discovered one chunk of length 4, being hardcoded to 7 combinations.
This would be correct for
0, 1, 2, 3, 4
My solution is a simple O(n) walk through. I need to sort the array as well, but as I don't build pairs, filter for 3-distance and don't add the starting 0, I ultimately save some time.
On my machine (M1 Pro), with the arc-runner crate, the times are:
Day 10 - Part 2 - combinations_recursive_o_n: 6908379398144
generator: 20.416µs,
runner: 27.541µs
Day 10 - Part 2 - hardcoded: 6908379398144
generator: 20.75µs,
runner: 38.125µs
Here is my code (only the solving function):
fn combinations_recursive_o_n(input: &[usize]) -> usize {
let mut adapters = input.to_vec();
match adapters.len() {
0 | 1 => 1,
2 => {
// only if the higher number can be reached from the start (0) there is an alternative path
if adapters[0].abs_diff(adapters[1]) <= 3 {
2
} else {
1
}
}
_ => {
// sorted_adapters.push(0); //add the outlet
adapters.sort_unstable();
let sorted_adapters = adapters;
// println!("adapter sequence: 0-{:?}", sorted_adapters);
// set up first three nodes
let mut n_1 = sorted_adapters[1];
let mut n_2 = sorted_adapters[0];
let mut n_3 = 0_usize;
let mut pathes_to_n_1 = if n_1 > 3 { 1_usize } else { 2_usize };
let mut pathes_to_n_2 = 1_usize;
let mut pathes_to_n_3 = 1_usize;
// find ways to reach the last asapter, going through each adapter
let mut pathes_to_adapter = 0_usize;
sorted_adapters[2..].iter().for_each(|adapter| {
pathes_to_adapter = pathes_to_n_1;
if adapter - n_2 <= 3 {
pathes_to_adapter += pathes_to_n_2;
}
if adapter - n_3 <= 3 {
pathes_to_adapter += pathes_to_n_3;
}
// println!("{} ways to adapter {}", pathes_to_adapter, *adapter);
//update paths
n_3 = n_2;
n_2 = n_1;
n_1 = *adapter;
pathes_to_n_3 = pathes_to_n_2;
pathes_to_n_2 = pathes_to_n_1;
pathes_to_n_1 = pathes_to_adapter;
});
pathes_to_adapter
}
}
}
Hope that after all these years you still enjoy reading my post. Thanks again for inspiring!!
Hi,
first: Many thanks for sharing your solution and your very insightful webpage, explaining the thinking process. This helped me tremendously.
On my way to solve the puzzle I implemented your solution to have an oracle, and came up with different test scenarios. When I finally got it, I discovered that your solution is not correct. In particular, the hard-coded part, where based on the length of the individual chunks you derive the possible combinations.
With this input it would lead to a wrong result: 0, 2, 4, 6, 8 there is only one way to walk through these adapters. Your solution discovered one chunk of length 4, being hardcoded to 7 combinations. This would be correct for 0, 1, 2, 3, 4
My solution is a simple O(n) walk through. I need to sort the array as well, but as I don't build pairs, filter for 3-distance and don't add the starting 0, I ultimately save some time.
On my machine (M1 Pro), with the arc-runner crate, the times are:
Here is my code (only the solving function):
Hope that after all these years you still enjoy reading my post. Thanks again for inspiring!!