Advent of Code 2023 Day 11 Highlights

Day 11 was a chill and easy exercise compared to the previous day. I decided to do it in Rust, not because I felt like it will be the best option for the task (Julia would’ve been shorter here), but because I wanted to stretch my Rust legs a bit :)

Code

Seeing “find the shortest distance” one might think that we need to do something like Dijkstra or something akin to it. Thankfully, we have no obstacles, and the permitted movements (up, down, left, and right) imply that the minimal distance is always equal to the Manhattan distance between points.

The only trick we need to add to solve part 1 is to keep track of the empty rows and columns. We can do it directly during parsing:

use std::collections::{HashMap, HashSet};

#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
pub struct Galaxy {
    row: usize,
    col: usize,
}

#[derive(Debug, Clone)]
pub struct Image {
    galaxies: Vec<Galaxy>,
    expanded_rows: HashSet<usize>,
    expanded_cols: HashSet<usize>,
}

pub fn parse_input(input: &str) -> Image {
    let rows = input.trim().split("\n").collect::<Vec<_>>();
    let mut expanded_rows = (0..rows.len()).into_iter().collect::<HashSet<_>>();
    let mut expanded_cols = (0..rows[0].len()).into_iter().collect::<HashSet<_>>();
    let mut galaxies = vec![];

    for (row, cells) in rows.into_iter().enumerate() {
        for (col, ch) in cells.trim().chars().enumerate() {
            match ch {
                '#' => {
                    galaxies.push(Galaxy { row, col });
                    expanded_rows.remove(&row);
                    expanded_cols.remove(&col);
                }
                _ => (),
            }
        }
    }

    Image { galaxies, expanded_rows, expanded_cols }
}

To account for the expanded rows and columns, we will add 1 for each of those we encounter in the inclusive ranges between the rows and columns of the galaxies we are comparing. It’s important to remember that we should count from the smaller value to the larger value, otherwise our range will be empty. We can use min and max functions to ensure it.

let walked_rows = row1.min(row2)..=row2.max(row1);
for expanded_row in &image.expanded_rows {
    if walked_rows.contains(expanded_row) {
        dist += 1;
    }
}

And to avoid duplicate counting of distances, we use a nested loop whose loop variable starts one away from the top-level loop’s variable value. This will give us pairs of ids like:

(0, 1)
(0, 2)
...
(0, 9)

(1, 2)
(1, 3)
...
(1, 9)

...

(8, 9)

Let’s put it together:

pub fn distances(image: &Image, factor: usize) -> (HashMap<(usize, usize), usize>, usize) {
    let mut sum = 0;
    let mut pairwise = HashMap::new();

    for id1 in 0..image.galaxies.len() {
        for id2 in (id1 + 1)..image.galaxies.len() {
            let &Galaxy { row: row1, col: col1 } = &image.galaxies[id1];
            let &Galaxy { row: row2, col: col2 } = &image.galaxies[id2];

            let mut dist = row2.abs_diff(row1) + col2.abs_diff(col1);

            let walked_rows = row1.min(row2)..=row2.max(row1);
            for expanded_row in &image.expanded_rows {
                if walked_rows.contains(expanded_row) {
                    dist += factor;
                }
            }

            let walked_cols = col1.min(col2)..=col2.max(col1);
            for expanded_col in &image.expanded_cols {
                if walked_cols.contains(expanded_col) {
                    dist += factor;
                }
            }

            sum += dist;
            pairwise.insert((id1, id2), dist);
        }
    }

    (pairwise, sum)
}

We are using factor here, because we can use this function to solve the second part as well. In part 1 factor will always be 1, but in part 2 for test cases we use 9 (“10 times larger”) and 99 (“100 times larger”), and for the actual solution we use 1000000 - 1:

pub fn p1(image: &Image) -> (HashMap<(usize, usize), usize>, usize) {
    distances(image, 1)
}

pub fn p2(image: &Image) -> (HashMap<(usize, usize), usize>, usize) {
    distances(image, 1000000 - 1)
}