OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 // The Great Computer Language Shootout | 4 // The Great Computer Language Shootout |
5 // http://shootout.alioth.debian.org/ | 5 // http://shootout.alioth.debian.org/ |
6 // Ported from JavaScript contributed by Isaac Gouy. | 6 // Ported from JavaScript contributed by Isaac Gouy. |
7 // Description: Repeatedly acccess a tiny integer-sequence. | 7 // Description: Repeatedly acccess a tiny integer-sequence. |
8 | 8 |
9 import "package:expect/expect.dart"; | 9 import "package:expect/expect.dart"; |
10 | 10 |
11 class FannkuchTest { | 11 class FannkuchTest { |
12 static fannkuch(n) { | 12 static fannkuch(n) { |
13 var p = new List(n), q = new List(n), s = new List(n); | 13 var p = new List(n), q = new List(n), s = new List(n); |
14 var sign = 1, maxflips = 0, sum = 0, m = n - 1; | 14 var sign = 1, maxflips = 0, sum = 0, m = n - 1; |
15 for (var i = 0; i < n; i++) { p[i] = i; q[i] = i; s[i] = i; } | 15 for (var i = 0; i < n; i++) { |
| 16 p[i] = i; |
| 17 q[i] = i; |
| 18 s[i] = i; |
| 19 } |
16 do { | 20 do { |
17 // Copy and flip. | 21 // Copy and flip. |
18 var q0 = p[0]; // Cache 0th element. | 22 var q0 = p[0]; // Cache 0th element. |
19 if (q0 != 0) { | 23 if (q0 != 0) { |
20 for (var i = 1; i < n; i++) q[i] = p[i]; // Work on a copy. | 24 for (var i = 1; i < n; i++) q[i] = p[i]; // Work on a copy. |
21 var flips = 1; | 25 var flips = 1; |
22 do { | 26 do { |
23 var qq = q[q0]; | 27 var qq = q[q0]; |
24 if (qq == 0) { // ... until 0th element is 0. | 28 if (qq == 0) { |
| 29 // ... until 0th element is 0. |
25 sum += sign * flips; | 30 sum += sign * flips; |
26 if (flips > maxflips) maxflips = flips; // New maximum? | 31 if (flips > maxflips) maxflips = flips; // New maximum? |
27 break; | 32 break; |
28 } | 33 } |
29 q[q0] = q0; | 34 q[q0] = q0; |
30 if (q0 >= 3) { | 35 if (q0 >= 3) { |
31 var i = 1, j = q0 - 1, t; | 36 var i = 1, j = q0 - 1, t; |
32 do { t = q[i]; q[i] = q[j]; q[j] = t; i++; j--; } while (i < j); | 37 do { |
| 38 t = q[i]; |
| 39 q[i] = q[j]; |
| 40 q[j] = t; |
| 41 i++; |
| 42 j--; |
| 43 } while (i < j); |
33 } | 44 } |
34 q0 = qq; flips++; | 45 q0 = qq; |
| 46 flips++; |
35 } while (true); | 47 } while (true); |
36 } | 48 } |
37 if (sign == 1) { | 49 if (sign == 1) { |
38 var t = p[1]; p[1] = p[0]; p[0] = t; sign = -1; // Rotate 0<-1. | 50 var t = p[1]; |
| 51 p[1] = p[0]; |
| 52 p[0] = t; |
| 53 sign = -1; // Rotate 0<-1. |
39 } else { | 54 } else { |
40 // Rotate 0<-1 and 0<-1<-2. | 55 // Rotate 0<-1 and 0<-1<-2. |
41 var t = p[1]; | 56 var t = p[1]; |
42 p[1] = p[2]; | 57 p[1] = p[2]; |
43 p[2] = t; | 58 p[2] = t; |
44 sign = 1; | 59 sign = 1; |
45 for(var i = 2; i < n; i++) { | 60 for (var i = 2; i < n; i++) { |
46 var sx = s[i]; | 61 var sx = s[i]; |
47 if (sx != 0) { s[i] = sx-1; break; } | 62 if (sx != 0) { |
| 63 s[i] = sx - 1; |
| 64 break; |
| 65 } |
48 if (i == m) { | 66 if (i == m) { |
49 return [sum, maxflips]; | 67 return [sum, maxflips]; |
50 } | 68 } |
51 s[i] = i; | 69 s[i] = i; |
52 // Rotate 0<-...<-i+1. | 70 // Rotate 0<-...<-i+1. |
53 t = p[0]; | 71 t = p[0]; |
54 for(var j=0; j<=i; j++) { p[j] = p[j+1]; } | 72 for (var j = 0; j <= i; j++) { |
55 p[i+1] = t; | 73 p[j] = p[j + 1]; |
| 74 } |
| 75 p[i + 1] = t; |
56 } | 76 } |
57 } | 77 } |
58 } while (true); | 78 } while (true); |
59 } | 79 } |
60 | 80 |
61 static testMain() { | 81 static testMain() { |
62 var n = 6; | 82 var n = 6; |
63 var pf = fannkuch(n); | 83 var pf = fannkuch(n); |
64 Expect.equals(49, pf[0]); | 84 Expect.equals(49, pf[0]); |
65 Expect.equals(10, pf[1]); | 85 Expect.equals(10, pf[1]); |
66 print("${pf[0]}\nPfannkuchen($n) = ${pf[1]}"); | 86 print("${pf[0]}\nPfannkuchen($n) = ${pf[1]}"); |
67 } | 87 } |
68 } | 88 } |
| 89 |
69 main() { | 90 main() { |
70 FannkuchTest.testMain(); | 91 FannkuchTest.testMain(); |
71 } | 92 } |
OLD | NEW |