diff options
Diffstat (limited to 'day12b/src')
| -rw-r--r-- | day12b/src/main.rs | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/day12b/src/main.rs b/day12b/src/main.rs new file mode 100644 index 0000000..9c422c3 --- /dev/null +++ b/day12b/src/main.rs @@ -0,0 +1,202 @@ +/// --- Part Two --- +/// +/// As you walk up the hill, you suspect that the Elves will want to turn this into a hiking +/// trail. The beginning isn't very scenic, though; perhaps you can find a better starting point. +/// +/// To maximize exercise while hiking, the trail should start as low as possible: elevation a. The +/// goal is still the square marked E. However, the trail should still be direct, taking the fewest +/// steps to reach its goal. So, you'll need to find the shortest path from any square at elevation +/// a to the square marked E. +/// +/// Again consider the example from above: +/// +/// ``` +/// Sabqponm +/// abcryxxl +/// accszExk +/// acctuvwj +/// abdefghi +/// ``` +/// +/// Now, there are six choices for starting position (five marked a, plus the square marked S that +/// counts as being at elevation a). If you start at the bottom-left square, you can reach the goal +/// most quickly: +/// +/// ``` +/// ...v<<<< +/// ...vv<<^ +/// ...v>E^^ +/// .>v>>>^^ +/// >^>>>>>^ +/// ``` +/// +/// This path reaches the goal in only 29 steps, the fewest possible. +/// +/// What is the fewest steps required to move starting from any square with elevation a to the +/// location that should get the best signal? +use clap::Parser; +use itertools::Itertools; +use pathfinding::prelude::bfs; + +use std::fs::File; +use std::hash::{Hash, Hasher}; +use std::io::prelude::*; +use std::io::BufReader; +use std::path::PathBuf; + +const FILEPATH: &'static str = "examples/input.txt"; + +#[derive(Parser, Debug)] +#[clap(author, version, about, long_about = None)] +struct Cli { + #[clap(short, long, default_value = FILEPATH)] + file: PathBuf, +} + +#[derive(Clone, Debug)] +struct Arena(Vec<Vec<Node>>); + +#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)] +struct Pos(usize, usize); + +#[derive(Clone, Debug)] +struct Node { + pos: Pos, + value: char, + connected: Vec<Pos>, +} + +impl Node { + fn new(pos: Pos, value: char) -> Self { + Node { + pos, + value, + connected: Vec::new(), + } + } +} + +impl PartialEq for Node { + fn eq(&self, other: &Self) -> bool { + self.pos == other.pos + } +} + +impl Eq for Node {} + +impl Hash for Node { + fn hash<H: Hasher>(&self, state: &mut H) { + self.pos.hash(state); + } +} + +impl Arena { + fn get(&self, coords: Pos) -> &Node { + &self.0[coords.0][coords.1] + } + + fn get_mut(&mut self, coords: Pos) -> &mut Node { + &mut self.0[coords.0][coords.1] + } +} + +fn is_connected(x: char, y: char) -> bool { + let (x, y) = match (x, y) { + ('S', _) => ('a', y), + ('E', _) => ('z', y), + (_, 'S') => (x, 'a'), + (_, 'E') => (x, 'z'), + _ => (x, y), + }; + + let (x, y) = (x as i8, y as i8); + i8::abs(x - y) <= 1 || x > y +} + +fn main() { + let args = Cli::parse(); + + let file = File::open(&args.file).unwrap(); + let reader = BufReader::new(file); + + let mut arena = Arena(Vec::new()); + let _ = reader + .lines() + .enumerate() + .map(|(idx, l)| { + l.unwrap() + .chars() + .enumerate() + .map(|(idy, c)| Node::new(Pos(idx, idy), c)) + .collect_vec() + }) + .scan(&mut arena, |arena, row| { + arena.0.push(row); + Some(()) + }) + .last(); + + let xdim = arena.0.len(); + let ydim = arena.0[0].len(); + + let mut lowest_pos = Vec::new(); + let mut end_pos = None; + + for idx in 0..xdim { + for idy in 0..ydim { + let node_val = arena.get(Pos(idx, idy)).value; + + match node_val { + 'a' | 'S' => lowest_pos.push(Pos(idx, idy)), + 'E' => end_pos = Some(Pos(idx, idy)), + _ => (), + } + + if idx != 0 { + let up_idx = Pos(idx - 1, idy); + if is_connected(node_val, arena.get(up_idx).value) { + arena.get_mut(Pos(idx, idy)).connected.push(up_idx); + } + } + + if idx != xdim - 1 { + let down_idx = Pos(idx + 1, idy); + if is_connected(node_val, arena.get(down_idx).value) { + arena.get_mut(Pos(idx, idy)).connected.push(down_idx); + } + } + + if idy != 0 { + let left_idx = Pos(idx, idy - 1); + if is_connected(node_val, arena.get(left_idx).value) { + arena.get_mut(Pos(idx, idy)).connected.push(left_idx); + } + } + + if idy != ydim - 1 { + let right_idx = Pos(idx, idy + 1); + if is_connected(node_val, arena.get(right_idx).value) { + arena.get_mut(Pos(idx, idy)).connected.push(right_idx); + } + } + } + } + + let end = arena.get(end_pos.unwrap()); + + let res = lowest_pos + .into_iter() + .filter_map(|s| { + let steps = bfs( + &arena.get(s), + |n| n.connected.iter().map(|&p| arena.get(p)), + |&n| n == end, + )? + .len() + - 1; + Some(steps) + }) + .min() + .unwrap(); + println!("{res}"); +} |