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:
...#.............#..#.........................#....#.................#.................#..#...#.....
- 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 columnslet 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
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 columnslet 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.
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 columnslet 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
1use itertools::Itertools;23#[derive(Debug, Clone, Copy, PartialEq, Eq)]4enum Tile {5 Galaxy,6 Empty,7}89#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]10struct Coord {11 row: usize,12 col: usize,13}1415impl Coord {16 fn manhattan_dist(&self, other: &Self) -> usize {17 self.row.abs_diff(other.row) + self.col.abs_diff(other.col)18 }19}2021fn parse(input: &str) -> Vec<Vec<Tile>> {22 input23 .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}3536fn 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 None44 }45 })46 .collect()47}4849fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {50 // this song and dance is only here so I can loop over columns51 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 }5758 empty_rows(&cols)59}6061fn galaxy_coordinates(grid: &[Vec<Tile>], expansion: usize) -> Vec<Coord> {62 let empty_rows = empty_rows(&grid);63 let empty_cols = empty_cols(&grid);6465 let mut galaxies = Vec::new();66 let mut curr_row = 0;67 let mut curr_col = 0;6869 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 += 186 }87 curr_col = 0;88 curr_row += 1;89 }9091 galaxies92}9394pub fn part_1(input: &str) -> usize {95 let grid = parse(input);96 let galaxies = galaxy_coordinates(&grid, 2);9798 galaxies99 .iter()100 .combinations(2)101 .map(|pair| pair[0].manhattan_dist(pair[1]))102 .sum()103}104105pub fn part_2(input: &str) -> usize {106 let grid = parse(input);107 let galaxies = galaxy_coordinates(&grid, 1_000_000);108109 galaxies110 .iter()111 .combinations(2)112 .map(|pair| pair[0].manhattan_dist(pair[1]))113 .sum()114}
Series navigation for: Advent of Code 2023