🎄

Advent of Code 2020 day06

2 min read

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

part1

abc

a
b
c

ab
ac

a
a
a
a

b

のような、day04と同様な空行で区切られたgroupがあり、各行がその同一group内で各人が"yes"と回答した質問を表す。

part1は、各groupで"yes"と回答された質問の数をかぞえ、合計を出せ、という問題。単純に各group内で出現するuniqueな文字数をカウントして合計すれば良いだけ。
aからzまでというのは分かっているので辞書にはHashSetなどを使う必要もなく、26 sizeのbool配列だけ用意すれば良い。

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> usize {
        let mut ret = 0;
        let mut d = [false; 26];
        for line in self.inputs.iter().chain([String::new()].iter()) {
            if line.is_empty() {
                for b in d.iter_mut() {
                    if *b {
                        ret += 1;
                    }
                    *b = false;
                }
            } else {
                for &b in line.as_bytes() {
                    d[(b - b'a') as usize] = true;
                }
            }
        }
        ret
    }
}

part2

実はかぞえるべきは「groupの誰かが"yes"と回答した」ではなく「groupの全員が"yes"と回答した」質問の数だった、という。
bool演算でいうと OR で見ていたのが AND で見る必要があった、ということになる。
せっかくなので、bool配列で管理していたものを u32の各bitで管理するように変更してみた。各人の回答をu32の値に変換して持ち、part1は | で、part2は & でgroup内全員の値をfoldしていけばあとは最終的な値のbit countを調べるだけで良くなる。 & の場合は初期値が全部立っている必要があるので注意。

struct Solution {
    groups: Vec<Vec<u32>>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        let mut groups: Vec<Vec<u32>> = Vec::new();
        let mut v: Vec<u32> = Vec::new();
        for line in inputs.iter().chain([String::new()].iter()) {
            if line.is_empty() {
                groups.push(v.clone());
                v.clear();
            } else {
                v.push(
                    line.as_bytes()
                        .iter()
                        .map(|&b| 1 << (b - b'a') as usize)
                        .fold(0, |acc, x| acc | x),
                );
            }
        }
        Self { groups }
    }
    fn solve_1(&self) -> usize {
        self.groups
            .iter()
            .map(|group| group.iter().fold(0, |acc, &x| acc | x).count_ones() as usize)
            .sum()
    }
    fn solve_2(&self) -> usize {
        self.groups
            .iter()
            .map(|group| {
                group
                    .iter()
                    .fold((1 << 26) - 1, |acc, &x| acc & x)
                    .count_ones() as usize
            })
            .sum()
    }
}

Discussion

ログインするとコメントできます