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
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
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 :)
If you enjoyed this content, you can sponsor me on Github to produce more videos / educational blog posts.
And if you're looking for consulting services, feel free to contact me .