Today’s puzzle was similar in difficulty than yesterday puzzle. I spent about 50 minutes for part 1, and 2 hours and a half for part 2.

the input data is an array of numbers (from 0 to 9) representing an heightmap. The puzzle objective is to discover “low points” on the map, (i.e points lower than all their neighbours), and to compute their respective basins.

Data structure.

The first version of my code was too slow for my standards, so I reengineered it before sending my answer for part 2.

I used a little trick I learned some years ago by studying chess programs. The map is represented as a 2-dimensional Vector of Option<usize>. and a border is added to the regular heightmap (the first and the last row, plus the first and the last column).

For locations in the heightmap, we set heightmap[i][j] = Some(height), and for locations on the border, we set heightmap[i][j] = None.

This trick accelerates the “border control”, to check whether a map location is on the border.

Part 1

This is the easy part of the puzzle. The objective is to find “low points” on the map, i.e points lower than all their neighbours.

pub fn is_lowpoint(heightmap: Vec<Vec<Option<usize>>>, row: usize, col: usize) -> bool {
    let min_neighbour = (0..4)
        .map(|dir| heightmap[(row as isize + DIRS[dir].0) as usize][(col as isize + DIRS[dir].1) as usize])
        .filter(|x| x.is_some())
        .map(|x| x.unwrap())
        .min().unwrap();
    min_neighbour > heightmap[row][col].unwrap()
}

Each time we encounter a low point, we add this point height plus 1 to the output value.

pub fn solve_part1(input: &Vec<String>) -> usize {
    let heightmap = parse_heightmap(input);

    let mut low_points_sum = 0;
    for i in 1..heightmap.len()-1 {
        for j in 1..heightmap[i].len()-1 {
            if is_lowpoint(heightmap.clone(), i, j) {
                low_points_sum += heightmap[i][j].unwrap() + 1;
            }
        }
    }

    low_points_sum
}

Part 2

Like yesterday, the part 2 was more challenging. First, I tried a recursive depth-first search algorithm, but I discarded it and changed for a breadth-first search algorithm.

The basin calculation function returns a HashSet of tuples, representing basin squares coordinates. This HashSet is initialized with the basin low point. Then, we search low point neighbours and we add them to the set. We repeat the operation in searching the neighbours of the last added points (i.e points higher than the last added points, except if their height equals 9), until no new point can be added to the set.

pub fn basin(heightmap: Vec<Vec<Option<usize>>>, row: usize, col: usize) -> HashSet<(usize, usize)> {
    let mut squares = HashSet::<(usize, usize)>::new();
    squares.insert((row, col));
    let mut last_loop_squares = squares.clone();
    
    loop {
        let mut new_squares = HashSet::<(usize, usize)>::new();
        
        for sq in &last_loop_squares {
            for dir in 0..4 {
                let new_row = (sq.0 as isize + DIRS[dir].0) as usize;
                let new_col = (sq.1 as isize + DIRS[dir].1) as usize;
                match heightmap[new_row][new_col] {
                    Some(9) | None => {},
                    Some(h) => { 
                        if h > heightmap[sq.0][sq.1].unwrap() {
                            new_squares.insert((new_row, new_col)); 
                        }
                    }
                }
            }
        }
        
        if new_squares.len() == 0 {
            return squares;
        }
        squares = squares.union(&new_squares).cloned().collect::<HashSet<(usize, usize)>>();
        last_loop_squares = new_squares.clone();
    }
}

In the main function, we first look for “low points”, exactly like the part 1. Each time a low point is detected, the basin computation function is called. Finally, all we have left to do is to build a vector with basins sizes, sort it and return the product of the first 3 elements.

pub fn solve_part2(input: &Vec<String>) -> u64 {
    let heightmap = parse_heightmap(input);
    let mut basins = Vec::<HashSet<(usize, usize)>>::new();

    for i in 1..heightmap.len()-1 {
        for j in 1..heightmap[i].len()-1 {
            if is_lowpoint(heightmap.clone(), i, j) {
                basins.push(basin(heightmap.clone(), i, j));
            }
        }
    }

    let mut basins_sizes = basins.iter().map(|s| s.len()).collect::<Vec<usize>>();
    basins_sizes.sort();
    basins_sizes = basins_sizes.iter().rev().cloned().collect::<Vec<usize>>();
    basins_sizes[0] as u64 * basins_sizes[1] as u64 * basins_sizes[2] as u64
}

Performances

The part 1 runs in 90 ms, and the part 2 in 130 ms. The first version on my code, without the little trick on the data structure, is about 6 times slower.