Advent of Code 2023 Days 5 and 6 Highlights

The days 5 and 6 were the least enjoyable for me so far. 6 was a bit too simple, and 5 was IMO slightly overloaded for the early part of the AoC + there was a lot of careful +/-1 stuff there, which … few people enjoy :) But on the flip side, I used Rust for the day 5 and Python (with Jupyter) for the day 6.

Let’s take a brief look at those solutions.

Day 5 in Rust

Code

The parsing was mildly annoying, and probably can be simplified, but in the end we just arrive at these struct:

#[derive(Debug)]
pub struct Input {
    seeds: Vec<u64>,
    maps: HashMap<Category, Vec<RangeMap>>,
}

#[derive(Debug, Clone)]
pub struct RangeMap {
    destination: Category,
    source_range: RangeInclusive<u64>,
    destination_range: RangeInclusive<u64>,
}

Where Category is an enum (Seed, Soil, etc.) and the source and destination ranges are expressed as std::ops::RangeInclusive<u64> type. We also store a vector of seeds and each RangeMap is stored in a hashmap with a key being the source Category.

The part 1 is easy enough, I went for an iterative solution for mapping seed ids to locations, but it can also be done with fold. We select the answer with a min() call.

The part 2 was the concentration of pain and long debugging :) The key idea is that each of the incoming ranges can be split into sub-ranges each of which will be processed by a single RangeMap or by no RangeMap at all. This way, we can directly map each of the new splitted source ranges to a destination range. Implementing this sub-range splitting logic was the tricky part:

fn intersect_with(this: &RangeInclusive<u64>, other: &RangeInclusive<u64>) -> Vec<RangeInclusive<u64>> {
    // this is outside other => no split
    if (this.start() < other.start() && this.end() < other.start())
        || (this.start() > other.end() && this.end() > other.end())
    {
        vec![this.clone()]
    // this intersects other from the end and this's end is contained inside other
    } else if this.start() < other.start() && this.end() <= other.end() {
        vec![*this.start()..=(*other.start() - 1), *other.start()..=*this.end()]
    // ranges overlap [other.start(), this.start(), other.end(), this.end()]
    } else if this.start() > other.start() && this.start() < other.end() && this.end() > other.end() {
        vec![*this.start()..=*other.end(), (*other.end() + 1)..=*this.end()]
    // this starts in other and continues beyond other
    } else if this.start() >= other.start() && this.end() > other.end() {
        vec![*this.start()..=*other.end(), (*other.end() + 1)..=*this.end()]
    // this is fully contained in other
    } else if this.start() >= other.start() && this.end() <= other.end() {
        vec![this.clone()]
    } else {
        panic!("unexpected condition: this = {:?}, other = {:?}", this, other);
    }
}


// split the ranges in such a way that each new range will be mapped to the destination via the same map
// or without using any maps
fn split_ranges_based_on_map_ranges(
    ranges: Vec<RangeInclusive<u64>>,
    map_ranges: impl Iterator<Item = RangeInclusive<u64>>,
) -> Vec<RangeInclusive<u64>> {
    let mut new_ranges = ranges;

    for map_source_ids_range in map_ranges {
        let mut new_ranges_updated = HashSet::new();

        for range in &new_ranges {
            for intersection_range in intersect_with(range, &map_source_ids_range) {
                new_ranges_updated.insert(intersection_range);
            }
        }

        new_ranges = new_ranges_updated.into_iter().collect();
    }

    new_ranges
}

To transform individual values and ranges (when both ends are guaranteed to be transformed by the same map) we can use these functions:

fn apply_maps(value: u64, maps: &[RangeMap]) -> u64 {
    match maps.iter().find(|m| value >= *m.source_range.start() && value <= *m.source_range.end()) {
        Some(m) => value + m.destination_range.start() - m.source_range.start(),
        None => value,
    }
}

fn to_desintation_range(this: RangeInclusive<u64>, maps: &[RangeMap]) -> RangeInclusive<u64> {
    apply_maps(*this.start(), maps)..=apply_maps(*this.end(), maps)
}

Putting it together, we arrive at the solution for the part 2:

pub fn p2(input: &Input) -> u64 {
    let mut ranges = input.seeds.chunks(2).map(|chunk| chunk[0]..=(chunk[0] + chunk[1] - 1)).collect::<Vec<_>>();

    for source_category in [Seed, Soil, Fertilizer, Water, Light, Temperature, Humidity] {
        let maps = input.maps.get(&source_category).unwrap();
        let new_ranges = split_ranges_based_on_map_ranges(ranges, maps.iter().map(|m| m.to_source_ids_range()));
        ranges = new_ranges.into_iter().map(|range| to_desintation_range(range, maps)).collect::<Vec<_>>();
    }

    ranges.into_iter().map(|r| *r.start()).min().unwrap()
}

Day 6 in Python with Jupyter

Code

The task was quite trivial. I just used brute-force for part 2, and since it finished in 4.4 seconds for me, I didn’t feel much need to optimize it further or even to write a parser/input pre-processing for the part 2 :)