🎄
Advent of Code 2020 day24
part1
sesenwnenenewseeswwswswwnenewsewsw
neeenesenwnwwswnenewnwwsewnenwseswesw
seswneswswsenwwnwse
nwnwneseeswswnenewneswwnewseswneseene
swweswneswnenwsewnwneneseenw
eesenwseswswnenwswnwnwsewwnwsene
sewnenenenesenwsewnenwwwse
wenwwweseeeweswwwnwwe
wsweesenenewnwwnwsenewsenwwsesesenwne
neeswseenwwswnwswswnw
nenwswwsewswnenenewsenwsenwnesesenew
enewnwewneswsewnwswenweswnenwsenwsw
sweneswneswneneenwnewenewwneswswnese
swwesenesewenwneswnwwneseswwne
enesenwswwswneneswsenwnewswseenwsese
wnwnesenesenenwwnenwsewesewsesesew
nenewswnwewswnenesenwnesewesw
eneswnwswnwsenenwnwnwwseeswneewsenese
neswnwewnwnwseenwseesewsenwsweewe
wseweeenwnesenwwwswnew
のような入力が与えられる。
六角形を敷き詰めたタイル上で、各行は起点となる中心から白黒反転すべきタイルの位置を示していて、e, se, sw, w, nw, neの6方向への移動を区切りなく繋げたもの。
初期状態はすべて白になっていて、一度反転すると黒になるがもう一度反転すると白に戻る。
各行すべて順番に反転作業を行った後、黒になっているタイルは何枚か、という問題。上の例だと20行あるが10枚が黒になり5枚が2回反転されて白に戻るため、最終的な黒の枚数は10となる。
結局各行がどの位置に行き着くか、を求めたい。
単純なXY軸方向ではなく斜めのものがあるので難しい…と思ってしまうかもしれないが、XY座標に投影してしまえば簡単で、se, sw, nw, neがそれぞれ(+1, -1), (-1, -1), (-1, +1), (+1, +1)への斜め移動と考えてe, wをそれぞれ(+2, 0), (-2, 0)の2マス移動と考えてしまえば良い。
文字の区切りが無いので例えばeがseのものかeのものか区別しづらいが、それもsかnの直後かどうかだけ見れば問題なく判別できる。
あとは求めた座標をHashSetにでも入れておいて 既に反転済みだったら削除する、といった操作をしてやれば良い。
struct Solution {
inputs: Vec<String>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self { inputs }
}
fn solve_1(&self) -> usize {
let mut flipped = HashSet::new();
for input in self.inputs.iter() {
let s: Vec<char> = input.chars().collect();
let mut p = (0, 0);
let mut i = 0;
while i < s.len() {
match s[i] {
'e' => p.0 += 2,
's' => {
p.1 -= 1;
match s[i + 1] {
'e' => p.0 += 1,
'w' => p.0 -= 1,
_ => unreachable!(),
}
i += 1
}
'w' => p.0 -= 2,
'n' => {
p.1 += 1;
match s[i + 1] {
'e' => p.0 += 1,
'w' => p.0 -= 1,
_ => unreachable!(),
}
i += 1
}
_ => unreachable!(),
}
i += 1;
}
if flipped.contains(&p) {
flipped.remove(&p);
} else {
flipped.insert(p);
}
}
flipped.len()
}
}
part2
part1で反転したものから、ライフゲームが始まる。次の日のタイルは隣接する6つのタイルによって状態が決まる。
- 黒のタイルは、
0個もしくは2個より多くの黒タイルが隣接していた場合は白になる - 白のタイルは、ちょうど
2個の黒タイルが隣接していた場合に黒になる
というルールで毎日同時に状態が遷移する。では100日後には何枚が黒になっているか？という問題。
今までのday11やday17のときと同様に、見るべき隣接タイルの位置は分かっているのだから、各黒タイルとその隣接タイルすべてにおいて、次の日が黒になるべきか否かを判定していけば良い。
struct Solution {
flipped: HashSet<(i32, i32)>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
let mut flipped = HashSet::new();
for input in inputs.iter() {
let mut p = (0, 0);
let mut ns = false;
for c in input.chars() {
match c {
'e' => {
p.0 += if ns { 1 } else { 2 };
ns = false;
}
's' => {
p.1 -= 1;
ns = true;
}
'w' => {
p.0 -= if ns { 1 } else { 2 };
ns = false;
}
'n' => {
p.1 += 1;
ns = true;
}
_ => unreachable!(),
}
}
if flipped.contains(&p) {
flipped.remove(&p);
} else {
flipped.insert(p);
}
}
Self { flipped }
}
fn solve_1(&self) -> usize {
self.flipped.len()
}
fn solve_2(&self) -> usize {
let mut flipped = self.flipped.clone();
let adjacents = [(2, 0), (1, -1), (-1, -1), (-2, 0), (-1, 1), (1, 1)];
for _ in 0..100 {
let mut targets = HashSet::new();
flipped.iter().for_each(|&p| {
targets.insert(p);
adjacents.iter().for_each(|&d| {
targets.insert((p.0 + d.0, p.1 + d.1));
})
});
flipped = targets
.into_iter()
.filter(|&p| {
let count = adjacents
.iter()
.filter(|&d| flipped.contains(&(p.0 + d.0, p.1 + d.1)))
.count();
count == 2 || (count == 1 && flipped.contains(&p))
})
.collect();
}
flipped.len()
}
}
Discussion