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(iter_cmp)]
  44
  45 use std::sync::Arc;
  46 use std::sync::mpsc::channel;
  47 use std::thread;
  48
  49 //
  50 // Utilities.
  51 //
  52
  53 // returns an infinite iterator of repeated applications of f to x,
  54 // i.e. [x, f(x), f(f(x)), ...], as haskell iterate function.
  55 fn iterate<T, F>(x: T, f: F) -> Iterate<T, F> where F: FnMut(&T) -> T {
  56     Iterate {f: f, next: x}
  57 }
  58 struct Iterate<T, F> where F: FnMut(&T) -> T {
  59     f: F,
  60     next: T
  61 }
  62 impl<T, F> Iterator for Iterate<T, F> where F: FnMut(&T) -> T {
  63     type Item = T;
  64
  65     fn next(&mut self) -> Option<T> {
  66         let mut res = (self.f)(&self.next);
  67         std::mem::swap(&mut res, &mut self.next);
  68         Some(res)
  69     }
  70 }
  71
  72 // a linked list using borrowed next.
  73 enum List<'a, T:'a> {
  74     Nil,
  75     Cons(T, &'a List<'a, T>)
  76 }
  77 struct ListIterator<'a, T:'a> {
  78     cur: &'a List<'a, T>
  79 }
  80 impl<'a, T> List<'a, T> {
  81     fn iter(&'a self) -> ListIterator<'a, T> {
  82         ListIterator{cur: self}
  83     }
  84 }
  85 impl<'a, T> Iterator for ListIterator<'a, T> {
  86     type Item = &'a T;
  87
  88     fn next(&mut self) -> Option<&'a T> {
  89         match *self.cur {
  90             List::Nil => None,
  91             List::Cons(ref elt, next) => {
  92                 self.cur = next;
  93                 Some(elt)
  94             }
  95         }
  96     }
  97 }
  98
  99 //
 100 // preprocess
 101 //
 102
 103 // Takes a pieces p on the form [(y1, x1), (y2, x2), ...] and returns
 104 // every possible transformations (the 6 rotations with their
 105 // corresponding mirrored piece), with, as minimum coordinates, (0,
 106 // 0).  If all is false, only generate half of the possibilities (used
 107 // to break the symmetry of the board).
 108 fn transform(piece: Vec<(i32, i32)> , all: bool) -> Vec<Vec<(i32, i32)>> {
 109     let mut res: Vec<Vec<(i32, i32)>> =
 110         // rotations
 111         iterate(piece, |rot| rot.iter().map(|&(y, x)| (x + y, -y)).collect())
 112         .take(if all {6} else {3})
 113         // mirror
 114         .flat_map(|cur_piece| {
 115             iterate(cur_piece, |mir| mir.iter().map(|&(y, x)| (x, y)).collect())
 116             .take(2)
 117         }).collect();
 118
 119     // translating to (0, 0) as minimum coordinates.
 120     for cur_piece in &mut res {
 121         let (dy, dx) = *cur_piece.iter().min_by(|e| *e).unwrap();
 122         for &mut (ref mut y, ref mut x) in cur_piece {
 123             *y -= dy; *x -= dx;
 124         }
 125     }
 126
 127     res
 128 }
 129
 130 // A mask is a piece somewhere on the board.  It is represented as a
 131 // u64: for i in the first 50 bits, m[i] = 1 if the cell at (i/5, i%5)
 132 // is occupied.  m[50 + id] = 1 if the identifier of the piece is id.
 133
 134 // Takes a piece with minimum coordinate (0, 0) (as generated by
 135 // transform).  Returns the corresponding mask if p translated by (dy,
 136 // dx) is on the board.
 137 fn mask(dy: i32, dx: i32, id: usize, p: &Vec<(i32, i32)>) -> Option<u64> {
 138     let mut m = 1 << (50 + id);
 139     for &(y, x) in p {
 140         let x = x + dx + (y + (dy % 2)) / 2;
 141         if x < 0 || x > 4 {return None;}
 142         let y = y + dy;
 143         if y < 0 || y > 9 {return None;}
 144         m |= 1 << (y * 5 + x) as usize;
 145     }
 146     Some(m)
 147 }
 148
 149 // Makes every possible masks.  masks[i][id] correspond to every
 150 // possible masks for piece with identifier id with minimum coordinate
 151 // (i/5, i%5).
 152 fn make_masks() -> Vec<Vec<Vec<u64> > > {
 153     let pieces = vec!(
 154         vec!((0,0),(0,1),(0,2),(0,3),(1,3)),
 155         vec!((0,0),(0,2),(0,3),(1,0),(1,1)),
 156         vec!((0,0),(0,1),(0,2),(1,2),(2,1)),
 157         vec!((0,0),(0,1),(0,2),(1,1),(2,1)),
 158         vec!((0,0),(0,2),(1,0),(1,1),(2,1)),
 159         vec!((0,0),(0,1),(0,2),(1,1),(1,2)),
 160         vec!((0,0),(0,1),(1,1),(1,2),(2,1)),
 161         vec!((0,0),(0,1),(0,2),(1,0),(1,2)),
 162         vec!((0,0),(0,1),(0,2),(1,2),(1,3)),
 163         vec!((0,0),(0,1),(0,2),(0,3),(1,2)));
 164
 165     // To break the central symmetry of the problem, every
 166     // transformation must be taken except for one piece (piece 3
 167     // here).
 168     let transforms: Vec<Vec<Vec<(i32, i32)>>> =
 169         pieces.into_iter().enumerate()
 170         .map(|(id, p)| transform(p, id != 3))
 171         .collect();
 172
 173     (0..50).map(|yx| {
 174         transforms.iter().enumerate().map(|(id, t)| {
 175             t.iter().filter_map(|p| mask(yx / 5, yx % 5, id, p)).collect()
 176         }).collect()
 177     }).collect()
 178 }
 179
 180 // Check if all coordinates can be covered by an unused piece and that
 181 // all unused piece can be placed on the board.
 182 fn is_board_unfeasible(board: u64, masks: &Vec<Vec<Vec<u64>>>) -> bool {
 183     let mut coverable = board;
 184     for (i, masks_at) in masks.iter().enumerate() {
 185         if board & 1 << i != 0 { continue; }
 186         for (cur_id, pos_masks) in masks_at.iter().enumerate() {
 187             if board & 1 << (50 + cur_id) != 0 { continue; }
 188             for &cur_m in pos_masks {
 189                 if cur_m & board != 0 { continue; }
 190                 coverable |= cur_m;
 191                 // if every coordinates can be covered and every
 192                 // piece can be used.
 193                 if coverable == (1 << 60) - 1 { return false; }
 194             }
 195         }
 196         if coverable & 1 << i == 0 { return true; }
 197     }
 198     true
 199 }
 200
 201 // Filter the masks that we can prove to result to unfeasible board.
 202 fn filter_masks(masks: &mut Vec<Vec<Vec<u64>>>) {
 203     for i in 0..masks.len() {
 204         for j in 0..(*masks)[i].len() {
 205             masks[i][j] =
 206                 (*masks)[i][j].iter().cloned()
 207                 .filter(|&m| !is_board_unfeasible(m, masks))
 208                 .collect();
 209         }
 210     }
 211 }
 212
 213 // Gets the identifier of a mask.
 214 fn get_id(m: u64) -> u8 {
 215     for id in 0..10 {
 216         if m & (1 << (id + 50) as usize) != 0 {return id;}
 217     }
 218     panic!("{:016x} does not have a valid identifier", m);
 219 }
 220
 221 // Converts a list of mask to a Vec<u8>.
 222 fn to_vec(raw_sol: &List<u64>) -> Vec<u8> {
 223     let mut sol = vec![b'.'; 50];
 224     for &m in raw_sol.iter() {
 225         let id = '0' as u8 + get_id(m);
 226         for i in 0..50 {
 227             if m & 1 << i != 0 {
 228                 sol[i] = id;
 229             }
 230         }
 231     }
 232     sol
 233 }
 234
 235 // Prints a solution in Vec<u8> form.
 236 fn print_sol(sol: &Vec<u8>) {
 237     for (i, c) in sol.iter().enumerate() {
 238         if (i) % 5 == 0 { println!(""); }
 239         if (i + 5) % 10 == 0 { print!(" "); }
 240         print!("{} ", *c as char);
 241     }
 242     println!("");
 243 }
 244
 245 // The data managed during the search
 246 struct Data {
 247     // Number of solution found.
 248     nb: isize,
 249     // Lexicographically minimal solution found.
 250     min: Vec<u8>,
 251     // Lexicographically maximal solution found.
 252     max: Vec<u8>
 253 }
 254 impl Data {
 255     fn new() -> Data {
 256         Data {nb: 0, min: vec!(), max: vec!()}
 257     }
 258     fn reduce_from(&mut self, other: Data) {
 259         self.nb += other.nb;
 260         let Data { min: min, max: max, ..} = other;
 261         if min < self.min { self.min = min; }
 262         if max > self.max { self.max = max; }
 263     }
 264 }
 265
 266 // Records a new found solution.  Returns false if the search must be
 267 // stopped.
 268 fn handle_sol(raw_sol: &List<u64>, data: &mut Data) {
 269     // because we break the symmetry, 2 solutions correspond to a call
 270     // to this method: the normal solution, and the same solution in
 271     // reverse order, i.e. the board rotated by half a turn.
 272     data.nb += 2;
 273     let sol1 = to_vec(raw_sol);
 274     let sol2: Vec<u8> = sol1.iter().rev().cloned().collect();
 275
 276     if data.nb == 2 {
 277         data.min = sol1.clone();
 278         data.max = sol1.clone();
 279     }
 280
 281     if sol1 < data.min {data.min = sol1;}
 282     else if sol1 > data.max {data.max = sol1;}
 283     if sol2 < data.min {data.min = sol2;}
 284     else if sol2 > data.max {data.max = sol2;}
 285 }
 286
 287 fn search(
 288     masks: &Vec<Vec<Vec<u64>>>,
 289     board: u64,
 290     mut i: usize,
 291     cur: List<u64>,
 292     data: &mut Data)
 293 {
 294     // Search for the lesser empty coordinate.
 295     while board & (1 << i)  != 0 && i < 50 {i += 1;}
 296     // the board is full: a solution is found.
 297     if i >= 50 {return handle_sol(&cur, data);}
 298     let masks_at = &masks[i];
 299
 300     // for every unused piece
 301     for id in (0..10).filter(|&id| board & (1 << (id + 50)) == 0) {
 302         // for each mask that fits on the board
 303         for m in masks_at[id].iter().filter(|&m| board & *m == 0) {
 304             // This check is too costly.
 305             //if is_board_unfeasible(board | m, masks) {continue;}
 306             search(masks, board | *m, i + 1, List::Cons(*m, &cur), data);
 307         }
 308     }
 309 }
 310
 311 fn par_search(masks: Vec<Vec<Vec<u64>>>) -> Data {
 312     let masks = Arc::new(masks);
 313     let (tx, rx) = channel();
 314
 315     // launching the search in parallel on every masks at minimum
 316     // coordinate (0,0)
 317     for m in (*masks)[0].iter().flat_map(|masks_pos| masks_pos) {
 318         let masks = masks.clone();
 319         let tx = tx.clone();
 320         let m = *m;
 321         thread::spawn(move|| {
 322             let mut data = Data::new();
 323             search(&*masks, m, 1, List::Cons(m, &List::Nil), &mut data);
 324             tx.send(data).unwrap();
 325         });
 326     }
 327
 328     // collecting the results
 329     drop(tx);
 330     let mut data = rx.recv().unwrap();
 331     for d in rx.iter() { data.reduce_from(d); }
 332     data
 333 }
 334
 335 fn main () {
 336     let mut masks = make_masks();
 337     filter_masks(&mut masks);
 338     let data = par_search(masks);
 339     println!("{} solutions found", data.nb);
 340     print_sol(&data.min);
 341     print_sol(&data.max);
 342     println!("");
 343 }