🎄

Advent of Code 2020 day09

2020/12/17に公開

Rust

adventofcode

tech

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

part1

といった数値列が与えられる。最初の幾つかの数値はpreambleと呼ばれ(上の例では5個、問題では25個がpreambleになる)以降の数値はすべてその数値より前の(preambleの長さ)個の数値の中の異なる2つの数値の和でなければならない。

part1は、そのルールに従っていない数値があるので最初に現れるその数値を探せ、というもの。上の例では 127が、その前にある 95, 102, 117, 150, 182 のどの2つの和でも表せないので答えとなる。

結局preambleの長さだけ直前の数値列を保持しておき、そこから総当たりで組み合わせを試して次の数値になるものがあるかどうかを試すのが良さそう。
毎回 25 * (25 - 1)回の試行になったとしても大した計算量ではない。VecDequeを使って順番で出し入れしていく。数値は32bitにはおさまらないものも入ってくるのでu64にしておく。

use std::collections::VecDeque;

struct Solution {
    inputs: Vec<u64>,
    preamble: usize,
}

impl Solution {
    fn new(inputs: Vec<u64>, preamble: usize) -> Self {
        Self { inputs, preamble }
    }
    fn solve_1(&self) -> u64 {
        let mut vd: VecDeque<&u64> = self.inputs.iter().take(self.preamble).collect();
        let has_pair = |vd: &VecDeque<&u64>, target: u64| -> bool {
            for &n1 in vd.iter() {
                for &n2 in vd.iter() {
                    if *n1 != *n2 && *n1 + *n2 == target {
                        return true;
                    }
                }
            }
            false
        };
        for i in self.preamble..self.inputs.len() {
            if !has_pair(&vd, self.inputs[i]) {
                return self.inputs[i];
            }
            vd.pop_front();
            vd.push_back(&self.inputs[i]);
        }
        0
    }
}

ちょっと考えると直前の値たちはHashSetに持っておいて、Two Sumの要領でtarget - n1になるものがあるかどうかだけ見れば $n^2$ を $n$ に減らせそう(値の重複があるかもしれないのでHashSetではなくHashMapじゃないと正確にならない…？)なのだけど、実際に実装してみるとHashSet使った方が遅かった。VecDequeのときと比較してHashSetの値を追加したり削除したりの方がかえって重い処理になってしまうようだ。

part2

part1で求めたinvalid numberの値に対し、総和がその値になる入力の連続部分列を探し、その部分列の最小値と最大値を足したものを求めよ、というもの。
例でいうと 127を 15+25+47+40 で表せるので、その4つの数値の最小値15と最大値47の和 62が答えになる。

invalid numberの検出はpart1のものをそのまま使う。連続部分列は尺取り法っていうのかな？左端と右端を和が目的の値になるまで動かしていくことで求められる。
あとはその範囲内をもう一度舐めていって最小値と最大値を求めてやれば良い。これもそんなに計算量は気にしなくて良さそう。

    fn solve_2(&self) -> u64 {
        let target = self.solve_1();
        let (mut l, mut r) = (0, 0);
        let mut sum = self.inputs[0];
        while sum != target {
            if sum < target {
                r += 1;
                sum += self.inputs[r];
            } else {
                sum -= self.inputs[l];
                l += 1;
            }
        }
        let (mut min, mut max) = (std::u64::MAX, std::u64::MIN);
        for i in l..=r {
            min = std::cmp::min(min, self.inputs[i]);
            max = std::cmp::max(max, self.inputs[i]);
        }
        min + max
    }

part1

part2

Discussion