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

#define ARRAY_LEN   (36 * 36 * 36)

typedef struct diceroll_s {
  int             fReady;           /* TRUE if initialised */
  int             fInitial;         /* TRUE if rollout of initial position */
  int             count;            /* used for getting first roll */
  unsigned short  first[36];        /* sequence of turn 0 dice */
  int             last;             /* wrap when we get to here */
  int             indices[36];      /* indices for 2nd & later rolls */
  unsigned short  rolls[ARRAY_LEN]; /* packed sequence of turns 1..3 */
  void   (*randfunc)(int *);        /* ptr to function returning a roll  */
} diceroll;

static void 
SwapRolls (unsigned short *a, unsigned short *b) {
  unsigned short c = *a;
  
  *a = *b; *b = c;
}

/* set up the first rolls array and randomise it. Then set up the indices
 * for second/third/fourth rolls and randomise them as well
 */
static void 
SetFirstRolls (diceroll *pDiceRoll) {
  
  int             i, save, swap;
  unsigned short *p = pDiceRoll->first;
  int            *ind = pDiceRoll->indices;

  for (i = 0; i < 36; ++i) {
      *p++ = i;
      /* the indices will point to a sub-array. The -1 is a
       *     setup for the first call to GetRoll
       */
      *ind++ = i *  1296 - 1;
  }
      
  p = pDiceRoll->first;
  
  for (i = 0; i < 36; ++i) 
    SwapRolls (p + i, p + (random () % 36));

  /* Randomise the indices */
  for (i = 0; i < 36; ++i) {
    swap = random () % 36;
    save = pDiceRoll->indices[i];
    pDiceRoll->indices[i] = pDiceRoll->indices[swap];
    pDiceRoll->indices[swap] = save;
  }

}

static void 
RandomiseLayers (diceroll *pDiceRoll) {

  int             layer, i, j, k, swap;
  unsigned short *p;
  int             seq_len, arr_len, no_sets;
                
  for (layer = 3, 
         seq_len = ARRAY_LEN,
         arr_len = ARRAY_LEN / 36,
         no_sets = 1;
       layer > 0;
       --layer, 
         seq_len /= 36,
         arr_len /= 36,
         no_sets *= 36) {

    /* treat the set of rolls as no_sets sequences of
     * 36 arrays of length arr_len. Within each set of arrays
     * the rolls for lower layers (earlier rolls) are repeated
     * in the same order in each array. The roll for this layer
     * is 11 in the first array, 12 in the second, etc.
     * We can swap corresponding elements in any of the arrays of
     * one set without breaking anything, thereby randomising the
     * rolls for this layer
     */
    for (i = 0; i < no_sets; ++i) {
      /* find the start of the set of 36 sequences */
      p = pDiceRoll->rolls + (i * seq_len);

      /* do every element within each array in the set */
      for (j = 0; j < arr_len; ++j) {
        /* for each of the 36 arrays in this set */
        for (k = 0; k < 36; ++k) {
          /* pick another array in the set */
          swap = random () % 36;

          /* just to ensure that we maintain the invariant that
           * we're only randomising higher layers
           */
          assert ((*(p + j + k * arr_len) % arr_len) ==
            (*(p + j + swap * arr_len) % arr_len));

          SwapRolls (p + j + k * arr_len, p + j + swap * arr_len);
        }
      }
    }
  }
}

/* Initialise/reinitialise the arrays */

static void 
InitRolls (diceroll *pDiceRoll, int nGames, int fInitial,
                       void   (*randfunc)(int *) ) {

  int                i;
  unsigned short    *p;

  pDiceRoll->fInitial = fInitial;
  pDiceRoll->randfunc = randfunc;
  pDiceRoll->last =  ARRAY_LEN;
  pDiceRoll->count = 0;

  /* scramble the initial rolls */
  SetFirstRolls (pDiceRoll);

  if (!pDiceRoll->fReady) {
    /* scramble rolls 1/2/3 only the first time */
    for (p = pDiceRoll->rolls, i = 0; i < ARRAY_LEN; ++i) 
      *p++ = i;

    RandomiseLayers (pDiceRoll);
    pDiceRoll->fReady = 1;
  }

}

static void 
GetRoll (diceroll *pDiceRoll, int nTurn, int *anDice) {

  int i, first;

  while (1) {   
    if ((nTurn == 0) && ((pDiceRoll->count % 36) == 0)) {
      /* update all the pointers for each 36 new games */
      for (i = 0; i < 36; ++i) {
        if (++pDiceRoll->indices[i] >= ARRAY_LEN)
          pDiceRoll->indices[i] -= ARRAY_LEN;
      }
    }

    first = i = pDiceRoll->first[(pDiceRoll->count) % 36];

    if (nTurn == 0) {
        ++pDiceRoll->count;
    }

    anDice[0] = 1 + i / 6;
    anDice[1] = 1 + (i % 6);
    
    /* keep tring if it's a double and fInitial */
    if (!pDiceRoll->fInitial || (anDice[0] != anDice[1]) || (nTurn != 0))
      break;

  }

  if (nTurn == 0)
    return;

  /* use the supplied function for turns after the first 4 */
  if (nTurn > 3) {
    (pDiceRoll->randfunc) (anDice);
    return;
  }

  /* get an entry out of the array and return the appropriate dice */
  i = pDiceRoll->rolls[pDiceRoll->indices[first]];

#if DEBUGGING_ROLLS
  assert (i < ARRAY_LEN);
# endif

  switch (nTurn) {
  case 3:

#if DEBUGGING_ROLLS
    pDiceRoll->rolls[pDiceRoll->indices[first]] = 0xffff;
# endif

    i /= 36;
    /* fall through */
  case 2:
    i /= 36;
    /* fall through */
  case 1:
    i %= 36;
    anDice[0] = 1 + i / 6;
    anDice[1] = 1 + (i % 6);
    return;

  default:
    assert ( 1 == 0 );
  }
}

#ifdef TEST_ROLLS
/* dummy function to get random dice for later rolls
 * in real life, some systems random() function may not be good enough, 
 * so we'd use something better.
 */
static void RandRoll (int *aRoll) {
  
  aRoll[0] = 1 + random () % 6;
  aRoll[1] = 1 + random () % 6;
}

static diceroll adRoll;

static void 
usage (char * program) {
  fprintf (stderr, 
           "Usage: %s <trials> <0|1>\n"
           "   trials = 1..4 to test 1..4 plies of full rollouts\n"
           "          other values are exact counts\n"
           "   optional flag 0/1 for Initial position\n", program);
  exit (1);
}

int main (int argc, char **argv) {

  int   trials = 1296;
  int   i, t;
  int   iGame, iTurn;
  int   fInitial = 0;
  int   anDice[2];

  switch (argc) {
  case 3:
    /* set fInitial from command line */
    sscanf (argv[2], "%d", &fInitial);
    if ((fInitial < 0) || (fInitial > 1)) {
      usage (argv[0]);
    }
    /* fall through */

  case 2:
    /* get number of full rollouts or no. of games */
    sscanf (argv[1], "%d", &trials);
    if (trials < 1) {
      usage (argv[0]);
    }
    if (trials < 5) {
      t = 1;
      for (i = 0; i < trials; ++i) {
        t *= (fInitial && (i == 0)) ? 30 : 36;
      }
      trials = t;
    }
    break;

  case 1:
    break;

  default:
    usage (argv[0]);
  }

  srandom (1);

  InitRolls (&adRoll, trials, fInitial, RandRoll);

  iGame = 0;

  while (1) {
    /* work out what the first four rolls of a game will be */
    for (iTurn = 0; iTurn < 4; ++iTurn) {
      GetRoll (&adRoll, iTurn, anDice);

      /* ensure printout shows low, high */
      if (anDice[0] > anDice[1]) {
        i = anDice[1];
        anDice[1] = anDice[0];
        anDice[0] = i;
      }
      /* make it easy to grep out all the nth moves from the results */
      printf ("%d%d ", anDice[0], anDice[1]);

    }
    printf (": %d\n", iGame);

    ++iGame; 
    if (--trials <= 0)
      break;
  }
    
  return 0;
}
    
#endif