Advent of code 2021: Day 9

This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.

In this article I'll be solving: Advent of code 2021: Day #9.

Part 1

I receive an input file with a height map about “lava tubes”. The goal here is to determine the low points of the height map. A low point is defined as a point to which the surrounding points are all higher than said point. We only have to consider the horizontal and vertical surrounding points. An example is presented:

The puzzle explains that there are 4 low points in this example. The 1 at position 0,1, the 0 at position 0,9, the 5 at position 2,2 and the 5 at position 4,6.

The risk level is the sum of each low point + 1. Determine the risk level of the input file.

The first part is determining the low points:

fn get_points(grid: &Vec<Vec<i32>>, y: usize, x: usize) -> Vec<i32> {
    let directions = vec![(1, 0), (0, -1), (0, 1), (-1, 0)];

    directions.iter().map(|(dy, dx)| {
        let temp = vec![];
        let y = y as i32 + dy;
        let x = x as i32 + dx;
        let y_row = grid.get(y as usize).unwrap_or(&temp);

        *y_row.get(x as usize).unwrap_or(&10)
    }).collect()
}

fn low_points(heightmap: &Vec<Vec<i32>>) -> i32 {
    let grid_height = heightmap.len();
    let grid_width = heightmap[0].len();
    let mut low_points = vec![];
    let mut total_sum = 0;

    for y in 0..grid_height {
        for x in 0..grid_width {
            let current_min = heightmap[y as usize][x as usize];
            let surrounded: i32 = *get_points(&heightmap, y, x)
                .iter()
                .min()
                .unwrap();

            if current_min < surrounded {
                total_sum += (current_min + 1)
            }
        }
    }

    total_sum
}

I have to take into account the fact that an edge point is missing some surrounding points, so I’ll assume those values are all the height of 10 to make them reasonably higher than the would-be minimum.

Part 2

The next part is where things get slightly more tricky. Each low point, is part of a basin. A basin is surrounded by 9’s, calculate the total area of each basin and multiply the 3 largest basin sizes.

The way I approached this problem is by taking the coordinates of a low point, look at the surrounding area, add the surrounding coordinates to a list which aren’t edges or 9’s. For each point added to the list, do the same trick again for these new points, remove the duplicates from the list and repeat until no more new points found. I was struggling a bit with setting this up. Initially, my code for part 2 looked like this. Looks pretty bad, doesn’t it? Eventually, after a lot of refactorings, I ended up with the code below:

fn basin_size(heightmap: &Grid, y: i32, x: i32) -> usize {
    let mut points = vec![(y, x)];
    let mut start = 0;

    while start < points.len() {
        let (py, px) = points[start];
        let mut findable: Vec<(i32, i32)> =
            get_points(&heightmap, py as usize, px as usize)
                .iter()
                .filter(|&&(y, x, p)| p < 9 && !points.contains(&(y, x)))
                .map(|&(y, x, _)| (y, x))
                .collect();

        points.append(&mut findable);
        start += 1;
    }

    points.len()
}

fn max_basins_size(heightmap: &Grid) -> u32 {
    let mut basin_sizes: Vec<usize> = low_points(heightmap)
        .iter()
        .map(|&(y, x, _)| basin_size(heightmap, y as i32, x as i32))
        .collect();

    basin_sizes.sort_by(|a, b| b.cmp(a));
    basin_sizes[0..3].iter().fold(1, |acc, a| acc * a) as u32
}

#[test]
fn test_max_basins_size() {
    let heightmap = vec![
        vec![2, 1, 9, 9, 9, 4, 3, 2, 1, 0],
        vec![3, 9, 8, 7, 8, 9, 4, 9, 2, 1],
        vec![9, 8, 5, 6, 7, 8, 9, 8, 9, 2],
        vec![8, 7, 6, 7, 8, 9, 6, 7, 8, 9],
        vec![9, 8, 9, 9, 9, 6, 5, 6, 7, 8]
    ];

    assert_eq!(max_basins_size(&heightmap), 1134);
}

The way this works: you make a list with one point (y, x) and set a counter to 0. To start the loop, you test if the counter is smaller than the list size, which equals to true the first time around because there’s one element in the list. In this loop, we fetch the coordinates from the list and check the surrounding top, bottom, left and right coordinates and test if they are lower than 9 and if it hasn’t encountered a point like it before. That list of points is appended to the initial list and the counter is increased by 1 etc. To give an example of the steps:

counter 0: {p1}
  Check surroundings of p1:
counter 1: {p1, p1.1, p1.2, p1.3}
  Check surroundings of p1.1:
counter 2: {p1, p1.1, p1.2, p1.3, p1.1.1, p1.1.2}
  check surroundings of p1.2:
etc.

After a while no more new points will be found, so the counter will increase, but the list will stop increasing, and it will eventually stop.

The full solution is available on GitHub.

17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1