1 // The Computer Language Benchmarks Game
2 // http://benchmarksgame.alioth.debian.org/
4 // contributed by the Rust Project Developers
6 // Copyright (c) 2014 The Rust Project Developers
8 // All rights reserved.
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions
14 // - Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
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
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.
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.
41 #![feature(slicing_syntax)]
43 use std::{cmp, iter, mem};
44 use std::thread::Thread;
46 fn rotate(x: &mut [i32]) {
48 for place in x.iter_mut().rev() {
49 prev = mem::replace(place, prev)
53 fn next_permutation(perm: &mut [i32], count: &mut [i32]) {
54 for i in range(1, perm.len()) {
55 rotate(perm.slice_to_mut(i + 1));
56 let count_i = &mut count[i];
57 if *count_i >= i as i32 {
83 fn new(n: u32) -> Perm {
84 let mut fact = [1; 16];
85 for i in range(1, n as uint + 1) {
86 fact[i] = fact[i - 1] * i as u32;
93 perm: P { p: [0; 16 ] }
97 fn get(&mut self, mut idx: i32) -> P {
98 let mut pp = [0u8; 16];
99 self.permcount = idx as u32;
100 for (i, place) in self.perm.p.iter_mut().enumerate() {
101 *place = i as i32 + 1;
104 for i in range(1, self.n as uint).rev() {
105 let d = idx / self.fact[i] as i32;
107 idx %= self.fact[i] as i32;
108 for (place, val) in pp.iter_mut().zip(self.perm.p[..(i+1)].iter()) {
109 *place = (*val) as u8
113 for j in range(0, i + 1) {
114 self.perm.p[j] = if j + d <= i {pp[j + d]} else {pp[j+d-i-1]} as i32;
121 fn count(&self) -> u32 { self.permcount }
122 fn max(&self) -> u32 { self.fact[self.n as uint] }
124 fn next(&mut self) -> P {
125 next_permutation(&mut self.perm.p, &mut self.cnt);
133 fn reverse(tperm: &mut [i32], k: uint) {
134 tperm.slice_to_mut(k).reverse()
137 fn work(mut perm: Perm, n: uint, max: uint) -> (i32, i32) {
138 let mut checksum = 0;
139 let mut maxflips = 0;
141 let mut p = perm.get(n as i32);
143 while perm.count() < max as u32 {
147 let k = p.p[0] as uint;
148 reverse(&mut p.p, k);
152 checksum += if perm.count() % 2 == 0 {flips} else {-flips};
153 maxflips = cmp::max(maxflips, flips);
161 fn fannkuch(n: i32) -> (i32, i32) {
162 let perm = Perm::new(n as u32);
165 let mut futures = vec![];
166 let k = perm.max() / N;
168 for (_, j) in range(0, N).zip(iter::count(0, k)) {
169 let max = cmp::min(j+k, perm.max());
171 futures.push(Thread::scoped(move|| {
172 work(perm, j as uint, max as uint)
176 let mut checksum = 0;
177 let mut maxflips = 0;
178 for fut in futures.into_iter() {
179 let (cs, mf) = fut.join().ok().unwrap();
181 maxflips = cmp::max(maxflips, mf);
187 let n = std::os::args().as_slice()
189 .and_then(|arg| arg.parse())
192 let (checksum, maxflips) = fannkuch(n);
193 println!("{}\nPfannkuchen({}) = {}", checksum, n, maxflips);