Skip to content

Instantly share code, notes, and snippets.

@bokenator
Created December 12, 2022 16:32
Show Gist options
  • Save bokenator/df9b8dd583655e47a4d46966c643f9b1 to your computer and use it in GitHub Desktop.
Save bokenator/df9b8dd583655e47a4d46966c643f9b1 to your computer and use it in GitHub Desktop.
use crate::common::get_input;
use std::collections::{BTreeMap, VecDeque};
type Point = (usize, usize);
fn get_index(character: char) -> usize {
match character {
'S' => 0,
'E' => 25,
character => "abcdefghijklmnopqrstuvwxyz"
.chars()
.position(|c| c == character)
.unwrap(),
}
}
fn get_position(input: &str, character: char) -> (usize, usize) {
let row_index = input.lines().position(|line| line.contains("S")).unwrap();
let col_index = input
.lines()
.collect::<Vec<_>>()
.get(row_index)
.unwrap()
.chars()
.position(|c| c == character)
.unwrap();
(row_index, col_index)
}
pub async fn part1() -> u32 {
let input = get_input("https://adventofcode.com/2022/day/12/input").await;
let map = input
.lines()
.map(|line| line.chars().map(|c| get_index(c)).collect::<Vec<_>>())
.collect::<Vec<_>>();
let mut distances: BTreeMap<Point, u32> = BTreeMap::new();
let mut bfs = VecDeque::from([(0, get_position(input.as_str(), 'S'))]);
while bfs.len() > 0 {
let (distance, point) = bfs.pop_front().unwrap();
if distances.contains_key(&point) {
// We've already been here
continue;
} else {
distances.insert(point, distance);
}
for point in [
(point.0 as i32 + 1, point.1 as i32),
(point.0 as i32 - 1, point.1 as i32),
(point.0 as i32, point.1 as i32 + 1),
(point.0 as i32, point.1 as i32 - 1),
]
.iter()
.filter(|(row, col)| {
row >= &0 && row < &(map.len() as i32) && col >= &0 && col < &(map[0].len() as i32)
})
.map(|&(row, col)| (row as usize, col as usize))
.filter(|&(row, col)| map[row][col] <= map[point.0][point.1] + 1)
{
bfs.push_back((distance + 1, point));
}
}
*distances.get(&get_position(input.as_str(), 'E')).unwrap()
}
pub async fn part2() -> u32 {
let input = get_input("https://adventofcode.com/2022/day/12/input").await;
let map = input
.lines()
.map(|line| line.chars().map(|c| get_index(c)).collect::<Vec<_>>())
.collect::<Vec<_>>();
input
.lines()
.enumerate()
.filter(|(_, line)| line.contains("a"))
.map(|(i, line)| {
line.chars()
.enumerate()
.filter(|(j, c)| c == &'a')
.map(|(j, _)| (i, j))
.collect::<Vec<_>>()
})
.flatten()
.map(|point| {
let mut distances: BTreeMap<Point, u32> = BTreeMap::new();
let mut bfs = VecDeque::from([(0, point)]);
while bfs.len() > 0 {
let (distance, point) = bfs.pop_front().unwrap();
if distances.contains_key(&point) {
// We've already been here
continue;
} else {
distances.insert(point, distance);
}
for point in [
(point.0 as i32 + 1, point.1 as i32),
(point.0 as i32 - 1, point.1 as i32),
(point.0 as i32, point.1 as i32 + 1),
(point.0 as i32, point.1 as i32 - 1),
]
.iter()
.filter(|(row, col)| {
row >= &0
&& row < &(map.len() as i32)
&& col >= &0
&& col < &(map[0].len() as i32)
})
.map(|&(row, col)| (row as usize, col as usize))
.filter(|&(row, col)| map[row][col] <= map[point.0][point.1] + 1)
{
bfs.push_back((distance + 1, point));
}
}
*distances
.get(&get_position(input.as_str(), 'E'))
.unwrap_or(&1000)
})
.min()
.unwrap()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment