aoc 2023 day 05

main.rs

use std::{collections::BTreeMap, io::BufRead, ops::Range};

fn main() {
    let t = parse(std::io::stdin().lock());
    println!("{t:?}");

    assert_eq!(t.0, 218513636); // unsure how long, had to put the car warming up
    assert_ne!(t.1, 81956385, "high");
    assert_eq!(t.1, 81956384);
}

#[test]
fn example() {
    let input = "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";

    let (min_slot, min_slot_for_ranges) = parse_str(input);

    assert_eq!(min_slot, 35);
    assert_eq!(min_slot_for_ranges, 46);
}

#[cfg(test)]
fn parse_str(input: &str) -> (u64, u64) {
    parse(std::io::Cursor::new(input))
}

fn parse(mut input: impl BufRead) -> (u64, u64) {
    let mut s = String::new();

    let mut slots = Vec::new();

    let mut ranges = BTreeMap::new();
    let mut scratch_removed = Vec::new();
    let mut next_ranges = BTreeMap::new();

    let mut intermediate_maps = 0;

    let mut tracked = Some(82); // tracked in example output

    loop {
        s.clear();

        let read = input.read_line(&mut s).unwrap();
        if read == 0 {
            break;
        }

        if slots.is_empty() {
            let line = s.trim();
            slots.extend(
                line.split_once("seeds: ")
                    .unwrap()
                    .1
                    .split_whitespace()
                    .map(|x| x.parse::<u64>().unwrap()),
            );

            assert_eq!(slots.len() % 2, 0);

            ranges.extend(slots.chunks_exact(2).map(|slice| {
                let start = slice[0];
                let len = slice[1];
                (start, (len, 0))
            }));

            assert!(slots.len() < 64);

            s.clear();
            assert_ne!(input.read_line(&mut s).unwrap(), 0);
            assert_eq!(s, "\n");

            for (r_s, (r_len, _)) in &ranges {
                println!("seeds: {r_s}..{} ({})", r_s + r_len, r_len);
            }
        } else {
            // read and map using a map
            let mut slots_visited_round = 0u64;

            let line = s.trim();
            assert_ne!(line, "");

            intermediate_maps += 1;
            let name = line.split_once(" map:").unwrap().0;
            println!("{name} is {intermediate_maps}th");

            let mut deviations = Vec::new();

            loop {
                s.clear();
                let read = input.read_line(&mut s).unwrap();

                if read == 0 || s == "\n" {
                    // out of mappings
                    break;
                }

                let line = s.trim();

                let mut parts = line.split_whitespace().map(|x| x.parse::<u64>().unwrap());

                let dest_start = parts.next().unwrap();
                let source_start = parts.next().unwrap();
                let range_length = parts.next().unwrap();

                for (i, v) in slots.iter_mut().enumerate() {
                    let mask = 1u64 << i;
                    if slots_visited_round & mask == mask {
                        continue;
                    }

                    if *v >= source_start && *v < source_start + range_length {
                        let nth = *v - source_start;

                        *v = dest_start + nth;

                        slots_visited_round |= mask;
                    }
                }

                deviations.push((dest_start, source_start, range_length));
            }

            apply_n(
                intermediate_maps,
                &deviations,
                &mut ranges,
                &mut next_ranges,
                &mut scratch_removed,
                &mut tracked,
            );
        }

        println!();
    }

    assert_eq!(intermediate_maps, 7);

    (
        slots.iter().min().copied().unwrap(),
        *ranges.first_entry().unwrap().key(),
    )
}

type Ranges = BTreeMap<u64, (u64, usize)>;

fn apply_n(
    nth_mapping: usize,
    commands: &[(u64, u64, u64)],
    ranges: &mut Ranges,
    next_ranges: &mut Ranges,
    scratch_removed: &mut Vec<u64>,
    tracked: &mut Option<u64>,
) {
    let mut unmapped = Vec::new();

    let magnitude_before = ranges.values().map(|t| t.0).sum::<u64>();

    for (dest_start, source_start, range_length) in commands.iter().copied() {
        let mut command_printed = false;

        // FIXME: this could be range query if we were making sure that we can get all matches somehow
        for (r_s, (r_len, version)) in ranges.iter() {
            let range = *r_s..(*r_s + *r_len);
            let move_from = source_start..(source_start + range_length);
            let target = dest_start..(dest_start + range_length);

            if !command_printed {
                command_printed = true;
                println!("command: {move_from:?} -> {target:?}");
            }

            let Some(outcome) = step(dest_start, source_start, range_length, r_s, r_len) else { continue; };

            scratch_removed.push(*r_s);

            println!("    {range:?} ({r_len}): {outcome:?}");

            if let Some(tracked) = tracked.as_mut() {
                if range.contains(tracked) {
                    let mapped = step(dest_start, source_start, range_length, tracked, &1)
                        .map(|x| x.unify().0.start);

                    // split might not affect a tracked
                    if let Some(mapped) = mapped {
                        *tracked = mapped;
                    }
                }
            }

            let (mapped, now_unmapped) = outcome.unify();

            let old = next_ranges.insert(mapped.start, (mapped.end - mapped.start, nth_mapping));
            assert_eq!(old, None);

            for remains in now_unmapped.into_iter().filter_map(|x| x) {
                unmapped.push((remains.start, (remains.end - remains.start, *version)));
            }
        }

        for removed in scratch_removed.drain(..) {
            ranges.remove(&removed).unwrap();
        }

        for unmapped in unmapped.drain(..) {
            let old = ranges.insert(unmapped.0, unmapped.1);
            assert_eq!(old, None);
        }

        check_overlap(&ranges);
    }

    next_ranges.append(ranges);
    std::mem::swap(ranges, next_ranges);

    println!();
    for (r_s, (r_len, _)) in ranges.iter() {
        let range = *r_s..(*r_s + *r_len);
        if let Some(tracked) = tracked.as_ref().filter(|x| range.contains(x)) {
            println!(
                "ranges: {r_s}..{} ({r_len}) <-- tracked {} is here",
                r_s + r_len,
                tracked
            );
        } else {
            println!("ranges: {r_s}..{} ({r_len})", r_s + r_len);
        }
    }

    let magnitude_after = ranges.values().map(|t| t.0).sum::<u64>();

    assert_eq!(magnitude_before, magnitude_after);

    check_overlap(ranges);
}

fn check_overlap(ranges: &Ranges) {
    let mut prev: Option<(&u64, &u64)> = None;
    for (r_s, (r_len, _)) in ranges.iter() {
        if let Some((prev_start, prev_len)) = prev {
            assert!(
                prev_start + prev_len <= *r_s,
                "ranges overlap: {:?} vs. {:?}",
                *prev_start..(prev_start + prev_len),
                *r_s..(r_s + r_len)
            );
        }

        prev = Some((r_s, r_len));
    }
}

fn contains(our: &Range<u64>, their: &Range<u64>) -> bool {
    our.contains(&their.start) && (our.contains(&their.end) || our.end == their.end)
}

fn overlaps_left(our: &Range<u64>, their: &Range<u64>) -> bool {
    their.contains(&our.start) && our.contains(&their.end)
}

fn overlaps_right(our: &Range<u64>, their: &Range<u64>) -> bool {
    our.contains(&their.start) && our.end <= their.end
}

#[test]
fn range_moves_completly() {
    let mut ranges = BTreeMap::from([(1, (10, 0)), (55, (68 - 55, 0)), (79, (93 - 79, 0))]);

    let command = (52, 50, (98 - 50));

    apply_test(1, command, &mut ranges);

    assert_eq!(
        ranges,
        BTreeMap::from([(1, (10, 0)), (57, (70 - 57, 1)), (81, (95 - 81, 1))])
    );
}

#[test]
fn range_moves_completly2() {
    let mut ranges = make_ranges([10..20], 0);

    let command = (40, 5, 15);

    apply_test(1, command, &mut ranges);

    let expected = make_ranges([45..55], 1);

    assert_eq!(ranges, expected);
}

#[test]
fn left_part_of_range_moves() {
    // ranges: 57..70 (13)
    // ranges: 81..95 (14)
    let mut ranges = make_ranges([1..11, 53..54, 57..70, 81..95], 0);

    // fertilizer-to-water is 3th
    // command: 53..61 -> 49..57
    let command = (49, 53, (61 - 53));

    apply_test(1, command, &mut ranges);

    // ranges: 53..58 (5)
    // ranges: 62..70 (8)
    // ranges: 81..95 (14)

    let mut moved = make_ranges([49..50, 53..57], 1);
    moved.append(&mut make_ranges([1..11, 61..70, 81..95], 0));

    assert_eq!(ranges, moved);
}

#[test]
fn right_part_of_range_moves() {
    for command in [(75, 65, 6), (75, 65, 5)] {
        right_part_of_range_moves_scenario(command);
    }
}

#[cfg(test)]
fn right_part_of_range_moves_scenario(command: (u64, u64, u64)) {
    let mut ranges = make_ranges([1..11, 57..70, 81..95], 0);

    apply_test(1, command, &mut ranges);

    let mut moved = make_ranges([75..80], 1);
    moved.append(&mut make_ranges([1..11, 57..65, 81..95], 0));

    assert_eq!(ranges, moved);
}

#[test]
fn non_overlapping_before_does_not_move() {
    let orig = make_ranges([10..20], 0);
    let mut ranges = orig.clone();

    apply_test(1, (0, 5, 5), &mut ranges);

    assert_eq!(orig, ranges);
}

#[test]
fn non_overlapping_after_does_not_move() {
    let orig = make_ranges([10..20], 0);
    let mut ranges = orig.clone();

    apply_test(1, (0, 20, 5), &mut ranges);

    assert_eq!(orig, ranges);
}

#[test]
fn regress_should_had_split_right() {
    // command: 77..100 -> 45..68
    //     looking at 46..51 <-- regress_should_had_split_right_but_overlaps
    //     looking at 55..63
    //     looking at 74..88
    let mut ranges = make_ranges([56..63, 74..88], 0);

    apply_test(1, (45, 77, 100 - 77), &mut ranges);

    let mut expected = make_ranges([56..63, 74..77], 0);
    expected.append(&mut make_ranges([45..56], 1));

    assert_eq!(ranges, expected);
}

#[test]
fn split_within() {
    let mut ranges = make_ranges([0..10], 1);

    apply_test(1, (15, 4, 2), &mut ranges);

    assert_eq!(ranges, make_ranges([0..4, 6..10, 15..17], 1));
}

#[cfg(test)]
fn make_ranges<const N: usize>(ranges: [Range<u64>; N], version: usize) -> Ranges {
    let res = ranges
        .into_iter()
        .map(|x| (x.start, (x.end - x.start, version)))
        .collect::<Ranges>();
    assert_eq!(res.len(), N);
    res
}

#[cfg(test)]
fn apply_test(nth_mapping: usize, command: (u64, u64, u64), ranges: &mut Ranges) {
    apply_n(
        nth_mapping,
        &[command],
        ranges,
        &mut BTreeMap::new(),
        &mut Vec::new(),
        &mut None,
    );
}

#[test]
fn yet_more_wrong() {
    // fertilizer-to-water is 3th
    // command: 53..61 -> 49..57
    let mut ranges = make_ranges([57..70], 0);
    let expected = make_ranges([53..57, 61..70], 0);

    apply_test(0, (49, 53, 8), &mut ranges);

    assert_eq!(ranges, expected);
}

#[test]
fn still_failing() {
    let a = 0..18647226;
    let b = 1..6421610;

    assert!(!contains(&b, &a));
}

#[test]
fn step_something() {
    // command: 56..93 -> 60..97
    //    looking at 46..57 (11)
    let mut ranges = make_ranges([46..57], 0);

    apply_test(1, (60, 56, 93 - 56), &mut ranges);

    let mut expected = make_ranges([46..56], 0);
    expected.append(&mut make_ranges([60..61], 1));

    assert_eq!(ranges, expected);
}

#[derive(Debug)]
enum Outcome {
    MappedFully {
        mapped: Range<u64>,
    },
    Split2 {
        mapped: Range<u64>,
        unmapped: Range<u64>,
    },
    Split3 {
        mapped: Range<u64>,
        unmapped: [Option<Range<u64>>; 2],
    },
}

impl Outcome {
    fn unify(self) -> (Range<u64>, [Option<Range<u64>>; 2]) {
        use Outcome::*;
        match self {
            MappedFully { mapped } => (mapped, [None, None]),
            Split2 { mapped, unmapped } => (mapped, [Some(unmapped), None]),
            Split3 { mapped, unmapped } => (mapped, unmapped),
        }
    }
}

fn step(
    dest_start: u64,
    source_start: u64,
    range_length: u64,
    r_s: &u64,
    r_len: &u64,
) -> Option<Outcome> {
    let range = *r_s..(*r_s + *r_len);
    let move_from = source_start..(source_start + range_length);
    if contains(&move_from, &range) {
        let source_diff = *r_s - source_start;

        let mapped_start = dest_start + source_diff;
        let mapped = mapped_start..(mapped_start + *r_len);

        Some(Outcome::MappedFully { mapped })
    } else if overlaps_left(&range, &move_from) {
        let left_start = source_start.max(*r_s);

        // when writing this originally, smuggled in a +-1 here on the line below. it seemed
        // reasonable. with that, you will get the correct example phase2 result. I did not put it
        // to the overlaps_right version...
        let left_len = range_length - (left_start - source_start);

        let right_start = left_start + left_len;
        let right_len = *r_len - left_len;

        let moved_left_start = dest_start + (left_start - source_start);

        let mapped = moved_left_start..(moved_left_start + left_len);
        let unmapped = right_start..(right_start + right_len);
        Some(Outcome::Split2 { mapped, unmapped })
    } else if overlaps_right(&range, &move_from) {
        let left_start = *r_s;
        let right_start = source_start;

        let left_len = right_start - left_start;
        let right_len = *r_len - left_len;

        let moved_right_start = dest_start + (source_start - right_start);

        let mapped = moved_right_start..(moved_right_start + right_len);
        let unmapped = left_start..(left_start + left_len);

        Some(Outcome::Split2 { mapped, unmapped })
    } else if contains(&range, &move_from) {
        // we can only map a subset

        let unmapped1 = if range.start != move_from.start {
            Some(range.start..move_from.start)
        } else {
            None
        };

        let mapped = dest_start..(dest_start + move_from.end - move_from.start);

        let unmapped2 = if move_from.end != range.end {
            Some(move_from.end..range.end)
        } else {
            None
        };

        Some(Outcome::Split3 {
            mapped,
            unmapped: [unmapped1, unmapped2],
        })
    } else {
        let their = move_from;

        assert!(
            !range.contains(&their.start),
            "{range:?} should not contain the start of {their:?}"
        );
        if let Some(last) = their.end.checked_sub(1).filter(|&x| x > their.start) {
            assert!(
                !range.contains(&last),
                "{range:?} should not contain the end of {their:?}"
            );
        }
        None
    }
}