src/main.rs

   1 use std::fmt;
   2 use std::env;
   3
   4 #[derive(Copy, Clone, PartialEq)]
   5 enum Sign {
   6     None,
   7     Cross,
   8     Circle,
   9 }
  10
  11 #[derive(Copy, Clone)]
  12 struct Game {
  13     grid: [[Sign; 3]; 3],
  14     next: Sign,
  15 }
  16
  17 struct Tree {
  18     id: usize,
  19     content: Content,
  20 }
  21
  22 struct Node {
  23     game: Game,
  24     rest: Vec<Tree>,
  25 }
  26
  27 enum Content {
  28     Node(Node),
  29     Leaf(Sign),
  30 }
  31
  32 impl fmt::Display for Sign {
  33     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  34         write!(f, "{}", match *self {
  35             Sign::None => '_',
  36             Sign::Cross => 'X',
  37             Sign::Circle => 'O',
  38         })
  39     }
  40 }
  41
  42 impl fmt::Display for Game {
  43     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  44         for i in 0..self.grid.len() {
  45             for j in 0..self.grid[i].len() {
  46                 if let Err(e) = write!(f, "{}", self.grid[i][j]) {
  47                     return Err(e);
  48                 }
  49             }
  50             if i < (self.grid.len() - 1) {
  51                 if let Err(e) = write!(f, "\\n") {
  52                     return Err(e);
  53                 }
  54             }
  55         }
  56         Ok(())
  57     }
  58 }
  59
  60 impl fmt::Display for Content {
  61     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  62         match self {
  63             &Content::Node(ref n) => write!(f, "[label=\"{}\"]", n.game),
  64             &Content::Leaf(s) => write!(f, "[label=\"{}\"]", s),
  65         }
  66     }
  67 }
  68
  69 impl fmt::Display for Tree {
  70     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  71         if let Err(e) = write!(f, "    {}{};\n",
  72                                self.id, self.content) {
  73             return Err(e);
  74         }
  75         match self.content {
  76             Content::Node(ref n) => {
  77                 for t in &n.rest {
  78                     if let Err(e) = write!(f, "{}    {} -> {};\n", t, self.id, t.id) {
  79                         return Err(e);
  80                     }
  81                 }
  82             },
  83             Content::Leaf(_) => {},
  84         }
  85         Ok(())
  86     }
  87 }
  88
  89 impl Game {
  90     fn new() -> Game {
  91         Game{
  92             grid: [[Sign::None; 3]; 3],
  93             next: Sign::Cross,
  94         }
  95     }
  96
  97     fn get_free_compartments(&self) -> Vec<(usize, usize)> {
  98         (0..self.grid.len()).flat_map(|x|
  99             (0..self.grid[0].len()).filter_map(|y|
 100                 if self.grid[x][y] == Sign::None {
 101                     Some((x, y))
 102                 } else {
 103                     None
 104                 }
 105             ).collect::<Vec<_>>()
 106         ).collect()
 107     }
 108
 109     #[inline]
 110     fn is_full(&self) -> bool {
 111         self.get_free_compartments().len() == 0
 112     }
 113
 114     fn play(&self, (x, y): (usize, usize)) -> Game {
 115         Game {
 116             grid: {
 117                 let mut grid = self.grid.clone();
 118                 grid[x][y] = self.next;
 119                 grid
 120             },
 121             next: match self.next {
 122                 Sign::None => Sign::None,
 123                 Sign::Cross => Sign::Circle,
 124                 Sign::Circle => Sign::Cross,
 125             },
 126         }
 127     }
 128
 129     fn is_over(&self) -> Option<Sign> {
 130         for &s in &[Sign::Cross, Sign::Circle] {
 131             for i in 0..self.grid.len() {
 132                 let mut row = true;
 133                 for j in 0..self.grid[i].len() {
 134                     if self.grid[i][j] != s {
 135                         row = false;
 136                         break;
 137                     }
 138                 }
 139                 if row {
 140                     return Some(s);
 141                 }
 142             }
 143             for i in 0..self.grid[0].len() {
 144                 let mut col = true;
 145                 for j in 0..self.grid.len() {
 146                     if self.grid[j][i] != s {
 147                         col = false;
 148                         break;
 149                     }
 150                 }
 151                 if col {
 152                     return Some(s);
 153                 }
 154             }
 155             {
 156                 let mut diag0 = true;
 157                 let mut diag1 = true;
 158                 for i in 0..self.grid.len() {
 159                     if self.grid[i][i] != s {
 160                         diag0 = false;
 161                     }
 162                     if self.grid[(self.grid.len() - 1) - i][i] != s {
 163                         diag1 = false;
 164                     }
 165                 }
 166                 if diag0 || diag1 {
 167                     return Some(s);
 168                 }
 169             }
 170         }
 171         if self.is_full() {
 172             return Some(Sign::None);
 173         }
 174         None
 175     }
 176 }
 177
 178 impl Tree {
 179     fn new(g: Game, id: &mut usize, max_id: usize, depth: usize, max_depth: usize) -> Tree {
 180         Tree {
 181             id: *id,
 182             content: Content::Node(Node {
 183                 game: g,
 184                 rest: if let Some(s) = g.is_over() {
 185                     *id += 1;
 186                     vec![Tree {
 187                         id: *id,
 188                         content: Content::Leaf(s),
 189                     }]
 190                 } else if depth < max_depth {
 191                     g.get_free_compartments().iter().filter_map(|&c| {
 192                         *id += 1;
 193                         if *id < max_id {
 194                             Some(Tree::new(g.play(c), id, max_id, depth + 1, max_depth))
 195                         } else {
 196                             None
 197                         }
 198                     }).collect()
 199                 } else {
 200                     Vec::new()
 201                 }
 202             }),
 203         }
 204     }
 205
 206     fn only_winning(self, sign: Sign) -> Option<Tree> {
 207         match self.content {
 208             Content::Node(Node { game: g, rest: r }) => {
 209                 let mut rest = Vec::new();/*r.iter().filter_map(|t|
 210                     t.only_winning(sign)
 211                 ).collect::<Vec<Tree>>();*/
 212                 for t in r {
 213                     if let Some(wt) = t.only_winning(sign) {
 214                         rest.push(wt);
 215                     }
 216                 }
 217                 if rest.len() > 0 {
 218                     Some(Tree {
 219                         id: self.id,
 220                         content: Content::Node(Node {
 221                             game: g,
 222                             rest: rest,
 223                         }),
 224                     })
 225                 } else {
 226                     None
 227                 }
 228             },
 229             Content::Leaf(s) => if s == sign {
 230                 Some(self)
 231             } else {
 232                 None
 233             },
 234         }
 235     }
 236 }
 237
 238 fn main() {
 239     let default_max_id = std::usize::MAX;
 240     let default_max_depth = std::usize::MAX;
 241
 242     let args: Vec<String> = env::args().collect();
 243
 244     let max_id = if args.len() >= 2 {
 245         match args[1].parse() {
 246             Ok(v) => v,
 247             Err(_) => default_max_id,
 248         }
 249     } else {
 250         default_max_id
 251     };
 252
 253     let max_depth = if args.len() >= 3 {
 254         match args[2].parse() {
 255             Ok(v) => v,
 256             Err(_) => default_max_depth,
 257         }
 258     } else {
 259         default_max_depth
 260     };
 261
 262     let ws = if args.len() == 4 {
 263         match args[3].as_ref() {
 264             "X" => Some(Sign::Cross),
 265             "x" => Some(Sign::Cross),
 266             "O" => Some(Sign::Circle),
 267             "o" => Some(Sign::Circle),
 268             "_" => Some(Sign::None),
 269             _ => None,
 270         }
 271     } else {
 272         None
 273     };
 274
 275     if args.len() > 4 {
 276         println!("{}: error: too many arguments", args[0]);
 277     } else {
 278         let t = Tree::new(Game::new(), &mut 0, max_id, 0, max_depth);
 279         let wt = match ws {
 280             Some(s) => t.only_winning(s),
 281             None => Some(t),
 282         };
 283         match wt {
 284             Some(tree) => {
 285                 println!("digraph G {{");
 286                 println!("    graph[fontname=\"Courier New\"];");
 287                 println!("    node[fontname=\"Courier New\"];");
 288                 println!("    edge[fontname=\"Courier New\"];");
 289                 print!("{}", tree);
 290                 println!("}}");
 291             },
 292             None => println!("no result"),
 293         }
 294     }
 295 }