blob: 0d24d338202905ec5742a33b49d34fac556d1c5f (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
// Based on Isaac Gouy's fannkuchredux.csharp
use std;
import std::_int;
import std::_vec;
fn fannkuch(int n) -> int {
fn perm1init(uint i) -> int {
ret i as int;
}
auto perm1init_ = perm1init; // Rustboot workaround
auto perm = _vec::init_elt(0, n as uint);
auto perm1 = _vec::init_fn(perm1init_, n as uint);
auto count = _vec::init_elt(0, n as uint);
auto f = 0;
auto i = 0;
auto k = 0;
auto r = 0;
auto flips = 0;
auto nperm = 0;
auto checksum = 0;
r = n;
while (r > 0) {
i = 0;
while (r != 1) {
count.(r - 1) = r;
r -=1;
}
while (i < n) {
perm.(i) = perm1.(i);
i += 1;
}
// Count flips and update max and checksum
f = 0;
k = perm.(0);
while (k != 0) {
i = 0;
while (2 * i < k) {
auto t = perm.(i);
perm.(i) = perm.(k - i);
perm.(k - i) = t;
i += 1;
}
k = perm.(0);
f += 1;
}
if (f > flips) {
flips = f;
}
if ((nperm & 0x1) == 0) {
checksum += f;
} else {
checksum -= f;
}
// Use incremental change to generate another permutation
auto go = true;
while (go) {
if (r == n) {
log checksum;
ret flips;
}
auto p0 = perm1.(0);
i = 0;
while (i < r) {
auto j = i + 1;
perm1.(i) = perm1.(j);
i = j;
}
perm1.(r) = p0;
count.(r) -= 1;
if (count.(r) > 0) {
go = false;
} else {
r += 1;
}
}
nperm += 1;
}
ret flips;
}
fn main(vec[str] args) {
auto n = 7;
log #fmt("Pfannkuchen(%d) = %d", n, fannkuch(n));
}
|