🎄
Advent of Code 2020 day20
part1
Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###
Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#..
...
といった入力が与えられる。TileのID、続いてモノクロ画像を表すその内容。
各Tileの画像はそれぞれバラバラに回転や反転されていたりする。が、隣り合うTile同士は同じ境界を持っている、とのこと。
すべてを正しく組み合わせることで元の全体画像を復元できる、らしい。
part1はまず、正しく組み合わせたときに四隅の角の位置に来るTileのIDを掛け合わせた値を求めよ、という問題。
この時点ではまだ完全に回転や反転まで求める必要は無い。
幸い(？)、複数の接続箇所で同一の境界パターンが出現することは無いようなので、すべてのTileの各辺のパターンを列挙して出現頻度を数えてみれば四隅に来るべきTileを特定することが出来る。
とりあえず回転や反転に関する値を定義
#[derive(Clone, Copy)]
enum Orientation {
Rotate000,
Rotate090,
Rotate180,
Rotate270,
Rotate000Flipped,
Rotate090Flipped,
Rotate180Flipped,
Rotate270Flipped,
}
90°ずつ回転したもの、それぞれをx軸y軸で逆にしたもの、で8種類のパターンが存在することになる。
Tileに関してはVec<Vec<bool>>で内容のデータを持つ。top, left, bottom, rightそれぞれの辺の表現を各Orientationで求めるメソッドを用意しておく。
#[derive(Clone)]
struct Tile {
image: Vec<Vec<bool>>,
}
struct Borders {
top: Vec<bool>,
left: Vec<bool>,
bottom: Vec<bool>,
right: Vec<bool>,
}
impl Borders {
fn all(&self) -> [&Vec<bool>; 4] {
[&self.top, &self.left, &self.bottom, &self.right]
}
}
impl Tile {
fn borders(&self, orientation: Orientation) -> Borders {
let size = self.image.len();
match orientation {
Orientation::Rotate000 => Borders {
top: self.image[0].clone(),
left: self.image.iter().map(|row| row[0]).collect(),
bottom: self.image[size - 1].clone(),
right: self.image.iter().map(|row| row[row.len() - 1]).collect(),
},
Orientation::Rotate090 => Borders {
top: self.image.iter().map(|row| row[0]).rev().collect(),
left: self.image[size - 1].clone(),
bottom: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
right: self.image[0].clone(),
},
Orientation::Rotate180 => Borders {
top: self.image[size - 1].clone().into_iter().rev().collect(),
left: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
bottom: self.image[0].clone().into_iter().rev().collect(),
right: self.image.iter().map(|row| row[0]).rev().collect(),
},
Orientation::Rotate270 => Borders {
top: self.image.iter().map(|row| row[row.len() - 1]).collect(),
left: self.image[0].clone().into_iter().rev().collect(),
bottom: self.image.iter().map(|row| row[0]).collect(),
right: self.image[size - 1].clone().into_iter().rev().collect(),
},
Orientation::Rotate000Flipped => Borders {
top: self.image.iter().map(|row| row[0]).collect(),
left: self.image[0].clone(),
bottom: self.image.iter().map(|row| row[row.len() - 1]).collect(),
right: self.image[size - 1].clone(),
},
Orientation::Rotate090Flipped => Borders {
top: self.image[size - 1].clone(),
left: self.image.iter().map(|row| row[0]).rev().collect(),
bottom: self.image[0].clone(),
right: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
},
Orientation::Rotate180Flipped => Borders {
top: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
left: self.image[size - 1].clone().into_iter().rev().collect(),
bottom: self.image.iter().map(|row| row[0]).rev().collect(),
right: self.image[0].clone().into_iter().rev().collect(),
},
Orientation::Rotate270Flipped => Borders {
top: self.image[0].clone().into_iter().rev().collect(),
left: self.image.iter().map(|row| row[row.len() - 1]).collect(),
bottom: self.image[size - 1].clone().into_iter().rev().collect(),
right: self.image.iter().map(|row| row[0]).collect(),
},
}
}
}
ここまで準備できれば、あとはinputをparseして数え上げていく。反転したものも有り得るので、各Tileにつき2パターンでの境界辺を算出する。
struct Solution {
inputs: Vec<String>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
Self { inputs }
}
fn solve_1(&self) -> u64 {
let mut tiles_map = HashMap::new();
let (mut id, mut tile) = (0, Vec::new());
for line in self.inputs.iter() {
if let Some(idstr) = line.strip_prefix("Tile ").map(|s| s.trim_end_matches(':')) {
if let Ok(n) = idstr.parse::<u64>() {
id = n;
}
} else if line.is_empty() {
tiles_map.insert(
id,
Tile {
image: tile.clone(),
},
);
tile.clear();
} else {
tile.push(line.chars().map(|c| c == '#').collect());
}
}
if !tile.is_empty() {
tiles_map.insert(id, Tile { image: tile });
}
let mut border_counts = HashMap::new();
for tile in tiles_map.values() {
for &orientation in [Orientation::Rotate000, Orientation::Rotate180].iter() {
for &border in tile.borders(orientation).all().iter() {
*border_counts.entry(border.clone()).or_insert(0) += 1
}
}
}
...
}
}
こうして得たborder_countsで すべての境界辺の出現数が求められる。Tileを正しく並べたときには隣り合うTile同士は辺を共有するのでその辺の出現数は2、隣が存在しない端のTileの端の辺は出現数が1になる。
各Tileにおける各辺の出現数を見たとき、四隅のTileだけは出現数1の辺が2つ存在する、ということになるので それだけを抽出すれば良い。
tiles_map
.iter()
.filter_map(|(&id, tile)| {
if tile
.borders(Orientation::Rotate000)
.all()
.iter()
.filter_map(|&border| border_counts.get(border))
.filter(|&count| *count == 1)
.count()
== 2
{
Some(id)
} else {
None
}
})
.product()
で解が得られる。
part2
実際にすべてのTileを正しく並べ、境界を取り除いて元の全体画像を復元して、それを正しく回転・反転した場合に
#
# ## ## ###
# # # # # #
で表されるsea monsterのパターンが検出される。その際にsea monsterではない#の数を求めよ、という問題。
ここでは完全に正しい並べ方を求める必要がある。
とはいえ四隅がどのTileになるかは求めることが出来ているし、各辺を共有する隣り合うTile同士のIDは求められるので、ただ順番に並べて行けば良いだけではある。
まずは四隅に該当するものを1つだけ抽出。これが一番左上に来るとするとtopとleftが出現数1、bottomとrightが出現数2になるはずなので、そうなる向きを求める。
let mut borders_map = HashMap::new();
for (&id, tile) in tiles_map.iter() {
for &orientation in [Orientation::Rotate000, Orientation::Rotate180].iter() {
for &border in tile.borders(orientation).all().iter() {
borders_map
.entry(border.clone())
.or_insert_with(Vec::new)
.push(id);
}
}
}
if let Some((&id, tile)) = tiles_map.iter().find(|&(_, tile)| {
tile.borders(Orientation::Rotate000)
.all()
.iter()
.filter_map(|&border| borders_map.get(border))
.filter(|&v| v.len() == 1)
.count()
== 2
}) {
if let Some(&orientation) = Orientation::all().iter().find(|&orientation| {
tile.borders(*orientation)
.all()
.iter()
.filter_map(|&border| borders_map.get(border))
.map(|v| v.len())
.collect::<Vec<usize>>()
== vec![1, 1, 2, 2]
}) {
...
}
}
}
そうして左上隅とその向きが確定したら、あとはそのrightと境界を共有するTileのIDは分かるし、そのTileのleftがそれと同じものになる向きを求めれば右隣が確定する。それを繰り返して最上段が確定できる。
let mut row = vec![(id, tile.clone(), orientation)];
while let Some(last) = row.last() {
let right = last.1.borders(last.2).right;
if let Some(ids) = borders_map.get(&right) {
if ids.len() != 2 {
break;
}
let id = if ids[0] == last.0 { ids[1] } else { ids[0] };
if let Some(tile) = tiles_map.get(&id) {
if let Some(&orientation) = Orientation::all()
.iter()
.find(|&orientation| tile.borders(*orientation).left == right)
{
row.push((id, tile.clone(), orientation));
}
}
}
}
そこから同様にして順番に下に繋げていけば、全体が完成する。
そうしたら境界を取り除いた全体画像を生成し、やはり8パターンの回転・反転を試しながらsea monsterのパターンに一致する数を求めていく。
code
use std::collections::HashMap;
use std::io::{BufRead, BufReader};
#[derive(Clone, Copy)]
enum Orientation {
Rotate000,
Rotate090,
Rotate180,
Rotate270,
Rotate000Flipped,
Rotate090Flipped,
Rotate180Flipped,
Rotate270Flipped,
}
impl Orientation {
fn all() -> [Orientation; 8] {
[
Orientation::Rotate000,
Orientation::Rotate090,
Orientation::Rotate180,
Orientation::Rotate270,
Orientation::Rotate000Flipped,
Orientation::Rotate090Flipped,
Orientation::Rotate180Flipped,
Orientation::Rotate270Flipped,
]
}
}
#[derive(Clone)]
struct Tile {
image: Vec<Vec<bool>>,
}
struct Borders {
top: Vec<bool>,
left: Vec<bool>,
bottom: Vec<bool>,
right: Vec<bool>,
}
impl Borders {
fn all(&self) -> [&Vec<bool>; 4] {
[&self.top, &self.left, &self.bottom, &self.right]
}
}
impl Tile {
fn borders(&self, orientation: Orientation) -> Borders {
let size = self.image.len();
match orientation {
Orientation::Rotate000 => Borders {
top: self.image[0].clone(),
left: self.image.iter().map(|row| row[0]).collect(),
bottom: self.image[size - 1].clone(),
right: self.image.iter().map(|row| row[row.len() - 1]).collect(),
},
Orientation::Rotate090 => Borders {
top: self.image.iter().map(|row| row[0]).rev().collect(),
left: self.image[size - 1].clone(),
bottom: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
right: self.image[0].clone(),
},
Orientation::Rotate180 => Borders {
top: self.image[size - 1].clone().into_iter().rev().collect(),
left: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
bottom: self.image[0].clone().into_iter().rev().collect(),
right: self.image.iter().map(|row| row[0]).rev().collect(),
},
Orientation::Rotate270 => Borders {
top: self.image.iter().map(|row| row[row.len() - 1]).collect(),
left: self.image[0].clone().into_iter().rev().collect(),
bottom: self.image.iter().map(|row| row[0]).collect(),
right: self.image[size - 1].clone().into_iter().rev().collect(),
},
Orientation::Rotate000Flipped => Borders {
top: self.image.iter().map(|row| row[0]).collect(),
left: self.image[0].clone(),
bottom: self.image.iter().map(|row| row[row.len() - 1]).collect(),
right: self.image[size - 1].clone(),
},
Orientation::Rotate090Flipped => Borders {
top: self.image[size - 1].clone(),
left: self.image.iter().map(|row| row[0]).rev().collect(),
bottom: self.image[0].clone(),
right: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
},
Orientation::Rotate180Flipped => Borders {
top: self
.image
.iter()
.map(|row| row[row.len() - 1])
.rev()
.collect(),
left: self.image[size - 1].clone().into_iter().rev().collect(),
bottom: self.image.iter().map(|row| row[0]).rev().collect(),
right: self.image[0].clone().into_iter().rev().collect(),
},
Orientation::Rotate270Flipped => Borders {
top: self.image[0].clone().into_iter().rev().collect(),
left: self.image.iter().map(|row| row[row.len() - 1]).collect(),
bottom: self.image[size - 1].clone().into_iter().rev().collect(),
right: self.image.iter().map(|row| row[0]).collect(),
},
}
}
fn translated(&self, orientation: Orientation) -> Vec<Vec<bool>> {
let size = self.image.len();
(0..size)
.map(|i| {
(0..size)
.map(|j| match orientation {
Orientation::Rotate000 => self.image[i][j],
Orientation::Rotate090 => self.image[size - 1 - j][i],
Orientation::Rotate180 => self.image[size - 1 - i][size - 1 - j],
Orientation::Rotate270 => self.image[j][size - 1 - i],
Orientation::Rotate000Flipped => self.image[j][i],
Orientation::Rotate090Flipped => self.image[size - 1 - i][j],
Orientation::Rotate180Flipped => self.image[size - 1 - j][size - 1 - i],
Orientation::Rotate270Flipped => self.image[i][size - 1 - j],
})
.collect()
})
.collect()
}
}
struct Solution {
tiles: Vec<Vec<(u64, Tile, Orientation)>>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
let mut tiles_map = HashMap::new();
let (mut id, mut tile) = (0, Vec::new());
for line in inputs.iter() {
if let Some(idstr) = line.strip_prefix("Tile ").map(|s| s.trim_end_matches(':')) {
if let Ok(n) = idstr.parse::<u64>() {
id = n;
}
} else if line.is_empty() {
tiles_map.insert(
id,
Tile {
image: tile.clone(),
},
);
tile.clear();
} else {
tile.push(line.chars().map(|c| c == '#').collect());
}
}
if !tile.is_empty() {
tiles_map.insert(id, Tile { image: tile });
}
Self {
tiles: Solution::build_image(&tiles_map),
}
}
fn solve_1(&self) -> u64 {
let (row, col) = (self.tiles.len(), self.tiles[0].len());
[
self.tiles[0][0].0,
self.tiles[0][col - 1].0,
self.tiles[row - 1][0].0,
self.tiles[row - 1][col - 1].0,
]
.iter()
.product()
}
fn solve_2(&self) -> usize {
let actual = Tile {
image: self
.tiles
.iter()
.map(|row| {
let size = row[0].1.image.len();
(1..size - 1)
.map(|i| {
row.iter()
.map(|tile| {
tile.1.translated(tile.2)[i]
.clone()
.into_iter()
.skip(1)
.take(size - 2)
.collect::<Vec<bool>>()
})
.flatten()
.collect()
})
.collect::<Vec<Vec<bool>>>()
})
.flatten()
.collect(),
};
let sea_monster = [
" # ",
"# ## ## ###",
" # # # # # # ",
]
.iter()
.enumerate()
.map(|(i, &row)| {
row.chars()
.enumerate()
.filter_map(|(j, c)| if c == '#' { Some((i, j)) } else { None })
.collect::<Vec<(usize, usize)>>()
})
.flatten()
.collect::<Vec<(usize, usize)>>();
let mut ret = actual
.image
.iter()
.map(|row| row.iter().filter(|&b| *b).count())
.sum();
if let Some(found) = Orientation::all()
.iter()
.map(|&orientation| {
let image = actual.translated(orientation);
let mut count = 0;
for i in 0..image.len() {
for j in 0..image[i].len() {
if sea_monster.iter().all(|&(di, dj)| {
i + di < image.len() && j + dj < image[i].len() && image[i + di][j + dj]
}) {
count += 1;
}
}
}
count
})
.max()
{
ret -= found * sea_monster.len()
}
ret
}
fn build_image(tiles_map: &HashMap<u64, Tile>) -> Vec<Vec<(u64, Tile, Orientation)>> {
let mut borders_map = HashMap::new();
for (&id, tile) in tiles_map.iter() {
for &orientation in [Orientation::Rotate000, Orientation::Rotate180].iter() {
for &border in tile.borders(orientation).all().iter() {
borders_map
.entry(border.clone())
.or_insert_with(Vec::new)
.push(id);
}
}
}
let mut tiles = Vec::new();
if let Some((&id, tile)) = tiles_map.iter().find(|&(_, tile)| {
tile.borders(Orientation::Rotate000)
.all()
.iter()
.filter_map(|&border| borders_map.get(border))
.filter(|&v| v.len() == 1)
.count()
== 2
}) {
if let Some(&orientation) = Orientation::all().iter().find(|&orientation| {
tile.borders(*orientation)
.all()
.iter()
.filter_map(|&border| borders_map.get(border))
.map(|v| v.len())
.collect::<Vec<usize>>()
== vec![1, 1, 2, 2]
}) {
let mut row = vec![(id, tile.clone(), orientation)];
while let Some(last) = row.last() {
let right = last.1.borders(last.2).right;
if let Some(ids) = borders_map.get(&right) {
if ids.len() != 2 {
break;
}
let id = if ids[0] == last.0 { ids[1] } else { ids[0] };
if let Some(tile) = tiles_map.get(&id) {
if let Some(&orientation) = Orientation::all()
.iter()
.find(|&orientation| tile.borders(*orientation).left == right)
{
row.push((id, tile.clone(), orientation));
}
}
}
}
tiles.push(row);
}
}
while let Some(last_row) = tiles.last() {
let mut row = Vec::with_capacity(last_row.len());
for last in last_row.iter() {
let bottom = last.1.borders(last.2).bottom;
if let Some(ids) = borders_map.get(&bottom) {
if ids.len() != 2 {
break;
}
let id = if ids[0] == last.0 { ids[1] } else { ids[0] };
if let Some(tile) = tiles_map.get(&id) {
if let Some(&orientation) = Orientation::all()
.iter()
.find(|&orientation| tile.borders(*orientation).top == bottom)
{
row.push((id, tile.clone(), orientation));
}
}
}
}
if row.is_empty() {
break;
} else {
tiles.push(row);
}
}
tiles
}
}
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