Advent of Code 2023, Day 11

❄️ Back to Advent of Code 2023 solutions homepage ❄️

# Imports
from aoc23.utils import read_input
import math
import numpy as np
from itertools import combinations

input_11 = read_input(11)

Part 1

In the first part of the day 11 puzzle, we are given an input consisting of an array of . and # characters. Each # represents a galaxy observed in the night sky, and . represents empty space.

The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies. However, there’s a catch: the universe expanded in the time it took the light from those galaxies to reach the observatory. Due to something involving gravitational effects, only some space expands. In fact, the result is that any rows or columns that contain no galaxies should all actually be twice as big.

An initial attempt might consider modifying the existing array, and duplicating every empty row/column to create an expanded version. However, this would require creating a copy of the original array, potentially increased in size many times (this is not desirable, partly with an eye looking ahead at what to expect in part 2). So, instead we can keep track of the times when an empty row/column is observed, and make a record to refer to later:

# Array size
n_rows = len(input_11)
n_cols = len(input_11[0])

# Track the empty rows/columns - initialise lists
col_tracker = n_cols*[1]
row_tracker = n_rows*[0]

# Also record the locations of the galaxies
galaxy_locs = []

The tracker lists will record a 1 when the row/column is empty (and so needs to be repeated), and a 0 otherwise:

for row in range(n_rows):
    is_row_empty = 1
    for col, val in enumerate(input_11[row]):
        if val == '#':
            # Record galaxy location
            galaxy_locs.append((row, col))
            
            # Update column tracker
            col_tracker[col] = 0
            
            is_row_empty = 0
    
    # Update row tracker
    row_tracker[row] = is_row_empty

Taking the cumulative sum of these trackers will record the cumulative number of empty rows/columns up to a certain index:

row_cumsum = np.cumsum(row_tracker)
col_cumsum = np.cumsum(col_tracker)

And so the distance between any two galaxies is the usual taxicab metric, plus an additional component for each axis adding extra row/columns:

sum_distances = 0

for (i1, j1), (i2, j2) in combinations(galaxy_locs, 2):
    row_expansion = row_cumsum[i2] - row_cumsum[i1]
    col_expansion = col_cumsum[j2] - col_cumsum[j1]
    
    distance = np.abs(i2 - i1 + row_expansion) + np.abs(j2 - j1 + col_expansion)
    sum_distances += distance

sum_distances

10276166

And so the answer to part 1 is: 10276166.

Part 2

The foresight from earlier has paid off - instead of repeating each empty row/column once, they should be repeated 1,000,000 times. In order to do this, all that is needed is an additional factor in the distance metric:

def compute_sum_distances(puzzle_input, factor):
    # Array size
    n_rows = len(puzzle_input)
    n_cols = len(puzzle_input[0])
    
    # Track the empty rows/columns - initialise lists
    col_tracker = n_cols*[1]
    row_tracker = n_rows*[0]
    
    # Also record the locations of the galaxies
    galaxy_locs = []
    
    for row in range(n_rows):
        is_row_empty = 1
        for col, val in enumerate(puzzle_input[row]):
            if val == '#':
                # Record galaxy location
                galaxy_locs.append((row, col))
                
                # Update column tracker
                col_tracker[col] = 0
                
                is_row_empty = 0
        
        # Update column tracker
        row_tracker[row] = is_row_empty
    
    # Cumulative empty row trackers
    row_cumsum = np.cumsum(row_tracker)
    col_cumsum = np.cumsum(col_tracker)
    
    sum_distances = 0
    for (i1, j1), (i2, j2) in combinations(galaxy_locs, 2):
        # Number of empty rows/columns between these two galaxies
        row_expansion = row_cumsum[i2] - row_cumsum[i1]
        col_expansion = col_cumsum[j2] - col_cumsum[j1]
        
        # Taxicab + expansion metric
        distance = np.abs(i2 - i1 + (factor-1)*row_expansion) + np.abs(j2 - j1 + (factor-1)*col_expansion)
        
        # Convert back to native int, to avoid overflow errors with np.int32
        sum_distances += int(distance)
    
    return sum_distances

On the part 1 problem, using factor=2 should reproduce the earlier result:

compute_sum_distances(input_11, 2)

10276166

Also, on the test input provided, the provided distances for factor=2, factor=10 and factor=100 can be reproduced:

test_input = [
    '...#......',
    '.......#..',
    '#.........',
    '..........',
    '......#...',
    '.#........',
    '.........#',
    '..........',
    '.......#..',
    '#...#.....'
]

assert compute_sum_distances(test_input, 2) == 374
assert compute_sum_distances(test_input, 10) == 1030
assert compute_sum_distances(test_input, 100) == 8410
print('Success!')

Success!

All that is left is to compute the distance with factor=1_000_000:

compute_sum_distances(input_11, 1_000_000)

598693078798

And so the answer to part 2 is: 598693078798.

❄️ Back to Advent of Code 2023 solutions homepage ❄️