/* This file is in the public domain. */

/*
 * Program to brute-force finding table-and-glasses algorithms.
 *
 * We consider a `node' to be a set of possible glass patterns.  For
 *  each node, we consider:
 *	For each possible hand pattern (which wells we check)
 *	  For each possible observation for that pattern
 *	    For each possible toggle pattern
 *	      Compute the new set (of possible glass patterns)
 *  and then, if we haven't yet created a node for the new set, record
 *  it, including how we reached it.
 *
 * Once this is done, we then need to extract an algorithm from the
 *  node graph, if there is one.  To do this, we look for nodes for
 *  which there is a mask for which each possible observation has a
 *  toggle pattern that reaches a goal state.  Such nodes are then
 *  effectively considered goal states when looking for more such
 *  nodes.  After doing all possible such markings, we have an
 *  algorithm iff the root node is marked.
 *
 * This needs to be built with -DINC_NAME naming a file written by
 *  gen-values giving tables and parameters; see gen-values.c and the
 *  Makefile.
 *
 * It can be run with -v or -V N.  -V sets the verbosity level; -v
 *  increments it.  Verbosity starts at 0.
 */

#include <avl.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

extern const char *__progname;

#include INC_NAME

#define MAXOBS (1U<<HANDS)
#define NFLIP (1U<<HANDS)
#define POSSBIT(x) (((REPRMASK)1)<<(x))
#define NPOSSV POSSBIT(NREPR)
#define EMPTYMASK ((MASKTYPE)0)
#define FULLMASK (((((MASKTYPE)1)<<(WELLS-1))<<1)-1)

typedef struct node NODE;
typedef struct actm ACTM;
typedef struct actmo ACTMO;
typedef struct action ACTION;
typedef struct nodelist NODELIST;

struct nodelist {
  NODELIST *link;
  NODE *n;
  } ;

struct action {
  NODE *to;
  } ;

struct actmo {
  MASKTYPE obs;
  MASKTYPE fflip;
  ACTION acts[NFLIP];
  } ;

struct actm {
  int nobs;
  ACTMO *obsv;
  } ;

struct node {
  NODE *link;
  signed char fdist;
  unsigned char mx;
  unsigned char ox;
  unsigned char fx;
  unsigned char fmask; // meaningful only when fdist>=0
  char printed;
  REPRMASK possible;
  ACTM arms[NMASK];
  } ;

static int verbose = 0;
static NODELIST *pend;
static NODELIST **pendtail;
static NODELIST *nlfree;
static MASKTYPE obs[MAXOBS];
static int nobs;
static AVL *nodefor;
static NODE *allnodes;
static NODE *rootnode;

static NODE *newnode(void)
{
 NODE *n;

 n = malloc(sizeof(NODE));
 n->fdist = -1;
 n->link = allnodes;
 n->printed = 0;
 allnodes = n;
 return(n);
}

static void append_pend(NODE *n)
{
 NODELIST *e;

 e = nlfree;
 if (! e)
  { e = malloc(sizeof(NODELIST));
  }
 else
  { nlfree = e->link;
  }
 e->n = n;
 e->link = 0;
 *pendtail = e;
 pendtail = &e->link;
}

static NODE *get_pend(void)
{
 NODELIST *e;
 NODE *n;

 e = pend;
 if (! e) return(0);
 pend = e->link;
 if (! pend) pendtail = &pend;
 n = e->n;
 e->link = nlfree;
 nlfree = e;
 return(n);
}

static void print_mask_2(MASKTYPE m, const char *ch)
{
 int i;

 for (i=WELLS-1;i>=0;i--) putchar(ch[(m>>i)&1]);
}

static void print_mask_4(MASKTYPE m1, MASKTYPE m2, const char *ch)
{
 int i;

 for (i=WELLS-1;i>=0;i--) putchar(ch[((m1>>i)&1)|(((m2>>i)&1)<<1)]);
}

static void print_possibilities(REPRMASK p)
{
 int i;

 for (i=NREPR-1;i>=0;i--)
  { if ((p >> i) & 1)
     { putchar(' ');
       print_mask_2(reprv[i],"-*");
     }
  }
}

/*
 * Even though ->possible has an integer type, we can't do the usual
 *  trick of returning a->field - b->field, because ->possible may be
 *  wider than int and hence coercing it to int may change the signum.
 */
static int nodefor_cmp(void *av, void *bv)
{
 if (((NODE *)av)->possible < ((NODE *)bv)->possible)
  { return(-1);
  }
 else if (((NODE *)av)->possible > ((NODE *)bv)->possible)
  { return(1);
  }
 return(0);
}

static AVLOPS nodefor_avlops = { .flags = AVL_F_NODUPS, .compare = &nodefor_cmp };

static void init(void)
{
 nodefor = avl_new(&nodefor_avlops);
 pend = 0;
 pendtail = &pend;
 nlfree = 0;
 allnodes = 0;
 rootnode = newnode();
 rootnode->possible = (NPOSSV - 1) ^ (POSSBIT(repr_inx[0]) | POSSBIT(repr_inx[(1U<<WELLS)-1]));
 avl_insert(nodefor,rootnode);
 append_pend(rootnode);
}

static NODE *find_node_for(REPRMASK m)
{
 NODE n;

 n.possible = m;
 return(avl_find(nodefor,&n));
}

static int step(void)
{
 NODE *n;
 int mx;
 MASKTYPE m;
 MASKTYPE p;
 int ox;
 int tx;
 MASKTYPE o;
 int i;
 REPRMASK np;
 NODE *nn;
 ACTM *actm;
 ACTMO *actmo;
 ACTION *a;
 MASKTYPE togg;
 MASKTYPE tp;

 n = get_pend();
 if (! n)
  { if (verbose > 0) printf("Nothing more to search\n");
    return(0);
  }
 if (verbose > 0)
  { printf("node %p: possible",(void *)n);
    print_possibilities(n->possible);
    printf("\n");
  }
 for (mx=NMASK-1;mx>=0;mx--)
  { m = maskv[mx];
    if (verbose > 1)
     { printf("  mask [%d] = ",mx);
       print_mask_2(m,"-X");
       printf("\n");
     }
    nobs = 0;
    p = (1U << WELLS) - 1;
    while (1)
     { do <"cont">
	{ if (! (n->possible & POSSBIT(repr_inx[p]))) break <"cont">;
	  o = m & p;
	  do <"recorded">
	   { for (i=nobs-1;i>=0;i--) if (obs[i] == o) break <"recorded">;
	     if (nobs >= MAXOBS) abort();
	     obs[nobs++] = o;
	   } while (0);
	  if (verbose > 1)
	   { printf("    possible ");
	     print_mask_2(p,"-*");
	     printf(" observed ");
	     print_mask_4(p,m,"..-*");
	     printf("\n");
	   }
	} while (0);
       if (p == 0) break;
       p --;
     }
    if (verbose > 1) printf("    observed count %d\n",nobs);
    actm = &n->arms[mx];
    actm->nobs = nobs;
    actm->obsv = malloc(nobs*sizeof(ACTMO));
    for (ox=nobs-1;ox>=0;ox--)
     { o = obs[ox];
       actmo = &actm->obsv[ox];
       actmo->obs = o;
       for (tx=NFLIP-1;tx>=0;tx--)
	{ togg = toggles[mx][tx];
	  a = &actmo->acts[tx];
	  np = 0;
	  p = (1U << WELLS) - 1;
	  while (1)
	   { do <"cont">
	      { if (o != (m & p)) break <"cont">;
		if (! (n->possible & POSSBIT(repr_inx[p]))) break <"cont">;
		tp = p ^ toggles[mx][tx];
		if ((tp == EMPTYMASK) || (tp == FULLMASK)) break <"cont">;
		np |= POSSBIT(repr_inx[tp]);
	      } while (0);
	     if (p == 0) break;
	     p --;
	   }
	  if (verbose > 1)
	   { printf("    observed ");
	     print_mask_4(o,m,"..-*");
	     printf(" toggle ");
	     print_mask_2(togg,"-*");
	     printf(" new:");
	     print_possibilities(np);
	     printf("\n");
	   }
	  nn = find_node_for(np);
	  if (! nn)
	   { nn = newnode();
	     if (verbose > 1) printf("    ** new set, node %p\n",(void *)nn);
	     nn->mx = mx;
	     nn->ox = ox;
	     nn->fx = tx;
	     nn->possible = np;
	     avl_insert(nodefor,nn);
	     append_pend(nn);
	   }
	  a->to = nn;
	}
     }
  }
 return(1);
}

static void algsearch(void)
{
 NODE *n;
 int any;
 int mx;
 int ox;
 int fx;
 ACTM *actm;
 ACTMO *actmo;
 int d;
 int obestdist;
 int obestflip;
 int mbestdist;
 int mbestobs;
 int mbestflip;
 int nbestmask;
 int nbestdist;
 int nbestobs;
 int nbestflip;
 int printed;

 do
  { any = 0;
    for (n=allnodes;n;n=n->link)
     { if (n->fdist >= 0) continue;
       if (n->possible == 0)
	{ if (verbose > 0) printf("Examining %p: grounding case\n",(void *)n);
	  n->fmask = 0;
	  n->fdist = 0;
	  any = 1;
	  continue;
	}
       if (verbose > 3)
	{ printf("Examining %p:",(void *)n);
	  print_possibilities(n->possible);
	  printf("\n");
	  printed = 1;
	}
       else
	{ printed = 0;
	}
       nbestmask = -1;
       for <"mask"> (mx=NMASK-1;mx>=0;mx--)
	{ actm = &n->arms[mx];
	  mbestobs = -1;
	  for (ox=actm->nobs-1;ox>=0;ox--)
	   { actmo = &actm->obsv[ox];
	     obestflip = -1;
	     for (fx=NFLIP-1;fx>=0;fx--)
	      { d = actmo->acts[fx].to->fdist;
		if (verbose > 3)
		 { printf("  mask ");
		   print_mask_2(maskv[mx],"-X");
		   printf(" obs ");
		   print_mask_4(actmo->obs,maskv[mx],".?-*");
		   printf(" flip ");
		   print_mask_4(toggles[mx][fx],maskv[mx],".?-*");
		   printf(" dist %d\n",d);
		 }
		if (d >= 0)
		 { if (verbose == 3)
		    { if (! printed)
		       { printf("Examining %p:",(void *)n);
			 print_possibilities(n->possible);
			 printf("\n");
			 printed = 1;
		       }
		      printf("  mask ");
		      print_mask_2(maskv[mx],"-X");
		      printf(" obs ");
		      print_mask_4(actmo->obs,maskv[mx],".?-*");
		      printf(" flip ");
		      print_mask_4(toggles[mx][fx],maskv[mx],".?-*");
		      printf(" dist %d\n",d);
		    }
		   if ( (obestflip < 0) ||
			(d < obestdist) ||
			((d == obestdist) && (pops[toggles[mx][fx]] < pops[toggles[mx][obestflip]])) )
		    { obestflip = fx;
		      obestdist = d;
		      if (verbose > 3) printf("  set obest: flip %d, dist %d\n",obestflip,obestdist);
		    }
		 }
	      }
	     if (obestflip < 0)
	      { if (printed)
		 { printf("  obs ");
		   print_mask_4(actmo->obs,maskv[mx],".?-*");
		   printf(" not forcable\n");
		 }
		continue <"mask">;
	      }
	     actmo->fflip = obestflip;
	     if ((mbestobs < 0) || (obestdist > mbestdist))
	      { mbestobs = ox;
		mbestflip = obestflip;
		mbestdist = obestdist;
		if (verbose > 3) printf("  set mbest: obs %d, flip %d, dist %d\n",mbestobs,mbestflip,mbestdist);
	      }
	   }
	  if (mbestobs >= 0)
	   { if ((nbestmask < 0) || (mbestdist < nbestdist))
	      { nbestmask = mx;
		nbestdist = mbestdist;
		nbestobs = mbestobs;
		nbestflip = mbestflip;
		if (verbose > 3) printf("  set nbest: mask %d, obs %d, flip %d, dist %d\n",nbestmask,nbestobs,nbestflip,nbestdist);
	      }
	   }
	}
       if (nbestmask >= 0)
	{ n->fmask = nbestmask;
	  n->fdist = nbestdist + 1;
	  if (verbose > 0)
	   { printf("Setting forcable on %p:",(void *)n);
	     print_possibilities(n->possible);
	     printf(" mask ");
	     print_mask_2(maskv[nbestmask],"-X");
	     printf(" depth %d\n",n->fdist);
	   }
	  any = 1;
	}
     }
  } while (any);
}

static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { fprintf(stderr,"%s: extra argument `%s'\n",__progname,*av);
       errs = 1;
       continue;
     }
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs = 1;
       continue;
     }
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-v"))
     { verbose ++;
       continue;
     }
    if (!strcmp(*av,"-V"))
     { WANTARG();
       verbose = atoi(av[skip]);
       continue;
     }
#undef WANTARG
    fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
    errs = 1;
  }
 if (errs) exit(1);
}

static void print_indent(int i)
{
 while (i >= 4)
  { printf("|   ");
    i -= 4;
  }
 if (i) printf("%-*s",i,"|");
}

static void dump_alg(NODE *n, int indent)
{
 int i;
 MASKTYPE m;
 ACTM *actm;
 ACTMO *actmo;

 if (n->possible == 0) return;
 print_indent(indent);
 printf("%p: mask ",(void *)n);
 m = maskv[n->fmask];
 print_mask_2(m,"-X");
 printf(" on");
 print_possibilities(n->possible);
 if (n->printed)
  { printf("   see above\n");
    return;
  }
 printf("\n");
 n->printed = 1;
 actm = &n->arms[n->fmask];
 for (i=actm->nobs-1;i>=0;i--)
  { actmo = &actm->obsv[i];
    print_indent(indent+2);
    printf("obs ");
    print_mask_4(actmo->obs,m,"..-*");
    printf(" invert ");
    print_mask_4(toggles[n->fmask][actmo->fflip],m,"..-X");
    printf("\n");
    dump_alg(actmo->acts[actmo->fflip].to,indent+4);
  }
}

int main(int, char **);
int main(int ac, char **av)
{
 handleargs(ac,av);
 init();
 while (step()) ;
 algsearch();
 if (rootnode->fdist < 0)
  { printf("No algorithm found\n");
  }
 else
  { printf("Algorithm found\n");
    dump_alg(rootnode,0);
  }
 return(0);
}