Day 11- Cosmic Expansion

Now that you’re out of the maze, you come to an observatory, where you need to find the shortest distance between galaxies.

As always, the complete problem definition is here, but in general, you have a map of the universe, which shows where galaxies are. You first have to account for the expansion of the universe since the image was compiled, then figure out the shortest Manhattan distance between each pair of galaxies. Add those up for the answer.

Approach

This appeared to be a simple text manipulation problem to me — it’s solvable in a fairly straightforward manner.

Reading the input file into a Vec<Vec<char>> was the first step. After that, you expand the universe according to the rules (only expand rows or columns that do not contain any galaxies). Then, you find the distance between each pair of galaxies, and add them up for a final answer.

Part 1

The expansion of the universe occurs by only expanding rows and columns which are devoid of galaxies, so a couple of helper functions to identify those are in order. Here’s an example:

fn column_empty(universe: &Vec<Vec<char>>, col: usize) -> bool{
    for y in 0..universe.len(){
        if universe[y][col] == '#' { return false; }
    }
    true;
}

Pulling those into another helper which handles the actual expansion is a good idea as well:

fn expand(universe: &mut Vec<Vec<char>>){
    // Check the columns first
    for x in (0..universe[0].len()).rev(){
        if column_empty(&universe, x){
            for y in 0..universe.len(){
                universe[y].insert(x, '.');
            }
        }
    }

    // Now we can check the rows
    for y in (0..universe.len()).rev(){
        if row_empty(&universe, y){
            universe.insert(y, vec!['.'; universe[y].len()])
        }
    }
}

This might have been better written by taking ownership of universe and returning it, but I was still fighting Rust norms.

Once the universe has been expanded, you need to find where all the galaxies are. A Vec<(usize, usize)> will track the position of each one:

let mut galaxies: Vec<(usize, usize)> = vec![];
for y in 0..universe.len(){
    for x in 0..universe[y].len(){
        if universe[y][x] == '#'{
            galaxies.push((x,y));
        }
    }
}

Now that you’ve found them all, it’s a simple matter to find and sum the distances between each pair:

for first in 0..galaxies.len()-1{
    for second in first+1..galaxies.len(){
        let mut xdist = galaxies[first].0.abs_diff(galaxies[second].0);
          let mut ydist = galaxies[first].1.abs_diff(galaxies[second].1);
        sum += xdist + ydist;
    }
}

sum

Notice the loops. Because you only need to calculate one distance for each pair of galaxies, the structure of these nested loops ensure you do just that. You will only ever compare first=1 to second=2, and never see first=2 compared to second=1.

Part 2

Ahhh, the dreaded Part 2 Complication!

Apparently, the expansion took place over a much longer period of time — instead of expanding each row and column to make them twice as big, they need to be one million times bigger.

However, you still need to calculate the same distances and sum as before.

Now, of course, you can’t simply add $1,000,000$ empty rows and columns to a Vec<> for every empty row and column you find there. So that means you have to find another way to track them. So, rather than actually expand the universe as you did in part 1, maybe you can just track where the expansions should go.

You can use your column_empty() and row_empty() functions to create a Vec<usize> containing all the empty columns and rows in the universe, like this:

fn find_empty_cols(universe: &Vec<Vec<char>>) -> Vec<usize>{
    let mut ec = vec![];
    for column in 0..universe[0].len(){
        if column_empty(universe, column){
            ec.push(column);
        }
    }
    ec
}

Now you can use that to determine how many empty columns or rows exist between any two galaxies:

fn find_expansions(er: &Vec<usize>, x1: usize, x2: usize) -> usize{
    let lo = usize::min(x1, x2);
    let hi = usize::max(x1, x2);

    let mut count = 0;
    for r in er{
        if lo < *r && hi > *r {
            count += 1;
        }
    }
    count
}

Here, er is the list of empty rows or columns, and x1 and x2 are the row or column coordinates for the two galaxies. If a row or column is between the lo and hi values, you count it.

Now, you can use that number to figure out the distance between each galaxy, using the same loops:

for first in 0..galaxies.len()-1{
    for second in first+1..galaxies.len(){
        let mut xdist = galaxies[first].0.abs_diff(galaxies[second].0);
        let expanded_cols = find_expansions(&empty_cols, galaxies[first].0, galaxies[second].0);
        xdist += expanded_cols * 1000000 - expanded_cols;

        let mut ydist = galaxies[first].1.abs_diff(galaxies[second].1);
        let expanded_rows = find_expansions(&empty_rows, galaxies[first].1, galaxies[second].1);
        ydist += expanded_rows * 1000000  - expanded_rows;

        sum += xdist + ydist;
    }
}

sum

It’s also good to know that you can use this structure for Part 1. Instead of multiplying out expanded_rows, you can just add them, since Part 1 just doubles each empty row.

Summary

My completed code is here, including some recent updates to the nested loops that just made sense.

Every now and then, the Advent of Code tosses you a bone. While the puzzles get generally harder as the days go on, sometimes the problem is easier than you think. This was the case today — after the stress and learning requirements of Day 10, today’s problem was a palate cleanser, straightforward and easy to visualize and solve.