Discussion on: Advent of Code 2020 Solution Megathread - Day 10: Adapter Array

View post

Took me a while to figure out. I was initially going down some path finding algorithm. But after looking at it a while It started to look like some dynamic programming/combinatorics.

Took me a while to get the actual equation down but finally did it.
input is with 0 and max + 3 already added.

#[aoc(day10, part1)]
fn the_path(input: &Vec<usize>) -> usize {
    let mut one_count = 0;
    let mut three_count = 0;
    for (i, v) in input[..input.len() - 1].iter().enumerate() {
        let diff = ((*v) as i32 - (input[i + 1]) as i32).abs() as usize;
        if diff == 1 {
            one_count += 1;
        } else if diff == 3 {
            three_count += 1;
        }
    }
    one_count * three_count
}

#[aoc(day10, part2)]
fn all_combinations(input: &Vec<usize>) -> usize {
    let mut the_ways = HashMap::new();
    // Only one way to get to 0 or 1
    the_ways.insert(0, 1);
    the_ways.insert(1, 1);
    for &v in &input[2..] {
        let mut val = the_ways.get(&(v - 1)).unwrap_or(&0) + the_ways.get(&(v - 2)).unwrap_or(&0);
        if v > 2 {
            val += the_ways.get(&(v - 3)).unwrap_or(&0);
        }
        the_ways.insert(v, val);
    }
    *the_ways.get(input.last().unwrap()).unwrap()
}