First draft of win checking

1 files changed, 198 insertions, 7 deletions

diff --git a/src/game.rs b/src/game.rs
index 99704b1..04bd76a 100644
--- a/src/game.rs
+++ b/src/game.rs
@@ -1,10 +1,12 @@
+use std::collections::HashSet;
 use std::fmt;
 
-#[derive(Clone, Copy)]
+#[derive(Clone, Copy, PartialEq, Eq, Hash)]
 pub struct Position {
     pub x: u8,
     pub y: u8,
 }
+
 impl fmt::Display for Position {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "{:x}{}", 10 + self.x, self.y + 1)
@@ -100,6 +102,29 @@ pub struct Piece {
     pub player: Player,
     pub stone: Stone,
 }
+
+pub enum WinType {
+    RoadWin(Player),
+    FlatWin(Player),
+    Draw,
+}
+
+impl fmt::Display for WinType {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(
+            f,
+            "{}",
+            match self {
+                WinType::RoadWin(Player::Black) => "0-R",
+                WinType::RoadWin(Player::White) => "R-0",
+                WinType::FlatWin(Player::Black) => "0-F",
+                WinType::FlatWin(Player::White) => "F-0",
+                WinType::Draw => "1/2-1/2",
+            }
+        )
+    }
+}
+
 pub type Stack = Vec<Piece>;
 
 struct GameState {
@@ -465,6 +490,173 @@ impl GameState {
         }
         Ok((pos_vec, copy))
     }
+
+    // Either up or right
+    fn dfs(&self, player: Player, up: bool, mut todo: Vec<Position>) -> bool {
+        let mut seen: HashSet<Position> = HashSet::new();
+        for i in 0..todo.len() {
+            seen.insert(todo[i].clone());
+        }
+        loop {
+            let more = todo.pop();
+            if let Some(p) = more {
+                if p.y + 1 < self.size {
+                    let p_up = Position { x: p.x, y: p.y + 1 };
+                    let i_up = self.pos_to_idx(&p_up);
+                    if !seen.contains(&p_up) && self.within_bounds(&p_up) {
+                        let l = self.board[i_up].len();
+                        if l > 0 {
+                            let piece = self.board[i_up][l - 1];
+                            if (piece.player == player) && (piece.stone != Stone::Standing) {
+                                if up && (p_up.y + 1 == self.size) {
+                                    return true;
+                                } else {
+                                    seen.insert(p_up);
+                                    todo.push(p_up);
+                                }
+                            }
+                        }
+                    }
+                }
+
+                if p.x + 1 < self.size {
+                    let p_right = Position { x: p.x + 1, y: p.y };
+                    let i_right = self.pos_to_idx(&p_right);
+                    if !seen.contains(&p_right) && self.within_bounds(&p_right) {
+                        let l = self.board[i_right].len();
+                        if l > 0 {
+                            let piece = self.board[i_right][l - 1];
+                            if (piece.player == player) && (piece.stone != Stone::Standing) {
+                                if !up && (p_right.x + 1 == self.size) {
+                                    return true;
+                                } else {
+                                    seen.insert(p_right);
+                                    todo.push(p_right);
+                                }
+                            }
+                        }
+                    }
+                }
+
+                if p.y > 0 {
+                    let p_down = Position { x: p.x, y: p.y - 1 };
+                    let i_down = self.pos_to_idx(&p_down);
+                    if !seen.contains(&p_down) && self.within_bounds(&p_down) {
+                        let l = self.board[i_down].len();
+                        if l > 0 {
+                            let piece = self.board[i_down][l - 1];
+                            if (piece.player == player) && (piece.stone != Stone::Standing) {
+                                seen.insert(p_down);
+                                todo.push(p_down);
+                            }
+                        }
+                    }
+                }
+
+                if p.x > 0 {
+                    let p_left = Position { x: p.x - 1, y: p.y };
+                    let i_left = self.pos_to_idx(&p_left);
+                    if !seen.contains(&p_left) && self.within_bounds(&p_left) {
+                        let l = self.board[i_left].len();
+                        if l > 0 {
+                            let piece = self.board[i_left][l - 1];
+                            if (piece.player == player) && (piece.stone != Stone::Standing) {
+                                seen.insert(p_left);
+                                todo.push(p_left);
+                            }
+                        }
+                    }
+                }
+
+                seen.insert(p);
+            } else {
+                break;
+            }
+        }
+        return false;
+    }
+
+    fn check_road_win(&self) -> Option<WinType> {
+        // Depth first search from bottom edge and left edge
+
+        let mut todo_black_up: Vec<Position> = Vec::new();
+        let mut todo_white_up: Vec<Position> = Vec::new();
+        let mut todo_black_right: Vec<Position> = Vec::new();
+        let mut todo_white_right: Vec<Position> = Vec::new();
+
+        for i in 0..self.size {
+            let pos_up = Position { x: i, y: 0 };
+            let pos_right = Position { x: 0, y: i };
+            let stack_up = &self.board[self.pos_to_idx(&pos_up)];
+            let stack_right = &self.board[self.pos_to_idx(&pos_right)];
+
+            if !stack_up.is_empty() {
+                match stack_up[stack_up.len() - 1].player {
+                    Player::Black => todo_black_up.push(pos_up),
+                    Player::White => todo_white_up.push(pos_up),
+                }
+            }
+
+            if !stack_right.is_empty() {
+                match stack_right[stack_right.len() - 1].player {
+                    Player::Black => todo_black_right.push(pos_right),
+                    Player::White => todo_white_right.push(pos_right),
+                }
+            }
+        }
+
+        if self.dfs(Player::Black, true, todo_black_up)
+            || self.dfs(Player::Black, false, todo_black_right)
+        {
+            return Some(WinType::RoadWin(Player::Black));
+        }
+
+        if self.dfs(Player::White, true, todo_white_up)
+            || self.dfs(Player::White, false, todo_white_right)
+        {
+            return Some(WinType::RoadWin(Player::White));
+        }
+
+        return None;
+    }
+
+    fn check_flat_win(&self) -> Option<WinType> {
+        let full_board = self.board.iter().all(|s| s.len() > 0);
+        let finished_flats = (self.black_flats == 0) || (self.white_flats == 0);
+
+        if full_board || finished_flats {
+            let count = self.board.iter().fold(0, |c, s| match s.last() {
+                None => c,
+                Some(piece) => {
+                    if piece.stone == Stone::Flat {
+                        match piece.player {
+                            Player::Black => c + 1,
+                            Player::White => c - 1,
+                        }
+                    } else {
+                        c
+                    }
+                }
+            });
+            // Trichotomy of reals ...
+            if count > 0 {
+                return Some(WinType::FlatWin(Player::Black));
+            } else if count == 0 {
+                return Some(WinType::Draw);
+            } else {
+                return Some(WinType::FlatWin(Player::White));
+            }
+        }
+        return None;
+    }
+
+    fn check_win(&self) -> Option<WinType> {
+        if let Some(w) = self.check_road_win() {
+            return Some(w);
+        } else {
+            return self.check_flat_win();
+        }
+    }
 }
 
 enum TurnOrder {
@@ -532,10 +724,6 @@ impl Game {
         }
     }
 
-    // pub fn query_action(&self, turn: u16) -> Option<&Action> {
-    //     self.actions.get(turn as usize)
-    // }
-
     pub fn get_size(&self) -> u8 {
         self.size
     }
@@ -558,7 +746,10 @@ impl Game {
         result
     }
 
-    pub fn perform_action(&mut self, act: Action) -> Result<Vec<Position>, String> {
+    pub fn perform_action(
+        &mut self,
+        act: Action,
+    ) -> Result<(Vec<Position>, Option<WinType>), String> {
         let maybe_state = self.states.last();
         if maybe_state.is_none() {
             return Err(String::from("Internal error: cannot find last game state"));
@@ -628,7 +819,7 @@ impl Game {
                     TurnOrder::WhitePlacesBlack => TurnOrder::Normal,
                     TurnOrder::Normal => TurnOrder::Normal,
                 };
-                return Ok(pos_vec);
+                return Ok((pos_vec, self.last_state().check_win()));
             }
         }
     }