Module aoc::year2023::day11

source ·
Expand description

§Cosmic Expansion

We simplify the problem by treating each axis independently. Consider 4 galaxies on the same axis at arbitrary non-decreasing values a b c d. The pairwise distances are:

  • b - a
  • c - b + c - a => 2c - (a + b)
  • d - c + d - b + d - a => 3d - (a + b + c)

We can see that each pairwise distance can be expressed as the current coordinate multiplied by the previous number of galaxies minus the prefix sum of the coordinates of the previous galaxies.

In the special case that two or more galaxies are at the same coordinate, for example c == d:

  • c - b + c - a => 2c - (a + b)
  • d - c + d - b + d - a => 3d - (a + b + c) => 2c - (a + b)
  • Total: 2 * [2c - (a + b)]

This implies that we only need the count of the number of galaxies at each coordinate and can multiply the total value by that count. This also find gaps with no galaxies to calculate the expanded coordinates.

Structs§

Functions§