Advent of Code 2023 - Day 10
I'ts that time of year again, the Advent of Code! I'm completing the challenges this year using Rust 🦀 Day 10 made me learn about a new type of algorithm: Ray Casting Algorithm!
You can read more about it here!
I didn't feel like writing my own implementation of Ray Casting though, so I used this one that I found 😅
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 10 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 file = file_as_string(input_file_path)
.unwrap_or_else(|_| panic!("Could not find input file {}", input_file_path));
let mut map: Vec<Vec<char>> = vec![];
for line in file.split("\r\n") {
let mut row: Vec<char> = vec![];
for char in line.chars() {
row.push(char)
}
map.push(row);
}
let map = map.iter()
.map(|r| r.as_slice().clone())
.collect::<Vec<&[char]>>();
let map = map.as_slice();
let mut path: Vec<(usize, usize)> = vec![
find_starting_position(map),
];
path.push(find_next_element(&path, map));
while path.first().unwrap() != path.last().unwrap() {
path.push(find_next_element(&path, map))
}
let farthest_point = (path.len() - 1) / 2;
println!("Farthest available point is {} steps from start", farthest_point);
}
fn find_next_element(path: &[(usize, usize)], map: &[&[char]]) -> (usize, usize) {
let (x, y) = path.last().unwrap();
let avoid: Option<(usize, usize)> = if path.len() > 1 {
Some(path[path.len() - 2])
} else {
None
};
let curr_step = map[*y][*x];
match curr_step {
'S' => {
// We know where to go, so we cheat a little :P
(*x, y - 1)
}
'F' => {
let possibilities: [(usize, usize); 2] = [
(*x, y + 1),
(x + 1, *y)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'|' => {
let possibilities: [(usize, usize); 2] = [
(*x, y + 1),
(*x, y - 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'L' => {
let possibilities: [(usize, usize); 2] = [
(x + 1, *y),
(*x, y - 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'J' => {
let possibilities: [(usize, usize); 2] = [
(x - 1, *y),
(*x, y - 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'7' => {
let possibilities: [(usize, usize); 2] = [
(x - 1, *y),
(*x, y + 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'-' => {
let possibilities: [(usize, usize); 2] = [
(x + 1, *y),
(x - 1, *y)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
_ => panic!("Unhandled char {}", curr_step)
}
}
fn resolve_avoidable_possibility(
x: &usize,
y: &usize,
avoid: Option<(usize, usize)>,
possibilities: [(usize, usize); 2],
) -> (usize, usize) {
match avoid {
None => { possibilities[0] }
Some(avoid) => {
*possibilities.iter().find(|el| el != &&avoid)
.unwrap_or_else(|| {
panic!("Could not determine path from {}, {}", *x, *y)
})
}
}
}
fn find_starting_position(map: &[&[char]]) -> (usize, usize) {
for (row_num, row) in map.iter().enumerate() {
for (col_num, char) in row.iter().enumerate() {
if char == &'S' {
return (col_num, row_num);
}
}
}
panic!("Could not find starting point!")
}
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
mod ray_casting;
use std::fs::File;
use std::io::{Read, Result};
use std::path::Path;
use crate::ray_casting::{Edge, Point, Polygon, pt_in_polygon};
fn main() {
let input_file_path = "path_to_input_file";
let file = file_as_string(input_file_path)
.unwrap_or_else(|_| panic!("Could not find input file {}", input_file_path));
let mut map: Vec<Vec<char>> = vec![];
for line in file.split("\r\n") {
let mut row: Vec<char> = vec![];
for char in line.chars() {
row.push(char)
}
map.push(row);
}
let map = map.iter()
.map(|r| r.as_slice().clone())
.collect::<Vec<&[char]>>();
let map = map.as_slice();
let mut path: Vec<(usize, usize)> = vec![
find_starting_position(map),
];
path.push(find_next_element(&path, map));
while path.first().unwrap() != path.last().unwrap() {
path.push(find_next_element(&path, map))
}
let mut edges: Vec<Edge> = Vec::new();
for vertices in path.windows(2) {
edges.push(Edge::new(
(vertices[0].0 as f64, vertices[0].1 as f64),
(vertices[1].0 as f64, vertices[1].1 as f64),
))
}
let polygon = Polygon { edges };
let mut nodes_nested_in_path = 0;
for (row_num, row) in map.iter().enumerate() {
for (col_num, _) in row.iter().enumerate() {
if path.contains(&(col_num, row_num)) {
continue;
}
let point = Point::new((col_num as f64, row_num as f64));
if pt_in_polygon(&point, &polygon) {
nodes_nested_in_path += 1;
}
}
}
println!("Number of nodes inside path: {}", nodes_nested_in_path);
}
fn find_next_element(path: &[(usize, usize)], map: &[&[char]]) -> (usize, usize) {
let (x, y) = path.last().unwrap();
let avoid: Option<(usize, usize)> = if path.len() > 1 {
Some(path[path.len() - 2])
} else {
None
};
let curr_step = map[*y][*x];
match curr_step {
'S' => {
(*x, y - 1) // input
// (x + 1, *y) // input-2
// (*x, y + 1) // input-3
// (x + 1, *y) // input
}
'F' => {
let possibilities: [(usize, usize); 2] = [
(*x, y + 1),
(x + 1, *y)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'|' => {
let possibilities: [(usize, usize); 2] = [
(*x, y + 1),
(*x, y - 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'L' => {
let possibilities: [(usize, usize); 2] = [
(x + 1, *y),
(*x, y - 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'J' => {
let possibilities: [(usize, usize); 2] = [
(x - 1, *y),
(*x, y - 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'7' => {
let possibilities: [(usize, usize); 2] = [
(x - 1, *y),
(*x, y + 1)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
'-' => {
let possibilities: [(usize, usize); 2] = [
(x + 1, *y),
(x - 1, *y)
];
resolve_avoidable_possibility(x, y, avoid, possibilities)
}
_ => panic!("Unhandled char {}", curr_step)
}
}
fn resolve_avoidable_possibility(
x: &usize,
y: &usize,
avoid: Option<(usize, usize)>,
possibilities: [(usize, usize); 2],
) -> (usize, usize) {
match avoid {
None => { possibilities[0] }
Some(avoid) => {
*possibilities.iter().find(|el| el != &&avoid)
.unwrap_or_else(|| {
panic!("Could not determine path from {}, {}", *x, *y)
})
}
}
}
fn find_starting_position(map: &[&[char]]) -> (usize, usize) {
for (row_num, row) in map.iter().enumerate() {
for (col_num, char) in row.iter().enumerate() {
if char == &'S' {
return (col_num, row_num);
}
}
}
panic!("Could not find starting point!")
}
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)
}