Advent of Code 2020 day01

Rustで解いた記録をつけていきます。

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

入力の読み込み

標準入力から1行ずつ読み込むのに、 BufReader を使った。 filter_map で雑に Result の中身を取得して、とりあえず一旦 Vec に入れる。

use std::io::{BufRead, BufReader};

fn main() {
    let inputs: Vec<i32> = BufReader::new(std::io::stdin().lock())
        .lines()
        .filter_map(|line| line.ok())
        .filter_map(|s| s.parse().ok())
        .collect();

    ...

}

Solution struct

leetcodeと同じように Solution struct に各partの解を返すメソッドを定義する。

struct Solution {
    inputs: Vec<i32>,
}

impl Solution {
    fn new(inputs: Vec<i32>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        ...
    }
    fn solve_2(&self) -> i32 {
        ...
    }
}

fn main() {

    ...

    let solution = Solution::new(inputs);
    println!("{}", solution.solve_1());
    println!("{}", solution.solve_2());
}

基本的に今後もすべてこの形で解いていくつもり。

part1

入力の中から、足して 2020 になる2つの数の組み合わせを探す。
全組み合わせを探索しても良いけど、 HashSet に入れて 2020 - n が存在していたかどうか確認しながら見ていけば O(N) で解ける。

part2

入力の中から、足して 2020 になる 3つ の数の組み合わせを探す。
part1 を上の方法でやっていれば 2020 - n - m が存在していたかどうか確認しながら n と m の組み合わせを見ていけば O(N^2) で解ける。

しかし実際には入力はせいぜい 200 件程度なので、力技で3重ループで回していくだけでも簡単に解けそうだ…。

code

use std::collections::HashSet;
use std::io::{BufRead, BufReader};

struct Solution {
    inputs: Vec<i32>,
}

impl Solution {
    fn new(inputs: Vec<i32>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        let hs: HashSet<&i32> = self.inputs.iter().collect();
        for &i in self.inputs.iter() {
            if hs.contains(&(2020 - i)) {
                return (2020 - i) * i;
            }
        }
        0
    }
    fn solve_2(&self) -> i32 {
        let hs: HashSet<&i32> = self.inputs.iter().collect();
        for i in 0..self.inputs.len() - 1 {
            for j in i + 1..self.inputs.len() {
                if hs.contains(&(2020 - self.inputs[i] - self.inputs[j])) {
                    return (2020 - self.inputs[i] - self.inputs[j])
                        * self.inputs[i]
                        * self.inputs[j];
                }
            }
        }
        0
    }
}

fn main() {
    let inputs: Vec<i32> = BufReader::new(std::io::stdin().lock())
        .lines()
        .filter_map(|line| line.ok())
        .filter_map(|s| s.parse().ok())
        .collect();
    let solution = Solution::new(inputs);
    println!("{}", solution.solve_1());
    println!("{}", solution.solve_2());
}