fertilizer.rs

//
// Advent of Code 2023 - Day 5: If You Give A Seed A Fertilizer
//
use std::ops::Range;
use std::cmp::min;

fn main() {
    // replace CR LF with LF, to run nicely on windows also,
    let input = include_str!("input.txt").replace("\r\n", "\n");

    // split input into chunks separated by two new-lines,
    let chunks: Vec<&str> = input.split("\n\n").collect();

    // the first chunk will be the input seeds,
    let seeds: Vec<i64> = chunks[0]
        .split(' ')
        .filter_map(|s| s.parse::<i64>().ok())
        .collect();

    // container for each category, in turn containing a vector of tuples representing the ranges
    let mut categories: Vec<Vec<(Range<i64>, Range<i64>)>> = Vec::new();
    let mut category_names: Vec<(&str, &str)> = Vec::with_capacity(chunks.len()-1);

    // the other chunks will be all the mappings
    for chunk in chunks.iter().skip(1) {
        let mut lines = chunk.lines();
        let from_to: Vec<&str> = lines
            .next()
            .expect("...")
            .split(|c| c == '-' || c == ' ')
            .enumerate()
            .filter_map(|(i, s)| if i % 2 == 0 {Some(s)} else {None})
            .collect();

        category_names.push((from_to[0], from_to[1]));
        
        let mut ranges: Vec<(Range<i64>, Range<i64>)> = Vec::new();
        // the other lines in the chunk should hold all the mapping ranges,
        for line in lines {
            let r: Vec<i64> = line
                .split(' ')
                .filter_map(|s| s.parse::<i64>().ok())
                .collect();
            let target = r[0]..r[0]+r[2];
            let source = r[1]..r[1]+r[2];
            ranges.push((target, source));
        }
        categories.push(ranges.clone());
    }

    // let's make our input data imutatable,
    let categories = categories;

    let mut min_location: i64 = i64::MAX;
    for seed in &seeds {
        // make two temporary numbers, i and o, for input and output in each mapping.
        let mut i = *seed;
        let mut o = i;
        for category in &categories {
            for (target, source) in category {
                if source.contains(&i) {
                    o = (i - source.start) + target.start;
                    break;  // assuming the ranges never overlap, we can break after we've found
                            // one.
                } else {
                    o = i;
                }
            }
            i = o;
        }
        min_location = min(min_location, i);
    }

    println!("Part one: {}", min_location);

    // for the second part, the inital seeds describes pairs of range start and range length,
    let seed_ranges: Vec<Range<i64>> = seeds.chunks(2).map(|x| x[0]..x[0]+x[1]).collect();

    // we are still looking for the lowest value at the end,
    let mut min_location = i64::MAX;
    for seed_range in seed_ranges {
        let mut ranges = vec![seed_range.clone()];
        for (category, names) in categories.iter().zip(&category_names) {
            println!("{}-to-{}", names.0, names.1);
            let mut output: Vec<Range<i64>> = Vec::new();
            for range in &ranges {
                let mut range = range.clone();
                for (target, source) in category {
                    let offset = target.start - source.start;
                    // if the range is fully inside the source range, just map that range
                    if source.start <= range.start && range.end <= source.end {
                        println!("{:?} fully inside {:?}", range, source);
                        output.push(range.start+offset..range.end+offset);
                        println!("Mapping it to => {:?}", range.start+offset..range.end+offset);
                        // make the range empty,
                        range.start = 0;
                        range.end = 0;
                        break;
                    }
                    else if source.start <= range.start && range.start <= source.end {
                        println!("{:?} start is inside {:?}", range, source);
                        output.push(range.start+offset..source.end+offset);
                        println!("Mapping it to => {:?}", range.start+offset..source.end+offset);
                        // cut off the overlapping part,
                        range.start = source.end;
                    }
                    else if source.start <= range.end && range.end <= source.end {
                        println!("{:?} end is inside {:?}", range, source);
                        output.push(source.start+offset..range.end+offset);
                        println!("Mapping it to => {:?}", source.start+offset..range.end+offset);
                        range.end = source.start;
                    }
                }
                if !range.is_empty() {
                    println!("No mapping found for {:?}", range);
                    output.push(range);
                }
            }

            if !output.is_empty() {
                ranges = output;
            } else {
                println!("No overlaps found so ranges {:?} are unchanged...", ranges);
            }

            println!();
        }

        println!();
        // get the lowest range start
        for range in ranges {
            min_location = min(min_location, range.start);
        }
    }

    println!("Part two: {}", min_location);
}