520 lines
14 KiB
Rust
520 lines
14 KiB
Rust
use std::collections::HashSet;
|
|
use std::error::Error;
|
|
use std::fs::File;
|
|
use std::io::{self, BufRead};
|
|
use std::vec::Vec;
|
|
|
|
#[derive(PartialEq, Clone, Debug, Hash, Eq)]
|
|
struct Tile {
|
|
id: u64,
|
|
pixels: Vec<Vec<bool>>,
|
|
}
|
|
|
|
fn rotate_90(img: &Vec<Vec<bool>>) -> Vec<Vec<bool>> {
|
|
let mut rot_img: Vec<Vec<bool>> = Vec::new();
|
|
for rot_y in 0..img[0].len() {
|
|
let mut rot_line = Vec::new();
|
|
for rot_x in 0..img.len() {
|
|
rot_line.push(img[img.len() - rot_x - 1][rot_y])
|
|
}
|
|
rot_img.push(rot_line);
|
|
}
|
|
|
|
rot_img
|
|
}
|
|
|
|
fn flip_hor(img: &Vec<Vec<bool>>) -> Vec<Vec<bool>> {
|
|
img.iter().cloned().rev().collect()
|
|
}
|
|
|
|
fn count_monsters(img: &Vec<Vec<bool>>, monster: &Vec<Vec<bool>>) -> usize {
|
|
let mut count = 0usize;
|
|
|
|
let img_w = img[0].len();
|
|
let img_h = img.len();
|
|
//println!("Img: {} {}", img_w, img_h);
|
|
|
|
let monster_w = monster[0].len();
|
|
let monster_h = monster.len();
|
|
//println!("Monster: {} {}", monster_w, monster_h);
|
|
|
|
for base_x in 0..img_w {
|
|
for base_y in 0..img_h {
|
|
let mut is_monster = true;
|
|
for x in 0..monster_w {
|
|
for y in 0..monster_h {
|
|
if base_x + x >= img_w || base_y + y >= img_h {
|
|
is_monster = false;
|
|
break;
|
|
}
|
|
|
|
if !img[base_y + y][base_x + x] && monster[y][x] {
|
|
is_monster = false;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if is_monster {
|
|
count += 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
count
|
|
}
|
|
|
|
impl Tile {
|
|
fn flip_hor(&self) -> Tile {
|
|
Tile {
|
|
id: self.id,
|
|
pixels: flip_hor(&self.pixels),
|
|
}
|
|
}
|
|
|
|
fn flip_vert(&self) -> Tile {
|
|
Tile {
|
|
id: self.id,
|
|
pixels: self
|
|
.pixels
|
|
.iter()
|
|
.map(|l| l.iter().cloned().rev().collect())
|
|
.collect(),
|
|
}
|
|
}
|
|
|
|
fn rotate_90(&self) -> Tile {
|
|
Tile {
|
|
id: self.id,
|
|
pixels: rotate_90(&self.pixels),
|
|
}
|
|
}
|
|
|
|
fn rotate_180(&self) -> Tile {
|
|
self.rotate_90().rotate_90()
|
|
}
|
|
|
|
fn rotate_270(&self) -> Tile {
|
|
self.rotate_180().rotate_90()
|
|
}
|
|
|
|
fn all_orientations(&self) -> Vec<Tile> {
|
|
let mut res = Vec::new();
|
|
res.push(self.clone());
|
|
res.push(self.flip_hor());
|
|
//res.push(self.flip_vert());
|
|
|
|
res.push(self.rotate_90());
|
|
res.push(self.rotate_90().flip_hor());
|
|
//res.push(self.rotate_90().flip_vert());
|
|
|
|
res.push(self.rotate_180());
|
|
res.push(self.rotate_180().flip_hor());
|
|
//res.push(self.rotate_180().flip_vert());
|
|
|
|
res.push(self.rotate_270());
|
|
res.push(self.rotate_270().flip_hor());
|
|
//res.push(self.rotate_270().flip_vert());
|
|
|
|
res
|
|
}
|
|
|
|
fn matches_below(&self, other: &Tile) -> bool {
|
|
let other_bottom = other.pixels.iter().last().unwrap();
|
|
let my_top = self.pixels.iter().next().unwrap();
|
|
for i in 0..my_top.len() {
|
|
if my_top[i] != other_bottom[i] {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
fn matches_right_of(&self, other: &Tile) -> bool {
|
|
for y in 0..self.pixels.len() {
|
|
let other_pixel = other.pixels[y].iter().last().unwrap();
|
|
let my_pixel = self.pixels[y].iter().next().unwrap();
|
|
if my_pixel != other_pixel {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
}
|
|
|
|
fn complete_puzzle(
|
|
puzzle: Vec<Vec<Tile>>,
|
|
tiles: &HashSet<Tile>,
|
|
x: usize,
|
|
y: usize,
|
|
len: usize,
|
|
) -> Option<Vec<Vec<Tile>>> {
|
|
if tiles.len() == 0 {
|
|
return Some(puzzle);
|
|
} else if x == 0 && y == 0 {
|
|
for tile in tiles.iter() {
|
|
//println!("Trying {} as first tile", tile.id);
|
|
|
|
let mut next_tiles = tiles.clone();
|
|
next_tiles.remove(tile);
|
|
|
|
for next_tile in tile.all_orientations() {
|
|
if let Some(p) = complete_puzzle(vec![vec![next_tile]], &next_tiles, 1, 0, len) {
|
|
return Some(p);
|
|
}
|
|
}
|
|
}
|
|
} else if y == 0 {
|
|
let other = &puzzle[y][x - 1];
|
|
|
|
let next_x = if x + 1 < len { x + 1 } else { 0 };
|
|
let next_y = if x + 1 < len { 0 } else { 1 };
|
|
|
|
for tile in tiles.iter() {
|
|
let mut next_tiles = tiles.clone();
|
|
next_tiles.remove(tile);
|
|
|
|
for next_tile in tile.all_orientations() {
|
|
if next_tile.matches_right_of(other) {
|
|
//println!("{} matches right of {}", next_tile.id, other.id);
|
|
let mut next_puzzle = puzzle.clone();
|
|
next_puzzle[0].push(next_tile);
|
|
if let Some(p) = complete_puzzle(next_puzzle, &next_tiles, next_x, next_y, len)
|
|
{
|
|
return Some(p);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} else if x == 0 {
|
|
let other = &puzzle[y - 1][0];
|
|
|
|
for tile in tiles.iter() {
|
|
let mut next_tiles = tiles.clone();
|
|
next_tiles.remove(tile);
|
|
|
|
for next_tile in tile.all_orientations() {
|
|
if next_tile.matches_below(other) {
|
|
//println!("{} matches below of {}", next_tile.id, other.id);
|
|
let mut next_puzzle = puzzle.clone();
|
|
next_puzzle.push(vec![next_tile]);
|
|
if let Some(p) = complete_puzzle(next_puzzle, &next_tiles, 1, y, len) {
|
|
return Some(p);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} else {
|
|
let other_top = &puzzle[y - 1][x];
|
|
let other_left = &puzzle[y][x - 1];
|
|
|
|
let next_x = if x + 1 < len { x + 1 } else { 0 };
|
|
let next_y = if x + 1 < len { y } else { y + 1 };
|
|
|
|
for tile in tiles.iter() {
|
|
let mut next_tiles = tiles.clone();
|
|
next_tiles.remove(tile);
|
|
|
|
for next_tile in tile.all_orientations() {
|
|
if next_tile.matches_below(other_top) && next_tile.matches_right_of(other_left) {
|
|
/*println!(
|
|
"{} matches right of {} and below {}",
|
|
next_tile.id, other_top.id, other_top.id
|
|
);*/
|
|
let mut next_puzzle = puzzle.clone();
|
|
next_puzzle[y].push(next_tile);
|
|
if let Some(p) = complete_puzzle(next_puzzle, &next_tiles, next_x, next_y, len)
|
|
{
|
|
return Some(p);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
//println!("No match for {} {}", x, y);
|
|
return None;
|
|
}
|
|
|
|
fn count_pixels(img: &Vec<Vec<bool>>) -> usize {
|
|
img.iter()
|
|
.map(|l| {
|
|
l.iter()
|
|
.map(|p| if *p { 1 } else { 0 })
|
|
.fold(0, |x, y| x + y)
|
|
})
|
|
.fold(0, |x, y| x + y)
|
|
}
|
|
|
|
fn get_puzzle_size(puzzle: &Vec<Vec<Tile>>) -> (usize, usize) {
|
|
let tile_w = puzzle[0][0].pixels[0].len() - 2;
|
|
let tile_h = puzzle[0][0].pixels.len() - 2;
|
|
let puzzle_w = puzzle[0].len();
|
|
let puzzle_h = puzzle.len();
|
|
|
|
(puzzle_w * tile_w, puzzle_h * tile_h)
|
|
}
|
|
|
|
fn get_puzzle_pixel(x: usize, y: usize, puzzle: &Vec<Vec<Tile>>) -> bool {
|
|
let tile_w = puzzle[0][0].pixels[0].len() - 2;
|
|
let tile_h = puzzle[0][0].pixels.len() - 2;
|
|
|
|
let puzzle_x = x / tile_w;
|
|
let tile_x = x % tile_w;
|
|
|
|
let puzzle_y = y / tile_h;
|
|
let tile_y = y % tile_h;
|
|
|
|
puzzle[puzzle_y][puzzle_x].pixels[tile_y + 1][tile_x + 1]
|
|
}
|
|
|
|
fn main() -> Result<(), Box<dyn Error>> {
|
|
let file = File::open("inputs/day20.txt")?;
|
|
let mut lines = io::BufReader::new(file).lines().map(|l| l.unwrap());
|
|
|
|
let mut tiles: HashSet<Tile> = HashSet::new();
|
|
|
|
let mut tile_id: u64 = 0;
|
|
let mut tile_pixels: Vec<Vec<bool>> = Vec::new();
|
|
while let Some(line) = lines.next() {
|
|
if line == "" {
|
|
tiles.insert(Tile {
|
|
id: tile_id,
|
|
pixels: tile_pixels,
|
|
});
|
|
tile_pixels = Vec::new();
|
|
} else if line.starts_with("Tile ") {
|
|
tile_id = line
|
|
.strip_prefix("Tile ")
|
|
.expect("Tile keyword")
|
|
.strip_suffix(":")
|
|
.expect(": missing in tile line.")
|
|
.parse()
|
|
.expect("Unable to parse tile id");
|
|
println!("Tile ID: {}", tile_id);
|
|
} else {
|
|
let tile_line: Vec<bool> = line.chars().map(|c| c == '#').collect();
|
|
tile_pixels.push(tile_line);
|
|
}
|
|
}
|
|
tiles.insert(Tile {
|
|
id: tile_id,
|
|
pixels: tile_pixels,
|
|
});
|
|
|
|
println!("Found {} tiles", tiles.len());
|
|
let len = (tiles.len() as f64).sqrt() as usize;
|
|
println!("Images is {} x {} tiles", len, len);
|
|
|
|
let p = complete_puzzle(Vec::new(), &tiles, 0, 0, len).expect("No soltuion found.");
|
|
println!("Found a solution");
|
|
for y in 0..len {
|
|
let line = p[y]
|
|
.iter()
|
|
.map(|t| t.id.to_string())
|
|
.fold(String::new(), |x, acc| acc + " " + &x);
|
|
println!("{}", line);
|
|
}
|
|
|
|
let answer = p[0][0].id * p[0][len - 1].id * p[len - 1][0].id * p[len - 1][len - 1].id;
|
|
println!("Answer1: {}", answer);
|
|
|
|
//
|
|
// Part 2
|
|
//
|
|
|
|
let (p_w, p_h) = get_puzzle_size(&p);
|
|
println!("Image size: {} x {}", p_w, p_h);
|
|
let mut img = Vec::new();
|
|
for y in 0..p_h {
|
|
let mut line = Vec::new();
|
|
for x in 0..p_w {
|
|
line.push(get_puzzle_pixel(x, y, &p));
|
|
}
|
|
img.push(line);
|
|
}
|
|
|
|
let monster_str = " # \n# ## ## ###\n # # # # # # \n";
|
|
println!("{}", monster_str);
|
|
|
|
let monster_img: Vec<Vec<bool>> = monster_str
|
|
.lines()
|
|
.map(|l| l.chars().map(|c| c == '#').collect())
|
|
.collect();
|
|
|
|
let monster_pixels_count = count_pixels(&monster_img);
|
|
println!("Monster-Pixels: {}", monster_pixels_count);
|
|
|
|
let img_pixel_count = count_pixels(&img);
|
|
|
|
let mut next_img = img;
|
|
for _ in 0..4 {
|
|
let monsters = count_monsters(&next_img, &monster_img);
|
|
if monsters > 0 {
|
|
println!("Monsters: {}", monsters);
|
|
println!(
|
|
"Roughness: {}",
|
|
img_pixel_count - monsters * monster_pixels_count
|
|
);
|
|
}
|
|
|
|
let flipped = flip_hor(&next_img);
|
|
let monsters = count_monsters(&flipped, &monster_img);
|
|
if monsters > 0 {
|
|
println!("Monsters: {}", monsters);
|
|
println!(
|
|
"Roughness: {}",
|
|
img_pixel_count - monsters * monster_pixels_count
|
|
);
|
|
}
|
|
|
|
next_img = rotate_90(&next_img);
|
|
}
|
|
|
|
Ok(())
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use crate::*;
|
|
#[test]
|
|
fn test_rot() {
|
|
let t = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, true, true],
|
|
vec![false, true, false],
|
|
vec![true, false, false],
|
|
],
|
|
};
|
|
|
|
let result_90 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, false, true],
|
|
vec![false, true, true],
|
|
vec![false, false, true],
|
|
],
|
|
};
|
|
|
|
let result_180 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![false, false, true],
|
|
vec![false, true, false],
|
|
vec![true, true, true],
|
|
],
|
|
};
|
|
|
|
let result_270 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, false, false],
|
|
vec![true, true, false],
|
|
vec![true, false, true],
|
|
],
|
|
};
|
|
|
|
assert_eq!(t.rotate_90(), result_90);
|
|
assert_eq!(t.rotate_180(), result_180);
|
|
assert_eq!(t.rotate_270(), result_270);
|
|
}
|
|
|
|
#[test]
|
|
fn test_matches_below() {
|
|
let t1 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![false, false, false],
|
|
vec![false, false, false],
|
|
vec![true, false, true],
|
|
],
|
|
};
|
|
|
|
let t2 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, false, true],
|
|
vec![false, false, false],
|
|
vec![false, true, false],
|
|
],
|
|
};
|
|
|
|
assert!(!t1.matches_below(&t1));
|
|
assert!(!t2.matches_below(&t2));
|
|
assert!(!t1.matches_below(&t2));
|
|
assert!(t2.matches_below(&t1));
|
|
}
|
|
|
|
#[test]
|
|
fn test_matches_right_off() {
|
|
let t1 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![false, false, true],
|
|
vec![false, false, false],
|
|
vec![false, false, true],
|
|
],
|
|
};
|
|
|
|
let t2 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, false, true],
|
|
vec![false, false, true],
|
|
vec![true, false, false],
|
|
],
|
|
};
|
|
|
|
assert!(!t1.matches_right_of(&t1));
|
|
assert!(!t2.matches_right_of(&t2));
|
|
assert!(!t1.matches_right_of(&t2));
|
|
assert!(t2.matches_right_of(&t1));
|
|
}
|
|
|
|
#[test]
|
|
fn test_flip_hor() {
|
|
let t1 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![false, false, false],
|
|
vec![false, true, false],
|
|
vec![true, true, true],
|
|
],
|
|
};
|
|
|
|
let result = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, true, true],
|
|
vec![false, true, false],
|
|
vec![false, false, false],
|
|
],
|
|
};
|
|
|
|
assert_eq!(t1.flip_hor(), result);
|
|
}
|
|
|
|
#[test]
|
|
fn test_flip_vert() {
|
|
let t1 = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![true, false, false],
|
|
vec![true, true, false],
|
|
vec![true, false, false],
|
|
],
|
|
};
|
|
|
|
let result = Tile {
|
|
id: 5,
|
|
pixels: vec![
|
|
vec![false, false, true],
|
|
vec![false, true, true],
|
|
vec![false, false, true],
|
|
],
|
|
};
|
|
|
|
assert_eq!(t1.flip_vert(), result);
|
|
}
|
|
}
|