Link to Advent of Code day 11

Part 1

Rules

Today we have to help analyzing a map of galaxies. The input looks like this:

...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....

To get the answer, we need to do 2 things:

1. We have to expand the rows and columns that contains no galaxies. With the previous example, the rows with no galaxies:

   v  v  v
 ...#......
 .......#..
 #.........
>..........<
 ......#...
 .#........
 .........#
>..........<
 .......#..
 #...#.....
   ^  ^  ^

Would become

....#........
.........#...
#............
.............
.............
........#....
.#...........
............#
.............
.............
.........#...
#....#.......

2. We then add to get all the possible pairs of galaxies, and sum the shortest path between each pair. A path can only use steps which are up,down,left,right. For example, the distance between the 2 top galaxies is 6:

....#@.......
.....@@@@#...
#............
.............
.............
........#....
.#...........
............#
.............
.............
.........#...
#....#.......

Note that the path can pass through another galaxy.

Code

Let's start by parsing the map. We need 2 parts: The map itself, and the galaxies.

from dataclasses import dataclass


@dataclass
class Point:
    y: int
    x: int


def get_galaxies_map(input_file: str) -> list[list[bool]]:
    galaxies_map = []
    with open(input_file) as f:
        for line in f.readlines():
            new_line = [value == "#" for value in line.strip()]
            galaxies_map.append(new_line)
    return galaxies_map


def get_galaxies(galaxies_map: list[list[bool]]) -> list[Point]:
    galaxies = []
    for y, line in enumerate(galaxies_map):
        for x, val in enumerate(line):
            if val:
                galaxies.append(Point(y, x))
    return galaxies

We then have to expand the galaxies map. To do this, I just created a second map with the additional rows/columns for empty lines.

Since it's easier to add an horizontal line to a 2d array, I used a cool Python trick I found on this stackoverflow post to rotate a 2d grid. This way we can add rows, rotate our map, add the rows again, and rotate it back to process both rows and columns with the same function:

def expand_galaxies_map(galaxies_map: list[list[bool]]) -> list[list[bool]]:
    half_expanded_map = expand_map_vertically(galaxies_map)
    # Rotate map 90 degrees clockwise
    half_expanded_map = list(zip(*half_expanded_map[::-1]))
    fully_expanded_map = expand_map_vertically(half_expanded_map)
    # Rotate 90 degrees counter-clockwise
    fully_expanded_map = list(reversed(list(zip(*fully_expanded_map))))
    return fully_expanded_map


def expand_map_vertically(galaxies_map: list[list[bool]]):
    expanded_map = []
    for line in galaxies_map:
        expanded_map.append(line)
        # Add an additional row if there is only space in this row
        if all(not val for val in line):
            expanded_map.append(line)
    return expanded_map

Since the distance between 2 points is calculating by moving only up/down/left/right, we can use a Manhattan distance to get it without simulating the path:

def manhattan_distance(point_a: Point, point_b: Point):
    return abs(point_a.x - point_b.x) + abs(point_a.y - point_b.y)

We then have all the pieces we need to solve part 1:

from itertools import combinations


def part_one(input_file: str):
    galaxies_map = get_galaxies_map(input_file)
    galaxies = get_galaxies(expanded_map)
    expanded_map = expand_galaxies_map(galaxies_map)

    total = 0
    for point_a, point_b in combinations(galaxies, 2):
        total += manhattan_distance(point_a, point_b)
    return total

Part 2

Rules

The part 2 is the same problem as before, but the galaxies expands way much more: each empty row/column now needs to be replaced with 1000000 empty rows/columns.

Code

The trick from part 1 were I was manually inserting the rows would takes way too much time now.

Instead, I opted for the following solution:

1. store the y/x index of each empty rows and columns
2. for each pair, get the number of points which are in the stored empty rows indexes
3. multiply this number by the expansion amount (1 for part 1, 999999 for part 2)
4. add this new number to the distance

Let's replace the expansion function by one which only returns the empty rows/columns:

def get_expanded_parts(galaxies_map: list[list[bool]]) -> [set[int], set[int]]:
    empty_y_set = set()
    empty_y_s = set()

    for y, line in enumerate(galaxies_map):
        if all(not val for val in line):
            empty_y_set.add(y)

    # Rotate map 90 degrees clockwise
    # from https://stackoverflow.com/a/8421412
    rotated_map = list(zip(*galaxies_map[::-1]))
    for x, col in enumerate(rotated_map):
        if all(not val for val in col):
            empty_y_s.add(x)
    return empty_y_set, empty_y_s

And implements the function to get the additional distance due to the expansion:

def get_additional_expanded_distance(
    expanded_parts: [set[int], set[int]], point_a: Point, point_b: Point, distance_coef: int
) -> int:
    min_y, max_y = sorted([point_a.y, point_b.y])
    min_x, max_x = sorted([point_a.x, point_b.x])
    empty_y_set = set(range(min_y, max_y + 1)) & expanded_parts[0]
    empty_x_set = set(range(min_x, max_x + 1)) & expanded_parts[1]
    return (len(empty_y_set) + len(empty_x_set)) * distance_coef

I then moved the logic from part 1 into a dedicated function, which implements this new logic:

def get_galaxies_distances_sum(input_file: str, expansion_rate: int):
    # I merged the previous `get_galaxies_map` and `get_galaxies` into one
    # to avoid iterating twice on the same map, and to have a tidier code
    galaxies, galaxies_map = get_galaxies_and_map(input_file)
    expanded_parts = get_expanded_parts(galaxies_map)

    total = 0
    for point_a, point_b in combinations(galaxies, 2):
        distance = manhattan_distance(point_a, point_b)
        distance += get_additional_expanded_distance(expanded_parts, point_a, point_b, expansion_rate)
        total += distance
    return total

We can now update part 1 and add part 2:

def part_one(input_file: str) -> int:
    return get_galaxies_distances_sum(input_file, 1)


def part_two(input_file: str) -> int:
    return get_galaxies_distances_sum(input_file, 999999)

And this day is solved !

---

All the code is available on github