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