🎄

Advent of Code 2020 day20

24 min read

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

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つだけ抽出。これが一番左上に来るとするとtopleftが出現数1bottomrightが出現数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

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