commit b434b533655630ca0e7b72e8a00b2029d3792cbd
parent c97da9a75995e9cf14447aaf09c1a4867e29625b
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 27 Jun 2025 15:18:13 +0200
Day 12 2022
Diffstat:
5 files changed, 132 insertions(+), 0 deletions(-)
diff --git a/2022/12/a.rs b/2022/12/a.rs
@@ -0,0 +1,8 @@
+mod common;
+use common::*;
+
+fn main() {
+ let mut map = read_input();
+ let end = |c: &Cell| c.is_start;
+ println!("{}", shortest_path_back(&mut map, end));
+}
diff --git a/2022/12/b.rs b/2022/12/b.rs
@@ -0,0 +1,8 @@
+mod common;
+use common::*;
+
+fn main() {
+ let mut map = read_input();
+ let end = |c: &Cell| c.h == 0;
+ println!("{}", shortest_path_back(&mut map, end));
+}
diff --git a/2022/12/common.rs b/2022/12/common.rs
@@ -0,0 +1,70 @@
+use std::collections::VecDeque;
+
+#[derive(Copy, Clone)]
+pub struct Cell {
+ pub h: i8,
+ #[allow(unused)]
+ pub is_start: bool,
+ pub seen: usize
+}
+
+pub struct Map {
+ pub cells: Vec<Vec<Cell>>,
+ pub end: (usize, usize)
+}
+
+impl Map {
+ pub fn neighbors(&self, v: (usize, usize)) -> Vec<(usize, usize)> {
+ [
+ ((v.0 as i64) -1, v.1 as i64),
+ ((v.0 as i64) +1, v.1 as i64),
+ (v.0 as i64, (v.1 as i64) -1),
+ (v.0 as i64, (v.1 as i64) +1)
+ ].iter()
+ .filter(|p| p.0 >= 0 && p.0 < self.cells.len() as i64 &&
+ p.1 >= 0 && p.1 < self.cells[0].len() as i64)
+ .map(|x| (x.0 as usize, x.1 as usize))
+ .collect()
+ }
+}
+
+pub fn read_input() -> Map {
+ let mut cells = Vec::<Vec<Cell>>::new();
+ let mut end = (0, 0);
+ let mut line = String::new();
+ while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+ let mut v = Vec::<Cell>::new();
+ let cs = line.as_bytes();
+ for i in 0..line.len()-1 {
+ let mut is_start = false;
+ let h = match cs[i] as char {
+ 'a'..='z' => cs[i] - ('a' as u8),
+ 'S' => { is_start = true; 0 },
+ 'E' => { end = (cells.len(), i); 26 },
+ u => panic!("Unexpected char {}", u)
+ } as i8;
+ let seen = if cs[i] as char == 'E' { 0 } else { usize::MAX };
+ v.push(Cell { h, is_start, seen });
+ }
+ cells.push(v);
+ line.clear();
+ }
+ Map { cells, end }
+}
+
+pub fn shortest_path_back(map: &mut Map, end: fn(&Cell) -> bool) -> usize {
+ let mut next = VecDeque::from([map.end]);
+ while !next.is_empty() {
+ let i = next.pop_front().unwrap();
+ let v = map.cells[i.0][i.1];
+ for j in map.neighbors(i) {
+ let w = &mut map.cells[j.0][j.1];
+ if w.h - v.h >= -1 && w.seen == usize::MAX {
+ w.seen = v.seen + 1;
+ if end(w) { return w.seen; }
+ next.push_back(j);
+ }
+ }
+ }
+ panic!("No path found");
+}
diff --git a/2022/12/input b/2022/12/input
@@ -0,0 +1,41 @@
+abaacccccccccccccaaaaaaaccccccccccccccccccccccccccccccccccaaaaaa
+abaaccccccccccccccaaaaaaaaaaccccccccccccccccccccccccccccccccaaaa
+abaaaaacccccccccaaaaaaaaaaaaccccccccccccccccccccccccccccccccaaaa
+abaaaaaccccccccaaaaaaaaaaaaaacccccccccccccccccdcccccccccccccaaaa
+abaaaccccccccccaaaaaaaaccacacccccccccccccccccdddcccccccccccaaaaa
+abaaacccccccccaaaaaaaaaaccaaccccccccccccciiiiddddcccccccccccaccc
+abcaaaccccccccaaaaaaaaaaaaaaccccccccccciiiiiijddddcccccccccccccc
+abccaaccccccccaccaaaaaaaaaaaacccccccccciiiiiijjddddccccaaccccccc
+abccccccccccccccaaacaaaaaaaaaaccccccciiiiippijjjddddccaaaccccccc
+abccccccccccccccaacccccaaaaaaacccccciiiippppppjjjdddddaaaaaacccc
+abccccccccccccccccccccaaaaaaccccccckiiippppppqqjjjdddeeeaaaacccc
+abccccccccccccccccccccaaaaaaccccckkkiippppuupqqjjjjdeeeeeaaccccc
+abccccccccccccccccccccccccaaccckkkkkkipppuuuuqqqjjjjjeeeeeaccccc
+abccccccccccccccccccccccccccckkkkkkoppppuuuuuvqqqjjjjjkeeeeccccc
+abcccccccccccccccccccccccccckkkkooooppppuuxuvvqqqqqqjkkkeeeecccc
+abccaaccaccccccccccccccccccckkkoooooopuuuuxyvvvqqqqqqkkkkeeecccc
+abccaaaaacccccaaccccccccccckkkoooouuuuuuuxxyyvvvvqqqqqkkkkeecccc
+abcaaaaacccccaaaacccccccccckkkooouuuuxxxuxxyyvvvvvvvqqqkkkeeeccc
+abcaaaaaaaaaaaaacccccccccccjjjooottuxxxxxxxyyyyyvvvvrrrkkkeecccc
+abcccaaaacaaaaaaaaacaaccccccjjoootttxxxxxxxyyyyyyvvvrrkkkfffcccc
+SbccaacccccaaaaaaaaaaaccccccjjjooottxxxxEzzzyyyyvvvrrrkkkfffcccc
+abcccccccccaaaaaaaaaaaccccccjjjooootttxxxyyyyyvvvvrrrkkkfffccccc
+abcaacccccaaaaaaaaaaaccccccccjjjooottttxxyyyyywwvrrrrkkkfffccccc
+abaaacccccaaaaaaaaaaaaaacccccjjjjonnttxxyyyyyywwwrrlllkfffcccccc
+abaaaaaaaaaaacaaaaaaaaaaccccccjjjnnnttxxyywwyyywwrrlllffffcccccc
+abaaaaaaaaaaaaaaaaaaaaaaccccccjjjnntttxxwwwwwywwwrrlllfffccccccc
+abaaccaaaaaaaaaaaaaaacccccccccjjjnntttxwwwsswwwwwrrlllfffccccccc
+abaacccaaaaaaaacccaaacccccccccjjinnttttwwsssswwwsrrlllgffacccccc
+abccccaaaaaaccccccaaaccccccccciiinnntttsssssssssssrlllggaacccccc
+abccccaaaaaaaccccccccccaaccccciiinnntttsssmmssssssrlllggaacccccc
+abccccaacaaaacccccccaacaaaccccciinnnnnnmmmmmmmsssslllgggaaaacccc
+abccccccccaaacccccccaaaaacccccciiinnnnnmmmmmmmmmmllllgggaaaacccc
+abaaaccccccccccccccccaaaaaacccciiiinnnmmmhhhmmmmmlllgggaaaaccccc
+abaaaaacccccccccccaaaaaaaaaccccciiiiiiihhhhhhhhmmlgggggaaacccccc
+abaaaaaccccaaccccaaaaaaacaacccccciiiiihhhhhhhhhhggggggcaaacccccc
+abaaaaccccaaaccccaaaacaaaaacccccccciiihhaaaaahhhhggggccccccccccc
+abaaaaaaacaaacccccaaaaaaaaaccccccccccccccaaaacccccccccccccccccaa
+abaacaaaaaaaaaaaccaaaaaaaaccccccccccccccccaaaccccccccccccccccaaa
+abcccccaaaaaaaaacccaaaaaaaccccccccccccccccaacccccccccccccccccaaa
+abccccccaaaaaaaaaaaaaaaaacccccccccccccccccaaacccccccccccccaaaaaa
+abcccccaaaaaaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccaaaaaa
diff --git a/2022/12/test b/2022/12/test
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi