fannkuch_with_sleep.cpp

#include <assert.h>
#include <emscripten.h>
#include <stdlib.h>
#include <stdio.h>

int possibleSleeps = 0;
int TOTAL_POSSIBLE_SLEEPS = 470642631;

int sleeps = 0;
int TOTAL_SLEEPS = 1000;

int INTERVAL = TOTAL_SLEEPS > 0 ? TOTAL_POSSIBLE_SLEEPS / TOTAL_SLEEPS : 4 * TOTAL_POSSIBLE_SLEEPS;

int SLEEP_MS = 1;

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];
               //====================================
               // Sleep in the worst possible place.
               if (possibleSleeps++ % INTERVAL == INTERVAL / 2) {
                 sleeps++;
                 emscripten_sleep(SLEEP_MS);
               }
               //====================================
               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]) : 11;

   if (n < 1) {
      printf("Wrong argument.\n");
      return 1;
   }
   printf("Pfannkuchen(%d) = %d.\n", n, fannkuch(n));
   printf("possible sleeps: %d\n", possibleSleeps);
   printf("sleeps: %d\n", sleeps);
   assert(possibleSleeps == TOTAL_POSSIBLE_SLEEPS);
   return 0;
}