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