#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(unused_mut)]
use std::fmt;
use std::fs::File;
use std::io::Read;

#[derive(Eq, PartialEq, Clone, Copy)]
enum State {
    Ok,
    Nok,
    Unk,
}
impl std::fmt::Debug for State {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let a = match self {
            State::Ok => '.',
            State::Nok => '#',
            State::Unk => '?',
        };
        write!(f, "{}", a)
    }
}

type Line = (Vec<State>, Vec<usize>);

fn rec(l: Line) -> u64 {
    for i in 0..l.0.len() {
        if l.0[i] == State::Unk {
            let mut sum = 0;
            let mut l1 = l.clone();
            let mut l2 = l.clone();
            l1.0[i] = State::Ok;
            l2.0[i] = State::Nok;
            sum += rec(l1);
            sum += rec(l2);
            return sum;
        }
    }

    if is_valid(&l) {
        return 1;
    } else {
        return 0;
    }
}

fn is_valid(l: &Line) -> bool {
    let mut a: Vec<usize> = Vec::new();

    let mut prev = State::Ok;
    let mut count = 0;

    for i in 0..l.0.len() {
        if l.0[i] == State::Nok {
            count += 1;
        } else if l.0[i] == State::Ok && prev == State::Nok {
            a.push(count);
            count = 0;
        }
        prev = l.0[i];
    }
    if count != 0 {
        a.push(count);
    }

    let ret = a == l.1;
    ret
}

fn rec2(mut s: &[State], mut arr: &[usize], depth: u32) -> u64 {
    // println!("{} {:?} {:?}", depth, s, arr);

    if arr.len() == 0 {
        let mut all = true;
        for i in 0..s.len() {
            if s[i] == State::Nok {
                all = false;
            }
        }
        if all {
            // println!("ret 1");
            return 1;
        } else {
            // println!("ret 0");
            return 0;
        }
    }
    if s.len() == 0 {
        // println!("ret 0");
        return 0;
    }

    let nok_count = arr.iter().fold(0, |x, y| x + y);
    let ok_count_min = arr.len() - 1;
    if s.len() < nok_count + ok_count_min {
        // println!("ret 0");
        return 0;
    }
    if nok_count > s.iter().filter(|&&x| x != State::Ok).fold(0, |x, _| x + 1) {
        return 0;
    }

    if ok_count_min > s.iter().filter(|&&x| x != State::Nok).fold(0, |x, _| x + 1) {
        return 0;
    }

    let n = arr[0];
    let arr = &arr[1..];

    let start = if depth == 0 { 0 } else { 1 };

    let mut ret = 0;
    // println!("nok_s {} {}", start, s.len() - n);
    for nok_s in start..=(s.len() - n) {
        let mut all = true;
        // check before first #
        for ii in 0..nok_s {
            if s[ii] == State::Nok {
                all = false;
            }
        }
        // check if # * n
        for ii in 0..n {
            if s[nok_s + ii] == State::Ok {
                all = false;
            }
        }

        if all {
            ret += rec2(&s[nok_s + n..], arr, depth + 1);
        }
    }

    ret
}

fn main() {
    // let filename = "in/day12.ref";
    let filename = "in/day12.pzl";

    let mut f = File::open(filename).expect("cannot open file");
    let mut content = String::new();
    f.read_to_string(&mut content).expect("cannot read file");
    let lines = content.trim_end().split('\n');

    let mut ls: Vec<Line> = Vec::new();
    for line in lines {
        let (a, b) = line.split_once(' ').unwrap();
        let mut l: Line = (Vec::new(), Vec::new());
        for c in a.chars() {
            let s = match c {
                '.' => State::Ok,
                '#' => State::Nok,
                '?' => State::Unk,
                _ => panic!(),
            };
            l.0.push(s);
        }
        for c in b.split(',') {
            l.1.push(c.parse().unwrap());
        }
        ls.push(l);
    }

    let mut res1 = 0;

    for (i, l) in ls.iter().enumerate() {
        // let a = rec(l.clone());
        let a = rec2(&l.0, &l.1, 0);
        println!("{} {}", i + 1, a);
        res1 += a;
    }

    let mut res2 = 0;

    let mut ls2: Vec<Line> = Vec::new();
    for i in 0..ls.len() {
        let mut l2: Line = Default::default();
        l2.0 = vec![ls[i].0.clone(); 5].join(&State::Unk);
        l2.1 = vec![ls[i].1.clone(); 5]
            .into_iter()
            .flat_map(|s| s)
            .collect::<Vec<usize>>();
        ls2.push(l2);
    }

    // !!! za part2 rabi 1562090s (18dni) !!!
    // it to z --release ter -C target-cpu=native
    // TODO: make faster
    for (i, l) in ls2.iter().enumerate() {
        let a = rec2(&l.0, &l.1, 0);
        println!("{} {}", i + 1, a);
        res2 += a;
    }

    println!("res1: {}", res1);
    println!("res2: {}", res2);
    assert_eq!(res1, 7084);
    assert_eq!(res2, 8414003326821);
}