adventofcode23/src/day5.rs

//! Day 5: If You Give A Seed A Fertilizer

use std::{borrow::BorrowMut, collections::HashMap, ops::Range};

use itertools::Itertools;
use rangemap::{RangeMap, RangeSet};

pub const DAY: u8 = 5;
pub const TITLE: &str = "If You Give A Seed A Fertilizer";

#[derive(Debug)]
struct Parsed {
    seeds: Vec<u64>,
    maps: Vec<RangeMap<u64, Range<u64>>>,
}

impl Parsed {
    fn lookup(&self, seed: u64) -> u64 {
        let mut s = seed;
        for map in &self.maps {
            if let Some((rng, dst)) = map.get_key_value(&s) {
                s = dst.start + (s - rng.start);
            }
        }
        s
    }

    /// Transform the list of seed maps into a single map
    fn transform(&self) -> RangeMap<u64, Range<u64>> {
        self.maps
            .clone()
            .into_iter()
            .reduce(|acc, m| {
                // have dangling keys from next map as fallback
                let mut res = m.clone();
                for (k, v) in acc.iter() {
                    // lookup value range in next map
                    for (olk, olv) in m.overlapping(v) {
                        let corr = olk.start.max(v.start)..olk.end.min(v.end);
                        let offset = corr.start - v.start;
                        let voffset = corr.start - olk.start;
                        let s = k.start + offset;
                        let l = rlen(&corr);
                        let olvs = olv.start + voffset;
                        res.insert(s..(s + l), olvs..(olvs + l));
                    }

                    // ranges in acc map not covered by next map
                    for g in m.gaps(v) {
                        let offset = g.start - v.start;
                        let s = k.start + offset;
                        let vs = v.start + offset;
                        let l = rlen(&g);
                        res.insert(s..(s + l), vs..(vs + l));
                    }
                }
                res
            })
            .unwrap()
    }
}

fn parse(input: Vec<String>) -> Parsed {
    let mut ip = input.iter();
    let seeds = ip
        .next()
        .unwrap()
        .strip_prefix("seeds: ")
        .unwrap()
        .split_ascii_whitespace()
        .map(|n| n.parse().unwrap())
        .collect();

    let mut maps = Vec::new();
    let mut map = RangeMap::new();

    for l in ip {
        if l.is_empty() {
            if !map.is_empty() {
                maps.push(map);
                map = RangeMap::new();
            }
            continue;
        }
        let fc = l.chars().next().unwrap();
        if !fc.is_numeric() {
            continue;
        }

        let mentry: (u64, u64, u64) = l
            .split_ascii_whitespace()
            .map(|n| n.parse().unwrap())
            .collect_tuple()
            .unwrap();

        map.insert(
            mentry.1..(mentry.1 + mentry.2),
            mentry.0..(mentry.0 + mentry.2),
        );
    }
    if !map.is_empty() {
        maps.push(map);
    }

    Parsed { seeds, maps }
}

pub fn part1(input: Vec<String>) -> String {
    let parsed = parse(input);
    let tf = parsed.transform();

    parsed
        .seeds
        .iter()
        .map(|s| {
            let (rng, dst) = tf.get_key_value(s).unwrap();
            dst.start + (s - rng.start)
        })
        .min()
        .unwrap()
        .to_string()
}

pub fn part2(input: Vec<String>) -> String {
    let parsed = parse(input);
    let tf = parsed.transform();

    let ranges = parsed
        .seeds
        .iter()
        .tuples()
        .map(|(a, b)| (*a)..(*a + *b))
        .collect::<RangeSet<_>>();

    tf.into_iter()
        .sorted_by_key(|(_, soils)| soils.start)
        .find_map(|(seeds, soils)| {
            ranges
                .iter()
                .find_map(|r| lowest_intersection(r, &seeds))
                .map(|seed| soils.start + (seed - seeds.start))
        })
        .unwrap()
        .to_string()
}

fn rlen(range: &Range<u64>) -> u64 {
    range.end - range.start
}

fn lowest_intersection(r1: &Range<u64>, r2: &Range<u64>) -> Option<u64> {
    let (l, h) = if r1.start < r2.start {
        (r1, r2)
    } else {
        (r2, r1)
    };

    if h.start <= l.end {
        Some(h.start)
    } else {
        None
    }
}

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

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

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

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

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