use std::{ops::Range, str::FromStr};

use anyhow::Context;

use crate::{Problem, Solution};

pub struct Day05;

impl Problem for Day05 {
    const DAY: u8 = 5;

    const INPUT: &'static str = include_str!("../input/day_05.txt");
}

impl Solution for Day05 {
    type Answer1 = usize;

    type Answer2 = usize;

    fn part_1(input: &str) -> anyhow::Result<Self::Answer1> {
        let (first, rest) = input
            .trim()
            .split_once('\n')
            .context("Missing value map label")?;

        let mut seeds = first
            .strip_prefix("seeds: ")
            .context("Failed to get seeds")?
            .split_whitespace()
            .map(FromStr::from_str)
            .try_collect::<Vec<usize>>()?
            .into_iter()
            .map(|n| n..(n + 1))
            .collect::<Vec<_>>();

        for set in rest
            .trim()
            .split("\n\n")
            .map(FromStr::from_str)
            .try_collect::<Vec<ValueMapSet>>()?
        {
            seeds = seeds
                .into_iter()
                .flat_map(|seed_range| set.transform(seed_range))
                .collect();
        }

        seeds
            .iter()
            .map(|range| range.start)
            .min()
            .context("Failed to find min seed")
    }

    fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
        let (first, rest) = input
            .trim()
            .split_once('\n')
            .context("Missing value map label")?;

        let mut seeds = first
            .strip_prefix("seeds: ")
            .context("Failed to get seeds")?
            .split_whitespace()
            .map(FromStr::from_str)
            .try_collect::<Vec<usize>>()?
            .into_iter()
            .array_chunks()
            .map(|[n, len]| n..(n + len))
            .collect::<Vec<_>>();

        for set in rest
            .trim()
            .split("\n\n")
            .map(FromStr::from_str)
            .try_collect::<Vec<ValueMapSet>>()?
        {
            seeds = seeds
                .into_iter()
                .flat_map(|seed_range| set.transform(seed_range))
                .collect();
        }

        seeds
            .iter()
            .map(|range| range.start)
            .min()
            .context("Failed to find min seed")
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct ValueMap {
    dest: usize,
    src: usize,
    length: usize,
}

impl ValueMap {
    fn intersect(&self, seed: &Range<usize>) -> Range<usize> {
        seed.start.max(self.src)..seed.end.min(self.src + self.length)
    }
}

impl FromStr for ValueMap {
    type Err = anyhow::Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let Some([Ok(dest), Ok(src), Ok(length)]) = s
            .split_whitespace()
            .map(FromStr::from_str)
            .array_chunks()
            .next()
        else {
            anyhow::bail!("Invalid value map range");
        };

        Ok(Self { dest, src, length })
    }
}

struct ValueMapSet(Vec<ValueMap>);

impl ValueMapSet {
    fn transform(&self, seed_range: Range<usize>) -> Vec<Range<usize>> {
        let mut queue = Vec::from([seed_range]);
        let mut mapped = Vec::new();

        while let Some(seed) = queue.pop() {
            let Some(&map) = self.0.iter().find(|t| !t.intersect(&seed).is_empty()) else {
                mapped.push(seed);
                continue;
            };

            let intersect = map.intersect(&seed);

            mapped.push(Range {
                start: (intersect.start + map.dest) - map.src,
                end: (intersect.end + map.dest) - map.src,
            });

            if seed.start < map.src {
                queue.push(Range {
                    start: seed.start,
                    end: intersect.start - 1,
                });
            }

            if seed.end > (map.src + map.length) {
                queue.push(Range {
                    start: intersect.end + 1,
                    end: seed.end,
                });
            }
        }

        mapped.into_iter().collect()
    }
}

impl FromStr for ValueMapSet {
    type Err = anyhow::Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        s.trim()
            .lines()
            .skip(1)
            .map(FromStr::from_str)
            .try_collect::<Vec<ValueMap>>()
            .map(Self)
    }
}

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

    const INPUT: &str = indoc::indoc! {"
        seeds: 79 14 55 13

        seed-to-soil map:
        50 98 2
        52 50 48

        soil-to-fertilizer map:
        0 15 37
        37 52 2
        39 0 15

        fertilizer-to-water map:
        49 53 8
        0 11 42
        42 0 7
        57 7 4

        water-to-light map:
        88 18 7
        18 25 70

        light-to-temperature map:
        45 77 23
        81 45 19
        68 64 13

        temperature-to-humidity map:
        0 69 1
        1 0 69

        humidity-to-location map:
        60 56 37
        56 93 4
    "};

    #[test]
    fn test_part_1() -> anyhow::Result<()> {
        Ok(assert_eq!(35, Day05::part_1(INPUT)?))
    }

    #[test]
    fn test_part_2() -> anyhow::Result<()> {
        Ok(assert_eq!(46, Day05::part_2(INPUT)?))
    }
}