commit ee0cbf2ec592b28dca6d1142639e06de52ff1b3e
parent 9637b5a1f8d10e3003651c5d9006f0e102f74f18
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 9 Jul 2025 17:18:36 +0200
Day 24 2022
Diffstat:
3 files changed, 226 insertions(+), 0 deletions(-)
diff --git a/2022/24/a.rs b/2022/24/a.rs
@@ -0,0 +1,8 @@
+mod common;
+use common::*;
+
+fn main() {
+ let map = read_map_from_stdin();
+ let result = map.shortest_path(Position::Start, Position::Finish, 0);
+ println!("{result}");
+}
diff --git a/2022/24/b.rs b/2022/24/b.rs
@@ -0,0 +1,14 @@
+mod common;
+use common::*;
+
+fn main() {
+ // The approach is greedy: once we reach the start / finish cell,
+ // we can wait there as long as we want, so it is always better
+ // to reach the partial destinations as soon as possible.
+
+ let map = read_map_from_stdin();
+ let a = map.shortest_path(Position::Start, Position::Finish, 0);
+ let b = map.shortest_path(Position::Finish, Position::Start, a);
+ let c = map.shortest_path(Position::Start, Position::Finish, b);
+ println!("{c}");
+}
diff --git a/2022/24/common.rs b/2022/24/common.rs
@@ -0,0 +1,204 @@
+// This code is more complicated than it should be. The reason is that
+// for part 1 I decided to ignore the start and finish position, and not
+// to treat them as other cells. This way I could get away with not
+// considering wall cells '#' at all.
+// But then for part 2 it was more convenient to include them, so I
+// added an enum Position {} that treats start and finish as special
+// cases. This is quite messy.
+
+use std::collections::{VecDeque, HashSet};
+
+#[derive(PartialEq, Debug)]
+pub enum Direction { Up, Down, Left, Right, None }
+
+impl Direction {
+ pub fn from_byte(b: u8) -> Direction {
+ match b {
+ b'^' => Direction::Up,
+ b'v' => Direction::Down,
+ b'>' => Direction::Right,
+ b'<' => Direction::Left,
+ b'.' => Direction::None,
+ x => panic!("unexpected char '{}'", x as char)
+ }
+ }
+}
+
+#[derive(Hash, Eq, PartialEq, Copy, Clone, Debug)]
+pub enum Position {
+ Start,
+ Finish,
+ Other { i: usize, j: usize }
+}
+
+impl Position {
+ pub fn dist(&self, other: Position) -> usize {
+ match (*self, other) {
+ (Position::Start, Position::Start) |
+ (Position::Finish, Position::Finish) =>
+ 0,
+ (Position::Start, Position::Finish) |
+ (Position::Finish, Position::Start) =>
+ usize::MAX, // Not technically correct, but it works
+ (Position::Start | Position::Finish, Position::Other { i, j }) |
+ (Position::Other { i, j }, Position::Start | Position::Finish) =>
+ i + j,
+ (Position::Other { i: i1, j: j1 },
+ Position::Other { i: i2, j: j2 }) => {
+ let i = (i1 as i64 - i2 as i64).abs() as usize;
+ let j = (j1 as i64 - j2 as i64).abs() as usize;
+ i + j
+ }
+ }
+ }
+}
+
+pub struct Map {
+ pub tiles: Vec<Vec<Direction>>,
+ pub imax: usize,
+ pub jmax: usize
+}
+
+#[derive(Hash, Eq, PartialEq, Copy, Clone, Debug)]
+struct Node {
+ p: Position,
+ t: usize
+}
+
+impl Map {
+ fn submod(i: usize, t: usize, m: usize) -> usize {
+ let maybeneg = ((i as i64) - (t as i64)) % m as i64;
+ (maybeneg as usize + m) % m
+ }
+
+ pub fn is_busy(&self, p: Position, t: usize) -> bool {
+ match p {
+ Position::Start | Position::Finish => false,
+ Position::Other { i, j } => {
+ let iup = Self::submod(i, t, self.imax);
+ let idown = (i + t) % self.imax;
+ let jleft = Map::submod(j, t, self.jmax);
+ let jright = (j + t) % self.jmax;
+
+ self.tiles[iup][j] == Direction::Down ||
+ self.tiles[idown][j] == Direction::Up ||
+ self.tiles[i][jleft] == Direction::Right ||
+ self.tiles[i][jright] == Direction::Left
+ }
+ }
+ }
+
+ #[allow(dead_code)]
+ pub fn print(&self, t: usize) {
+ print!("#.");
+ for _ in 0..self.jmax { print!("#"); }
+ println!();
+
+ for i in 0..self.imax {
+ print!("#");
+ for j in 0..self.jmax {
+ let p = Position::Other { i, j };
+ print!("{}", if self.is_busy(p, t) { '*' } else { '.' });
+ }
+ println!("#");
+ }
+
+ for _ in 0..self.jmax { print!("#"); }
+ print!(".#");
+ println!();
+ }
+
+ fn mv(&self, p: Position, d: Direction) -> Option<Position> {
+ if d == Direction::None { return Some(p); }
+ match p {
+ Position::Start => if d == Direction::Down {
+ Some(Position::Other { i: 0, j: 0 })
+ } else { None },
+ Position::Finish => if d == Direction::Up {
+ Some(Position::Other { i: self.imax-1, j: self.jmax-1 })
+ } else { None },
+ Position::Other { i, j } => match d {
+ Direction::Up => if i > 0 {
+ Some(Position::Other { i: i-1, j })
+ } else {
+ if i == 0 && j == 0 {
+ Some(Position::Start)
+ } else { None }
+ },
+ Direction::Down => if i < self.imax-1 {
+ Some(Position::Other { i: i+1, j })
+ } else {
+ if i == self.imax-1 && j == self.jmax-1 {
+ Some(Position::Finish)
+ } else { None }
+ },
+ Direction::Left => if j > 0 {
+ Some(Position::Other { i, j: j-1 })
+ } else { None },
+ Direction::Right => if j < self.jmax-1 {
+ Some(Position::Other { i, j: j+1 })
+ } else { None },
+ Direction::None => panic!("stupid rust")
+ }
+ }
+ }
+
+ fn maybe_push(&self, x: Node, d: Direction, v: &mut HashSet<Node>) {
+ if let Some(p) = self.mv(x.p, d) {
+ if !self.is_busy(p, x.t+1) {
+ v.insert(Node { p, t: x.t+1 });
+ }
+ }
+ }
+
+ pub fn shortest_path(
+ &self,
+ start: Position,
+ finish: Position,
+ t0: usize
+ ) -> usize {
+ let mut vnext = HashSet::<Node>::new();
+ vnext.insert(Node { p: start, t: t0 });
+ while !vnext.is_empty() {
+ let mut v = vnext.clone().into_iter().collect::<Vec<_>>();
+ // Heuristic: explore first the positions closer to the target
+ v.sort_by(|a, b| a.p.dist(finish).cmp(&(b.p.dist(finish))));
+ let mut v = VecDeque::<Node>::from(v);
+ vnext.clear();
+ while !v.is_empty() {
+ let x = v.pop_front().unwrap();
+ if x.p == finish { return x.t; }
+
+ self.maybe_push(x, Direction::Up, &mut vnext);
+ self.maybe_push(x, Direction::Down, &mut vnext);
+ self.maybe_push(x, Direction::Left, &mut vnext);
+ self.maybe_push(x, Direction::Right, &mut vnext);
+ if !self.is_busy(x.p, x.t+1) {
+ self.maybe_push(x, Direction::None, &mut vnext);
+ }
+ }
+ }
+ panic!("queue is empty");
+ }
+}
+
+pub fn read_map_from_stdin() -> Map {
+ let mut tiles = vec![];
+ let mut line = String::new();
+ while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+ let bytes = line.as_bytes();
+ if bytes[2] == b'#' {
+ line.clear();
+ continue;
+ }
+ let i = tiles.len();
+ tiles.push(vec![]);
+ for j in 1..bytes.len()-2 {
+ tiles[i].push(Direction::from_byte(bytes[j]));
+ }
+ line.clear();
+ }
+ let imax = tiles.len();
+ let jmax = tiles[0].len();
+ Map { tiles, imax, jmax }
+}
