//  9-puzzle.cpp
//
//  Author: Fred Curtis, May 2000
//  URL:    http://f2.org/products/
//
//  This program solves a permutation puzzle (first encountered on a
//  mobile phone!) where the grid of numbers:
//
//      1 2 3
//      4 5 6
//      7 8 9
//
//  are jumbled up and then restored by clockwise rotations
//  of 2x2 blocks of numbers in each corner of the 3x3 square.

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <time.h>

//  Routines for indexing permutations
//

class Factorial {
public:
  static int const Max = 12;

  inline
  static long of(int index) {
    static long factorial[Max + 1];
    static class FactInit {
    public:
      FactInit() {
        factorial[0] = 1;
        for (int i = 1; i <= Max; i++) {
          factorial[i] = factorial[i - 1] * i;
        }
      }
    } init;
    return (index >= 0 && index <= Max) ? factorial[index] : 0;
  }
};

int perm2index(char const *str) {
  int len = strlen(str);

  if (len > Factorial::Max) {
    len = Factorial::Max;
  }
  char const *end = &str[len];
  long retval = 0;
  for (; len-- > 0; str++) {
    long mul = Factorial::of(len);
    for (char const *tmp = str + 1; tmp < end; tmp++) {
      if (*str > *tmp) {
        retval += mul;
      }
    }
  }
  return retval;
}

static char *index2perm(int index, int len, char const *refOrig) {
  static char retval[Factorial::Max + 1];

  if (len > Factorial::Max) {
    len = Factorial::Max;
  }
  memcpy(retval, refOrig, len);
  retval[Factorial::Max] = '\0';
  index %= Factorial::of(len);
  if (index < 0) {
    index = 0;
  }
  char *str = retval;
  for (; len-- > 0; str++) {
    int elt = index / Factorial::of(len);
    index %= Factorial::of(len);
    char ch = str[elt];
    while (elt > 0) {
      str[elt] = str[elt - 1];
      elt--;
    }
    *str = ch;
  }
  return retval;
}

int main(int argc, char *argv[]) {
  printf("9-puzzle  --  Author: Fred Curtis, May 2000  "
    "--  http://f2.org/products/\n\n");

  long nperm = Factorial::of(9);
  struct Perm9 {
    char s[10];
    char revop;
    short delta;
    void print() {
      printf("%c %c %c\n", s[0], s[1], s[2]);
      printf("%c %c %c\n", s[3], s[4], s[5]);
      printf("%c %c %c\n", s[6], s[7], s[8]);
    }
  };

  struct Transform {
    char *name;
    short srcCell[9];
    char revop;
    Perm9 apply(Perm9 const &src) {
      Perm9 retval = src;
      for (int i = 0; i < 9; i++) {
        retval.s[i] = src.s[srcCell[i]];
      }
      retval.revop = revop;
      return retval;
    }
  };

  Transform transforms[8] = {
    { "NW-", { 1, 4, 2, 0, 3, 5, 6, 7, 8 }, 4 },
    { "NE-", { 0, 2, 5, 3, 1, 4, 6, 7, 8 }, 5 },
    { "SW-", { 0, 1, 2, 4, 7, 5, 3, 6, 8 }, 6 },
    { "SE-", { 0, 1, 2, 3, 5, 8, 6, 4, 7 }, 7 },
    { "NW+", { 3, 0, 2, 4, 1, 5, 6, 7, 8 }, 0 },
    { "NE+", { 0, 4, 1, 3, 5, 2, 6, 7, 8 }, 1 },
    { "SW+", { 0, 1, 2, 6, 3, 5, 7, 4, 8 }, 2 },
    { "SE+", { 0, 1, 2, 3, 7, 4, 6, 8, 5 }, 3 },
  };

  time_t startTime = time(0);
  Perm9 *perms = new Perm9[nperm];
  long *prev = new long[nperm];
  short *delta = new short[nperm];
  for (long index = 0; index < nperm; index++) {
    Perm9 *perm = &perms[index];
    if (index % 10000 == 0) {
      printf("Initialising -- %2.0f %%\r", 100.0 * index / nperm);
      fflush(stdout);
    }
    strcpy(perm->s, index2perm(index, 9, "123456789"));
    perm->delta = -1;
  }
  printf("Initialising - done           \r");

  perms[0].delta = 0;
  int nTotal = 0;
  Perm9 *worst = &perms[0];
  for (int currDelta = 0; ; currDelta++) {
    int nAdded = 0;
    for (long index = 0; index < nperm; index++) {
      Perm9 *perm = &perms[index];
      if (index % 10000 == 0) {
        printf("Delta %2d -- %2.0f %% --  %6d left to go  -- %6d new\r", currDelta, 100.0 * index / nperm, nperm - nTotal, nAdded);
        fflush(stdout);
      }
      if (perm->delta == currDelta) {
        //  Mark all permutations adjacent to this one
        //
        for (int transIndex = 0; transIndex < 4; transIndex++) {
          Transform *t = &transforms[transIndex];
          Perm9 transPerm = t->apply(*perm);
          long newIndex = perm2index(transPerm.s);
          Perm9 *newPerm = &perms[newIndex];
          if (newPerm->delta == -1) {
            newPerm->delta = currDelta + 1;
            newPerm->revop = t->revop;
            nAdded++;
            nTotal++;
            worst = newPerm;
          }
        }
      }
    }
    if (nAdded < 1) {
      break;
    }
  }
  time_t endTime = time(0);
  printf("-----------------  %ld seconds (realtime) to initialise  --------------------\n",
          (long) (endTime - startTime));
  printf("\n  Furthest perm:\n");
  worst->print();

  char buf[20];
  for (;;) {
    printf("\nEnter permutation of digits 1..9  (or q to quit) ... ");
    fflush(stdout);
    if (fgets(buf, sizeof(buf), stdin) == 0) {
      break;
    }
    if (toupper(buf[0]) == 'Q') {
      break;
    }
    char *end = &buf[sizeof(buf) - 1];
    char *tmp = buf;
    for (; tmp < end && isprint(*tmp); tmp++) {
    }
    *tmp = '\0';
    long index = perm2index(buf) % Factorial::of(9);
    perms[index].print();
    struct {
      char const *name;
      int count;
    } moves[20];
    int nmove = 0;
    while (index != 0) {
      Perm9 *oldPerm = &perms[index % Factorial::of(9)];
      if (oldPerm->revop < 0) {
        printf("  ---- Unsolvable! ----\n");
        break;
      }
      Transform *t = &transforms[oldPerm->revop];
      Perm9 newPerm = t->apply(*oldPerm);
      printf("---- transform: %s  ->  %.3s / %.3s / %.3s\n",
        t->name,
        newPerm.s,
        newPerm.s + 3,
        newPerm.s + 6
        );
      if (nmove == 0 || t->name != moves[nmove-1].name) {
        moves[nmove].name = t->name;
        moves[nmove].count = 1;
        nmove++;
      } else {
        moves[nmove-1].count++;
      }
      long newIndex = perm2index(newPerm.s);
      index = newIndex;
    }
    printf("Solution: ", nmove);
    for (int i = 0; i < nmove; i++) {
      printf("%s%s", i == 0 ? "" : "  ", moves[i].name);
      if (moves[i].count > 1) {
        printf("x%d", moves[i].count);
      }
    }
    printf("\n");
  }
  return 0;
}