src/test/bench/shootout-meteor.rs

   1 // The Computer Language Benchmarks Game
   2 // http://benchmarksgame.alioth.debian.org/
   3 //
   4 // contributed by the Rust Project Developers
   5
   6 // Copyright (c) 2013-2014 The Rust Project Developers
   7 //
   8 // All rights reserved.
   9 //
  10 // Redistribution and use in source and binary forms, with or without
  11 // modification, are permitted provided that the following conditions
  12 // are met:
  13 //
  14 // - Redistributions of source code must retain the above copyright
  15 //   notice, this list of conditions and the following disclaimer.
  16 //
  17 // - Redistributions in binary form must reproduce the above copyright
  18 //   notice, this list of conditions and the following disclaimer in
  19 //   the documentation and/or other materials provided with the
  20 //   distribution.
  21 //
  22 // - Neither the name of "The Computer Language Benchmarks Game" nor
  23 //   the name of "The Computer Language Shootout Benchmarks" nor the
  24 //   names of its contributors may be used to endorse or promote
  25 //   products derived from this software without specific prior
  26 //   written permission.
  27 //
  28 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  31 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  32 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  33 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  34 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  35 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  37 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  38 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  39 // OF THE POSSIBILITY OF SUCH DAMAGE.
  40
  41 // no-pretty-expanded FIXME #15189
  42
  43 #![feature(associated_types)]
  44
  45 use std::iter::repeat;
  46 use std::sync::Arc;
  47 use std::sync::mpsc::channel;
  48 use std::thread::Thread;
  49
  50 //
  51 // Utilities.
  52 //
  53
  54 // returns an infinite iterator of repeated applications of f to x,
  55 // i.e. [x, f(x), f(f(x)), ...], as haskell iterate function.
  56 fn iterate<'a, T>(x: T, f: |&T|: 'a -> T) -> Iterate<'a, T> {
  57     Iterate {f: f, next: x}
  58 }
  59 struct Iterate<'a, T> {
  60     f: |&T|: 'a -> T,
  61     next: T
  62 }
  63 impl<'a, T> Iterator for Iterate<'a, T> {
  64     type Item = T;
  65
  66     fn next(&mut self) -> Option<T> {
  67         let mut res = (self.f)(&self.next);
  68         std::mem::swap(&mut res, &mut self.next);
  69         Some(res)
  70     }
  71 }
  72
  73 // a linked list using borrowed next.
  74 enum List<'a, T:'a> {
  75     Nil,
  76     Cons(T, &'a List<'a, T>)
  77 }
  78 struct ListIterator<'a, T:'a> {
  79     cur: &'a List<'a, T>
  80 }
  81 impl<'a, T> List<'a, T> {
  82     fn iter(&'a self) -> ListIterator<'a, T> {
  83         ListIterator{cur: self}
  84     }
  85 }
  86 impl<'a, T> Iterator for ListIterator<'a, T> {
  87     type Item = &'a T;
  88
  89     fn next(&mut self) -> Option<&'a T> {
  90         match *self.cur {
  91             List::Nil => None,
  92             List::Cons(ref elt, next) => {
  93                 self.cur = next;
  94                 Some(elt)
  95             }
  96         }
  97     }
  98 }
  99
 100 //
 101 // preprocess
 102 //
 103
 104 // Takes a pieces p on the form [(y1, x1), (y2, x2), ...] and returns
 105 // every possible transformations (the 6 rotations with their
 106 // corresponding mirrored piece), with, as minimum coordinates, (0,
 107 // 0).  If all is false, only generate half of the possibilities (used
 108 // to break the symmetry of the board).
 109 fn transform(piece: Vec<(int, int)> , all: bool) -> Vec<Vec<(int, int)>> {
 110     let mut res: Vec<Vec<(int, int)>> =
 111         // rotations
 112         iterate(piece, |rot| rot.iter().map(|&(y, x)| (x + y, -y)).collect())
 113         .take(if all {6} else {3})
 114         // mirror
 115         .flat_map(|cur_piece| {
 116             iterate(cur_piece, |mir| mir.iter().map(|&(y, x)| (x, y)).collect())
 117             .take(2)
 118         }).collect();
 119
 120     // translating to (0, 0) as minimum coordinates.
 121     for cur_piece in res.iter_mut() {
 122         let (dy, dx) = *cur_piece.iter().min_by(|e| *e).unwrap();
 123         for &(ref mut y, ref mut x) in cur_piece.iter_mut() {
 124             *y -= dy; *x -= dx;
 125         }
 126     }
 127
 128     res
 129 }
 130
 131 // A mask is a piece somewhere on the board.  It is represented as a
 132 // u64: for i in the first 50 bits, m[i] = 1 if the cell at (i/5, i%5)
 133 // is occupied.  m[50 + id] = 1 if the identifier of the piece is id.
 134
 135 // Takes a piece with minimum coordinate (0, 0) (as generated by
 136 // transform).  Returns the corresponding mask if p translated by (dy,
 137 // dx) is on the board.
 138 fn mask(dy: int, dx: int, id: uint, p: &Vec<(int, int)>) -> Option<u64> {
 139     let mut m = 1 << (50 + id);
 140     for &(y, x) in p.iter() {
 141         let x = x + dx + (y + (dy % 2)) / 2;
 142         if x < 0 || x > 4 {return None;}
 143         let y = y + dy;
 144         if y < 0 || y > 9 {return None;}
 145         m |= 1 << (y * 5 + x) as uint;
 146     }
 147     Some(m)
 148 }
 149
 150 // Makes every possible masks.  masks[i][id] correspond to every
 151 // possible masks for piece with identifier id with minimum coordinate
 152 // (i/5, i%5).
 153 fn make_masks() -> Vec<Vec<Vec<u64> > > {
 154     let pieces = vec!(
 155         vec!((0i,0i),(0,1),(0,2),(0,3),(1,3)),
 156         vec!((0i,0i),(0,2),(0,3),(1,0),(1,1)),
 157         vec!((0i,0i),(0,1),(0,2),(1,2),(2,1)),
 158         vec!((0i,0i),(0,1),(0,2),(1,1),(2,1)),
 159         vec!((0i,0i),(0,2),(1,0),(1,1),(2,1)),
 160         vec!((0i,0i),(0,1),(0,2),(1,1),(1,2)),
 161         vec!((0i,0i),(0,1),(1,1),(1,2),(2,1)),
 162         vec!((0i,0i),(0,1),(0,2),(1,0),(1,2)),
 163         vec!((0i,0i),(0,1),(0,2),(1,2),(1,3)),
 164         vec!((0i,0i),(0,1),(0,2),(0,3),(1,2)));
 165
 166     // To break the central symmetry of the problem, every
 167     // transformation must be taken except for one piece (piece 3
 168     // here).
 169     let transforms: Vec<Vec<Vec<(int, int)>>> =
 170         pieces.into_iter().enumerate()
 171         .map(|(id, p)| transform(p, id != 3))
 172         .collect();
 173
 174     range(0i, 50).map(|yx| {
 175         transforms.iter().enumerate().map(|(id, t)| {
 176             t.iter().filter_map(|p| mask(yx / 5, yx % 5, id, p)).collect()
 177         }).collect()
 178     }).collect()
 179 }
 180
 181 // Check if all coordinates can be covered by an unused piece and that
 182 // all unused piece can be placed on the board.
 183 fn is_board_unfeasible(board: u64, masks: &Vec<Vec<Vec<u64>>>) -> bool {
 184     let mut coverable = board;
 185     for (i, masks_at) in masks.iter().enumerate() {
 186         if board & 1 << i != 0 { continue; }
 187         for (cur_id, pos_masks) in masks_at.iter().enumerate() {
 188             if board & 1 << (50 + cur_id) != 0 { continue; }
 189             for &cur_m in pos_masks.iter() {
 190                 if cur_m & board != 0 { continue; }
 191                 coverable |= cur_m;
 192                 // if every coordinates can be covered and every
 193                 // piece can be used.
 194                 if coverable == (1 << 60) - 1 { return false; }
 195             }
 196         }
 197         if coverable & 1 << i == 0 { return true; }
 198     }
 199     true
 200 }
 201
 202 // Filter the masks that we can prove to result to unfeasible board.
 203 fn filter_masks(masks: &mut Vec<Vec<Vec<u64>>>) {
 204     for i in range(0, masks.len()) {
 205         for j in range(0, (*masks)[i].len()) {
 206             masks[i][j] =
 207                 (*masks)[i][j].iter().map(|&m| m)
 208                 .filter(|&m| !is_board_unfeasible(m, masks))
 209                 .collect();
 210         }
 211     }
 212 }
 213
 214 // Gets the identifier of a mask.
 215 fn get_id(m: u64) -> u8 {
 216     for id in range(0u8, 10) {
 217         if m & (1 << (id + 50) as uint) != 0 {return id;}
 218     }
 219     panic!("{:016x} does not have a valid identifier", m);
 220 }
 221
 222 // Converts a list of mask to a Vec<u8>.
 223 fn to_vec(raw_sol: &List<u64>) -> Vec<u8> {
 224     let mut sol = repeat('.' as u8).take(50).collect::<Vec<_>>();
 225     for &m in raw_sol.iter() {
 226         let id = '0' as u8 + get_id(m);
 227         for i in range(0u, 50) {
 228             if m & 1 << i != 0 {
 229                 sol[i] = id;
 230             }
 231         }
 232     }
 233     sol
 234 }
 235
 236 // Prints a solution in Vec<u8> form.
 237 fn print_sol(sol: &Vec<u8>) {
 238     for (i, c) in sol.iter().enumerate() {
 239         if (i) % 5 == 0 { println!(""); }
 240         if (i + 5) % 10 == 0 { print!(" "); }
 241         print!("{} ", *c as char);
 242     }
 243     println!("");
 244 }
 245
 246 // The data managed during the search
 247 struct Data {
 248     // Number of solution found.
 249     nb: int,
 250     // Lexicographically minimal solution found.
 251     min: Vec<u8>,
 252     // Lexicographically maximal solution found.
 253     max: Vec<u8>
 254 }
 255 impl Data {
 256     fn new() -> Data {
 257         Data {nb: 0, min: vec!(), max: vec!()}
 258     }
 259     fn reduce_from(&mut self, other: Data) {
 260         self.nb += other.nb;
 261         let Data { min: min, max: max, ..} = other;
 262         if min < self.min { self.min = min; }
 263         if max > self.max { self.max = max; }
 264     }
 265 }
 266
 267 // Records a new found solution.  Returns false if the search must be
 268 // stopped.
 269 fn handle_sol(raw_sol: &List<u64>, data: &mut Data) {
 270     // because we break the symmetry, 2 solutions correspond to a call
 271     // to this method: the normal solution, and the same solution in
 272     // reverse order, i.e. the board rotated by half a turn.
 273     data.nb += 2;
 274     let sol1 = to_vec(raw_sol);
 275     let sol2: Vec<u8> = sol1.iter().rev().map(|x| *x).collect();
 276
 277     if data.nb == 2 {
 278         data.min = sol1.clone();
 279         data.max = sol1.clone();
 280     }
 281
 282     if sol1 < data.min {data.min = sol1;}
 283     else if sol1 > data.max {data.max = sol1;}
 284     if sol2 < data.min {data.min = sol2;}
 285     else if sol2 > data.max {data.max = sol2;}
 286 }
 287
 288 fn search(
 289     masks: &Vec<Vec<Vec<u64>>>,
 290     board: u64,
 291     mut i: uint,
 292     cur: List<u64>,
 293     data: &mut Data)
 294 {
 295     // Search for the lesser empty coordinate.
 296     while board & (1 << i)  != 0 && i < 50 {i += 1;}
 297     // the board is full: a solution is found.
 298     if i >= 50 {return handle_sol(&cur, data);}
 299     let masks_at = &masks[i];
 300
 301     // for every unused piece
 302     for id in range(0u, 10).filter(|&id| board & (1 << (id + 50)) == 0) {
 303         // for each mask that fits on the board
 304         for m in masks_at[id].iter().filter(|&m| board & *m == 0) {
 305             // This check is too costly.
 306             //if is_board_unfeasible(board | m, masks) {continue;}
 307             search(masks, board | *m, i + 1, List::Cons(*m, &cur), data);
 308         }
 309     }
 310 }
 311
 312 fn par_search(masks: Vec<Vec<Vec<u64>>>) -> Data {
 313     let masks = Arc::new(masks);
 314     let (tx, rx) = channel();
 315
 316     // launching the search in parallel on every masks at minimum
 317     // coordinate (0,0)
 318     for m in (*masks)[0].iter().flat_map(|masks_pos| masks_pos.iter()) {
 319         let masks = masks.clone();
 320         let tx = tx.clone();
 321         let m = *m;
 322         Thread::spawn(move|| {
 323             let mut data = Data::new();
 324             search(&*masks, m, 1, List::Cons(m, &List::Nil), &mut data);
 325             tx.send(data).unwrap();
 326         }).detach();
 327     }
 328
 329     // collecting the results
 330     drop(tx);
 331     let mut data = rx.recv().unwrap();
 332     for d in rx.iter() { data.reduce_from(d); }
 333     data
 334 }
 335
 336 fn main () {
 337     let mut masks = make_masks();
 338     filter_masks(&mut masks);
 339     let data = par_search(masks);
 340     println!("{} solutions found", data.nb);
 341     print_sol(&data.min);
 342     print_sol(&data.max);
 343     println!("");
 344 }