src/test/bench/shootout-meteor.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //
  12 // Utilities.
  13 //
  14
  15 // returns an infinite iterator of repeated applications of f to x,
  16 // i.e. [x, f(x), f(f(x)), ...], as haskell iterate function.
  17 fn iterate<'a, T>(x: T, f: 'a |&T| -> T) -> Iterate<'a, T> {
  18     Iterate {f: f, next: x}
  19 }
  20 struct Iterate<'a, T> {
  21     f: 'a |&T| -> T,
  22     next: T
  23 }
  24 impl<'a, T> Iterator<T> for Iterate<'a, T> {
  25     fn next(&mut self) -> Option<T> {
  26         let mut res = (self.f)(&self.next);
  27         std::mem::swap(&mut res, &mut self.next);
  28         Some(res)
  29     }
  30 }
  31
  32 // a linked list using borrowed next.
  33 enum List<'a, T> {
  34     Nil,
  35     Cons(T, &'a List<'a, T>)
  36 }
  37 struct ListIterator<'a, T> {
  38     cur: &'a List<'a, T>
  39 }
  40 impl<'a, T> List<'a, T> {
  41     fn iter(&'a self) -> ListIterator<'a, T> {
  42         ListIterator{cur: self}
  43     }
  44 }
  45 impl<'a, T> Iterator<&'a T> for ListIterator<'a, T> {
  46     fn next(&mut self) -> Option<&'a T> {
  47         match *self.cur {
  48             Nil => None,
  49             Cons(ref elt, next) => {
  50                 self.cur = next;
  51                 Some(elt)
  52             }
  53         }
  54     }
  55 }
  56
  57 //
  58 // preprocess
  59 //
  60
  61 // Takes a pieces p on the form [(y1, x1), (y2, x2), ...] and returns
  62 // every possible transformations (the 6 rotations with their
  63 // corresponding mirrored piece), with, as minimum coordinates, (0,
  64 // 0).  If all is false, only generate half of the possibilities (used
  65 // to break the symetry of the board).
  66 fn transform(piece: Vec<(int, int)> , all: bool) -> vec!(Vec<(int, int)> ) {
  67     let mut res =
  68         // rotations
  69         iterate(piece, |rot| rot.iter().map(|&(y, x)| (x + y, -y)).collect())
  70         .take(if all {6} else {3})
  71         // mirror
  72         .flat_map(|cur_piece| {
  73             iterate(cur_piece, |mir| mir.iter().map(|&(y, x)| (x, y)).collect())
  74             .take(2)
  75         }).to_owned_vec();
  76
  77     // translating to (0, 0) as minimum coordinates.
  78     for cur_piece in res.mut_iter() {
  79         let (dy, dx) = *cur_piece.iter().min_by(|e| *e).unwrap();
  80         for &(ref mut y, ref mut x) in cur_piece.mut_iter() {
  81             *y -= dy; *x -= dx;
  82         }
  83     }
  84
  85     res
  86 }
  87
  88 // A mask is a piece somewere on the board.  It is represented as a
  89 // u64: for i in the first 50 bits, m[i] = 1 if the cell at (i/5, i%5)
  90 // is occuped.  m[50 + id] = 1 if the identifier of the piece is id.
  91
  92 // Takes a piece with minimum coordinate (0, 0) (as generated by
  93 // transform).  Returns the corresponding mask if p translated by (dy,
  94 // dx) is on the board.
  95 fn mask(dy: int, dx: int, id: uint, p: &[(int, int)]) -> Option<u64> {
  96     let mut m = 1 << (50 + id);
  97     for &(y, x) in p.iter() {
  98         let x = x + dx + (y + (dy % 2)) / 2;
  99         if x < 0 || x > 4 {return None;}
 100         let y = y + dy;
 101         if y < 0 || y > 9 {return None;}
 102         m |= 1 << (y * 5 + x);
 103     }
 104     Some(m)
 105 }
 106
 107 // Makes every possible masks.  masks[id][i] correspond to every
 108 // possible masks for piece with identifier id with minimum coordinate
 109 // (i/5, i%5).
 110 fn make_masks() -> Vec<Vec<Vec<u64> > > {
 111     let pieces = vec!(
 112         vec!((0,0),(0,1),(0,2),(0,3),(1,3)),
 113         vec!((0,0),(0,2),(0,3),(1,0),(1,1)),
 114         vec!((0,0),(0,1),(0,2),(1,2),(2,1)),
 115         vec!((0,0),(0,1),(0,2),(1,1),(2,1)),
 116         vec!((0,0),(0,2),(1,0),(1,1),(2,1)),
 117         vec!((0,0),(0,1),(0,2),(1,1),(1,2)),
 118         vec!((0,0),(0,1),(1,1),(1,2),(2,1)),
 119         vec!((0,0),(0,1),(0,2),(1,0),(1,2)),
 120         vec!((0,0),(0,1),(0,2),(1,2),(1,3)),
 121         vec!((0,0),(0,1),(0,2),(0,3),(1,2)));
 122     let mut res = Vec::new();
 123     for (id, p) in pieces.move_iter().enumerate() {
 124         // To break the central symetry of the problem, every
 125         // transformation must be taken except for one piece (piece 3
 126         // here).
 127         let trans = transform(p, id != 3);
 128         let mut cur_piece = Vec::new();
 129         for dy in range(0, 10) {
 130             for dx in range(0, 5) {
 131                 let masks =
 132                     trans.iter()
 133                     .filter_map(|t| mask(dy, dx, id, *t))
 134                     .collect();
 135                 cur_piece.push(masks);
 136             }
 137         }
 138         res.push(cur_piece);
 139     }
 140     res
 141 }
 142
 143 // Check if all coordinates can be covered by an unused piece and that
 144 // all unused piece can be placed on the board.
 145 fn is_board_unfeasible(board: u64, masks: &[Vec<Vec<u64> > ]) -> bool {
 146     let mut coverable = board;
 147     for i in range(0, 50).filter(|&i| board & 1 << i == 0) {
 148         for (cur_id, pos_masks) in masks.iter().enumerate() {
 149             if board & 1 << (50 + cur_id) != 0 {continue;}
 150             for &cur_m in pos_masks[i].iter() {
 151                 if cur_m & board == 0 {coverable |= cur_m;}
 152             }
 153         }
 154         if coverable & (1 << i) == 0 {return true;}
 155     }
 156     // check if every coordinates can be covered and every piece can
 157     // be used.
 158     coverable != (1 << 60) - 1
 159 }
 160
 161 // Filter the masks that we can prove to result to unfeasible board.
 162 fn filter_masks(masks: &[Vec<Vec<u64> > ]) -> Vec<Vec<Vec<u64> > > {
 163     masks.iter().map(
 164         |p| p.iter().map(
 165             |p| p.iter()
 166                 .map(|&m| m)
 167                 .filter(|&m| !is_board_unfeasible(m, masks))
 168                 .collect())
 169             .collect())
 170         .collect()
 171 }
 172
 173 // Gets the identifier of a mask.
 174 fn get_id(m: u64) -> u8 {
 175     for id in range(0, 10) {
 176         if m & (1 << (id + 50)) != 0 {return id as u8;}
 177     }
 178     fail!("{:016x} does not have a valid identifier", m);
 179 }
 180
 181 // Converts a list of mask to a ~str.
 182 fn to_utf8(raw_sol: &List<u64>) -> ~str {
 183     let mut sol: Vec<u8> = Vec::from_elem(50, '.' as u8);
 184     for &m in raw_sol.iter() {
 185         let id = get_id(m);
 186         for i in range(0, 50) {
 187             if m & 1 << i != 0 {sol[i] = '0' as u8 + id;}
 188         }
 189     }
 190     std::str::from_utf8_owned(sol).unwrap()
 191 }
 192
 193 // Prints a solution in ~str form.
 194 fn print_sol(sol: &str) {
 195     for (i, c) in sol.chars().enumerate() {
 196         if (i) % 5 == 0 { println!(""); }
 197         if (i + 5) % 10 == 0 { print!(" "); }
 198         print!("{} ", c);
 199     }
 200     println!("");
 201 }
 202
 203 // The data managed during the search
 204 struct Data {
 205     // If more than stop_after is found, stop the search.
 206     stop_after: int,
 207     // Number of solution found.
 208     nb: int,
 209     // Lexicographically minimal solution found.
 210     min: ~str,
 211     // Lexicographically maximal solution found.
 212     max: ~str
 213 }
 214
 215 // Records a new found solution.  Returns false if the search must be
 216 // stopped.
 217 fn handle_sol(raw_sol: &List<u64>, data: &mut Data) -> bool {
 218     // because we break the symetry, 2 solutions correspond to a call
 219     // to this method: the normal solution, and the same solution in
 220     // reverse order, i.e. the board rotated by half a turn.
 221     data.nb += 2;
 222     let sol1 = to_utf8(raw_sol);
 223     let sol2: ~str = sol1.chars().rev().collect();
 224
 225     if data.nb == 2 {
 226         data.min = sol1.clone();
 227         data.max = sol1.clone();
 228     }
 229
 230     if sol1 < data.min {data.min = sol1.clone();}
 231     if sol2 < data.min {data.min = sol2.clone();}
 232     if sol1 > data.max {data.max = sol1;}
 233     if sol2 > data.max {data.max = sol2;}
 234     data.nb < data.stop_after
 235 }
 236
 237 // Search for every solutions.  Returns false if the search was
 238 // stopped before the end.
 239 fn search(
 240     masks: &[Vec<Vec<u64> > ],
 241     board: u64,
 242     mut i: int,
 243     cur: List<u64>,
 244     data: &mut Data)
 245     -> bool
 246 {
 247     // Search for the lesser empty coordinate.
 248     while board & (1 << i)  != 0 && i < 50 {i += 1;}
 249     // the board is full: a solution is found.
 250     if i >= 50 {return handle_sol(&cur, data);}
 251
 252     // for every unused piece
 253     for id in range(0, 10).filter(|id| board & (1 << (id + 50)) == 0) {
 254         // for each mask that fits on the board
 255         for &m in masks[id][i].iter().filter(|&m| board & *m == 0) {
 256             // This check is too costy.
 257             //if is_board_unfeasible(board | m, masks) {continue;}
 258             if !search(masks, board | m, i + 1, Cons(m, &cur), data) {
 259                 return false;
 260             }
 261         }
 262     }
 263     return true;
 264 }
 265
 266 fn main () {
 267     let args = std::os::args();
 268     let stop_after = if args.len() <= 1 {
 269         2098
 270     } else {
 271         from_str(args[1]).unwrap()
 272     };
 273     let masks = make_masks();
 274     let masks = filter_masks(masks);
 275     let mut data = Data {stop_after: stop_after, nb: 0, min: ~"", max: ~""};
 276     search(masks, 0, 0, Nil, &mut data);
 277     println!("{} solutions found", data.nb);
 278     print_sol(data.min);
 279     print_sol(data.max);
 280     println!("");
 281 }