Advent of Code 2020 day17
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