🎄

Advent of Code 2020 day17

6 min read

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

part1

.#.
..#
###

のような入力が与えられる。#がactive、.がinactiveを示していて、無限に広がる3次元空間内のある平面の位置だけこの入力の状態で、あとはすべてinactiveで初期化されているとする。
各座標のcubeは、3次元での各軸で±1以内の距離にある26個のneighborsの状態によって次の状態が決まる。

  • 既にactiveなcubeは、neighborsが2個または3個activeな場合だけactiveのまま、そうでない場合はinactiveになる
  • inactiveなcubeは、neighborsが3個activateな場合だけactiveになり、そうでない場合はinactiveのまま

というルールで状態が同時に遷移する、とのこと。
初期状態から6サイクル遷移した後、activeなcubeは幾つあるか?という問題。

6サイクルと決まっているのであれば各次元の+方向,-方向それぞれに高々6までしか拡張していかないはずなので、初期入力が3x3なら15x15x13くらいの空間を定義してしまってその中だけで計算してしまえばsimulationは出来る。

例えばこんな感じ。

struct Solution {
    grid: Vec<Vec<Vec<bool>>>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        let (x, y) = (inputs[0].len(), inputs.len());
        let mut grid = vec![vec![vec![false; x + 12]; y + 12]; 13];
        for (i, row) in inputs.iter().enumerate() {
            for (j, c) in row.chars().enumerate() {
                grid[6][i + 6][j + 6] = c == '#'
            }
        }
        Self { grid }
    }
    fn solve_1(&self) -> usize {
        let mut grid = self.grid.clone();
        let mut d: Vec<(i32, i32, i32)> = Vec::with_capacity(26);
        for i in -1..=1 {
            for j in -1..=1 {
                for k in -1..=1 {
                    if i == 0 && j == 0 && k == 0 {
                        continue;
                    }
                    d.push((i, j, k));
                }
            }
        }
        for _ in 0..6 {
            grid = grid
                .iter()
                .enumerate()
                .map(|(i, plane)| {
                    plane
                        .iter()
                        .enumerate()
                        .map(|(j, row)| {
                            row.iter()
                                .enumerate()
                                .map(|(k, &b)| {
                                    let neighbors = d
                                        .iter()
                                        .filter(|&d| {
                                            let z = i as i32 + d.0;
                                            let y = j as i32 + d.1;
                                            let x = k as i32 + d.2;
                                            z >= 0
                                                && y >= 0
                                                && x >= 0
                                                && z < grid.len() as i32
                                                && y < grid[0].len() as i32
                                                && x < grid[0][0].len() as i32
                                                && grid[z as usize][y as usize][x as usize]
                                        })
                                        .count();
                                    match b {
                                        true if neighbors != 2 && neighbors != 3 => false,
                                        false if neighbors == 3 => true,
                                        b => b,
                                    }
                                })
                                .collect()
                        })
                        .collect()
                })
                .collect();
        }
        grid.iter()
            .map(|plane| {
                plane
                    .iter()
                    .map(|row| row.iter().filter(|&&b| b).count())
                    .sum::<usize>()
            })
            .sum()
    }
}

part2

なんと、無限に広がる空間は3次元ではなく4次元だった(!)。同様に各次元軸で±1以内の距離にあるneighborsが今度は26ではなく80個になる。状態遷移のルールは同様。

となるとVec<Vec<Vec<bool>>>>にしていたのをVec<Vec<Vec<Vec<bool>>>>>にして同様に対応できるが、無駄な空間も増えるし別のやり方をしてみよう。activeなものがある座標だけをHashSetに持たせる。次にactiveになり得るcubeは、現在activeなcubeから見たneighborsたち(+本人)だけなので、それらについてだけactiveなneighborsの数を確認していけば良い。

で、最初から4次元で座標を用意しておき、neighborsの定義だけ3次元と4次元で切り替えれば(3次元のときはw軸を無視すれば良いだけ)、part1でもpart2でもsimulationのロジックは使い回せる。

最後は.len()で答えが求められる。

struct Solution {
    active: HashSet<(i32, i32, i32, i32)>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        let mut active: HashSet<(i32, i32, i32, i32)> = HashSet::new();
        for (i, row) in inputs.iter().enumerate() {
            for (j, col) in row.chars().enumerate() {
                if col == '#' {
                    active.insert((i as i32, j as i32, 0, 0));
                }
            }
        }
        Self { active }
    }
    fn solve_1(&self) -> usize {
        let mut neighbors = Vec::new();
        for x in -1..=1 {
            for y in -1..=1 {
                for z in -1..=1 {
                    if !(x == 0 && y == 0 && z == 0) {
                        neighbors.push((x, y, z, 0));
                    }
                }
            }
        }
        self.simulate(&neighbors)
    }
    fn solve_2(&self) -> usize {
        let mut neighbors = Vec::new();
        for x in -1..=1 {
            for y in -1..=1 {
                for z in -1..=1 {
                    for w in -1..=1 {
                        if !(x == 0 && y == 0 && z == 0 && w == 0) {
                            neighbors.push((x, y, z, w));
                        }
                    }
                }
            }
        }
        self.simulate(&neighbors)
    }
    fn simulate(&self, neighbors: &[(i32, i32, i32, i32)]) -> usize {
        let mut active = self.active.clone();
        for _ in 0..6 {
            let mut targets = HashSet::new();
            for &p in active.iter() {
                targets.insert(p);
                for &d in neighbors.iter() {
                    targets.insert((p.0 + d.0, p.1 + d.1, p.2 + d.2, p.3 + d.3));
                }
            }
            active = targets
                .into_iter()
                .filter(|&p| {
                    let count = neighbors
                        .iter()
                        .filter(|d| active.contains(&(p.0 + d.0, p.1 + d.1, p.2 + d.2, p.3 + d.3)))
                        .count();
                    count == 3 || (count == 2 && active.contains(&p))
                })
                .collect();
        }
        active.len()
    }
}

Discussion

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