| 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 |