After a 15-minute late start (once again), I solved today’s problem in less than 2 hours, and I got a slightly better rank than yesterday.

Input

The input file is a list of vent coordinates, with the following format :

x_start,y_start -> x_end_x,y_end

where x_start, y_start, x_end, y_end are integers.

I chose not to use regular expressions for this task, and to rely on the split() method instead.

Data structures

Nothing very complicated here. Points on the map are defined as structs containing two integers, and vents are defined as structs containing two Point structs. Note the traits PartialEq, Eq, and Hash of the Point struct, needed to use Points as keys in a HashMap.

#[derive(Copy, Clone, PartialEq, Eq, Hash)]
pub struct Point {
    x: i64,
    y: i64
}

pub struct Vent {
    start: Point,
    end: Point
}

We will define two methods for the Vent struct : a method new(), that parses a line of input data, and a method covered_points(), where all the calculations for a given Vent are performed.

Part 1

Vents can either be :

For the part 1, diagonal vents are ignored.

For each vent, we compute the list of covered points. This calculation is done in 3 steps :

Step 1 : determine if the vent is horizontal, vertical or diagonal. We use an Option here. If the vent is neither horizontal nor vertical nor diagonal, the increment is set to None. Furthermore, for the part 1 of this problem, the increment is also set to None for diagonal vents.

let vent_vector = (self.end.x - self.start.x, self.end.y - self.start.y);

let increment = if vent_vector.0 == 0 && vent_vector.1 != 0 { /* Vertical vent */
    Some((0, 1))
}
else if vent_vector.1 == 0 && vent_vector.0 != 0 { /* Horizontal vent */
    Some((1, 0))
}
else if !no_diagonals && vent_vector.0 / vent_vector.1 == 1 { /* Diagonal vent, from the bottom left */
    Some((1, 1))
}
else if !no_diagonals && vent_vector.0 / vent_vector.1 == -1 { /* Diagonal vent, from the upper left */
    Some((1, -1))
}
else {
    None
};

Step 2 : determine the starting point (i.e the leftmost point, and the bottommost point for vertical vents)

let start_point = if self.end.x > self.start.x ||
    self.end.x == self.start.x && self.end.y > self.start.y {
    self.start
}
else {
    self.end
};

Step 3 : If the vent can be taken into account (i.e if the increment variable is not None), calculate the vent length, and add the length covered points, one by one.

let mut covered = Vec::new();
if increment.is_some() {
    let length = vent_vector.0.abs().max(vent_vector.1.abs());
    for i in 0..=length {
        covered.push(Point {
            x: start_point.x + i * increment.unwrap().0, 
            y: start_point.y + i * increment.unwrap().1})
    }
}

The overall covered points list calculation is done in the main function. Finally, the points list is filtered to keep “dangerous” points.

let mut overall_covered = HashMap::<Point, i64>::new();

for line in input {
	let vent = Vent::new(line);

	for point in vent.covered_points(true) {
	    overall_covered.insert(point, overall_covered.get(&point).unwrap_or(&0) + 1);
	}
}

overall_covered.values().filter(|x| **x > 1).count()

Part 2

This time, diagonal vents are taken into account.

The solve_part2() function is almost identical to the solve_part1() function. The only difference is that the method covered_points is called with the

Performances

The code is a bit slow in my opinion (several hundreds of milliseconds for both parts on my new laptop). This is probably caused by the HashMap usage, with the default hasher function (SipHash). I will try to profile the code, and to make performance tests with other hash functions.