feat(guest): Add zk_dungeon program

Ported from
https://github.com/blocksense-network/noir/tree/6a4f172c0cbee1e2baea7d4c0684121d5921c09a/test_programs/plonky2_prove_success/zk_dungeon

Co-authored-by: Stan Manilov <stanislav.manilov@gmail.com>

2 files changed, 75 insertions, 0 deletions

diff --git a/guests/zk_dungeon/src/dungeon.rs b/guests/zk_dungeon/src/dungeon.rs
new file mode 100644
index 0000000..f0659a2
--- /dev/null
+++ b/guests/zk_dungeon/src/dungeon.rs
@@ -0,0 +1,65 @@
+#[derive(Copy, Clone)]
+pub struct Square {
+    x: u8,
+    y: u8,
+}
+
+impl From<(u8, u8)> for Square {
+    fn from(val: (u8, u8)) -> Self {
+        Square { x: val.0, y: val.1 }
+    }
+}
+
+impl Square {
+    pub fn from_array<const N: usize>(val: [(u8, u8); N]) -> [Square; N] {
+        val.map(|x| x.into())
+    }
+}
+
+fn is_valid_step(prev: Square, curr: Square) -> bool {
+    ((prev.x + 2 == curr.x) & (prev.y + 1 == curr.y))
+        | ((prev.x - 2 == curr.x) & (prev.y + 1 == curr.y))
+        | ((prev.x + 2 == curr.x) & (prev.y - 1 == curr.y))
+        | ((prev.x - 2 == curr.x) & (prev.y - 1 == curr.y))
+        | ((prev.x + 1 == curr.x) & (prev.y + 2 == curr.y))
+        | ((prev.x - 1 == curr.x) & (prev.y + 2 == curr.y))
+        | ((prev.x + 1 == curr.x) & (prev.y - 2 == curr.y))
+        | ((prev.x - 1 == curr.x) & (prev.y - 2 == curr.y))
+}
+
+fn is_within_bounds(square: Square) -> bool {
+    (square.x >= 0) & (square.x < 8) & (square.y >= 0) & (square.y < 8)
+}
+
+pub fn is_valid_path(path: [Square; 8], dagger: Square) {
+    assert!(path[0].x == 0);
+    assert!(path[0].y == 0);
+    assert!(path[7].x == dagger.x);
+    assert!(path[7].y == dagger.y);
+    for i in 1..8 {
+        assert!(is_within_bounds(path[i]));
+        assert!(is_valid_step(path[i - 1], path[i]));
+    }
+}
+
+fn is_safe_step(square: Square, watcher_map: [[bool; 8]; 8]) -> bool {
+    let mut result = true;
+    for x in 0..8 {
+        for y in 0..8 {
+            if watcher_map[x][y] {
+                let fx = x as u8;
+                let fy = y as u8;
+                if (square.x - fx == square.y - fy) | (square.x - fx == fy - square.y) {
+                    result = false;
+                }
+            }
+        }
+    }
+    result
+}
+
+pub fn is_safe_path(path: [Square; 8], watcher_map: [[bool; 8]; 8]) {
+    for i in 0..8 {
+        assert!(is_safe_step(path[i], watcher_map));
+    }
+}
diff --git a/guests/zk_dungeon/src/lib.rs b/guests/zk_dungeon/src/lib.rs
new file mode 100644
index 0000000..b79167a
--- /dev/null
+++ b/guests/zk_dungeon/src/lib.rs
@@ -0,0 +1,10 @@
+#![cfg_attr(feature = "no_std", no_std)]
+
+mod dungeon;
+
+#[guests_macro::proving_entrypoint]
+pub fn main(watcher_map: [[bool; 8]; 8], dagger: (u8, u8), path: [(u8, u8); 8]) {
+    let path = dungeon::Square::from_array(path);
+    dungeon::is_valid_path(path, dagger.into());
+    dungeon::is_safe_path(path, watcher_map);
+}