Cosmic Expansion

Advent of Code 2023 Day 11

Part 1

Easy, if I understand it all correctly

As I understand it:

1. 'Empty' rows and columns should duplicate themselves once in either direction
2. The 'shortest path' can be found by determining the difference between the X and Y locations of each endpoint

Duplicating empty rows and columns

Identifying an empty row is simple:

For each row
  Is every character in the row a .?

Identifying an empty column requires another step:

For each character in the first row
  Create a list of all N characters in each row where N is the current index
    Is every character in the list a .?

Once the rows and columns are flagged, duplication can occur.

For rows, it will mean inserting a row in the 2D array.

For columns, it will mean inserting one item in each nested array in the grid.

I should start writing my algorithm and check that I'm on the right track.

My finder algorithms

Identifying the empty rows:

let rows = input.reduce((indices, row, index) => {
  if (row.match(/#/) == null) indices.push(index)
  return indices
}, [])

Identifying the empty columns:

let cols = input[0].split('').reduce(
  (indices, col, index) => {
    if (!input.map(el => el[index]).includes('#')) {
      indices.push(index)
    }
    return indices
  }, []
)

Works like a charm!

It correctly identified the two rows and three columns in the example input!

My duping algorithms

Before duping, I recognized that I didn't want to insert rows or columns from left-to-right or top-to-bottom.

That would cause unwanted shifting of rows and screw up all rows and columns after the first one in the list.

So, first, I reversed each list.

Then, I added rows to the input:

rows.forEach(
  row => input.splice(
    row, 0, new Array(input[0].length).fill('.').join('')
  )
)

The column duping was a bit more involved, and took some unplanned time to get working as expected due to in-place editing and converting between strings and arrays.

But, I got it to work with this:

input = input.map(row => {
  row = row.split('')
  for (let i = 0; i < cols.length; i++) {
    row.splice(cols[i], 0, '.')
  }
  return row
})

After running all of this on the example input, I saw the expected grid with added rows and columns.

Next, I need to geolocate each galaxy.

Finding each galaxy in the expanded grid

Pretty easy task at this point in the series:

let coords = input.reduce((coords, row, index) => {
  let matches = [...row.join('').matchAll(/#/g)].map(el => el.index)
  matches.forEach(match => coords.push([index, match]))
  return coords
}, [])

Now I have a list of all galaxies.

Time to iterate through each one, then find the shortest path between it and all others.

Finding all shortest paths

Nested loops that walk the remainder of the list, walking fewer items each iteration. At each stop, summing the (absolute value of the) differences between matching X-Y coordinates.

let sums = 0
for (let a = 0; a < coords.length - 1; a++) {
  for (let b = a + 1; b < coords.length; b++) {
    sums += Math.abs(coords[a][0] - coords[b][0]) + Math.abs(coords[a][1] - coords[b][1])
  }
}
return sums

Checking and celebrating

It works on the example input!

And it works on my puzzle input!

Woohoo!

Part 2

I thought the twist would be different

I had a hunch that Part 2 would add a constraint: find the shortest path that avoids any other galaxies.

But then comes the scale-based test:

• There's no way I am expected to build a 2D array that is several hundred million rows or columns in area
• So, this must be calculable some other way

It's definitely worth my time to enhance my algorithm in a way that lets me explore the sums of shortest paths in incrementing expanses.

If nothing else, then to at least confirm the 10 and 100 times expansion suggested by the author.

Let's give it a try!

Refactoring for variable expansion sizes

Putting it all in a function that accepts as a parameter the number of times to expand empty rows and columns:

function run(times) {

}

And adjusting my row and column expander algorithms for varying amounts of dots:

  rows.forEach(row => {
    for (let i = 0; i < times; i++) {
      input.splice(row, 0, new Array(input[0].length).fill('.').join(''))
    }
  })

  let dots = new Array(times).fill(null).map(el => '.')
  input = input.map(row => {
    row = row.split('')
    for (let i = 0; i < cols.length; i++) {
      row.splice(cols[i], 0, ...dots)
    }
    return row
  })

Except...that generates an answer larger than the expected 1030 for a 10 times expanded grid.

What's going on?

Being one off in two places

After studying my expanded grid, I noticed:

• I had 11 empty rows and columns
• Where I should have had 10

I was adding one too many rows and columns.

The fix is shown below with i = 1 and (times - 1):

  rows.forEach(row => {
    for (let i = 1; i < times; i++) {
      input.splice(row, 0, new Array(input[0].length).fill('.').join(''))
    }
  })

  let dots = new Array(times - 1).fill(null).map(el => '.')
  input = input.map(row => {
    row = row.split('')
    for (let i = 0; i < cols.length; i++) {
      row.splice(cols[i], 0, ...dots)
    }
    return row
  })

Running my algorithm now showed the correct answers for 10 times and 100 times expanded example input.

Next, I'm on the hunt for a pattern as the number of expansions changes!

Studying the change in sums as expansion times increase

First, I had to amass the sums of several iterations of expansions:

let counts = []
for (let i = 1; i <= 100; i++) {
  counts.push(run(i))
}
console.log(counts)

I saw the numbers I was expecting with the example input for 2x and 10x and 100x.

Next, I had to calculate the differences between each of those values.

let diffs = []
for (let i = 1; i < counts.length; i++) {
  diffs.push(counts[i] - counts[i - 1])
}
console.log(diffs)

Guess what I saw:

[N, N, N, N, N, N, N, ...]

The same number again and again!

That means that each expansion increases the sum of shortest paths by the same amount!

I can calculate my answer for 1 million expansions now!

The final calculation

Here's how I did it:

Algorithmically determine my N
Multiply it by 999998
Add to that my answer from expanding twice

I generated a massive number: several hundred billions!

It was the correct answer!!!

Yeehawww!

What another fun and rewarding puzzle!

I'm amazed I figured out how to work around Part 2 and deduce the pattern of expansion.

Day 12, here I come!