Advent of Code: Day Four

Spoilers for Advent of Code below

• Day three
• All Advent of Code posts
• Source

Day four was probably the quickest for me to complete - but mostly because the other days had primed me pretty well for this kind of task and I’d been reading about using HashSet the night before.

Part one

Given set of range pairs, find the total number of pairs in which one is a subset of the other.

So, given:

2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

I’d expect the following outputs:

false
false
false
true
true
false

The standard library makes it really easy to work with both ranges and structs, so first off I split and parse the ranges, and add them to HashSets:

fn parse_range(range: &str) -> HashSet<i32> {
	let pieces: Vec<i32> = range.split('-').map(|r| r.parse::<i32>().unwrap()).collect();
 	(pieces[0] .. pieces[1]).collect()
}

fn overlaps(ranges: &str) -> bool {
	let (a, b) = range.split(',')
		.map(parse_range)
		.collect_tuple()
		.unwrap();
}

Then, I just check if a is a superset of b, or vice-versa:

a.superset(&b) || b.superset(&a)

and tests pass! Seems to work. So I read my input file, and then filter it using this function:

let outputs: Vec<&str> = input.split('\n').filter(cleaning::range_overlaps).collect();
println!("Overlaps: {}", overlaps);

Except…

It doesn’t. My answer was wrong - after a bit of investigation, I found an example that shouldn’t have passed:

50-50,1-49

It turns out that in Rust, ranges don’t include the final index - so a range of [50 - 50] is actually an empty set, so any tests involving this would pass - because a set always contains an empty set.

I updated my parse_range code to handle this:

fn parse_range(range: &str) -> HashSet<i32> {
	let pieces: Vec<i32> = range.split('-').map(|r| r.parse::<i32>().unwrap()).collect();
	if pieces[0] == pieces[1] {
		return HashSet::from([pieces[0]]);
	}
 	(pieces[0] .. pieces[1] + 1).collect()
}

and everything passes! On to Part Two

Part two

Now find the number of entries that simply overlap, rather than are subsets.

This was a one-line change, because HashSet also has functions for this. I changed:

a.superset(&b) || b.superset(&a)

to:

!a.is_disjoint(&b)

And ran it, which turned out to be all that I needed. Day four complete, and if I remember to do tomorrow, I’ll have beaten my own high score.

Update

After reading this post from fasterthanli.me, I’ve updated my parsing code to use RangeInclusive rather than just a Range. This means that I can get rid of my preemptive assertion, as well as the incremement on my range:

fn parse_range(range: &str) -> HashSet<i32> {
	let pieces: Vec<i32> = range.split('-').map(|r| r.parse::<i32>().unwrap()).collect();
 	(pieces[0]..=pieces[1]).collect()
}