Day 11 - Cosmic Expansion

Solution
Breakdown

link to challenge

Today's challenge was a grid-like challenge in which you were asked to find all the pairs of galaxies in a grid and find the shortest route between each one.

With the stipulation that when there is an empty row or column, an extra row or column is added (I didn't get this from the initial read, at first I thought it meant the WHOLE row or column count was doubled, but it was more scoped to each column or row, not doubling the whole grid.

Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace Code;

public static class Day11
{

  public static long Solve(string input, int scale)
  {

    string[] universe = input.Split(Environment.NewLine);
    HashSet<int> emptyRows = [..universe.Select((string row, int index)=>(row, index))
      .Where(entry => entry.row.All(c => c == '.'))
      .Select(entry => entry.index)];

    HashSet<int> emptyColumns = [];

    for (int col = 0; col < universe[0].Length; col++)
    {
      bool empty = true;
      for (int row = 0; row < universe.Length; row++)
      {
        if (universe[row][col] != '.')
        {
          empty = false;
          break;
        }
      }
      if (empty) emptyColumns.Add(col);
    }

    List<Position> galaxyLocations = ExpandFindGalaxy(universe, scale, emptyRows, emptyColumns).ToList();
    List<(Position first, Position second)> pairs = new();

    for (int x = 0; x < galaxyLocations.Count; x++)
    {
      for (int y = x + 1; y < galaxyLocations.Count; y++)
      {
        pairs.Add((galaxyLocations[x], galaxyLocations[y]));
      }
    }

    return pairs
      .Select(x => ManhattanDistance(x.first.row, x.second.row, x.first.col, x.second.col))
      .Sum();
  }

  public static long ManhattanDistance(int x1, int x2, int y1, int y2)
  {
    return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
  }

  public static IEnumerable<Position> ExpandFindGalaxy(string[] universe, int scale, HashSet<int> emptyRows, HashSet<int> emptyColumns)
  {
    List<Position> positions = new List<Position>();

    for (int row = 0; row < universe.Length; row++)
    {
      if (emptyRows.Contains(row))
      {
        continue;
      }

      for (int col = 0; col < universe[row].Length; col++)
      {
        if (emptyColumns.Contains(col))
        {
          continue;
        }

        if (universe[row][col] == '#')
        {
          int adjustedRow = row + (scale - 1) * emptyRows.TakeWhile(r => r < row).Count();
          int adjustedCol = col + (scale - 1) * emptyColumns.TakeWhile(c => c < col).Count();
          positions.Add(new Position(adjustedRow, adjustedCol));
        }
      }
    }

    return positions;
  }
}

public record Position(int row, int col);

Breakdown

1: We need to know which rows and columns are empty, so we can use this information later, to help expand the columns / and move the galaxies. Do this by simply looping over the columns and rows, checking for the . character.

2: Once we have the rows and columns, we need to find the galaxies.

At first, I thought I could do this simply by looping over every line, and adding the column and row when we get to an empty one. However, this would not be scalable, as it would add more rows to iterate over, and you would also have to handle the length of the array being looped over ever-growing.

Therefore to resolve this problem, we can simply "pretend" the grid has been expanded, by adjusting the row index and column index by the number of rows we'd have passed (within empty rows and columns) and multiply this by the scaling factor (Part 1 = 2, and Part2 = 1million) -1 to account for the zero-based indexing.

This is done using the TakeWhile method. This method returns items whilst the condition is met, as soon as the condition doesn't match it will stop, and then we receive a count of how many items match the criteria.

Example:

if current rowIndex = 10
emptyRows = [2,4,14]
We can virtually expand the grid without actually adding any rows or columns using maths, making it much more performant.

emptyRows.TakeWhile(r => r < row)
would return elements [2, 4].Count => 2
We can then apply our mathematical formula to this, creating an offset of rows (which would have been created from the empty rows).

We can apply the same logic to the columns and store the adjusted row and column index, giving us the coordinates for the galaxy.

3: Find all the pairs within the galaxy positions, by looping over the rows and columns, and adding the positions for each pair,

i.e
a -> b, a -> c , a -> d
b -> c, b->d
c -> d

and so on.

1. Find the shortest distance - Using the well-known Manhattan Distance mathematical formula (a common formula for traversing grid layouts named after the Manhattan street layout, where taxi cabs can only drive in straight lines from block to block, turning at intersections and wanted to do so in the quickest time).

The ManhattanDistance method will return the number of steps taken to get from point a to point b. Sum these numbers, and we have our answer.

Part 2 was a simple case of updating the scaling factor to 1 million (in C# you can write this using _ to make it easier to separate the 0's.

Problem Solved

I hope you found this solution both useful and educational. Feel free to use the concepts in your solution.

As always give me a follow for more articles, or follow me on twitter.