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
 207 fn main() {
 208     let default_max_id = std::usize::MAX;
 209     let default_max_depth = std::usize::MAX;
 210
 211     let args: Vec<String> = env::args().collect();
 212
 213     let max_id = if args.len() >= 2 {
 214         match args[1].parse() {
 215             Ok(v) => v,
 216             Err(_) => default_max_id,
 217         }
 218     } else {
 219         default_max_id
 220     };
 221
 222     let max_depth = if args.len() == 3 {
 223         match args[2].parse() {
 224             Ok(v) => v,
 225             Err(_) => default_max_depth,
 226         }
 227     } else {
 228         default_max_depth
 229     };
 230
 231     if args.len() > 3 {
 232         println!("{}: error: too many arguments", args[0]);
 233     } else {
 234         println!("digraph G {{");
 235         println!("    graph[fontname=\"Courier New\"];");
 236         println!("    node[fontname=\"Courier New\"];");
 237         println!("    edge[fontname=\"Courier New\"];");
 238         print!("{}", Tree::new(Game::new(), &mut 0, max_id, 0, max_depth));
 239         println!("}}");
 240     }
 241 }