🎄
Advent of Code 2020 day11
part1
変則ライフゲーム、的なもの。
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
といった形でLで座席の配置を表す入力がある。
part1は、隣接する8つの位置を見て
- その座席が空席で(
L)、隣接するすべての位置にも埋まっている座席(#)が無ければ、埋まる(→#) - その座席が埋まっていて(
#)、隣接する座席のうち4つ以上が埋まっていたら(#)、空席になる(→L)
というルールに従って同時に更新される。
これが繰り返されるとやがて安定し、どの座席も状態が更新されなくなるという(すごい)。そのときの埋まっている席数を求めよ、という問題。
素朴に、安定するまでsimulationを続けていく、で良い。
Stringだと扱いづらいのでVec<Vec<char>>に展開して持っておき、各座標でそれぞれ隣接する8つの座席の状況を確認。ルールに従って次の状態を決定していく。loopが止まったら改めて#の数をcountして返す。
struct Solution {
layout: Vec<Vec<char>>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self {
layout: inputs.iter().map(|s| s.chars().collect()).collect(),
}
}
fn solve_1(&self) -> usize {
let mut curr = self.layout.clone();
let (r, c) = (self.layout.len(), self.layout[0].len());
loop {
let mut next = curr.clone();
for i in 0..r {
for j in 0..c {
let mut occupied = 0;
for ii in i as i32 - 1..=i as i32 + 1 {
for jj in j as i32 - 1..=j as i32 + 1 {
if (ii == i as i32 && jj == j as i32)
|| ii < 0
|| ii == r as i32
|| jj < 0
|| jj == c as i32
{
continue;
}
if curr[ii as usize][jj as usize] == '#' {
occupied += 1;
}
}
}
next[i][j] = match curr[i][j] {
'L' => {
if occupied == 0 {
'#'
} else {
'L'
}
}
'#' => {
if occupied >= 4 {
'L'
} else {
'#'
}
}
c => c,
}
}
}
if curr == next {
break;
}
curr = next;
}
curr.iter()
.map(|v| v.iter().filter(|&c| *c == '#').count())
.sum()
}
}
part2
実は考えなければならないのは「隣接している8つの位置の座席」ではなく「8方向それぞれで見える最初の座席」だった。床(.)は無視してその方向で最も近い座席の空席状況を見ることになる。ついでに、空席になる条件として「4つ以上が埋まっていたら」だったのが「5つ以上が埋まっていたら」と閾値が変わる。このルールを適用した場合に、更新されなくなったときに埋まっている座席数を求めよ、という問題になる。
part1では無条件で隣接する座標の状況だけを確認していたが、今度は座標によって見るべき座席の座標が変わってくる。毎回求めていては非効率なので 予め「この座席の位置からは、この座標の座席たちをチェックする」というmapを作っておくと良さそう。
それぞれの座席から、8方向それぞれに最初に見える座席を探していく。adjacent == trueのときはその探索を距離1で打ち切ることで、part1の場合の条件になる。
fn target_seats(&self, adjacent: bool) -> HashMap<(usize, usize), Vec<(usize, usize)>> {
let (r, c) = (self.layout.len() as i32, self.layout[0].len() as i32);
let mut seats: HashMap<(usize, usize), Vec<(usize, usize)>> = HashMap::new();
for (i, row) in self.layout.iter().enumerate() {
for (j, &col) in row.iter().enumerate() {
if col == '.' {
continue;
}
for &d in [
(-1, -1),
(-1, 0),
(-1, 1),
(0, -1),
(0, 1),
(1, -1),
(1, 0),
(1, 1),
]
.iter()
{
for k in 1.. {
if adjacent && k > 1 {
break;
}
let ii = i as i32 + k * d.0;
let jj = j as i32 + k * d.1;
if ii < 0 || ii == r || jj < 0 || jj == c {
break;
}
if self.layout[ii as usize][jj as usize] != '.' {
seats
.entry((i, j))
.or_insert_with(Vec::new)
.push((ii as usize, jj as usize));
break;
}
}
}
}
}
seats
}
これで、各座標から見るべき座席の座標が引けるようになるので、part1同様にsimulationしていく。
part1とpart2で空席になる閾値が変わるので引数thresholdを受け取るようにする。
いちいち毎回状態をcopyしなくても、iter().map(...).collect()でnextが作れるので変えてみた。
fn simulate(
&self,
target_seats: &HashMap<(usize, usize), Vec<(usize, usize)>>,
threshold: usize,
) -> usize {
let mut curr = self.layout.clone();
loop {
let next: Vec<Vec<char>> = curr
.iter()
.enumerate()
.map(|(i, row)| {
row.iter()
.enumerate()
.map(|(j, &col)| {
if col != '.' {
let count = if let Some(v) = target_seats.get(&(i, j)) {
v.iter().filter(|&p| curr[p.0][p.1] == '#').count()
} else {
0
};
match col {
'L' if count == 0 => '#',
'#' if count >= threshold => 'L',
c => c,
}
} else {
col
}
})
.collect()
})
.collect();
if next == curr {
return curr
.iter()
.map(|row| row.iter().filter(|&c| *c == '#').count())
.sum();
}
curr = next
}
}
これで、part1, part2ともに共通の処理で引数を変えるだけで答えが求められるようになる。
code
use std::collections::HashMap;
use std::io::{BufRead, BufReader};
struct Solution {
layout: Vec<Vec<char>>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self {
layout: inputs.iter().map(|s| s.chars().collect()).collect(),
}
}
fn solve_1(&self) -> usize {
let target_seats = self.target_seats(true);
self.simulate(&target_seats, 4)
}
fn solve_2(&self) -> usize {
let target_seats = self.target_seats(false);
self.simulate(&target_seats, 5)
}
fn target_seats(&self, adjacent: bool) -> HashMap<(usize, usize), Vec<(usize, usize)>> {
let (r, c) = (self.layout.len() as i32, self.layout[0].len() as i32);
let mut seats: HashMap<(usize, usize), Vec<(usize, usize)>> = HashMap::new();
for (i, row) in self.layout.iter().enumerate() {
for (j, &col) in row.iter().enumerate() {
if col == '.' {
continue;
}
for &d in [
(-1, -1),
(-1, 0),
(-1, 1),
(0, -1),
(0, 1),
(1, -1),
(1, 0),
(1, 1),
]
.iter()
{
for k in 1.. {
if adjacent && k > 1 {
break;
}
let ii = i as i32 + k * d.0;
let jj = j as i32 + k * d.1;
if ii < 0 || ii == r || jj < 0 || jj == c {
break;
}
if self.layout[ii as usize][jj as usize] != '.' {
seats
.entry((i, j))
.or_insert_with(Vec::new)
.push((ii as usize, jj as usize));
break;
}
}
}
}
}
seats
}
fn simulate(
&self,
target_seats: &HashMap<(usize, usize), Vec<(usize, usize)>>,
threshold: usize,
) -> usize {
let mut curr = self.layout.clone();
loop {
let next: Vec<Vec<char>> = curr
.iter()
.enumerate()
.map(|(i, row)| {
row.iter()
.enumerate()
.map(|(j, &col)| {
if col != '.' {
let count = if let Some(v) = target_seats.get(&(i, j)) {
v.iter().filter(|&p| curr[p.0][p.1] == '#').count()
} else {
0
};
match col {
'L' if count == 0 => '#',
'#' if count >= threshold => 'L',
c => c,
}
} else {
col
}
})
.collect()
})
.collect();
if next == curr {
return curr
.iter()
.map(|row| row.iter().filter(|&c| *c == '#').count())
.sum();
}
curr = next
}
}
}
fn main() {
let solution = Solution::new(
BufReader::new(std::io::stdin().lock())
.lines()
.filter_map(|line| line.ok())
.collect(),
);
println!("{}", solution.solve_1());
println!("{}", solution.solve_2());
}
Discussion