Cosmic Expansion

Published: 2023-12-11 Original Prompt

Part 1

As least for part 1, all we need from the grid is the locations of the #. We can make a slight modification to our grid parser from yesterday:

def parse_grid(raw_grid: list[str], ignore_chars: str = '') -> Grid:
    """
    returns 2-tuples of (row, col) with their value

    (0, 0) ------> (0, 9)
      |              |
      |              |
      |              |
      |              |
      |              V
    (9, 0) ------> (9, 9)
    """
    result = {}
    ignore = set(ignore_chars)

    for row, line in enumerate(raw_grid):
        for col, c in enumerate(line):
            if c in ignore:
                continue
            result[row, col] = c

    return result

If we call .keys() on the result of parse_grid, we’ll have a list of every relevant point. Those are ultimately the points we’ll measure between. But first, expansion!

First, we need the empty rows and columns. We can make a set of every possible column number and remove from it the column from every point; we’ll do the same for rows:

def empty_lines(grid: list[GridPoint], grid_size: int, dim: int) -> set[int]:
    return set(range(grid_size)) - {p[dim] for p in grid}

Next, the expansion. For each point, each of its dimensions needs to increase by the number of empty lines before it. We know which lines are empty, so we can filter that list to only include lines with an index lower than each dimension:

def expand_points(val: int, empty_lines: set[int]) -> int:
    return len(tuple(filter(lambda i: i < val, empty_lines)))

The last thing we’ll need is the distance between two points on a grid! This is a simple formula known as the taxicab (or Manhattan) distance:

def taxicab_distance(a: GridPoint, b: GridPoint) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

Now, let’s put it all together!

from itertools import combinations

...

class Solution(StrSplitSolution):
    def part_1(self) -> int:
        grid_size = len(self.input)
        grid = list(parse_grid(self.input, ignore_chars=".").keys())

        rows_to_expand = empty_lines(grid, grid_size, dim=0)
        cols_to_expand = empty_lines(grid, grid_size, dim=1)

        expanded_points = {
            (
                row + expand_points(row, rows_to_expand),
                col + expand_points(col, cols_to_expand),
            )
            for row, col in grid
        }

        return sum(taxicab_distance(a, b) for a, b in combinations(expanded_points, 2))

Once we have our expanded points, we get every pair of them using itertools.combinations and we’re all set!

Part 2

I had an linking about what part 2 might be, so I structured the above to make this transition easier on us. We need to make 3 changes:

move all of part 1 into a function
add a multiplier to expand_points
call our new function

The only tricky thing is the multiplier value. In part 1, lines got 2x as big, so we added 1 * len(...) to each dimension. To get 1 million times bigger, we’ll add 999,999 * len(...) (not 1M, which is what I tried first).

Here are those changes:

...

def expand_points(val: int, empty_lines: set[int], multiplier: int) -> int:
    return len(tuple(filter(lambda i: i < val, empty_lines))) * (multiplier - 1)


class Solution(StrSplitSolution):
    def _solve(self, multiplier: int) -> int:
        ...

        expanded_points = {
            (
                row + expand_points(row, rows_to_expand, multiplier),
                col + expand_points(col, cols_to_expand, multiplier),
            )
            for row, col in grid
        }

        return sum(taxicab_distance(a, b) for a, b in combinations(expanded_points, 2))

    def part_1(self) -> int:
        return self._solve(2)

    def part_2(self) -> int:
        return self._solve(1_000_000)

And that’ll do it! Today plays nicely into one of my AoC rules of thumb: store only what you need and resort to math when the numbers get big (instead of iterating over large ranges).