Advent of Code 2020 day15
part1
0,3,6
といった入力が与えられ、その続きの数を言っていく。最後の数字に着目し、次の数字は
- その数字が初めて現れた場合は
0 - そうでない場合は、幾つ前に現れたか、の値
になる、というルール。
上の例でいうと 6は初めてなので次は0、0は3つ前に出ているので次は3、3はやはり3つ前に出ているので次はまた3、といった具合に
0, 3, 6, 0, 3, 3, 1, 0, 4, 0, ...
と続いていく。
Van Eck's sequence と呼ばれるものらしい(特に0から始まって0, 0, 1, 0, 2, 0, ...と続くものをそう呼ぶ？)。
こうやって続けていったとき、2020番目の数字は幾つになるか、という問題。
その程度の数なら、愚直にすべて記録していって毎回遡りながら見ていっても求められる。
struct Solution {
inputs: Vec<usize>,
}
impl Solution {
fn new(input: String) -> Self {
Self {
inputs: input.split(',').filter_map(|s| s.parse().ok()).collect(),
}
}
fn solve_1(&self) -> usize {
let mut numbers: Vec<usize> = Vec::with_capacity(2020);
numbers.extend(self.inputs.iter());
for i in numbers.len()..2020 {
numbers.push(
if let Some(j) = numbers
.iter()
.rev()
.skip(1)
.position(|&x| x == numbers[i - 1])
{
j + 1
} else {
0
},
);
}
numbers[2019]
}
}
part2
では、30,000,000番目(！)は幾つになるかという問題。
流石にこれは毎回遡っていては終わらない。
実際すべての数を記録しておく必要はなく、「各数字が最後に現れた位置」だけが分かれば次の数を求められる。
単純に考えるとHashMapでそれを記録できそうだが、それでも3000万回操作を繰り返す中で存在checkしたりinsertしたりの操作だと結構重くなる。
どうせkeyは整数値になると分かっているのだから、Vecで記録してしまう方がindexアクセスできて早い。最初にドカンと30_000_000サイズのVecを確保してしまって、そこに記録していく。usizeの方が書きやすいけどu32にしておいた方がメモリ使用量も少なく 速度も1.5倍ほど早くなるようだった。HashMapを使って同様の実装する場合と比較すると6〜8倍くらいは早い。
fn solve_1(&self) -> u32 {
self.play(2020)
}
fn solve_2(&self) -> u32 {
self.play(30_000_000)
}
fn play(&self, num: u32) -> u32 {
let mut memory: Vec<u32> = vec![0; num as usize];
self.inputs
.iter()
.enumerate()
.for_each(|(i, &input)| memory[input] = i as u32 + 1);
let mut prev = self.inputs[self.inputs.len() - 1] as u32;
for i in self.inputs.len() as u32..num {
let last_index = memory[prev as usize];
memory[prev as usize] = i;
prev = if last_index == 0 { 0 } else { i - last_index };
}
prev
}
これで cargo build --release でoptimizedされたものを実行すると手元のMacBookでは 560msほどだった。
さらにチューニングしようとすると どこかで境界を設けて小さい値の場合はVecなどに記録しつつ 大きい値はHashMapに記録してEntryで操作していく、という方法でもう少し早くなるようだった。これは相当深いところまで知ってないと難しそうだ…
Discussion