567 lines
18 KiB
Rust
567 lines
18 KiB
Rust
use std::collections::{HashMap, HashSet};
|
|
use std::str::FromStr;
|
|
use std::io::BufRead;
|
|
use std::rc::Rc;
|
|
use std::ops::{Deref, DerefMut};
|
|
|
|
use itertools::Itertools;
|
|
|
|
|
|
#[derive(Debug, Eq, PartialEq, Hash, Clone)]
|
|
struct OrientedTile {
|
|
id: u32,
|
|
north: u16,
|
|
east: u16,
|
|
south: u16,
|
|
west: u16,
|
|
raw_data: Rc<Grid<char>>,
|
|
rotation: u8,
|
|
flipped: bool,
|
|
}
|
|
|
|
#[derive(Debug, Clone)]
|
|
struct Constraint {
|
|
north: Option<u16>,
|
|
east: Option<u16>,
|
|
south: Option<u16>,
|
|
west: Option<u16>,
|
|
}
|
|
|
|
#[derive(Debug, Clone, Eq, PartialEq, Hash)]
|
|
enum Edge {
|
|
North,
|
|
South,
|
|
East,
|
|
West,
|
|
}
|
|
|
|
#[derive(Debug, Clone)]
|
|
struct Puzzle {
|
|
edge_cache: Rc<HashMap<(Edge, u16), Vec<OrientedTile>>>,
|
|
constraint_map: HashMap<(i32, i32), Constraint>,
|
|
placed_tiles: HashMap<(i32, i32), OrientedTile>,
|
|
free_tiles: HashSet<u32>,
|
|
}
|
|
|
|
impl Edge {
|
|
const ALL: &'static [Edge] = &[
|
|
Edge::North,
|
|
Edge::East,
|
|
Edge::South,
|
|
Edge::West,
|
|
];
|
|
|
|
fn to_coord(&self) -> (i32, i32) {
|
|
match self {
|
|
Edge::North => (0, 1),
|
|
Edge::East => (1, 0),
|
|
Edge::South => (0, -1),
|
|
Edge::West => (-1, 0),
|
|
}
|
|
}
|
|
|
|
fn oposite(&self) -> Edge {
|
|
match self {
|
|
Edge::North => Edge::South,
|
|
Edge::East => Edge::West,
|
|
Edge::South => Edge::North,
|
|
Edge::West => Edge::East,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Constraint {
|
|
fn new() -> Constraint {
|
|
Constraint {
|
|
north: None,
|
|
east: None,
|
|
south: None,
|
|
west: None,
|
|
}
|
|
}
|
|
|
|
fn get_all(&self) -> Vec<(Edge, u16)> {
|
|
let mut constraint = vec![
|
|
self.north.map(|v| (Edge::North, v)),
|
|
self.east.map(|v| (Edge::East, v)),
|
|
self.south.map(|v| (Edge::South, v)),
|
|
self.west.map(|v| (Edge::West, v)),
|
|
];
|
|
constraint.drain(..).filter_map(|c| c).collect()
|
|
}
|
|
|
|
fn set(&mut self, edge: &Edge, value: u16) {
|
|
match edge {
|
|
Edge::North => self.north = Some(value),
|
|
Edge::East => self.east = Some(value),
|
|
Edge::South => self.south = Some(value),
|
|
Edge::West => self.west = Some(value),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl OrientedTile {
|
|
fn compositions(&self) -> Vec<OrientedTile> {
|
|
let mut tiles = Vec::new();
|
|
let mut new_tile = self.clone();
|
|
for _ in 0..4 {
|
|
new_tile = new_tile.rotate();
|
|
let flipped_tile = new_tile.flip_horizontally();
|
|
tiles.push(new_tile.clone());
|
|
tiles.push(flipped_tile);
|
|
}
|
|
tiles
|
|
}
|
|
|
|
fn rotate(&self) -> OrientedTile {
|
|
OrientedTile {
|
|
id: self.id,
|
|
north: OrientedTile::flip_edge(self.west),
|
|
east: self.north,
|
|
south: OrientedTile::flip_edge(self.east),
|
|
west: self.south,
|
|
raw_data: self.raw_data.clone(),
|
|
rotation: self.rotation + 1,
|
|
flipped: self.flipped,
|
|
}
|
|
}
|
|
|
|
fn flip_horizontally(&self) -> OrientedTile {
|
|
OrientedTile {
|
|
id: self.id,
|
|
north: OrientedTile::flip_edge(self.north),
|
|
east: self.west,
|
|
south: OrientedTile::flip_edge(self.south),
|
|
west: self.east,
|
|
raw_data: self.raw_data.clone(),
|
|
rotation: self.rotation,
|
|
flipped: !self.flipped,
|
|
}
|
|
}
|
|
|
|
fn flip_edge(edge: u16) -> u16 {
|
|
u16::from_str_radix(&format!("{:010b}", edge).chars().rev().collect::<String>(), 2).unwrap()
|
|
}
|
|
|
|
fn edge(&self, name: &Edge) -> u16 {
|
|
match name {
|
|
Edge::North => self.north,
|
|
Edge::East => self.east,
|
|
Edge::South => self.south,
|
|
Edge::West => self.west,
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
impl FromStr for OrientedTile {
|
|
type Err = ();
|
|
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let mut it = s.lines();
|
|
let tile_id: u32 = it.next().unwrap().chars().filter(|c| c.is_ascii_digit()).collect::<String>().parse().unwrap();
|
|
let raw_data = it.map(|l| l.replace('.', "0").replace('#', "1").chars().collect::<Vec<_>>())
|
|
.collect::<Vec<_>>();
|
|
|
|
let len = raw_data.len() - 1;
|
|
let mut north = String::new();
|
|
let mut east = String::new();
|
|
let mut south = String::new();
|
|
let mut west = String::new();
|
|
|
|
for i in 0..=len {
|
|
north.push(raw_data[0][i]);
|
|
east.push(raw_data[i][len]);
|
|
south.push(raw_data[len][i]);
|
|
west.push(raw_data[i][0]);
|
|
}
|
|
|
|
Ok(OrientedTile {
|
|
id: tile_id,
|
|
north: u16::from_str_radix(&north, 2).unwrap(),
|
|
east: u16::from_str_radix(&east, 2).unwrap(),
|
|
south: u16::from_str_radix(&south, 2).unwrap(),
|
|
west: u16::from_str_radix(&west, 2).unwrap(),
|
|
raw_data: Rc::new(Grid(raw_data)),
|
|
rotation: 0,
|
|
flipped: false,
|
|
})
|
|
}
|
|
}
|
|
|
|
impl Puzzle {
|
|
fn new(mut tiles: Vec<OrientedTile>) -> Puzzle {
|
|
let mut edge_cache = HashMap::new();
|
|
let mut free_tiles = HashSet::new();
|
|
for tile in tiles.drain(..).flat_map(|t| t.compositions()) {
|
|
free_tiles.insert(tile.id);
|
|
for edge in Edge::ALL {
|
|
let edge_value = tile.edge(edge);
|
|
let edge_tiles = edge_cache.entry((edge.clone(), edge_value)).or_insert(Vec::new());
|
|
edge_tiles.push(tile.clone());
|
|
}
|
|
}
|
|
|
|
Puzzle {
|
|
edge_cache: Rc::new(edge_cache),
|
|
constraint_map: HashMap::new(),
|
|
placed_tiles: HashMap::new(),
|
|
free_tiles,
|
|
}
|
|
}
|
|
fn get_tiles_with_constraint(&self, constraint: &Constraint) -> HashSet<&OrientedTile> {
|
|
let by_edges = constraint.get_all();
|
|
by_edges.iter()
|
|
.filter_map(move |c| self.edge_cache.get(c))
|
|
.flat_map(|t| t.iter())
|
|
.filter(|tile| {
|
|
let res = self.free_tiles.contains(&tile.id) && by_edges.iter().all(|(edge, value)| tile.edge(edge) == *value);
|
|
res
|
|
|
|
}).collect()
|
|
}
|
|
|
|
fn place_tile(&mut self, tile: OrientedTile, (x, y): (i32, i32)) {
|
|
for edge in Edge::ALL {
|
|
let (i, j) = edge.to_coord();
|
|
let coord = (x + i, y + j);
|
|
if !self.placed_tiles.contains_key(&coord) {
|
|
let constraint = self.constraint_map.entry(coord).or_insert(Constraint::new());
|
|
constraint.set(&edge.oposite(), tile.edge(&edge));
|
|
}
|
|
}
|
|
self.constraint_map.remove(&(x, y));
|
|
self.free_tiles.remove(&tile.id);
|
|
self.placed_tiles.insert((x, y), tile);
|
|
}
|
|
|
|
fn solve(mut puzzle: Puzzle) -> Option<Puzzle> {
|
|
{
|
|
let first_tile = puzzle.edge_cache.values().next().unwrap()[0].clone();
|
|
puzzle.place_tile(first_tile, (0, 0));
|
|
}
|
|
let mut stack = vec![puzzle];
|
|
loop {
|
|
if let Some(puzzle) = stack.pop() {
|
|
if puzzle.free_tiles.len() == 0 {
|
|
return Some(puzzle);
|
|
}
|
|
let candidates = puzzle.constraint_map.iter()
|
|
.map(|(coord, constraint)| (coord, puzzle.get_tiles_with_constraint(constraint)))
|
|
.filter(|(_c, t)| t.len() > 0)
|
|
.collect::<Vec<_>>();
|
|
|
|
let coords = candidates.iter().map(|(c, _)| **c).collect::<Vec<_>>();
|
|
let configurations = candidates.iter().map(|(_, t)| t);
|
|
for mut configuration in configurations.multi_cartesian_product() {
|
|
let mut new_puzzle = puzzle.clone();
|
|
for (i, tile) in configuration.drain(..).enumerate() {
|
|
new_puzzle.place_tile((*tile).clone(), coords[i])
|
|
}
|
|
stack.push(new_puzzle)
|
|
}
|
|
} else {
|
|
// No solution can be found for this puzzle
|
|
return None;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(Eq, Hash, Debug, PartialEq, Clone)]
|
|
struct Grid<T>(Vec<Vec<T>>);
|
|
|
|
impl<T> Deref for Grid<T> {
|
|
type Target = Vec<Vec<T>>;
|
|
|
|
fn deref(&self) -> &Self::Target {
|
|
&self.0
|
|
}
|
|
}
|
|
|
|
impl<T> DerefMut for Grid<T> {
|
|
fn deref_mut(&mut self) -> &mut Self::Target {
|
|
&mut self.0
|
|
}
|
|
}
|
|
|
|
impl<T: Default + Clone + Copy> Grid<T> {
|
|
fn new(len: usize) -> Self {
|
|
Grid(vec![vec![T::default(); len]; len])
|
|
}
|
|
|
|
fn rotate(&self) -> Grid<T> {
|
|
let len = self.len();
|
|
let mut new_grid = Grid::new(len);
|
|
for x in 0..len {
|
|
for y in 0..len {
|
|
new_grid[x][len - y - 1] = self[y][x];
|
|
}
|
|
}
|
|
new_grid
|
|
}
|
|
|
|
fn flip_horizontally(&self) -> Grid<T> {
|
|
let len = self.len();
|
|
let mut new_grid = Grid::new(len);
|
|
for x in 0..len {
|
|
for y in 0..len {
|
|
new_grid[y][x] = self[y][len - x - 1];
|
|
}
|
|
}
|
|
new_grid
|
|
}
|
|
}
|
|
|
|
#[derive(Clone)]
|
|
struct SolvedPuzzle {
|
|
grid: Grid<u32>,
|
|
}
|
|
|
|
impl SolvedPuzzle {
|
|
fn new(puzzle: Puzzle) -> SolvedPuzzle {
|
|
let bl = puzzle.placed_tiles.keys().min_by_key(|(x, y)| x + y).unwrap();
|
|
let tr = puzzle.placed_tiles.keys().max_by_key(|(x, y)| x + y).unwrap();
|
|
|
|
let mut grid = Grid::new((tr.1 - bl.1 + 1) as usize * 8);
|
|
|
|
for y in ((bl.1)..=(tr.1)).rev() {
|
|
for x in (bl.0)..=(tr.0) {
|
|
|
|
let tile = &puzzle.placed_tiles[&(x, y)];
|
|
let mut sub_grid = Grid(tile.raw_data.to_vec());
|
|
for _ in 0..tile.rotation {
|
|
sub_grid = sub_grid.rotate();
|
|
}
|
|
if tile.flipped {
|
|
sub_grid = sub_grid.flip_horizontally();
|
|
}
|
|
for i in 0..8 {
|
|
for j in 0..8 {
|
|
let cell = sub_grid[j + 1][i + 1] as u32 - '0' as u32;
|
|
grid[((tr.1 - y) * 8 + j as i32) as usize][((x - bl.0) * 8 + i as i32) as usize] = cell;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
SolvedPuzzle {
|
|
grid,
|
|
}
|
|
}
|
|
|
|
fn find_pattern(&self, pattern_str: &Vec<String>) -> HashSet<(usize, usize)> {
|
|
let pattern_width = pattern_str[0].len();
|
|
let pattern_height = pattern_str.len();
|
|
let pattern: Vec<u32> = pattern_str.iter()
|
|
.map(|l| u32::from_str_radix(&l.replace(' ', "0").replace('#', "1"), 2).unwrap())
|
|
.collect();
|
|
let indices: Vec<Vec<usize>> = pattern_str.iter().map(|l|
|
|
l.chars().enumerate().filter(|(_, c)| *c == '#').map(|(i, _)| i)
|
|
.collect::<Vec<_>>()
|
|
).collect();
|
|
let mask = (1 << pattern_width) - 1;
|
|
let height = self.grid.len();
|
|
let width = self.grid[0].len();
|
|
let mut win = vec![0; pattern_height];
|
|
let mut res = HashSet::new();
|
|
|
|
for y in 0..(height - pattern_height) {
|
|
for i in 0..(win.len()) {
|
|
win[i] = self.grid[y + i].iter().take(19).fold(0, |acc, c| (acc << 1) | c );
|
|
}
|
|
for x in 0..(width - (pattern_width - 1)) {
|
|
let mut found = true;
|
|
for i in 0..win.len() {
|
|
win[i] = ((win[i] << 1) & mask) | self.grid[y + i][x + 19];
|
|
found = found && (win[i] & pattern[i]) == pattern[i];
|
|
}
|
|
if found {
|
|
for i in 0..indices.len() {
|
|
for idx in &indices[i] {
|
|
res.insert((x + idx, y + i));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
res
|
|
}
|
|
|
|
fn compute_roughness(&self, pattern: &Vec<String>) -> usize {
|
|
let mut only_rot_puzzle = self.clone();
|
|
let mut maybe_flipped;
|
|
for case in 0..8 {
|
|
if case % 2 == 1 {
|
|
maybe_flipped = SolvedPuzzle {
|
|
grid: only_rot_puzzle.grid.flip_horizontally()
|
|
};
|
|
} else {
|
|
only_rot_puzzle = SolvedPuzzle {
|
|
grid: only_rot_puzzle.grid.rotate()
|
|
};
|
|
maybe_flipped = only_rot_puzzle.clone();
|
|
}
|
|
|
|
let taken = maybe_flipped.find_pattern(pattern);
|
|
|
|
if taken.len() > 0 {
|
|
let ones: HashSet<(usize, usize)> = maybe_flipped.grid.iter().enumerate()
|
|
.flat_map(|(y, l)| l.iter().enumerate().filter(|(_, v)| **v == 1).map(move |(x, _)| (x, y)))
|
|
.collect();
|
|
return ones.difference(&taken).count();
|
|
}
|
|
}
|
|
0
|
|
}
|
|
}
|
|
|
|
pub fn part1<F: BufRead> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let tiles = buffer.split("\n\n").map(|t| t.parse::<OrientedTile>().unwrap()).collect();
|
|
let solved = {
|
|
Puzzle::solve(Puzzle::new(tiles)).unwrap().placed_tiles
|
|
};
|
|
let bl = solved.keys().min_by_key(|(x, y)| x + y).unwrap();
|
|
let tr = solved.keys().max_by_key(|(x, y)| x + y).unwrap();
|
|
for x in (bl.0)..=(tr.0) {
|
|
for y in ((bl.1)..=(tr.1)).rev() {
|
|
print!("{}\t", solved[&(x, y)].id)
|
|
}
|
|
println!("")
|
|
}
|
|
let checksum = (solved[&(bl.0, bl.1)].id as u64) * (solved[&(bl.0, tr.1)].id as u64) *
|
|
(solved[&(tr.0, tr.1)].id as u64) * (solved[&(tr.0, bl.1)].id as u64);
|
|
println!("checksum = {}", checksum);
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let tiles = buffer.split("\n\n").map(|t| t.parse::<OrientedTile>().unwrap()).collect();
|
|
let puzzle = Puzzle::solve(Puzzle::new(tiles)).unwrap();
|
|
let pattern = vec![
|
|
" # ".into(),
|
|
"# ## ## ###".into(),
|
|
" # # # # # # ".into(),
|
|
];
|
|
let solved = SolvedPuzzle::new(puzzle);
|
|
println!("{:?}", solved.compute_roughness(&pattern));
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
#[test]
|
|
pub fn test_parse() {
|
|
let input = "Tile 2311:
|
|
..##.#..#.
|
|
##..#.....
|
|
#...##..#.
|
|
####.#...#
|
|
##.##.###.
|
|
##...#.###
|
|
.#.#.#..##
|
|
..#....#..
|
|
###...#.#.
|
|
..###..###";
|
|
let tile = OrientedTile {
|
|
id: 2311,
|
|
north: 0b0011010010,
|
|
east: 0b0001011001,
|
|
south: 0b0011100111,
|
|
west: 0b0111110010,
|
|
rotation: 0,
|
|
flipped: false,
|
|
raw_data: Rc::new(Grid(vec![
|
|
vec!['0', '0', '1', '1', '0', '1', '0', '0', '1', '0'],
|
|
vec!['1', '1', '0', '0', '1', '0', '0', '0', '0', '0'],
|
|
vec!['1', '0', '0', '0', '1', '1', '0', '0', '1', '0'],
|
|
vec!['1', '1', '1', '1', '0', '1', '0', '0', '0', '1'],
|
|
vec!['1', '1', '0', '1', '1', '0', '1', '1', '1', '0'],
|
|
vec!['1', '1', '0', '0', '0', '1', '0', '1', '1', '1'],
|
|
vec!['0', '1', '0', '1', '0', '1', '0', '0', '1', '1'],
|
|
vec!['0', '0', '1', '0', '0', '0', '0', '1', '0', '0'],
|
|
vec!['1', '1', '1', '0', '0', '0', '1', '0', '1', '0'],
|
|
vec!['0', '0', '1', '1', '1', '0', '0', '1', '1', '1'],
|
|
])),
|
|
};
|
|
assert_eq!(tile, input.parse::<OrientedTile>().unwrap());
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_rotate() {
|
|
let tile = OrientedTile {
|
|
id: 2311,
|
|
north: 0b0011010010,
|
|
east: 0b0001011001,
|
|
south: 0b0011100111,
|
|
west: 0b0111110010,
|
|
rotation: 0,
|
|
flipped: false,
|
|
raw_data: Rc::new(Grid(Vec::new())),
|
|
};
|
|
let rotated = OrientedTile {
|
|
id: 2311,
|
|
east: 0b0011010010,
|
|
south: 0b1001101000,
|
|
west: 0b0011100111,
|
|
north: 0b0100111110,
|
|
rotation: 1,
|
|
flipped: false,
|
|
raw_data: Rc::new(Grid(Vec::new())),
|
|
};
|
|
assert_eq!(rotated, tile.rotate());
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_rotate_grid() {
|
|
let grid = Grid(vec![
|
|
vec!['0', '1'],
|
|
vec!['0', '0'],
|
|
]);
|
|
let rotated = Grid(vec![
|
|
vec!['0', '0'],
|
|
vec!['0', '1'],
|
|
]);
|
|
assert_eq!(rotated, grid.rotate());
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_find_pattern() {
|
|
let grid = Grid(vec![
|
|
vec![0,1,1,1,1,0,0,0,1,1,1,1,1,0,0,1,0,0,0,1,1,1,0,0],
|
|
vec![1,1,1,1,1,0,0,1,0,0,1,0,1,0,1,1,1,1,0,0,1,0,1,0],
|
|
vec![0,1,0,1,0,0,0,1,0,1,1,1,0,0,0,1,0,1,1,0,1,1,0,0],
|
|
vec![1,0,1,0,1,1,0,1,1,1,0,1,0,1,1,0,1,1,0,1,1,1,1,1],
|
|
vec![0,0,1,1,0,1,1,1,0,1,1,1,1,0,0,1,0,1,1,1,1,0,1,1],
|
|
vec![0,0,0,1,0,1,0,0,1,1,0,1,1,0,0,0,1,0,0,1,0,0,1,1],
|
|
vec![1,0,1,1,0,1,0,0,1,0,1,0,0,1,0,0,1,1,0,1,0,1,0,0],
|
|
vec![0,1,1,1,0,1,1,0,0,0,0,0,1,0,0,0,1,1,1,0,1,0,0,0],
|
|
vec![1,0,1,1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,0,0,1,0,1,0],
|
|
vec![1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,1,1,1],
|
|
vec![0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,1],
|
|
vec![0,0,0,0,1,0,1,1,0,1,0,1,1,1,1,1,0,0,0,0,1,0,0,0],
|
|
vec![0,0,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,0,1,1,0,0,1,0],
|
|
vec![1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,0,0,0,1,1,0],
|
|
vec![0,1,0,1,1,0,0,0,1,0,1,1,0,1,0,1,0,1,1,1,0,0,0,1],
|
|
vec![1,0,1,1,1,0,1,0,0,1,1,1,1,0,0,0,1,1,0,0,1,0,0,0],
|
|
vec![1,0,1,1,1,0,0,0,1,0,1,1,0,0,0,1,0,1,1,1,1,1,1,0],
|
|
vec![0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0],
|
|
vec![0,0,1,1,0,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,0,1,1,1],
|
|
vec![1,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,0,1,0,0,1,1,0],
|
|
vec![1,0,1,1,1,1,1,0,0,1,0,1,0,0,0,1,1,0,0,1,0,0,0,0],
|
|
vec![1,0,0,0,0,1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1],
|
|
vec![1,0,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,1,1,1,0,1,1],
|
|
vec![1,0,0,1,1,1,0,0,0,0,1,1,0,1,0,0,0,1,1,0,1,1,0,1],
|
|
]);
|
|
let pattern = vec![
|
|
" # ".into(),
|
|
"# ## ## ###".into(),
|
|
" # # # # # # ".into(),
|
|
];
|
|
println!("{:?}", SolvedPuzzle { grid }.find_pattern(&pattern))
|
|
//assert_eq!(rotated, SolvedPuzzle::rotate_grid(grid));
|
|
}
|
|
}
|