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);
    }
}