You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

466 lines
15 KiB

use std::collections::HashMap;
const INPUT: &str = include_str!("../../data/day20");
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash, Debug)]
enum Side {
Top,
Right,
Bottom,
Left,
}
impl Side {
fn opposite(self) -> Self {
match self {
Side::Top => Side::Bottom,
Side::Right => Side::Left,
Side::Bottom => Side::Top,
Side::Left => Side::Right,
}
}
fn transform(self, width: usize, flip: bool, row: usize, col: usize) -> (usize, usize) {
let (row, col) = if flip {
(row, width - col - 1)
} else {
(row, col)
};
let (row, col) = match self {
Side::Top => (row, col),
Side::Right => (col, width - row - 1),
Side::Bottom => (width - row - 1, width - col - 1),
Side::Left => (width - col - 1, row),
};
(row, col)
}
}
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
struct Edge {
len: u32,
mask: u32,
}
impl Edge {
fn new<I>(bits: I) -> Self
where
I: IntoIterator<Item=bool>,
{
let (len, mask) = bits.into_iter().fold((0u32, 0u32), |(len, mask), bit| {
(len+1, (mask << 1) + if bit { 1 } else { 0 })
});
Edge { len, mask }
}
fn norm_dir(self) -> Self {
let rev_mask = self.mask.reverse_bits() >> (32 - self.len);
if self.mask < rev_mask {
Edge { len: self.len, mask: self.mask }
} else {
Edge { len: self.len, mask: rev_mask }
}
}
}
impl std::fmt::Debug for Edge {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
use std::fmt::Write;
f.write_char('"')?;
for ndx in 0..self.len {
let v = 0 != self.mask & (1 << ndx);
f.write_char(if v { '#' } else { '.' })?;
}
f.write_char('"')
}
}
#[derive(Clone, Copy)]
struct Mask {
lines: [[bool; 20]; 3],
}
impl Mask {
const EMPTY: Mask = Mask { lines: [[false; 20]; 3] };
const DEFAULT: Mask = {
let mut lines = Self::EMPTY.lines;
lines[0][18] = true;
lines[1][0] = true;
lines[1][5] = true;
lines[1][6] = true;
lines[1][11] = true;
lines[1][12] = true;
lines[1][17] = true;
lines[1][18] = true;
lines[1][19] = true;
lines[2][1] = true;
lines[2][4] = true;
lines[2][7] = true;
lines[2][10] = true;
lines[2][13] = true;
lines[2][16] = true;
Self { lines }
};
fn _flip_y(self) -> Self {
let [a,b,c] = self.lines;
Self { lines: [c, b, a] }
}
fn _flip_x(self) -> Self {
let [mut a, mut b, mut c] = self.lines;
a.reverse();
b.reverse();
c.reverse();
Self { lines: [a, b, c] }
}
fn all_masks() -> Vec<Mask> {
let def = Self::DEFAULT;
let flip_x = def._flip_x();
vec![
def,
def._flip_y(),
flip_x,
flip_x._flip_y(),
]
}
fn matches_horizontal(&self, tile: &Tile, row: usize, col: usize) -> bool {
if row + 3 > tile.width || col + 20 > tile.width {
return false;
}
for y in 0..3 {
for x in 0..20 {
if self.lines[y][x] && !tile[(row+y, col+x)] {
return false;
}
}
}
true
}
fn mark_horizontal(&self, tile: &mut Tile, row: usize, col: usize) {
for y in 0..3 {
for x in 0..20 {
if self.lines[y][x] {
tile[(row+y, col+x)] = true;
}
}
}
}
fn matches_vertical(&self, tile: &Tile, row: usize, col: usize) -> bool {
if row + 20 > tile.width || col + 3 > tile.width {
return false;
}
for y in 0..3 {
for x in 0..20 {
if self.lines[y][x] && !tile[(row+x, col+y)] {
return false;
}
}
}
true
}
fn mark_vertical(&self, tile: &mut Tile, row: usize, col: usize) {
for y in 0..3 {
for x in 0..20 {
if self.lines[y][x] {
tile[(row+x, col+y)] = true;
}
}
}
}
}
impl std::fmt::Debug for Mask {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
use std::fmt::Write;
f.write_char('\n')?;
for y in 0..3 {
for x in 0..20 {
f.write_char(if self.lines[y][x] { '#' } else { '.' })?;
}
f.write_char('\n')?;
}
Ok(())
}
}
#[derive(Clone, PartialEq, Eq, Hash)]
struct Tile {
width: usize,
data: Vec<bool>,
}
impl Tile {
fn parse(block: &str) -> (u32, Self) {
let head_split = block.find(":\n").unwrap();
let id = block[..head_split].strip_prefix("Tile ").unwrap().parse::<u32>().unwrap();
let block = &block[head_split+2..];
let first_line = block.lines().next().unwrap();
let width = first_line.len();
let data = block.lines()
.map(|l| {
assert_eq!(l.len(), width);
l.chars().map(|c| c == '#')
})
.flatten().collect::<Vec<_>>();
assert_eq!(data.len(), width * width);
(id, Self { width, data })
}
fn edge(&self, side: Side) -> Edge {
match side {
Side::Top => Edge::new(self.data[..self.width].iter().copied()),
Side::Bottom => Edge::new(self.data[self.width*(self.width-1)..].iter().copied()),
Side::Left => Edge::new((0..self.width).map(|n| self.data[n*self.width])),
Side::Right => Edge::new((0..self.width).map(|n| self.data[(n+1)*self.width-1])),
}
}
// rotate/flip given previous sides to top and left
fn rotate(&self, top: Side, left: Side) -> Self {
let flip = match (top, left) {
(Side::Top, Side::Left) => false,
(Side::Top, Side::Right) => true,
(Side::Right, Side::Top) => false,
(Side::Right, Side::Bottom) => true,
(Side::Bottom, Side::Right) => false,
(Side::Bottom, Side::Left) => true,
(Side::Left, Side::Bottom) => false,
(Side::Left, Side::Top) => true,
_ => panic!("invalid rotation: {:?} -> Top and {:?} -> Left", top, left),
};
let data = (0..self.width).map(|row| {
(0..self.width).map(move |col| {
let (row, col) = top.transform(self.width, flip, row, col);
self[(row, col)]
})
}).flatten().collect();
Self { width: self.width, data }
}
fn find_monster(&self) -> Tile {
let mut marked = Self { width: self.width, data: self.data.iter().map(|_| false).collect() };
let patterns = Mask::all_masks();
for row in 0..self.width {
for col in 0..self.width {
for pattern in &patterns {
if pattern.matches_horizontal(self, row, col) {
pattern.mark_horizontal(&mut marked, row, col);
}
if pattern.matches_vertical(self, row, col) {
pattern.mark_vertical(&mut marked, row, col);
}
}
}
}
marked
}
}
impl std::ops::Index<(usize, usize)> for Tile {
type Output = bool;
fn index(&self, (row, col): (usize, usize)) -> &Self::Output {
assert!(col <= self.width);
&self.data[row * self.width + col]
}
}
impl std::ops::IndexMut<(usize, usize)> for Tile {
fn index_mut(&mut self, (row, col): (usize, usize)) -> &mut Self::Output {
assert!(col <= self.width);
&mut self.data[row * self.width + col]
}
}
impl std::fmt::Debug for Tile {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
use std::fmt::Write;
f.write_char('\n')?;
for y in 0..self.width {
for x in 0..self.width {
f.write_char(if self[(y, x)] { '#' } else { '.' })?;
}
f.write_char('\n')?;
}
Ok(())
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
struct TileDetailed {
tile: Tile,
edge_to_side: HashMap<Edge, Side>,
side_to_edge: HashMap<Side, Edge>,
}
impl TileDetailed {
fn edge(&self, side: Side) -> Edge {
*self.side_to_edge.get(&side).unwrap()
}
fn parse(block: &str) -> (u32, Self) {
let (id, tile) = Tile::parse(block);
let edges = vec![
(Side::Top, tile.edge(Side::Top).norm_dir()),
(Side::Right, tile.edge(Side::Right).norm_dir()),
(Side::Bottom, tile.edge(Side::Bottom).norm_dir()),
(Side::Left, tile.edge(Side::Left).norm_dir()),
];
let edge_to_side = edges.iter().map(|&(side, edge)| (edge, side)).collect();
let side_to_edge = edges.into_iter().collect();
(id, Self { tile, edge_to_side, side_to_edge })
}
}
#[derive(Clone, Copy, Debug)]
struct TilePlacement {
tile: u32,
top_side: Side,
bottom_edge: Edge,
left_side: Side,
right_edge: Edge,
}
fn main() {
let tiles: HashMap<u32, TileDetailed> = INPUT.trim().split("\n\n").map(TileDetailed::parse).collect();
let mut edges: HashMap<Edge, Vec<(u32, Side)>> = HashMap::new();
for (&id, tile) in &tiles {
for (&side, &edge) in &tile.side_to_edge {
edges.entry(edge).or_default().push((id, side));
}
}
let single_edges = edges.iter().filter_map(|(_edge, id_sides)| {
if id_sides.len() == 1 {
Some(id_sides[0])
} else {
assert!(id_sides.len() == 2);
None
}
}).collect::<Vec<_>>();
let mut single_edges_per_tile = HashMap::<u32, Vec<Side>>::new();
for &(tile_id, side) in &single_edges {
single_edges_per_tile.entry(tile_id).or_default().push(side);
}
let corners = single_edges_per_tile.iter().filter_map(|(&tile_id, sides)| {
if sides.len() == 2 {
Some(tile_id)
} else {
None
}
}).collect::<Vec<_>>();
let corners_prod = corners.iter().map(|&tile_id| tile_id as u64).product::<u64>();
println!("Product of corner tile ids: {}", corners_prod);
let mut grid_tiles: [[Option<TilePlacement>; 12]; 12] = [[None; 12]; 12];
for row in 0..12 {
if row == 0 {
// orient top left tile
let tile: u32 = corners.iter().copied().min().unwrap();
let top_side: Side = *single_edges_per_tile.get(&tile).unwrap().iter().min().unwrap();
let bottom_edge = tiles.get(&tile).unwrap().edge(top_side.opposite());
let left_side: Side = *single_edges_per_tile.get(&tile).unwrap().iter().max().unwrap();
let right_edge = tiles.get(&tile).unwrap().edge(left_side.opposite());
grid_tiles[0][0] = Some(TilePlacement { tile, top_side, bottom_edge, left_side, right_edge });
} else {
// left column; look at tile above
let tile_top = grid_tiles[row-1][0].unwrap().tile;
let top_edge = grid_tiles[row-1][0].unwrap().bottom_edge;
let (tile, top_side) = edges.get(&top_edge).unwrap().iter().filter_map(|&(tile_id, side)| {
if tile_id != tile_top {
Some((tile_id, side))
} else {
None
}
}).next().unwrap();
let bottom_side = top_side.opposite();
let left_side = *single_edges_per_tile.get(&tile).unwrap().iter().filter(|&&side| side != bottom_side).next().unwrap();
assert_ne!(top_side, left_side);
assert_ne!(top_side, left_side.opposite());
let bottom_edge = tiles.get(&tile).unwrap().edge(top_side.opposite());
let right_edge = tiles.get(&tile).unwrap().edge(left_side.opposite());
grid_tiles[row][0] = Some(TilePlacement { tile, top_side, bottom_edge, left_side, right_edge });
}
// complete row
for col in 1..12 {
// look at tile to the left
let tile_left = grid_tiles[row][col-1].unwrap().tile;
let left_edge = grid_tiles[row][col-1].unwrap().right_edge;
let (tile, left_side) = edges.get(&left_edge).unwrap().iter().filter_map(|&(tile_id, side)| {
if tile_id != tile_left {
Some((tile_id, side))
} else {
None
}
}).next().unwrap();
let right_edge = tiles.get(&tile).unwrap().edge(left_side.opposite());
let top_side;
if row == 0 {
if col == 11 {
// top right corner
let right_side = left_side.opposite();
top_side = *single_edges_per_tile.get(&tile).unwrap().iter().filter(|&&side| side != right_side).next().unwrap();
} else {
top_side = *single_edges_per_tile.get(&tile).unwrap().iter().next().unwrap();
}
} else {
let tile_top = grid_tiles[row-1][col].unwrap().tile;
let top_edge = grid_tiles[row-1][col].unwrap().bottom_edge;
top_side = edges.get(&top_edge).unwrap().iter().filter_map(|&(tile_id, side)| {
if tile_id != tile_top {
assert_eq!(tile, tile_id);
Some(side)
} else {
None
}
}).next().unwrap();
}
assert_ne!(left_side, top_side);
assert_ne!(left_side, top_side.opposite());
let bottom_edge = tiles.get(&tile).unwrap().edge(top_side.opposite());
grid_tiles[row][col] = Some(TilePlacement { tile, top_side, bottom_edge, left_side, right_edge });
}
}
let mut rotated_tiles = Vec::new();
let mut picture = Tile { width: 12 * 8, data: Vec::new() };
picture.data.resize(picture.width * picture.width, false);
for row in 0..12 {
rotated_tiles.push(Vec::new());
for col in 0..12 {
let tp = grid_tiles[row][col].unwrap();
let tile = tiles.get(&tp.tile).unwrap().tile.rotate(tp.top_side, tp.left_side);
rotated_tiles[row].push(tile.clone());
assert_eq!(rotated_tiles[row][col], tile);
// check edges
if row > 0 {
assert_eq!(rotated_tiles[row-1][col].edge(Side::Bottom), tile.edge(Side::Top));
}
if col > 0 {
assert_eq!(rotated_tiles[row][col-1].edge(Side::Right), tile.edge(Side::Left));
}
// assemble full picture
for y in 0..tile.width-2 {
for x in 0..tile.width-2 {
picture[(row*8+y, col*8+x)] = tile[(y+1, x+1)];
}
}
}
}
println!("{:?}", picture);
let monsters = picture.find_monster();
println!("{:?}", monsters);
let sea_count = picture.data.iter().filter(|&&v| v).count();
let monster_count = monsters.data.iter().filter(|&&v| v).count();
println!("Roughness: {}", sea_count - monster_count);
}