diff options
Diffstat (limited to 'day12a')
| -rw-r--r-- | day12a/Cargo.toml | 11 | ||||
| -rw-r--r-- | day12a/examples/input.txt | 41 | ||||
| -rw-r--r-- | day12a/examples/test.txt | 5 | ||||
| -rw-r--r-- | day12a/src/main.rs | 212 |
4 files changed, 269 insertions, 0 deletions
diff --git a/day12a/Cargo.toml b/day12a/Cargo.toml new file mode 100644 index 0000000..3f67904 --- /dev/null +++ b/day12a/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "day12a" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +clap = { version = "3.2.20", features = ["derive"] } +itertools = "0.10.5" +pathfinding = "4.2.0" diff --git a/day12a/examples/input.txt b/day12a/examples/input.txt new file mode 100644 index 0000000..4b447da --- /dev/null +++ b/day12a/examples/input.txt @@ -0,0 +1,41 @@ +abccccaaaaaaaaaaaaaccaaaaaaaacccccccccaaaaaaaaccccccccaaacaaacccccccaaaaaaccccccccccccccccccccccaaaacccccccccccacccccccccccccccccccccccccccccccccccccccccccccccaaaa +abccccaaaaacaaaaaaccccaaaaaaccccccccccaaaaaaacccccccccaaaaaaacccccaaaaaaaaaacccccccccccccccccccaaaaaacccccccccaaaaaaaaccccccccccccccccccccccccccccccccccccccccaaaaa +abcccaaaaaccaaaaaaccccaaaaaaccccccaacccaaaaaacccccccccaaaaaacccaaaaaaaaaaaaaaacaaccacccccccccccaaaaaaccccccccccaaaaaacccccccccccccccccccccccccccccccccccccccccaaaaa +abccccccaaccaaaaaaccaaaaaaaaccccccaaacaaaacaaacccccccaaaaaaaaccaaaaaaaaaaaaaaacaaaaacccccccccccccaaccccccccccccaaaaaaccccccccccccccccccccccccccccacccccccccccaaaaaa +abccccccccccaaccaaccaaaaccaacccccccaaaaaaaccccccccccaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacccccccaaaaccccccccccccccccaaaaaaaacccccccccccccccccccccccccccaaccccccccccccccaa +abcccccccaaaaacccaaaaaaaacccaaccccaaaaaaccccccccccccaaaaaaaaaaaaaaaacaaaaaaaccaaaaaaccccccaaaaaccccccccccccccaaaaaaaaaaccaccccccccccccccccccccccccaccccccccccccccca +abcccccccaaaaacccaaaaaaaaccaaaaccaaaaaaaaccccccccccccccaaacaaaaaaaaacaaaaaacccccaaaacccccaaaaaaccccccccccccccaaaaaaaaaaaaacccccccccccccccllllllccccdccccccccccccccc +abccccccaaaaaacccccaaaaccccaaaaacaaaaaaaaccccccccccccccaaacccccaaaccccaaaaaacccaaccccccccaaaaaacccccccccccccccccaaaaaaaaaacccccccccccccklllllllllcddddccaccaaaccccc +abccccccaaaaaacccccaaaaaaaaaaaaaaaccaaccccccaacaacccccccaaccccccccccccaaacaacccccccccccccaaaaaacccccccccccccccccaaaaaaaaaacccccccccccckklllppllllcddddddddaaaaccccc +abccccccaaaaaaccccaaacaaaaaaaaaaaaccaaccccccaaaaaccccccccccccccccccccccccccccccccccccccccccaaccccccaaccccccccccccaacaaaaaaaccccccccccckklpppppplllmdddddddddacccccc +abccccccccaaacccccaacccaccaaaaaaccccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccccccaaaaccccccccccccaaaaaaaaaaccccccccckkkkppppppplmmmmmmddddddaacccc +abccccaaacaaacccccccccccccaaaaaaccccccccccccaaaaaacccccccccccccccccaaaccccccccccccccccccccccccccccaaaaccccccccccccaaaaaaaaaaccccccccckkkppppuppppmmmmmmmmddeeeacccc +abccccaaaaaaacccccccccccccaaaaaacccaccccccccaaaaaacccccccccccccccccaaaacccccccccccccccccccccaaacccaaaacccccccccccaaaacaaaccccccccccckkkpppuuuuuppqqmmmmmmmmeeeacccc +abcccccaaaaaaccccccccccccaaaaaaaacaaccccccccccaaaccccccccccccccccccaaaaccccccccccccccccccccaaaaccccccccccccccccccaaaaaaaacccccccccckkkkpppuuuuupqqqqqqqmmmmeeeccccc +abcccccaaaaaaaacccccccccccaccccaaaaacccccccccccccccccccccccccccccccaaaccccccccccccccaaaccccaaaacccccccccccccaaccaaaaaaaaccccccccckkkkkrrpuuuxuuuqqqqqqqqmmmmeeccccc +abccccaaaaaaaaaccccccccccccccaaaaaacccccccacaacccccccccccccccccccccccccccccccccccccaaaaaacccaaaccccccccccaaaaccaaaaaaacccccccccckkkkrrrrruuuxxuvvvvvvqqqqnnneeccccc +abcccaaaaaaaaaaccccccccccccccaaaaaaaacccccaaaaacccccccccccccccaaaaaccccccccccccccccaaaaaaccccccccccccccccaaaaaaaaaaaaacccccccccjjjkrrrrruuuxxxxvvvvvvvqqqnnneeccccc +abcaaaaacaaacccccccccccccccccaaaaaaaacccccaaaaaccaacccccccccccaaaaaccccccccccccccccaaaaaccccccccccccccccccaaaaaccaaaaaacccccccjjjrrrrruuuuuxxxyvyyyvvvqqqnneeeccccc +abcaaaaacaaaccaaccccccccccccccccaacccccccaaaaaaaaaaaccccccccccaaaaaaccccccccccccccccaaaaaccccccccccccccccaaaaacccaaaaaaaacaaacjjjrrrtttuuxxxxxyyyyyvvvqqnnneeeccccc +abaaaaaccaacccaaaccaacccaaccccccaccccccccaaaaaaaaaacccccccccccaaaaaaccccccccccccccccaacaacccccccccccccccccccaacccaaccccaaaaaacjjjrrrtttxxxxxxxyyyyyvvvrrnnneeeccccc +SbaaaaacccccccaaaaaaaccaaaacccccccccccccccaaaaaaaaacccccccccccaaaaaaccccccccccccccccccccccccccccccccccccccccccccccaacccaaaaaacjjjrrrtttxxxEzzzzyyyvvvrrnnneeecccccc +abcaaaaacccccccaaaaaaccaaaacccccccccccccccaaaaaaaaacccccccccccccaaccccccccccccccccccccccccccccaaccccccccccaaccccacaaaacaaaaaaajjjrrrtttxxxxxyyyyyvvvrrrnnnfffcccccc +abcaacccccccaaaaaaaacccaaaaccccccccccccccccaaaaaaaaaaccccccccccccccccccccccccccccccccccccccaaaaaccccccccccaaccccaaaaaaaaaaaaaajjjqqqttttxxxxyyyyyyvvrrrnnnfffcccccc +abccccccccccaaaaaaaaaccccccccccccccccccccaaaaaaaaaaaaacccccccccccccccccaacccccccccccccccccccaaaaaccccccaacaaaaaccaaaacaaaaaaaacjjjqqqqttttxxyywyyyywvrrnnnfffcccccc +abccccccccccaaaaaaaaaacccccccccccccccccccaaaaaaaaacaaacccccccccccccaaacaacccccccccccccccccccaaaaaccccccaaaaaaaaccaaaaccccaaacccjjjjqqqqtttxwywwwyywwwrrnnnfffcccccc +abcccccccccccccaaaaaaacccccccccccccccccccaaaaaaaaaaaaaaaacccccccccccaaaaaccccccccccccccccccaaaaacccaaccccaaaaccccaacaacccaaaccccjjjiqqqtttwwywwwwwwwwrrroofffcccccc +abcccccccccccccaaaccccccccccccccccccccccaaaaaaaaaaaaaaaaaccccccccccccaaaaaacccccccccccccccccccaaacaaaccccaaaaaccccccccccccccccccciiiiqqqttwwwwwswwwwrrrroofffcccccc +abcccccccccccccaaccccccccccccaaaacccccccaaaaaaaaccaaaaacccccccccccccaaaaaaacccccccccccccccccccaaaaaaacccaaacaacccccaaaaacccccccccciiiqqqttwwwwsssssrrrrroofffaccccc +abcccccccccccccccccccccccccccaaaaccccccccacaaacccaaaaaaccccccaaccccaaaaaaccccccccaacaaccccccccaaaaaaccccaaaacacccccaaaaacccccccccciiiqqqtsswsssssssrrrrooofffaccccc +abcccccccccccccccccccccccccccaaaaccccccccccaaaccaaaaaaaccccccaaaaccaacaaaccccccccaaaaacccccccccaaaaaaaaccaaacacccccaaaaaacccccccccciiqqqssssssspposrrroooofffaccccc +abccccaaacccccccccccccccccccccaaacccccccccccccccaaacaaaccccaaaaaacccccaaaccccccccaaaaaacccccccaaaaaaaaaaaaaaaaaccccaaaaaaccccccaccciiiqqpsssssppppooooooogffaaccccc +abccccaaaaaacccaaaccccccccccccccccccccccccccccccccccccaccccaaaaacccccccccccccccccaaaaaaccccccaaaaaaaaaaaaaaaaaaccccaaaaaacccaaaaccciiiqqppppppppppoooooogggfaaacccc +abcccaaaaaaacccaaaccccccccccccccccccccccccccccccccccccccccccaaaaaccccccccccccccccaaaaaaccccccaaacaaaccccaaaaaacccccccaacccccaaaaaacciiipppppppphgggggggggggaaaacccc +abccaaaaaaaacccaaacaaacccccccccccccccccccccaacccccccccccccccaacaacccccaacccccccccccaaacccccccccccaaacccccaaaaacccccccccccccccaaaaacciiihppppphhhhgggggggggaaccccccc +abccaaaaaaacaaaaaaaaaacccccccccccccccccccccaaaccccccacccccccccccccccccaaccccccccccccccccccccccccaaaaccccaaaaaaccccccccccccccaaaaacccciihhhhhhhhhhgggggggccaaccccccc +abccccaaaaaaaaaaaaaaacccccccccccccccccccaaaaaaaaccccaaacaaaccccccccccaaaaccaaccccccccaacaacccccaaaaaaacccaacccccccccccccccccaacaaccccchhhhhhhhhaaaacccccccccccccccc +abccccaaaaaacaaaaaaaccccccccccccccccccccaaaaaaaaccccaaaaaaaccccccccccaaaaaaaacaccccccaaaaaccccccaaaaacccccccccccccccccccccccccccccccccchhhhhhacaaaaaccccccccccccccc +abccccaaccccccaaaaaacccccccccccccaaccccccaaaaaacccccaaaaaaccccccaaaaaaaaaaaaaaaccccccaaaaaacccaaaaaaacccccccccccccccccccccccccccccccccccccaaaaccaaacccccccccccaaaca +abccccccccccccaaaaaaaccccccccccccaaccccccaaaaaacccaaaaaaaaccccccaaaaaaaaaaaaaacccccccaaaaaacccaaaaaaaaccccccaaacccccccccccccccccccccccccccaaaaccccccccccccccccaaaaa +abccaaacccccccaaacaaacccccccccaaaaaaaacccaaaaaacccaaaaaaaaacccccaaaaaaaaaaaaaacccccccaaaaaccccaaaaaaaaccccccaaaaccccccccccccccccccccccccccaaaccccccccccccccccccaaaa +abcaaaacccccccaaccccccccccccccaaaaaaaacccaaccaacccaaaaaaaaaaccccccccaaaaaaacaacccccccccaaaccccccaaacaaccccccaaaacccccccccccccccccccccccccccccccccccccccccccccaaaaaa diff --git a/day12a/examples/test.txt b/day12a/examples/test.txt new file mode 100644 index 0000000..86e9cac --- /dev/null +++ b/day12a/examples/test.txt @@ -0,0 +1,5 @@ +Sabqponm +abcryxxl +accszExk +acctuvwj +abdefghi diff --git a/day12a/src/main.rs b/day12a/src/main.rs new file mode 100644 index 0000000..2ae1c4b --- /dev/null +++ b/day12a/src/main.rs @@ -0,0 +1,212 @@ +/// --- Day 12: Hill Climbing Algorithm --- +/// +/// You try contacting the Elves using your handheld device, but the river you're following must be +/// too low to get a decent signal. +/// +/// You ask the device for a heightmap of the surrounding area (your puzzle input). The heightmap +/// shows the local area from above broken into a grid; the elevation of each square of the grid is +/// given by a single lowercase letter, where a is the lowest elevation, b is the next-lowest, and +/// so on up to the highest elevation, z. +/// +/// Also included on the heightmap are marks for your current position (S) and the location that +/// should get the best signal (E). Your current position (S) has elevation a, and the location +/// that should get the best signal (E) has elevation z. +/// +/// You'd like to reach E, but to save energy, you should do it in as few steps as possible. +/// During each step, you can move exactly one square up, down, left, or right. To avoid needing +/// to get out your climbing gear, the elevation of the destination square can be at most one +/// higher than the elevation of your current square; that is, if your current elevation is m, you +/// could step to elevation n, but not to elevation o. (This also means that the elevation of the +/// destination square can be much lower than the elevation of your current square.) +/// +/// For example: +/// +/// ``` +/// Sabqponm +/// abcryxxl +/// accszExk +/// acctuvwj +/// abdefghi +/// ``` +/// +/// Here, you start in the top-left corner; your goal is near the middle. You could start by +/// moving down or right, but eventually you'll need to head toward the e at the bottom. From +/// there, you can spiral around to the goal: +/// +/// ``` +/// v..v<<<< +/// >v.vv<<^ +/// .>vv>E^^ +/// ..v>>>^^ +/// ..>>>>>^ +/// ``` +/// +/// In the above diagram, the symbols indicate whether the path exits each square moving up (^), +/// down (v), left (<), or right (>). The location that should get the best signal is still E, and +/// . marks unvisited squares. +/// +/// This path reaches the goal in 31 steps, the fewest possible. +/// +/// What is the fewest steps required to move from your current position 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 start_pos = None; + 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 { + 'S' => start_pos = Some(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 start = arena.get(start_pos.unwrap()); + let end = arena.get(end_pos.unwrap()); + + let res = bfs( + &start, + |n| n.connected.iter().map(|&p| arena.get(p)), + |&n| n == end, + ) + .unwrap() + .len() + - 1; + println!("{res}"); +} |