1 files changed, 204 insertions, 0 deletions

diff --git a/2022/24/common.rs b/2022/24/common.rs
new file mode 100644
index 0000000..0af4789
--- /dev/null
+++ 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 }
+}