use crate::*;
use once_cell::sync::Lazy;
use std::collections::HashMap;
use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
pub struct Game {
    hp: i32,
    mp: i32,
    shield: i32,
    poison: i32,
    recharge: i32,
    mana_spent: i32,
    boss_hp: i32,
    boss_dmg: i32,
}

pub fn parse_input(input: &str) -> Result<Game> {
    let (hp, dmg) = scan_fmt::scan_fmt!(
        input,
        "Hit Points: {}
Damage: {}",
        i32,
        i32
    )
    .map_err(|_| task_error!("Wrong input format"))?;
    Ok(Game::new(hp, dmg))
}

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum Spell {
    MagicMissile,
    Drain,
    Shield,
    Poison,
    Recharge,
}

const PRICES: Lazy<HashMap<Spell, i32>> = Lazy::new(|| {
    HashMap::from([
        (Spell::MagicMissile, 53),
        (Spell::Drain, 73),
        (Spell::Shield, 113),
        (Spell::Poison, 173),
        (Spell::Recharge, 229),
    ])
});

impl Game {
    fn new(hp: i32, dmg: i32) -> Game {
        Game {
            hp: 50,
            mp: 500,
            shield: 0,
            poison: 0,
            recharge: 0,
            mana_spent: 0,
            boss_hp: hp,
            boss_dmg: dmg,
        }
    }
    fn effects(&mut self) {
        if self.shield > 0 {
            self.shield -= 1;
        }
        if self.poison > 0 {
            self.boss_hp -= 3;
            self.poison -= 1;
        }
        if self.recharge > 0 {
            self.mp += 101;
            self.recharge -= 1;
        }
    }
    fn player_action(&mut self, action: Spell, hard_mode: bool) -> bool {
        if hard_mode {
            self.hp -= 1;
        }
        if self.lose() {
            return false;
        }
        let price = PRICES[&action];
        if price > self.mp {
            return false;
        }
        match action {
            Spell::MagicMissile => {
                self.boss_hp -= 4;
            }
            Spell::Drain => {
                self.hp += 2;
                self.boss_hp -= 2;
            }
            Spell::Shield if self.shield == 0 => {
                self.shield = 6;
            }
            Spell::Poison if self.poison == 0 => {
                self.poison = 6;
            }
            Spell::Recharge if self.recharge == 0 => {
                self.recharge = 5;
            }
            _ => return false,
        }
        self.mp -= price;
        self.mana_spent += price;
        true
    }
    fn boss_action(&mut self) {
        if self.shield == 0 {
            self.hp -= self.boss_dmg;
        } else {
            self.hp -= self.boss_dmg - 7;
        }
    }
    fn win(&self) -> bool {
        self.hp > 0 && self.boss_hp <= 0
    }
    fn lose(&self) -> bool {
        self.hp <= 0
    }
}

pub fn task(&game: &Game, hard_mode: bool) -> Result<i32> {
    let mut situations = HashSet::from([game]);
    let mut best_mana = None;
    while !situations.is_empty() {
        let mut new_situations = HashSet::new();
        for game in situations {
            for action in [
                Spell::MagicMissile,
                Spell::Drain,
                Spell::Shield,
                Spell::Poison,
                Spell::Recharge,
            ] {
                let mut game = game;
                game.effects();
                if game.player_action(action, hard_mode) {
                    game.effects();
                    if game.win() {
                        best_mana = Some(best_mana.map_or_else(
                            || game.mana_spent,
                            |x: i32| x.min(game.mana_spent),
                        ));
                    }
                    game.boss_action();
                    if !game.lose()
                        && best_mana
                            .map_or_else(|| true, |x| x > game.mana_spent)
                    {
                        new_situations.insert(game);
                    }
                }
            }
        }
        situations = new_situations;
    }
    best_mana.ok_or(task_error!("No solution found"))
}

pub fn task1(game: &Game) -> Result<i32> {
    task(game, false)
}

pub fn task2(game: &Game) -> Result<i32> {
    task(game, true)
}

use crate::*;

use itertools::Itertools;
use once_cell::sync::Lazy;
use std::collections::{HashMap, HashSet};

#[derive(Clone, Hash, PartialEq, Eq, Debug)]
pub struct Position {
    state: i32,
}

impl Position {
    fn get_item(&self, n: usize) -> i32 {
        self.state >> (n * 2 + 2) & 0x3
    }
    fn set_item(&mut self, n: usize, val: i32) {
        let mask = 0x3 << (n * 2 + 2);
        self.state &= !mask;
        self.state |= (val & 0x3) << (n * 2 + 2);
    }
    fn get_elev(&self) -> i32 {
        self.state & 0x3
    }
    fn set_elev(&mut self, val: i32) {
        self.state &= !0x3;
        self.state |= val & 0x3;
    }

    fn is_done(&self, size: usize) -> bool {
        self.get_elev() == 3
            && (0..2 * size)
                .map(|i| self.get_item(i))
                .all(|item| item == 3)
    }
    fn is_valid(&self, size: usize) -> bool {
        for floor in 0..=3 {
            let mut has_generator = false;
            for i in 0..size {
                if self.get_item(2 * i + 1) == floor {
                    has_generator = true;
                    break;
                }
            }
            if has_generator {
                for i in 0..size {
                    if self.get_item(2 * i) == floor
                        && self.get_item(2 * i + 1) != floor
                    {
                        return false;
                    }
                }
            }
        }
        true
    }
    fn get_elevator_floor(&self, size: usize) -> Vec<usize> {
        let elev = self.get_elev();
        (0..2 * size)
            .filter(|&i| self.get_item(i) == elev)
            .collect()
    }
}

pub fn parse_input(input: &str) -> Result<(usize, Position)> {
    let mut position = Position { state: 0 };
    let mut name_map = HashMap::new();
    for line in input.lines() {
        let (floor, list) = scan_fmt::scan_fmt!(
            line,
            "The {/first|second|third|fourth/} floor contains {/[^.]*/}.{e}",
            String,
            String
        )?;
        if list == "nothing relevant" {
            continue;
        }
        let floor = match floor.as_str() {
            "first" => 0,
            "second" => 1,
            "third" => 2,
            "fourth" => 3,
            other => return Err(task_error!("Unknown floor '{other}'")),
        };
        static SPLIT_REGEX: Lazy<regex::Regex> =
            Lazy::new(|| regex::Regex::new(r"(, and )|(, )|( and )").unwrap());
        for item in SPLIT_REGEX.split(&list) {
            let name_map_len = name_map.len();
            if let Ok(generator) =
                scan_fmt::scan_fmt!(item, "a {} generator", String)
            {
                let idx = *name_map.entry(generator).or_insert(name_map_len);
                position.set_item(2 * idx + 1, floor);
            } else {
                let microchip = scan_fmt::scan_fmt!(
                    item,
                    "a {}-compatible microchip",
                    String
                )
                .map_err(|_| {
                    task_error!("List '{list}', item '{item}' fails")
                })?;
                let idx = *name_map.entry(microchip).or_insert(name_map_len);
                position.set_item(2 * idx, floor);
            }
        }
    }
    Ok((name_map.len(), position))
}

pub fn task(input: &Position, size: usize) -> Result<usize> {
    let mut visited = HashSet::new();
    let mut current = HashSet::from([input.clone()]);
    for step in 1.. {
        let mut new = HashSet::new();
        for pos in &current {
            let elevator_floor: Vec<usize> = pos.get_elevator_floor(size);
            for direction in [-1, 1] {
                let new_floor = pos.get_elev() + direction;
                if (0..=3).contains(&new_floor) {
                    for num_items in 1..=2 {
                        for moving in
                            elevator_floor.iter().combinations(num_items)
                        {
                            let mut new_pos = pos.clone();
                            for &item in moving {
                                new_pos.set_item(item, new_floor);
                            }
                            new_pos.set_elev(new_floor);
                            if new_pos.is_done(size) {
                                return Ok(step);
                            }
                            if new_pos.is_valid(size)
                                && !visited.contains(&new_pos)
                            {
                                new.insert(new_pos);
                            }
                        }
                    }
                }
            }
        }
        if new.is_empty() {
            break;
        }
        visited.extend(current);
        current = new;
    }
    Err(task_error!("Solution not found"))
}

pub fn task1((size, position): &(usize, Position)) -> Result<usize> {
    task(position, *size)
}

pub fn task2((size, position): &(usize, Position)) -> Result<usize> {
    task(&position, *size + 2)
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        let input = "The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
The second floor contains a hydrogen generator.
The third floor contains a lithium generator.
The fourth floor contains nothing relevant.";
        let position = parse_input(input);
        assert_eq!(task1(&position.unwrap()).unwrap(), 11);
    }
}