Advent of Code 2020 day10

https://adventofcode.com/2020/day/10

part1

16
10
15
5
1
11
7
19
6
12
4

のような入力が与えられる。0から最大値+3まで、差分が3以下になるように繋げていく必要がある、とのこと。

part1はすべてを使って繋げていく場合に差分が1になる数と3になる数を掛け合わせたものを求めよ、というもの。例の場合は 0 -> 1 -> 4 -> 5 -> 6 -> 7 -> 10 -> 11 -> 12 -> 15 -> 16 -> 19 -> 22 と繋げていって 差分1が7個、差分3が5個 現れるので、35が答えになる。

単純に全入力をsortして順番に差分を数えていけば良いだけ。最後は最大値+3になるので差分3になるのは確定していて、0は入力には含まれないので考慮し忘れないよう注意。

struct Solution {
    inputs: Vec<i32>,
}

impl Solution {
    fn new(inputs: Vec<i32>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        let mut inputs = self.inputs.clone();
        inputs.push(0);
        inputs.sort_unstable();
        let (mut diff1, mut diff3) = (0, 0);
        for i in 1..inputs.len() {
            match inputs[i] - inputs[i - 1] {
                1 => diff1 += 1,
                3 => diff3 += 1,
                _ => {}
            }
        }
        diff1 * (diff3 + 1)
    }
}

part2

全部使う必要はないとして、前述のルール通り差分3以下で繋げていって最大値+3まで繋ぐ方法は何通りあるか数えよ、というもの。上の例でいうと

(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 7, 10, 12, 15, 16, 19, (22)

の8通りが存在する、ということになる。

ここはDPを使っていく。part1同様 全入力をsortした数値列inputsを使い、DP[i]を「inputs[i]に到達する繋ぎ方の数」と定義する。
差分は3以下である必要があるので、inputs[i]の直前の数は inputs[i-3], inputs[i-2], inputs[i-1] までしか可能性が無い(全入力がuniqueであるという前提)。それらが差分3以内に収まっているかを調べて、可能なものだけ足し合わせればDP[i]となる。
DPの最後の要素が、求める全組み合わせの数となる。

    fn solve_2(&self) -> u64 {
        let mut dp: Vec<u64> = vec![0; self.inputs.len()];
        dp[0] = 1;
        for i in 1..dp.len() {
            for j in 1..=3 {
                if i >= j && self.inputs[i] - self.inputs[i - j] <= 3 {
                    dp[i] += dp[i - j];
                }
            }
        }
        *dp.last().unwrap()
    }