Advent of Code 2023 Day 11

Day 11: Cosmic Expansion

https://adventofcode.com/2023/day/11

You meet a researcher studying space. You want to help with today’s analysis.

It’s a 2D map of space.

An example input looks like this:

input.txt

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

a # represents a galaxy
a . represents empty space

Parsing

I represented every point in the grid as a Tile and stored them in a 2D list.

enum Tile {
    Galaxy,
    Empty,
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

Part 1

The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies.

But because the universe is expanding, the readings are out of date.

Because of ✨✨reasons✨✨ only some space expands.

Any rows or columns that contain no galaxies should all actually be twice as big.

The question asks for the sum of all distances between each pair galaxies.

some skeleton/pseudo-code:

let grid = parse(input);
let galaxies = galaxy_coordinates(&grid);

galaxies
    .iter()
    .combinations(2)
    .map(/* distance between those 2 galaxies */)
    .sum()

Helpers

I represent each point as a Coord

struct Coord {
    row: usize,
    col: usize,
}

Because it’s a 2D list, the distance between 2 points can be calculated with the Manhattan distance.

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

Next is the helper that turns the 2D grid into a list of Coord of galaxies. Because of that expansion rule, I can’t loop over the original grid and use those coordinates, so I keep track of them manually.

Each time I come across an empty row or column, I increment the corresponding coordinate appropriately. If I come across a galaxy during my loop, I add the current coordinates to a list.

fn galaxy_coordinates(grid: &[Vec<Tile>]) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += 2;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += 2;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

This function uses 2 helper functions to keep track of indexes for empty rows or empty columns.

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

Time to put it all together.

Code

day_11.rs

use itertools::Itertools;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Galaxy,
    Empty,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

fn galaxy_coordinates(grid: &[Vec<Tile>]) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += 2;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += 2;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let galaxies = galaxy_coordinates(&grid);

    galaxies
        .iter()
        .combinations(2)
        .map(|pair| pair[0].manhattan_dist(pair[1]))
        .sum()
}

Part 2

Turns out the galaxies are much further apart.

Any rows or columns that contain no galaxies should all actually be one million times as big.

The question asks for the sum of all distances between each pair galaxies.

Code

The galaxy_coordinates jumped 2 steps when it found an empty line in part1, it jumps 1_000_000 steps in part2.

I normally don’t do this Advent of Code, but I generalized a helper function so it can be used for part 1 and part 2.

day_11.rs

use itertools::Itertools;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Galaxy,
    Empty,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

fn galaxy_coordinates(grid: &[Vec<Tile>], expansion: usize) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += expansion;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += expansion;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    let galaxies = galaxy_coordinates(&grid, 1_000_000);

    galaxies
        .iter()
        .combinations(2)
        .map(|pair| pair[0].manhattan_dist(pair[1]))
        .sum()
}

Final code

day_11.rs

1use itertools::Itertools;
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4enum Tile {
5    Galaxy,
6    Empty,
7}
8
9#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
10struct Coord {
11    row: usize,
12    col: usize,
13}
14
15impl Coord {
16    fn manhattan_dist(&self, other: &Self) -> usize {
17        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
18    }
19}
20
21fn parse(input: &str) -> Vec<Vec<Tile>> {
22    input
23        .lines()
24        .map(|line| {
25            line.chars()
26                .map(|c| match c {
27                    '.' => Tile::Empty,
28                    '#' => Tile::Galaxy,
29                    _ => panic!("at the disco"),
30                })
31                .collect()
32        })
33        .collect()
34}
35
36fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
37    grid.iter()
38        .enumerate()
39        .filter_map(|(idx, row)| {
40            if !row.contains(&Tile::Galaxy) {
41                Some(idx)
42            } else {
43                None
44            }
45        })
46        .collect()
47}
48
49fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
50    // this song and dance is only here so I can loop over columns
51    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
52    for (row_idx, row) in grid.iter().enumerate() {
53        for (col_idx, c) in row.iter().enumerate() {
54            cols[col_idx][row_idx] = *c;
55        }
56    }
57
58    empty_rows(&cols)
59}
60
61fn galaxy_coordinates(grid: &[Vec<Tile>], expansion: usize) -> Vec<Coord> {
62    let empty_rows = empty_rows(&grid);
63    let empty_cols = empty_cols(&grid);
64
65    let mut galaxies = Vec::new();
66    let mut curr_row = 0;
67    let mut curr_col = 0;
68
69    for (row_idx, row) in grid.iter().enumerate() {
70        if empty_rows.contains(&row_idx) {
71            curr_row += expansion;
72            continue;
73        }
74        for (col_idx, c) in row.iter().enumerate() {
75            if empty_cols.contains(&col_idx) {
76                curr_col += expansion;
77                continue;
78            }
79            if *c == Tile::Galaxy {
80                galaxies.push(Coord {
81                    row: curr_row,
82                    col: curr_col,
83                });
84            }
85            curr_col += 1
86        }
87        curr_col = 0;
88        curr_row += 1;
89    }
90
91    galaxies
92}
93
94pub fn part_1(input: &str) -> usize {
95    let grid = parse(input);
96    let galaxies = galaxy_coordinates(&grid, 2);
97
98    galaxies
99        .iter()
100        .combinations(2)
101        .map(|pair| pair[0].manhattan_dist(pair[1]))
102        .sum()
103}
104
105pub fn part_2(input: &str) -> usize {
106    let grid = parse(input);
107    let galaxies = galaxy_coordinates(&grid, 1_000_000);
108
109    galaxies
110        .iter()
111        .combinations(2)
112        .map(|pair| pair[0].manhattan_dist(pair[1]))
113        .sum()
114}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 11

Day 11: Cosmic Expansion

Parsing

Part 1

Helpers

Code

Part 2

Code

Final code