performance measurements

Each table row shows performance measurements for this Rust program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
2,0980.090.10?3837  10% 0% 0% 100%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read meteor-contest benchmark to see what this program should do.

 notes

rustc 1.1.0 (35ceea399 2015-06-19)

 meteor-contest Rust #2 program source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/
   contributed by Olof Kraigher

   Tested with rust 1.0.0-beta
   Compile with: rustc -C opt-level=3 meteor.rs -o meteor
*/

use std::sync::Arc;
use std::sync::mpsc::{Sender, Receiver, channel};
use std::thread::spawn;
use std::cmp::Ordering;


fn main () {
    match read_args() {
        Ok(num_solutions) => {
            solve(num_solutions);
        }
        Err(message) => {
            println!("{}", message);
            std::process::exit(1);
        }
    }
}

fn solve(num_solutions : usize) {
    let (min, max, num_found) = read_solutions(spawn_solvers(), num_solutions);
    println!("{} solutions found\n", num_found);
    min.pretty_print();
    max.pretty_print();
}

fn read_args() -> Result<usize, String> {
    let args : Vec<String> = std::env::args().collect();
    if args.len() != 2 {
        return Err(format!(
            "Usage: {} num_solutions",
            args[0]));
    }

    let maybe_int : Result<usize, _> = args[1].parse();
    if !maybe_int.is_ok() {
        return Err(format!(
            "Invalid argument '{}' cannot parse as unsigned integer",
            args[1]));
    }

    let num_solutions = maybe_int.unwrap();
    if num_solutions == 0 {
        return Err(format!(
            "Invalid argument '{}' must be greather than 0",
            args[1]));
    }

    return Ok(num_solutions);
}

fn read_solutions(solution_receiver : Receiver<Solution>,
                  num_solutions : usize)  -> (Solution, Solution, usize) {
    let first = solution_receiver.recv().unwrap();
    let mut num_found = 1;
    let mut min = first.clone();
    let mut max = first;
    for solution in solution_receiver.iter() {
        if num_found == num_solutions {
            break;
        }
        if solution < min {
            min = solution;
        } else if solution > max {
            max = solution;
        }
        num_found += 1;
    }

    (min, max, num_found)
}

fn spawn_solvers() -> Receiver<Solution> {
    let mask_lookup = Arc::new(MaskLookup::new());

    let (solution_sender, solution_receiver) = channel();

    for first_piece in (0..NUM_PIECES) {
        let num_masks = mask_lookup.get(first_piece, LAST_POSITION).len();

        for mask_idx in (0..num_masks) {
            let my_solution_sender = solution_sender.clone();
            let my_mask_lookup = mask_lookup.clone();

            spawn(move || {
                let mut solver = Solver::new(
                    &*my_mask_lookup,
                    &my_solution_sender);
                solver.place_piece(first_piece,
                                   LAST_POSITION,
                                   mask_idx,
                                   num_masks);
            });
        }
    }
    solution_receiver
}

struct Solver<'a> {
    mask_lookup: &'a MaskLookup,
    masks: [u64; NUM_PIECES],
    mask : u64,
    used_pieces: usize,
    solution_sender : &'a Sender<Solution>,
    solution: Solution,
    reversed_solution: Solution
}

impl<'a> Solver<'a> {
    fn new(mask_lookup : &'a MaskLookup,
           solution_sender : &'a Sender<Solution>) -> Solver<'a> {
        Solver {
            mask_lookup: mask_lookup,
            masks: [0; NUM_PIECES],
            mask: 0,
            used_pieces: 0,
            solution_sender: solution_sender,
            solution: Solution::default(),
            reversed_solution: Solution::default()
        }
    }

    fn place_piece(&mut self,
                   piece : usize,
                   position : usize,
                   start : usize,
                   step : usize) {
        self.toggle_piece(piece);
        let masks = self.mask_lookup.get(piece, position);
        let mut idx = start;
        while idx < masks.len() {
            self.evaluate(piece, masks[idx]);
            idx += step;
        }
        self.toggle_piece(piece);
    }

    fn evaluate(&mut self, piece : usize, mask : u64) {
        if self.fits(mask) {
            self.place_mask(piece, mask);
            if self.done() {
                self.send_solution();
            } else if self.still_possible() {
                self.choose_piece();
            }
            self.unplace_mask(mask);
        }
    }

    fn choose_piece(&mut self) {
        let position = self.first_free_position();
        let mut piece = 0;
        while piece < NUM_PIECES {
            if self.is_not_placed(piece) {
                self.place_piece(piece, position, 0, 1);
            }
            piece += 1;
        }
    }

    fn toggle_piece(&mut self, piece : usize) {
        self.used_pieces ^= 1 << piece;
    }

    fn place_mask(&mut self, piece: usize, mask : u64) {
        self.mask ^= mask;
        self.masks[piece] = mask;
    }

    fn unplace_mask(&mut self, mask : u64) {
        self.mask ^= mask;
    }

    fn done(&self) -> bool {
        self.used_pieces == (1 << NUM_PIECES) - 1
    }

    fn still_possible(&self) -> bool {
        no_islands(self.mask)
    }

    fn first_free_position(&self) -> usize {
        find_first_one(!self.mask & FULL_MASK)
    }

    fn is_not_placed(&self, piece : usize) -> bool {
        self.used_pieces & (1 << piece) == 0
    }

    fn fits(&self, mask : u64) -> bool {
        self.mask & mask == 0
    }

    fn send_solution(&mut self) {
        self.fill_solutions();
        let _ = self.solution_sender.send(self.solution.clone());
        let _ = self.solution_sender.send(self.reversed_solution.clone());
    }

    fn fill_solutions(&mut self) {
        for position in (0..NUM_POSITIONS) {
            let piece = self.piece_at_position(position);
            self.solution.pieces[position] = piece;
            let reversed_position = LAST_POSITION - position;
            self.reversed_solution.pieces[reversed_position] = piece;
        }
    }

    fn piece_at_position(&self, position : usize) -> u8 {
        let position_mask = 1 << position;
        for piece in (0..NUM_PIECES) {
            let mask = self.masks[piece];
            let uses_piece = (self.used_pieces >> piece) & 1 == 1;
            let occupies_position = overlaps(mask, position_mask);
            if uses_piece && occupies_position {
                return piece as u8;
            }
        }
        return 0;
    }
}


struct Solution {
    pieces: [u8; NUM_POSITIONS]
}

impl Solution {
    fn default() -> Solution {
        Solution {
            pieces: [0; NUM_POSITIONS]
        }
    }
}

impl Clone for Solution {
    fn clone(&self) -> Solution {
        Solution {
            pieces: self.pieces
        }
    }
}

impl PartialOrd for Solution {
    fn partial_cmp(&self, other : &Solution) -> Option<Ordering> {
        for i in (0..NUM_POSITIONS) {
            if self.pieces[i] < other.pieces[i] {
                return Some(Ordering::Less)
            } else if self.pieces[i] > other.pieces[i] {
                return Some(Ordering::Greater)
            }
        }
        Some(Ordering::Equal)
    }
}

impl PartialEq for Solution {
    fn eq(&self, other : &Solution) -> bool {
        self.pieces.partial_cmp(other.pieces.as_ref()) == Some(Ordering::Equal)
    }
}

impl Solution {
    fn pretty_print(&self) {
        for (idx, &piece) in self.pieces.iter().enumerate() {
            let glyph = (('0' as u8) + piece) as char;
            print!("{}", glyph);
            print!(" ");

            let x = idx % WIDTH;
            let y = idx / WIDTH;

            if x == WIDTH-1 {
                if y%2 == 0 {
                    print!("\n ");
                } else {
                    print!("\n");
                }
            }
        }
        print!("\n");
    }
}

struct MaskLookup {
    masks_by_piece_and_position: Vec<Vec<u64>>
}

impl MaskLookup {
    fn new() -> MaskLookup {
        let mut ml = MaskLookup::default();
        ml.add_piece(false, 0, &[E, E, E, SE]);
        ml.add_piece(false, 1, &[SE, SW, W, SW]);
        ml.add_piece(false, 2, &[W, W, SW, SE]);
        ml.add_piece(true,  3, &[E, E, SW, SE]);
        ml.add_piece(false, 4, &[NW, W, NW, SE, SW]);
        ml.add_piece(false, 5, &[E, E,  NE, W]);
        ml.add_piece(false, 6, &[NW, NE, NE, W]);
        ml.add_piece(false, 7, &[NE, SE, E, NE]);
        ml.add_piece(false, 8, &[SE, SE, E, SE]);
        ml.add_piece(false, 9, &[E, NW, NW, NW]);
        ml
    }

    fn default() -> MaskLookup {
        MaskLookup {
            masks_by_piece_and_position:
            (0..NUM_PIECES * NUM_POSITIONS).map(|_| Vec::with_capacity(2*6)).collect()
        }
    }

    fn add_piece(&mut self,
                 fully_rotated : bool,
                 index : usize,
                 directions : &[Direction]) {
        let mut piece : Piece = Piece::new(directions);
        let num_orientations : usize = 2;
        let num_rotations : usize = if fully_rotated {3} else {6};

        for _ in (0..num_orientations) {
            for _ in (0..num_rotations) {
                for x in (0..WIDTH as isize) {
                    for y in (0..HEIGHT as isize) {
                        let position = Position::new(x,y);
                        self.add_piece_at_position(index,
                                                   &piece,
                                                   position);
                    }
                }
                piece = piece.rotate();
            }
            piece = piece.flip();
        }
    }

    fn add_piece_at_position(&mut self,
                             index : usize,
                             piece : &Piece,
                             position : Position) {

        match piece.to_mask(position) {
            Some(mask) => {
                let last = find_first_one(mask);
                let idx = index*NUM_POSITIONS + last;
                self.masks_by_piece_and_position.get_mut(idx).unwrap().push(mask);
            }
            None => ()
        }
    }

    fn get<'a>(&'a self, index : usize, position : usize) -> &'a [u64] {
        let idx = index*NUM_POSITIONS + position;
        self.masks_by_piece_and_position[idx].as_ref()
    }
}

#[derive(Clone)]
struct Piece {
    directions: Vec<Direction>
}

impl Piece {
    fn new(directions : &[Direction]) -> Piece {
        Piece {
            directions: (0..directions.len()).map(|i| directions[i].clone()).collect()
        }
    }

    fn to_mask(&self, position : Position) -> Option<u64> {
        let mut mask = position.to_mask();
        let mut current_position = position;

        for direction in self.directions.iter() {
            match current_position.in_direction(direction) {
                Some(position) => {
                    current_position = position;
                    mask |= current_position.to_mask();
                },
                None => return None
            }
        }
        return Piece::prune(mask);
    }

    fn prune(mask : u64) -> Option<u64> {
        let border = 0b11111_10001_10001_10001_10001_10001_10001_10001_10001_11111;
        if mask & border == 0 || no_islands(mask) {
            Some(mask)
        } else {
            None
        }
    }

    fn flip(&self) -> Piece {
        self.as_modified(|x| x.flip())
    }

    fn rotate(&self) -> Piece {
        self.as_modified(|x| x.rotate())
    }

    fn as_modified<F : Fn(&Direction) -> Direction>(&self, fun : F) -> Piece {
        Piece {
            directions: self.directions.iter().map(fun).collect()
        }
    }
}

#[derive(Clone)]
struct Position {
    x: isize,
    y: isize
}

impl Position {
    fn new(x : isize, y : isize) -> Position {
        Position {x:x, y:y}
    }

    fn in_direction(&self, direction : &Direction) -> Option<Position> {

        let (dx, dy) =
            match direction {
                &E => (-1, 0),
                &W => ( 1, 0),
                &NE => (self.y%2 - 1,  1),
                &NW => (self.y%2    ,  1),
                &SE => (self.y%2 - 1, -1),
                &SW => (self.y%2    , -1)
            };

        let new_position = self.in_2d_direction(dx, dy);

        if Position::is_valid(&new_position) {
            Some(new_position.clone())
        } else {
            None
        }
    }

    fn in_2d_direction(&self, dx : isize, dy : isize) -> Position {
        Position {
            x: self.x + dx,
            y: self.y + dy
        }
    }

    fn is_valid(&Position{x,y} : &Position) -> bool {
        0 <= x && x < WIDTH as isize && 0 <= y && y < HEIGHT as isize
    }

    fn to_mask(&self) -> u64 {
        1u64 << (self.y * WIDTH as isize + self.x) as usize
    }
}

use Direction::*;

#[derive(Clone)]
enum Direction {
    E=0, SE=1, SW=2, W=3, NW=4, NE=5
}

impl Direction {
    fn rotate(&self) -> Direction {
        self.as_modified(|x| (x + 1)%6)
    }

    fn flip(&self) -> Direction {
        self.as_modified(|x| (9 - x)%6)
    }

    fn from_int(value : isize) -> Option<Direction> {
        match value {
            0 => Some(E),
            1 => Some(SE),
            2 => Some(SW),
            3 => Some(W),
            4 => Some(NW),
            5 => Some(NE),
            _ => None,
        }
    }

    fn as_modified<F : Fn(isize) -> isize>(&self, modifier : F) -> Direction {
        Direction::from_int(modifier(self.clone() as isize)).unwrap()
    }
}

fn no_islands(mask : u64) -> bool {
    let allowed = !mask & FULL_MASK;
    let seed = (1 << mask.trailing_zeros() as usize) - 1;
    let filled = flood_fill(seed, allowed);
    filled.count_ones() % 5 == 0
}

fn flood_fill(seed : u64, allowed : u64) -> u64 {
    let mut filled = seed;

    loop {
        let new_filled = grow(filled) & allowed;
        if new_filled == filled {
            return filled;
        }
        filled = new_filled;
    }
}

fn find_first_one(mask : u64) -> usize {
    63 - mask.leading_zeros() as usize
}

fn overlaps(m1 : u64, m2 : u64) -> bool {
    return m1 & m2 != 0u64;
}

fn grow(mask : u64) -> u64 {
    let even = 0b00000_11111_00000_11111_00000_11111_00000_11111_00000_11111;
    let odd = 0b11111_00000_11111_00000_11111_00000_11111_00000_11111_00000;
    let right = 0b00001_00001_00001_00001_00001_00001_00001_00001_00001_00001;
    let left = 0b10000_10000_10000_10000_10000_10000_10000_10000_10000_10000;

    let not_right = mask & !right;
    let not_left = mask & !left;
    let east = not_right>>1;
    let west = not_left<<1;
    let body = mask | (east & (even>>1)) | (west & (odd<<1));

    mask | west | (body << WIDTH) | east | (body >> WIDTH)
}


const NUM_PIECES : usize = 10;
const WIDTH : usize = 5;
const HEIGHT : usize = 10;
const NUM_POSITIONS : usize = WIDTH*HEIGHT;
const LAST_POSITION : usize = NUM_POSITIONS-1;
const FULL_MASK : u64 = (1 << NUM_POSITIONS) - 1;

 make, command-line, and program output logs

Fri, 26 Jun 2015 03:10:37 GMT

MAKE:
/usr/local/src/rust-1.1.0-x86_64-unknown-linux-gnu/rustc/bin/rustc -C opt-level=3 -C target-cpu=core2 -C lto  meteor.rs -o meteor.rust-2.rust_run
8.41s to complete and log all make actions

COMMAND LINE:
./meteor.rust-2.rust_run 2098

PROGRAM OUTPUT:
2098 solutions found

0 0 0 0 1 
 2 2 2 0 1 
2 6 6 1 1 
 2 6 1 5 5 
8 6 5 5 5 
 8 6 3 3 3 
4 8 8 9 3 
 4 4 8 9 3 
4 7 4 7 9 
 7 7 7 9 9 

9 9 9 9 8 
 9 6 6 8 5 
6 6 8 8 5 
 6 8 2 5 5 
7 7 7 2 5 
 7 4 7 2 0 
1 4 2 2 0 
 1 4 4 0 3 
1 4 0 0 3 
 1 1 3 3 3 

Revised BSD license

  Home   Conclusions   License   Play