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