use std::collections::HashMap;

#[path = "../lib.rs"]
mod lib;

fn parse_map(s: &str, fold: usize) -> Vec<(u128, usize)> {
    let mut map = vec![];
    let mut run = 0;
    let mut count = 0;
    for k in 0..fold {
        if k > 0 {
            count += 1;
        }
        for b in s.bytes() {
            if b == b'.' {
                if count > 0 {
                    map.push((run, count));
                    run = 0;
                    count = 0;
                }
            } else {
                if b == b'#' {
                    run |= 1 << count;
                }
                count += 1;
            }
        }
    }
    if count > 0 {
        map.push((run, count));
    }

    for (_, c) in map.iter() {
        assert!(*c <= 128);
    }
    assert!(map.len() < 32);

    return map;
}

fn parse_runs(s: &str, fold: usize) -> Vec<usize> {
    let mut runs = vec![];
    for _ in 0..fold {
        for part in s.split(',') {
            runs.push(part.parse().unwrap());
        }
    }
    assert!(runs.len() < 32);
    return runs;
}

fn cache_key(i: usize, j: usize, x: usize) -> usize {
    return (x << 10) | (j << 5) | i;
}

fn count(
    runs: &Vec<usize>,
    map: &Vec<(u128, usize)>,
    cache: &mut HashMap<usize, usize>,
    i: usize,
    j: usize,
    x: usize,
) -> usize {
    if let Some(result) = cache.get(&cache_key(i, j, x)) {
        return *result;
    }

    if i >= runs.len() {
        if j >= map.len() {
            return 1;
        } else if map[j].0 >> x == 0 {
            return count(runs, map, cache, i, j + 1, 0);
        } else {
            return 0;
        }
    }
    if j >= map.len() {
        return 0;
    }

    let run = runs[i];
    let (m, len) = map[j];
    let mut sum = 0;

    for end in (x + run)..=len {
        if (m << 1) & (1 << (end - run)) != 0 {
            break;
        }
        if m & (1 << end) == 0 {
            let s = count(runs, map, cache, i + 1, j, end + 1);
            if s == 0 && m >> (end + 1) == 0 {
                break;
            } else {
                sum += s;
            }
        }
    }

    if m >> x == 0 {
        sum += count(runs, map, cache, i, j + 1, 0);
    }

    cache.insert(cache_key(i, j, x), sum);

    return sum;
}

fn process_line(line: &str, fold: usize) -> usize {
    let (a, b) = line.split_once(' ').unwrap();
    let map = parse_map(a, fold);
    let runs = parse_runs(b, fold);
    let mut cache = HashMap::new();
    return count(&runs, &map, &mut cache, 0, 0, 0);
}

fn main() {
    let mut sum1 = 0;
    let mut sum2 = 0;

    for line in lib::iter_input() {
        sum1 += process_line(&line, 1);
        sum2 += process_line(&line, 5);
    }

    println!("part1: {}", sum1);
    println!("part2: {}", sum2);
}