/*
-----------------------------------------------------------------------
Dice is essentially prolog in C.

The main program (the test harness) calls a user routine, driver(), 
which has to be finite and deterministic, except that it can call a 
routine choose(n) that returns a choice in 0..n-1.  choose(n) is like 
a throw of an n-sided die.  But the test harness calls driver() 
multiple times, once for all possible settings of all its calls to 
choose(n).  So driver() gets to explore all its possible parallel 
universes.  The user should also implement init(), which initializes 
some reusable context for driver().
-----------------------------------------------------------------------
*/

#include <stdio.h>
#include <stddef.h>
#include <memory.h>

typedef unsigned long int  u4;  /* unsigned 4-byte value */
#define U4BITS 32               /* bits per u4 */

static u4 choose(u4 n);
static void *init();
static void driver(void *ctx);

/*
-----------------------------------------------------------------------
User code goes here: it has to define init() and driver()

This particular user code is looking for balanced binary functions
of NAND depth MAX_DEPTH or less, using MAX_VAR variables or less.
Once you've generated all possible tables, I recommend running them
through sort and unique.  I resorted to dice instead of nested loops
because it makes it easy to explore recursive things like nand trees.
-----------------------------------------------------------------------
*/

#define MAX_DEPTH 3
#define MAX_VAR 8

static int varused;
static int lastused;  /* varused from previous success */
static char lasttruth[1<<MAX_VAR];  /* truth from previous success */

typedef struct node {
  struct node *left;
  struct node *right;
  u4 var;
} node;

node *nodepop(node **stack)
{
  node *x = *stack;
  *stack = x->left;
  x->left = (node *)0;
  x->right = (node *)0;
  return x;
}

void nodepush(node **stack, node *x)
{
  x->left = *stack;
  *stack = x;
}

int varorder(node *x, node *y)
{
  if (!x->left) {
    if (x->var == y->var) {
      return 0;
    } else if (x->var < y->var) {
      return 1;
    } else if (x->var > y->var) {
      return -1;
    }
  } else {
    int order = varorder(x->left, y->left);
    if (order == 0) {
      order = varorder(x->right, y->right);
    }
    return order;
  }
}

int treeorder(node *x, node *y)
{
  if (!x) {
    if (!y) {
      return 0;
    } else {
      return 1;
    }
  } else if (!y) {
    return -1;
  } else {
    int order = treeorder(x->left, y->left);
    if (order == 0) {
      order = treeorder(x->right, y->right);
      if (order == 0) {
	order = varorder(x, y);
      }
    }
    return order;
  }
}
 
int add_children(node *x, int depth, node **stack)
{
  node *left;
  node *right;
  int order;

  /* maybe no children */
  if (depth == 0 || !choose(2)) {
    x->var = choose(MAX_VAR);
    varused |= (1 << x->var);
    return 1;
  }

  /* add two children */
  left = nodepop(stack);
  x->left = left;
  if (!add_children(x->left, depth-1, stack)) {
    return 0;
  }
  right = nodepop(stack);
  x->right = right;
  if (!add_children(x->right, depth-1, stack)) {
    return 0;
  }
  if (treeorder(x->left, x->right) == -1)
    return 0;

  return 1;
}

/* evaluate a NAND tree */
int eval(node *x, int i)
{
  if (!x->left) {
    /* return this variable */
    return ((i & (1<<x->var)) != 0);
  } else {
    /* NAND the subtrees */
    return !(eval(x->left, i) & eval(x->right, i));
  }
}

void show(node *x)
{
  if (!x->left && !x->right) {
    printf("%d", x->var);
  } else {
    printf("(");
    if (x->left) {
      show(x->left);
      printf(" ");
    }
    if (x->right) {
      show(x->right);
    }
    printf(")");
  }
}

void nodefree(node *x, node **stack)
{
  if (x->left) nodefree(x->left, stack);
  if (x->right) nodefree(x->right, stack);
  nodepush(stack, x);
}

void *init()
{
  node *stack = (node *)0;
  int i;

  /* make a stack of all the nodes we might need */
  for (i = 0;  i < (1<<(MAX_DEPTH+1));  ++i) {
    node *x = (node *)malloc(sizeof(node));
    x->left = stack;
    x->right = (node *)0;
    stack = x;
  }
  return (void *)stack;
}

void driver(void *ctx)
{
  node *stack = (node *)ctx;
  node *x = nodepop(&stack);
  int count = 0, i, j;
  char truth[1<<MAX_VAR];

  varused = 0;

  /* choose a tree and its variables */
  if (!add_children(x, MAX_DEPTH, &stack)) goto done;

  /* Make sure the bits in varused are dense, 0..#vars-1 */
  if (varused & (varused+1)) goto done;

  /* evaluate the function at all its points */
  for (count=0, i=0; i <= varused; ++i) {
    int result = eval(x,i);
    count += result;
    truth[i] = '0'+result;
  }

  /* is it balanced? */
  if (count != (varused+1)/2) goto done;

  /* is it different from the previous result? */
  if (lastused == varused) {
    for (i=0; i<=varused; ++i) {
      if (truth[i] != lasttruth[i]) break;
    }
    if (i > varused) goto done;
  }

  /* make sure all the variables actually affect the result */
  for (j=1; j<varused; j <<= 1) {
    for (i=0; i<=varused; ++i) {
      if (truth[i] != truth[i^j]) break;
    }
    if (i > varused) goto done;
  }

  /* This is a balanced binary function; report it */
  printf("%3d  ", varused+1);
  printf("%.*s   :  ", varused+1, truth);
  /* show(x); */
  for (i=0; i<=varused; ++i) lasttruth[i] = truth[i];
  lastused = varused;
  printf("\n");

 done:
  nodefree(x, &stack);
}

/*
-----------------------------------------------------------------------
The test harness is below
-----------------------------------------------------------------------
*/

#define DICE_SIZE 256  /* max bits of entropy from the dice */

static u4 dice_state[DICE_SIZE/U4BITS];  /* the actual dice bits */
static u4 dice_offset;  /* the lowest used dice bit */



/* Set bits DICE_SIZE-offset-logn to DICE_SIZE-offset-1 */
void dice_mask(u4 *state, u4 offset, u4 logn)
{
  offset -= logn;
  u4 index = offset / U4BITS;
  u4 shift = offset % U4BITS;
  u4 mask = (1<<logn)-1;
  state[index] |= (mask << shift);
  if (U4BITS-shift < logn) {
    state[index+1] |= (mask >> (U4BITS-shift));
  }
}



/* read bits DICE_SIZE-offset-logn to DICE_SIZE-offset-1 */
u4 dice_read(u4 *state, u4 offset, u4 logn)
{
  offset -= logn;
  u4 index = offset / U4BITS;
  u4 shift = offset % U4BITS;
  u4 mask = (1<<logn)-1;
  u4 result = (state[index] & (mask << shift)) >> shift;
  if (U4BITS-shift < logn) {
    result |= (state[index+1] & (mask >> (U4BITS-shift))) << (U4BITS-shift);
  }
  return result;
}



/* Increment the state at DICE_SIZE-offset-1.  Return TRUE if we can't. */
int dice_inc(u4 *state, u4 offset)
{
  u4 index = offset / U4BITS;
  u4 shift = offset % U4BITS;
  state[index] += (1<<shift);
  while (state[index] == 0 && ++index < DICE_SIZE/U4BITS) {
    state[index] += 1;
  }
  return (index == DICE_SIZE/U4BITS);
}



/* choose a value in 0..n-1 */
static u4 choose(u4 n)
{
  int logn;
  int result;

  /* check that the dice aren't too big */
  if (n > 0x80000000) {
    fprintf(stderr, "Error: Can't do choose(%ul), %ul is too big\n", n, n);
    exit(1);
  }

  /* figure out how many bits to use */
  for (logn=0; (1<<logn) < n; ++logn) ;
  if (dice_offset < logn) {
    fprintf(stderr, "Error: Too many dice rolls\n");
    exit(1);
  }

  /* read the result */
  result = dice_read(dice_state, dice_offset, logn);

  if (result >= n-1) {
    /* If we've reached n-1, pretend we've reached (1<<logn)-1 */
    if (result == n-1) {
      dice_mask(dice_state, dice_offset, logn);
    } else {
      result = n-1;
    }
  }

  /* record how many bits we used and report the result */
  dice_offset -= logn;

  return result;
}


/* call driver() with all possible values of all calls to choose() */
int main()
{
  u4 i;
  void *ctx = init();

  /* initialize the state to zero */
  for (i=0; i<DICE_SIZE/U4BITS; ++i) {
    dice_state[i] = 0;
  }

  /* call driver, then increment the state */
  for (;;) {

    /* call the user's driver with a new state */
    dice_offset = DICE_SIZE;
    driver(ctx);

    /* increment the state; quit when we wrap around */
    if (dice_inc(dice_state, dice_offset)) break;
  }
}