aoc2025/src/day5.rs

use std::cmp::max;
use std::fmt::Debug;
use std::ops::RangeInclusive;

use aoc_runner_derive::{aoc, aoc_generator};

struct Database {
    fresh_ingredients: Vec<RangeInclusive<u64>>,
    available_ingredients: Vec<u64>,
}

struct Database2 {
    fresh_ingredients: Vec<Span>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct Span {
    start: u64,
    end: u64,
}

impl From<(u64, u64)> for Span {
    fn from(value: (u64, u64)) -> Self {
        Self {
            start: value.0,
            end: value.1,
        }
    }
}

impl Span {
    fn len(&self) -> u64 {
        self.end - self.start + 1
    }
}

struct RangeSet {
    ranges: Vec<Span>,
}

impl RangeSet {
    fn new() -> Self {
        Self { ranges: Vec::new() }
    }
    fn simplify(&mut self) {
        if self.ranges.len() < 2 {
            return;
        }
        let mut modified = true;
        while modified {
            modified = false;
            // sort the ranges by start
            self.ranges.sort_by_key(|s| s.start);
            let mut new_ranges = Vec::new();
            let mut pos = 1;

            while pos <= self.ranges.len() {
                // part of a disgusting hack to avoid skipping or double adding at the end
                if pos == self.ranges.len() {
                    pos -= 1;
                }
                let (l, r) = (&self.ranges[pos - 1], &self.ranges[pos]);

                if r.start <= l.end + 1 {
                    modified = true;
                    new_ranges.push((l.start, max(l.end, r.end)).into());
                    // if we merged, skip checking the next range to avoid double-adding it
                    // this screws us up at the very end, so need the disgusting hack above
                    pos += 2;
                } else if pos < self.ranges.len() - 1 {
                    // keep only the lhs if we didn't merge
                    new_ranges.push(l.clone());
                    pos += 1;
                } else {
                    // at the end, keep both sides, otherwise the rhs gets excluded (if it didn't merge)
                    new_ranges.push(l.clone());
                    new_ranges.push(r.clone());
                    pos += 2;
                }
            }

            self.ranges = new_ranges;
        }
    }
    fn add(&mut self, s: Span) {
        self.ranges.push(s);
    }
}

#[aoc_generator(day5)]
fn parse(input: &str) -> Database {
    let mut fresh_ingredients = Vec::new();
    let mut available_ingredients = Vec::new();
    let mut parsing_ranges = true;
    for line in input.lines() {
        if line.is_empty() {
            parsing_ranges = false;
            continue;
        }
        if parsing_ranges {
            let (start, end) = line.split_once('-').unwrap();
            fresh_ingredients.push(RangeInclusive::new(
                start.parse().unwrap(),
                end.parse().unwrap(),
            ));
        } else {
            available_ingredients.push(line.parse().unwrap())
        }
    }
    Database {
        fresh_ingredients,
        available_ingredients,
    }
}

#[aoc(day5, part1)]
fn part1(input: &Database) -> u64 {
    input
        .available_ingredients
        .iter()
        .filter(|i| input.fresh_ingredients.iter().any(|r| r.contains(i)))
        .count() as u64
}

#[aoc_generator(day5, part2, Naive)]
fn parse2(input: &str) -> Database2 {
    let mut fresh_ingredients = Vec::new();
    for line in input.lines() {
        if line.is_empty() {
            return Database2 { fresh_ingredients };
        }
        let (start, end) = line.split_once('-').unwrap();
        fresh_ingredients.push((start.parse().unwrap(), end.parse().unwrap()).into());
    }
    Database2 { fresh_ingredients }
}

#[aoc(day5, part2, Naive)]
fn part2(input: &Database2) -> u64 {
    let mut all_ingredients = RangeSet::new();
    for r in &input.fresh_ingredients {
        all_ingredients.add(r.clone());
    }
    all_ingredients.simplify();
    all_ingredients.ranges.iter().map(|r| r.len()).sum::<u64>()
}

#[aoc(day5, part2, RangeSet)]
fn part2_rangeset(input: &Database) -> u64 {
    let mut all_ingredients = misc::range::RangeSet::new();
    for r in &input.fresh_ingredients {
        all_ingredients.add(r);
    }
    all_ingredients.store.iter().map(|r| r.end - r.start).sum()
}

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

    const EXAMPLE: &str = "3-5
10-14
16-20
12-18

1
5
8
11
17
32";

    #[test]
    fn part1_example() {
        assert_eq!(part1(&parse(EXAMPLE)), 3);
    }

    #[test]
    fn part2_example() {
        assert_eq!(part2(&parse2(EXAMPLE)), 14);
    }

    #[test]
    fn part2_set_example() {
        assert_eq!(part2_rangeset(&parse(EXAMPLE)), 14);
    }
}