commit d78541c47c0b2b2a977a8a23114541bbbf7a0556
parent 6fb3f5aa5a2c076bd6263fca2b105d5837513c25
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 9 Jul 2025 17:18:36 +0200
Day 24 2022
Diffstat:
5 files changed, 269 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 }
+}
diff --git a/2022/24/input b/2022/24/input
@@ -0,0 +1,37 @@
+#.####################################################################################################
+#<v>v>v><>^<>^.^vv<>><>>v.>v<.v>>v<<v<.^<>>>v<v^>.^<^>v>^<^v.^>v^>>><v<>v^<v<<^^.vv>.^>v>v<.^v<><v<>>#
+#>>v<^<>vvv.>^.v^^>^<<vv>>v.<^<>v^<v^>v^<>>.v.^<<v^.^v^v><<.^vv<^<^v>.vvv<v>.<>>^>.<<<<<<.<^^<v.<>.v<#
+#<<<>^^>>>>.v^>v<>^>^^v>v^^v..v^.<<^>^>.>v^^vv.<>>^><<>v.<v<^^<<v^v<.>^>v<>^^<<>v<<^^><vv>vv<<^^...^>#
+#>>v><><<<^<.>v^<<v^>v^^<>>v<<>>.<>v><^<^<.^<><^^^vv>><v<v>vv>^>v^>>vv>><<v^<><>^v.vv>^<^<>v<vvvv^v><#
+#<^<^>v^^<>>^<.^^>^vv><v<^^^.v^>><v^>v^.>>v^<..>>.v>v<v^^<.v<<^v<<>v.^>><>v<<>.^<<<<<>>>^<><v>><^>>v>#
+#>v>^^^v<v^.>^>^>v>>>v>v<v^v^<v>>><<>v..>>vvv<^><<>>^^.>v^<^>>.^v><v<^<.^>>vv<v^<^vv^<<<^><v.>v<^<.v>#
+#>v^>>v^<^<<^<v>..<.v^<.<><>v>v^<.><<<<^><<.<><><><.<.^.>^v^><<<vv.<>vvv<v^v.<^<>>>^>v<^v^<><><v>.^><#
+#<><>>vv..<v^vv><^v^.^^vv.^>^>>v<>vv>^><<<><^vvv>>><>><>>^^<v<><^^v^^>.^>^<.<<^..v<v>v^>^v^v<<.v^<v<>#
+#>><^<>.v.><^.^^..^<v.v><v^<<v>^<><^>^..<vv>><^^>v^>.^><v>v^v>>>>vv<<>><v^<<^^v^vv<.>vv^><v^.^v>...v>#
+#>vv<v<><v>v>v>><^>>.<^<<^<^>^.^v>>vv^vv<^v><>>v^<^v.v^<v<vv^v><.^^>><.v^^><<^<><^>>vv^.><vv^<>>v.><<#
+#<^<^<>v^v^^^<<v<>vv<<<.v<v^v^^><.>^.v.>vvv>^<<<v>^^>.^<<.v<v>^v..v<<<<<^^v^v^<>^>>^.>^<^v<.v..^v^>^>#
+#<<^^<>^^><v>v.<<><<<v<^<^>^<<^v<<>^^<.^^^^<>^>><^>.v^v>v.<.^<<vv^^>>>^v<v<<vv^><<.<>>><.v<^^>>^v>^^<#
+#>v><>..v^>v>^<<^>vv>.^v^v>>v^^^>><><<>v^.vv^.<><v>^^v^>.<^><<^^>>v^.^^^>v.<>^^<^>>^<^<<<^>^<>>^<<v<>#
+#>vv<.vv><>^>>>>.<>.>v^>>v><<<v<.v^v>v^<v^<>>vv><.<><v>^>^<^^v^>v^<><>^^^>^<<^^.>..>.>^>^>>^>v>v<v<><#
+#<>>v^>^<.v^^.^<vv^<>^>^^<^.^.>^<<^>><^vv><.v><^vv^^^^^v><><vv.v.>.^^v^v.>^v.<><v>>v>vv^.vv^^<>^>.><<#
+#>>>>>>>.v<>^<^.>><v^^<v.<^<^>vv.^v>^>.>^>>^>>v^>v>.v.><<^^<^<vv.vv<vvvvv^^v><^^^>>><^>>v<v>>>v<^^.^>#
+#>^^^^<<v^^^...^<v>>^^v^^><<.<><>^v^v^>>>^^>.v<v.v<v^^v<vv>v>vv>^v^<>^vv^vv.^vv>v^v>v>>.<>>><^^<^^>^<#
+#<^^^<v>^.<>^>^<^<v>vv<vv<^vv^^<><v^>v>^.><^^v<>><>vvvv^>^^<<^v><<v^v<><^<<>^.v<><vv<><>>^.>v>vv>><^<#
+#>v^^^^><^<vv<^<v>v.<^.><.^>>^<>v.<<^<>.>vv<<.vv.v>v^.<^<^^>>^.><>v<v<v>v<v>>vv>^<><^<v>>><v>><<vvv^.#
+#>><>><^^<^^>v<^.^>><<v<^v<>v>v^<<<<^^.v>v^.>v^<^><^v<v.>><v<^>^^>^^^^.<v>^>.v^<^^<<><>.<v^v>^^>v<^.<#
+#><v>v^^<>.vvv>>.<..^^.<<^>>v^<>.<v<<vv><v<^v.^>>>v>.<^>.vvv<v<^<^^>^>v>v<>v<^v<vv^>v<<<<<>.^v^^.>><.#
+#<>>.<>^^>>><>>^<><<^^v^><v><<<<v>>^<^vv<<.v^<<<^>v>v^<^.<<<<^<^v^>vv.<.^><v<.^^<^>^.>^v^v>^>^<^.v><.#
+#<^<.<^^<>^v<^<^>^>^.>.<<^.v<>v^^>>..v^v<.>^>^.^^v>^v^>vv>>^<^>>>^>><<v><><<v^<>>v.vv><>.><^.v<^<v<<>#
+#<v^.v<>^^>v>.vv><>^v<^<^.<^>>v^^.><^<v<>v<<vv<>.<>v<v<>.>^^.v.^v><^^.^v<vv<<^<>>v.>^^.>^^><>>>>.^^.<#
+#<>^<>^><.^^^v<^v^>v.>^<>^^v<vv^><v^^>^.><>^v<v>v<>.^><^^>^v<<.>>^^<.v<><vv>vv>>>v^v><v^<^<>v<^>>^<.<#
+#>v^<v^>^>>^<^<^>v<^vvvv<<<vv<.><^<.^^>.>^.v<v<><<.<v>v^vv<>^<v<^<>>.^<>^v<vv<<><<.<^><v<<^><^<><<>^>#
+#<<><..v<^v<>^.v>v^.<v.><>>v>>vv>v^^^><vvv<.>^^<v<vv<<v<.^^^..^<<<^^v^>><>>^v>v><<>^^v..>^<^vv^<v><^<#
+#><>vv<<<.vv>^^<v>^<^<vvv^v<<<<<^v<.>>^><^v>vv><v>>>^^^<v.><>><<v^^.vv.^v><<<<<<^>^v>>.>>v.>v^<<>^v^.#
+#.^>>>vv>vv>^^v>>^.<v>^v.>^>..<v.><^<^>.^<v^<>^v^v^>vv<>v^^><<.^>>^..<^^>><.vv>>v^<v><<^v>>>>v><>.^v>#
+#>^^^>v<><><v>>>^^vv^^^v.v><v<>>^v^v^^>^v.>vv..^>>^v^<.^<<v<>^v<^<..^v>^<^^^v.v^>^^<>v><^<.^<v^.v.v>>#
+#>v>v>>>vvvv<>>v^><>v<v^.^>>v>.v^vv.^^v.^>>>^^^>v.v<^>>v<v<>^^v^^>^<v..v^<^>^v^vv<<v><vv.v^v.vv>v<^.>#
+#><^<>v^>>^><>vv>v^><<v<.>^.v^><<<^v>^>.v<<>^vvvv>.vv^v.><<^<v^.<.vv.vv^^>v^>v>>v^v><<v<^<v<><^v<>^^<#
+#<vv^^>v>v<^>.<>..>>vv^^v^<vv>^.>^<^><v><^>>>><.^>v^<v^>v^<>.<.>.<<^<v>><v>>vvv<>.v^<>vvvv>v<.>^vv^v>#
+#>.<^<<^<>^v.^v^>v^<<>^^>^<.vvvv<^<.v^<>v>><v^^.v^v^<>><.^<v<<>.>v^>^><.>^>>.v^.^..^<v^^v^vv<^v.><<>>#
+#<>>>v<vv.^v>v^.v<<v<><v..v>vv^^v^<vv>><<v<v^>v<.>^.^v^<.>><><>^<>>vv>^>.>v><><^vv>>v>^^<<..><.>.>^.>#
+####################################################################################################.#
diff --git a/2022/24/test b/2022/24/test
@@ -0,0 +1,6 @@
+#.######
+#>>.<^<#
+#.<..<<#
+#>v.><>#
+#<^v^^>#
+######.#
