adventofcode23/src/day12.rs

//! Day 12

use std::collections::hash_map::DefaultHasher;
use std::collections::{hash_map::Entry, HashMap};
use std::hash::{Hash, Hasher};
use std::sync::Mutex;

use itertools::Itertools;

pub const DAY: u8 = 12;
pub const TITLE: &str = "Hot Springs";

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum SpringState {
    Ok,
    Broken,
    Unknown,
}

impl SpringState {
    fn from_c(c: char) -> Self {
        match c {
            '.' => Self::Ok,
            '#' => Self::Broken,
            '?' => Self::Unknown,
            _ => panic!("invalid char `{c}`"),
        }
    }
}

#[derive(Debug)]
struct Row {
    springs: Vec<SpringState>,
    groups: Vec<usize>,
}

impl Row {
    fn parse(input: &str) -> Self {
        let (p1, p2) = input.split_once(' ').unwrap();
        Self {
            springs: p1.chars().map(SpringState::from_c).collect(),
            groups: p2.split(',').map(|n| n.parse().unwrap()).collect(),
        }
    }

    fn combinations(&self) -> usize {
        let mut cache = CcCache::new();
        count_combinations_cached(
            &self.springs,
            &self.groups,
            None,
            0,
            0,
            0,
            String::new(),
            &mut cache,
        )
        .unwrap()
    }

    fn unfold(&self) -> Self {
        let mut springs = Vec::new();
        for i in 0..5 {
            springs.extend(&self.springs);
            if i != 4 {
                springs.push(SpringState::Unknown);
            }
        }

        Self {
            springs,
            groups: self
                .groups
                .iter()
                .copied()
                .cycle()
                .take(self.groups.len() * 5)
                .collect(),
        }
    }
}

fn parse(input: Vec<String>) -> Vec<Row> {
    input.iter().map(|r| Row::parse(r)).collect()
}

#[derive(Clone, Hash, PartialEq, Eq)]
struct CcInput {
    pre: Option<SpringState>,
    si: usize,
    gi: usize,
    glen: usize,
}

type CcCache<'a> = HashMap<CcInput, Option<usize>>;

fn count_combinations_cached(
    springs: &[SpringState],
    groups: &[usize],
    pre: Option<SpringState>,
    si: usize,
    gi: usize,
    glen: usize,
    tmp: String,
    cache: &mut CcCache,
) -> Option<usize> {
    let inp = CcInput { pre, si, gi, glen };
    match cache.entry(inp) {
        Entry::Occupied(e) => *e.get(),
        Entry::Vacant(e) => {
            let res = count_combinations(springs, groups, pre, si, gi, glen, tmp);
            e.insert(res);
            res
        }
    }
}

fn count_combinations(
    springs: &[SpringState],
    groups: &[usize],
    pre: Option<SpringState>,
    si: usize,
    gi: usize,
    glen: usize,
    tmp: String,
) -> Option<usize> {
    if let Some(s) = pre.or(springs.get(si).copied()) {
        match s {
            SpringState::Ok => {
                if glen > 0 {
                    // broken springs before
                    if &glen == groups.get(gi)? {
                        count_combinations(springs, groups, None, si + 1, gi + 1, 0, tmp + ".")
                    } else {
                        None
                    }
                } else {
                    count_combinations(springs, groups, None, si + 1, gi, 0, tmp + ".")
                }
            }
            SpringState::Broken => {
                let nc = glen + 1;
                if &nc > groups.get(gi)? {
                    // more broken springs than specified
                    None
                } else {
                    count_combinations(springs, groups, None, si + 1, gi, nc, tmp + "#")
                }
            }
            SpringState::Unknown => {
                let mut s = 0;

                // Attempt 2 configurations
                s += count_combinations(
                    springs,
                    groups,
                    Some(SpringState::Ok),
                    si,
                    gi,
                    glen,
                    tmp.clone(),
                )
                .unwrap_or_default();

                s += count_combinations(
                    springs,
                    groups,
                    Some(SpringState::Broken),
                    si,
                    gi,
                    glen,
                    tmp.clone(),
                )
                .unwrap_or_default();

                // return amount of possible combinations
                Some(s).filter(|s| s > &0)
            }
        }
    } else if gi >= groups.len() || (gi == groups.len() - 1 && groups.last().unwrap() == &glen) {
        // println!("{tmp}; {groups:?}");
        Some(1)
    } else {
        None
    }
}

pub fn part1(input: Vec<String>) -> String {
    let rows = parse(input);
    rows.iter()
        // .map(Row::combinations)
        .map(|r| {
            let x = r.combinations();
            // dbg!(x);
            x
        })
        .sum::<usize>()
        .to_string()
}

pub fn part2(input: Vec<String>) -> String {
    let rows = parse(input);
    rows.iter()
        // .map(Row::combinations)
        .map(|r| {
            let x = r.unfold().combinations();
            dbg!(x);
            x
        })
        .sum::<usize>()
        .to_string()
}

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

    #[test]
    fn tmp() {
        // .#.###.#.######
        let r = Row::parse(".#? 1");
        dbg!(r.combinations());
        // dbg!(r.unfold().combinations());
    }

    #[test]
    fn t_example1() {
        assert_eq!(part1(crate::read_example(DAY, 1)), "21");
    }

    #[test]
    fn t_part1() {
        // < 11405
        assert_eq!(part1(crate::read_input(DAY)), "8193");
    }

    #[test]
    fn t_example2() {
        assert_eq!(part2(crate::read_example(DAY, 2)), "525152");
    }

    #[test]
    fn t_part2() {
        assert_eq!(part2(crate::read_input(DAY)), "45322533163795");
    }
}