Skip to content

Instantly share code, notes, and snippets.

@gozzoo
Last active October 6, 2015 20:58
Show Gist options
  • Save gozzoo/3052070 to your computer and use it in GitHub Desktop.
Save gozzoo/3052070 to your computer and use it in GitHub Desktop.
fannkuchredux benchmark implementation in java
public class Fannkuchredux {
static int fannkuchredux(int n) {
int[] perm = new int[n];
int[] perm1 = new int[n];
int[] count = new int[n];
int maxFlipsCount = 0;
int permCount = 0;
int checksum = 0;
int i;
for (i = 0; i < n; i++)
perm1[i] = i;
int r = n;
while (true) {
while (r != 1) {
count[r-1] = r;
r -= 1;
}
for (i = 0; i < n; i += 1)
perm[i] = perm1[i];
int flipsCount = 0;
for (int k = perm[0]; k != 0; k = perm[0]) {
int k2 = (k+1) >> 1;
for (i = 0; i < k2; i++) {
int temp = perm[i];
perm[i] = perm[k-i];
perm[k-i] = temp;
}
flipsCount += 1;
}
if (flipsCount > maxFlipsCount)
maxFlipsCount = flipsCount;
int csi = flipsCount;
if (permCount % 2 != 0)
csi = -flipsCount;
checksum += csi;
while (true) {
if (r == n) {
System.out.printf("%d\n", checksum);
return maxFlipsCount;
}
int perm0 = perm1[0];
i = 0;
while (i < r) {
int 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;
}
public static void main(String[] args) {
int n = 11;
long t1 = System.currentTimeMillis();
System.out.printf("Pfannkuchen(%d) = %d\n", n, fannkuchredux(n));
long t2 = System.currentTimeMillis();
System.out.println("time: " + (t2 - t1));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment