Advent of Code 2023: Day 11

Code for solutions available on GitHub.

Still covid. Was slightly better a few hours ago, but getting worse from sitting at the computer. I probably shouldn’t be doing these puzzles. Or writing these posts.

Cosmic Expansion

Thankfully, today was really simple. The input is a grid where some coordinates are marked. The twist is, every row and every column in the grid that does not have a mark, should actually be doubled. We then need to get the sum of the pairwise Manhattan distances of each possible pair of marked coordinates.

The first part of the solution is easy – iterate through all rows and columns of the grid, and save the marked coordinates in a vector, keeping track of which row and column indices contain no marks as you go.

Then, go through the list of coordinates, and add to their row index the number of empty rows above them. Then add to their column index the number of empty rows to the left of them. Once you have done this to all the galaxies (the marked coordinates are galaxies in the lore), the solution is straightforward with the help of Itertools::tuple_combinations:

galaxies
    .iter()
    .tuple_combinations()
    .fold(0, |acc, (a, b)| acc + a.manhattan_distance(b))

Part 2

For part 2, it turns out that each empty row or column shouldn’t be replaced with 2 empty rows or columns, but a million. The solution from part 1 is simply adapted by instead of adding the number of empties to each coordinate index, add the number of empties times 999999 (one less than a million, such that the final number of copies is one million). The solution is then exactly the same once you have the Vec of galaxies with adjusted coordinates.