Advent of Code 2023 - Day 11
I'ts that time of year again, the Advent of Code! I'm completing the challenges this year using Rust 🦀 Day 11 made us expand the universe, just to learn we can solve almost anything with numbers!
I'll be posting them here, just to document how I'm solving each challenge, and I highly encourage you to check them out before reading my solutions!
Here's the Day 11 Challenge
BTW: Complete Part 1 to have access to Part 2 😉
Solution for Part 1
use std::fs::File;
use std::io::{Read, Result};
use std::path::Path;
fn main() {
let input_file_path = "path_to_input_file";
let mut curr_sum = 0;
let file = file_as_string(input_file_path)
.unwrap_or_else(|_| panic!("Could not find input file {}", input_file_path));
let mut universe: Vec<Vec<char>> = Vec::new();
for line in file.split("\r\n") {
let mut universe_row: Vec<char> = Vec::new();
for char in line.chars() {
universe_row.push(char);
}
universe.push(universe_row);
}
let mut universe = expand_universe_vertically(universe);
expand_universe_horizontally(&mut universe);
let galaxy_positions: Vec<(usize, usize)> = find_galaxies(universe);
for galaxy_ref in &galaxy_positions {
for galaxy_target in &galaxy_positions {
curr_sum += calculate_distance(galaxy_ref, galaxy_target);
}
}
println!("Sum of all shortest paths: {}", curr_sum/2)
}
fn find_galaxies(universe: Vec<Vec<char>>) -> Vec<(usize, usize)> {
let mut result: Vec<(usize, usize)> = Vec::new();
for (row_num, row) in universe.iter().enumerate() {
for (col_num, char) in row.iter().enumerate() {
if char == &'#' {
result.push((col_num, row_num))
}
}
}
result
}
fn calculate_distance(point_a: &(usize, usize), point_b: &(usize, usize)) -> usize {
let (x1, y1) = point_a;
let (x2, y2) = point_b;
let x = if x1 > x2 {
x1 - x2
} else {
x2 - x1
};
let y = if y1 > y2 {
y1 - y2
} else {
y2 - y1
};
x + y
}
fn expand_universe_vertically(universe: Vec<Vec<char>>) -> Vec<Vec<char>> {
let mut new_universe: Vec<Vec<char>> = Vec::new();
for universe_row in &universe {
new_universe.push(universe_row.clone());
if universe_row.iter().all(|c| c == &'.') {
new_universe.push(universe_row.clone());
}
}
new_universe
}
fn expand_universe_horizontally(universe: &mut [Vec<char>]) {
let mut curr_idx = 0_usize;
let mut curr_size = universe.first().unwrap().len();
while curr_idx < curr_size {
let mut col_is_expandable = true;
'main: for row in universe.iter() {
if row.get(curr_idx).unwrap() != &'.' {
col_is_expandable = false;
break 'main;
}
}
if col_is_expandable {
for row in universe.iter_mut() {
row.insert(curr_idx, '.')
}
curr_idx += 1;
curr_size += 1;
}
curr_idx += 1;
}
}
fn file_as_string<P: AsRef<Path>>(filename: P) -> Result<String> {
let mut file = File::open(filename)?;
let mut file_as_str = String::new();
File::read_to_string(&mut file, &mut file_as_str)?;
Ok(file_as_str)
}
Solution for Part 2
use std::fs::File;
use std::io::{Read, Result};
use std::path::Path;
const MULTIPLIER: usize = 1_000_000_usize - 1; // Compensate for already existing rows
fn main() {
let input_file_path = "path_to_input_file";
let mut curr_sum = 0;
let file = file_as_string(input_file_path)
.unwrap_or_else(|_| panic!("Could not find input file {}", input_file_path));
let mut universe: Vec<Vec<char>> = Vec::new();
for line in file.split("\r\n") {
let mut universe_row: Vec<char> = Vec::new();
for char in line.chars() {
universe_row.push(char);
}
universe.push(universe_row);
}
let expandable_rows: Vec<usize> = find_expandable_rows(&universe);
let expandable_columns: Vec<usize> = find_expandable_columns(&universe);
let galaxy_positions: Vec<(usize, usize)> = find_galaxies(universe);
for galaxy_ref in &galaxy_positions {
for galaxy_target in &galaxy_positions {
curr_sum += calculate_distance(galaxy_ref, galaxy_target, &expandable_columns, &expandable_rows);
}
}
println!("Sum of all shortest paths: {}", curr_sum / 2)
}
fn find_expandable_columns(universe: &[Vec<char>]) -> Vec<usize> {
let mut result: Vec<usize> = Vec::new();
let curr_size = universe.first().unwrap().len();
for curr_idx in 0..curr_size {
let mut col_is_expandable = true;
'main: for row in universe.iter() {
if row.get(curr_idx).unwrap() != &'.' {
col_is_expandable = false;
break 'main;
}
}
if col_is_expandable {
result.push(curr_idx);
}
}
result
}
fn find_expandable_rows(universe: &[Vec<char>]) -> Vec<usize> {
let mut result: Vec<usize> = Vec::new();
for (idx, row) in universe.iter().enumerate() {
if row.iter().all(|c| c == &'.') {
result.push(idx);
}
}
result
}
fn find_galaxies(universe: Vec<Vec<char>>) -> Vec<(usize, usize)> {
let mut result: Vec<(usize, usize)> = Vec::new();
for (row_num, row) in universe.iter().enumerate() {
for (col_num, char) in row.iter().enumerate() {
if char == &'#' {
result.push((col_num, row_num))
}
}
}
result
}
fn calculate_distance(
point_a: &(usize, usize),
point_b: &(usize, usize),
expandable_columns: &[usize],
expandable_rows: &[usize],
) -> usize {
let (mut x1, mut y1) = point_a;
let (mut x2, mut y2) = point_b;
x1 += expandable_columns.iter().filter(|x| &&x1 > x).count() * MULTIPLIER;
x2 += expandable_columns.iter().filter(|x| &&x2 > x).count() * MULTIPLIER;
y1 += expandable_rows.iter().filter(|y| &&y1 > y).count() * MULTIPLIER;
y2 += expandable_rows.iter().filter(|y| &&y2 > y).count() * MULTIPLIER;
let x = if x1 > x2 {
x1 - x2
} else {
x2 - x1
};
let y = if y1 > y2 {
y1 - y2
} else {
y2 - y1
};
x + y
}
fn file_as_string<P: AsRef<Path>>(filename: P) -> Result<String> {
let mut file = File::open(filename)?;
let mut file_as_str = String::new();
File::read_to_string(&mut file, &mut file_as_str)?;
Ok(file_as_str)
}