blob: e21cec6548274bea1aca325cd52f1c4353b1fcd6 [file] [log] [blame]
/*
* Copyright 2010 The Emscripten Authors. All rights reserved.
* Emscripten is available under two separate licenses, the MIT license and the
* University of Illinois/NCSA Open Source License. Both these licenses can be
* found in the LICENSE file.
*
* The Computer Language Benchmarks Game
* http://shootout.alioth.debian.org/
*
* Contributed by Eckehard Berns
* Based on code by Heiner Marxen
* and the ATS version by Hongwei Xi
*
* Modified for emscripten by azakai
*/
#include <stdlib.h>
#include <stdio.h>
struct worker_args {
int i, n;
struct worker_args *next;
};
int
fannkuch_worker(void *_arg)
{
struct worker_args *args = (worker_args*)_arg;
int *perm1, *count, *perm;
int maxflips, flips, i, n, r, j, k, tmp;
maxflips = 0;
n = args->n;
perm1 = (int*)malloc(n * sizeof(int));
perm = (int*)malloc(n * sizeof(int));
count = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++)
perm1[i] = i;
perm1[args->i] = n - 1;
perm1[n - 1] = args->i;
r = n;
for (;;) {
for (; r > 1; r--)
count[r - 1] = r;
if (perm1[0] != 0 && perm1[n - 1] != n - 1) {
for (i = 0; i < n; i++)
perm[i] = perm1[i];
flips = 0;
k = perm[0];
do {
for (i = 1, j = k - 1; i < j; i++, j--) {
tmp = perm[i];
perm[i] = perm[j];
perm[j] = tmp;
}
flips++;
tmp = perm[k];
perm[k] = k;
k = tmp;
} while (k);
if (maxflips < flips)
maxflips = flips;
}
for (;;) {
if (r >= n - 1) {
free(perm1);
free(perm);
free(count);
return maxflips;
}
{
int p0 = perm1[0];
for (i = 0; i < r; i++)
perm1[i] = perm1[i + 1];
perm1[i] = p0;
}
if (--count[r] > 0)
break;
r++;
}
}
}
static int
fannkuch(int n)
{
struct worker_args *args, *targs;
int showmax = 30;
int *perm1, *count, i, r, maxflips, flips;
args = NULL;
for (i = 0; i < n - 1; i++) {
targs = (worker_args*)malloc(sizeof(struct worker_args));
targs->i = i;
targs->n = n;
targs->next = args;
args = targs;
}
perm1 = (int*)malloc(n * sizeof(int));
count = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++)
perm1[i] = i;
r = n;
for (;;) {
if (showmax) {
for (i = 0; i < n; i++)
printf("%d", perm1[i] + 1);
printf("\n");
showmax--;
} else
goto cleanup;
for (; r > 1; r--)
count[r - 1] = r;
for (;;) {
if (r == n)
goto cleanup;
{
int p0 = perm1[0];
for (i = 0; i < r; i++)
perm1[i] = perm1[i + 1];
perm1[i] = p0;
}
if (--count[r] > 0)
break;
r++;
}
}
cleanup:
free(perm1);
free(count);
maxflips = 0;
while (args != NULL) {
flips = (int)fannkuch_worker(args);
if (maxflips < flips)
maxflips = flips;
targs = args;
args = args->next;
free(targs);
}
return maxflips;
}
int main(int argc, char **argv) {
int n = argc > 1 ? atoi(argv[1]) : 0;
if (n < 1) {
printf("Wrong argument.\n");
return 1;
}
printf("Pfannkuchen(%d) = %d.\n", n, fannkuch(n));
return 0;
}