day10 solution is not correct and I found a faster one

[patmuk]

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:

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!!

[timvisee]

Happy to see you find it useful.

Thanks nothing this issue, for sharing your approach and for wiring this down!