Skip to content

Instantly share code, notes, and snippets.

@gozzoo
Created July 5, 2012 07:47
Show Gist options
  • Save gozzoo/3052132 to your computer and use it in GitHub Desktop.
Save gozzoo/3052132 to your computer and use it in GitHub Desktop.
annkuchredux benchmark implementation in javascript
function fannkuchredux(n) {
var perm = new Array(n);
var perm1 = new Array(n);
var count = new Array(n);
var maxFlipsCount = 0;
var permCount = 0;
var checksum = 0;
var i;
for (i = 0; i < n; i++)
perm1[i] = i;
var r = n;
while (true) {
while (r != 1) {
count[r-1] = r;
r -= 1;
}
for (i = 0; i < n; i += 1)
perm[i] = perm1[i];
var flipsCount = 0;
for (var k = perm[0]; k != 0; k = perm[0]) {
var k2 = (k+1) >> 1;
for (i = 0; i < k2; i++) {
var temp = perm[i];
perm[i] = perm[k-i];
perm[k-i] = temp;
}
flipsCount += 1;
}
if (flipsCount > maxFlipsCount)
maxFlipsCount = flipsCount;
var csi = flipsCount;
if (permCount % 2 != 0)
csi = -flipsCount;
checksum += csi;
while (true) {
if (r == n) {
console.log(checksum);
return maxFlipsCount;
}
var perm0 = perm1[0];
i = 0;
while (i < r) {
var j = i + 1;
perm1[i] = perm1[j];
i = j;
}
perm1[r] = perm0;
count[r] = count[r] - 1;
if (count[r] > 0)
break;
r++;
}
permCount++;
}
//return 0;
}
var n = 11;
var res = fannkuchredux(n);
console.log("Pfannkuchen(" + n + ") = " + res);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment