🎄

Advent of Code 2020 day05

2020/12/12に公開

Rust

adventofcode

tech

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

part1

FBFBBFFRLR

のように F or B からなる7文字に続いて L or R からなる3文字が続く文字列が与えられる。前半7文字で128rowsのうちどれか、後半3文字で8columnsのうちどれか、をそれぞれ二分探索のような操作で表すことになるのだけど、これは問題をよく読んでちょっと考えると単純に2進数に変換できることに気付く。

F と L を 0、 B と R を 1 としてそれぞれ扱う。FBFBBFF は 0b0101100 なので 44 に、 RLR は 0b101 なので 5 になる。
そして求めるべき seat ID は row * 8 + column なのでこれはそのまま繋げて2進数として扱うだけで良い。 FBFBBFFRLR がそのまま 0b0101100101 で 357 になる。

part1 は seat ID の最大値を求める、とのことなので単純に全入力を変換した上で max を求めれば良いだけ。

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        self.inputs
            .iter()
            .map(|seat| {
                seat.chars()
                    .rev()
                    .enumerate()
                    .map(|(i, c)| if matches!(c, 'B' | 'R') { 1 << i } else { 0 })
                    .sum()
            })
            .max()
            .unwrap()
    }
}

part2

求める seat ID は入力列の中に存在していないIDである、とのこと。ただし実際に有り得る 0 から 1023 までのうち小さい方や大きい方のIDはそもそも存在していない。
全IDをsortして順番に見ていって抜けているIDを探しても良いけど、 $O(n\log n)$ かかってしまう ( $n$ はせいぜい数百なので問題ないのだけど)。

問題にある通り、 0 から 1023 までのうちのどこかの区間でほぼ連続になっているはず、なので、「part1で求めた最大値」と「入力の行数」から全seat IDがどの範囲にあるはずなのかは見当がつく。例えばpart1で求めた最大値が 900 で、入力が全部で 800 行あったとしたら、 100 が最小値で入力はすべて 100 と 900 の間のどれか、になることが分かる。その 801個の候補のうち 1つだけ存在していない数値があるはず。なので入力数+1の領域だけboolを入れる配列を確保して存在確認だけしていけば良い。これなら $O(n)$ で求めることが出来る。

struct Solution {
    seats: Vec<i32>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self {
            seats: inputs
                .iter()
                .map(|seat| {
                    seat.chars()
                        .rev()
                        .enumerate()
                        .map(|(i, c)| if matches!(c, 'B' | 'R') { 1 << i } else { 0 })
                        .sum()
                })
                .collect(),
        }
    }
    fn solve_1(&self) -> i32 {
        *self.seats.iter().max().unwrap()
    }
    fn solve_2(&self) -> i32 {
        let offset = self.solve_1() as usize - self.seats.len();
        let mut v = vec![false; self.seats.len() + 1];
        for &seat in self.seats.iter() {
            v[seat as usize - offset] = true;
        }
        (v.iter().position(|&b| !b).unwrap() + offset) as i32
    }
}

part1

part2

Discussion