/*
 * Do Monte Carlo simulation of the slot machines at Pickham and
 *  Baccarat, assuming the machines are honest (ie, each spin chooses a
 *  position for each wheel unformly and uncorrelated with the other
 *  wheels).
 *
 * Some things are fixed:
 *
 * - There are three wheels.
 *
 * - Each wheel has three visible symbols.
 *
 * - There are five payoff lines.  If the wheel symbols are
 *
 *		| A |  | B |  | C |
 *		|   |  |   |  |   |
 *		| D |  | E |  | F |
 *		|   |  |   |  |   |
 *		| G |  | H |  | I |
 *
 *    then the payoff lines are:
 *
 *	1 - D E F
 *	2 - A B C
 *	3 - G H I
 *	4 - A E I
 *	5 - G E C
 *
 * The machine description is read from stdin on startup.  It consists
 *  of lines.  Each line is broken into whitespace-separated fields.
 *  If the line has no non-whitespace characters, or if the first
 *  non-whitespace character is a # or ;, the line is a comment and is
 *  ignored.  Otherwise, the first field is a keyword specifying what
 *  kind of line it is.  Lines can appear in any order; the keywords
 *  and the semantics of the rest of their lines are:
 *
 *	syms
 *		List of the possible symbols, whitespace-separated.
 *		Must occur exactly once.
 *
 *	wheel1
 *	wheel2
 *	wheel3
 *		Three lines, one describing each wheel.  Each one must
 *		occur exactly once.  The contents simply list that
 *		wheel's symbols, in order top to bottom (ie, A-D-G or
 *		B-E-H or C-F-I order); the list is assumed to wrap
 *		around from the last item to the first.  The number of
 *		symbols on the wheel is the number of symbols on this
 *		line.  It is an error if a symbol occurs here that's
 *		not present on the syms line.
 *
 *	win
 *		Describes one of the possible winning combinations.
 *		The first field here must be a number, which is the
 *		multiplier for this combination.  After that must be
 *		exactly three symbols, except that any subset of the
 *		symbols may be *, which are wildcards.  A win line
 *		matches when the listed symbols are present, except
 *		that for wildcards any symbol may be present.  If a
 *		given line of symbols matches more than one win line,
 *		the one (or one of the ones, if multiple) with the
 *		highest value is used.  It is an error if a
 *		(non-wildcard) symbol occurs here that's not present on
 *		the syms line.
 *
 *		At least one win line must be present; multiple may be,
 *		with no specific limit on how many.
 *
 * It is an error if the machine description does not end with a
 *  newline.
 *
 * Output consists of one line every 1<<20 spins, giving the number of
 *  spins and the measured expected profit (or, if negative, loss) for
 *  each of the five ways of playing.  (The first number corresponds to
 *  a single stake, with a single possible winning combination; the
 *  second, two; etc, up to the fifth being for betting on all five
 *  winning combinations.)  Thus, for example, if the machine is fair
 *  (its expected payout equals the stake), all five numbers will stay
 *  within statistical noise of zero.  As of this writing, every
 *  machine from the game I've tested has shown positive expectation -
 *  all the numbers are positive - meaning you can expect to make
 *  "money" playing them (in sharp contrast to real-world slot
 *  machines).
 */

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>
#include <sys/time.h>
#include <sys/stat.h>

extern const char *__progname;

typedef struct wheel WHEEL;
typedef struct winline WINLINE;

struct wheel {
  int size;
  int *syms;
  } ;

struct winline {
  WINLINE *link;
  int mult;
  int syms[3]; // -1 means wildcard
  } ;

static int nsyms;
static char **symnames;
static int *symnamelens;
static int maxsymnamelen;
static WHEEL wheels[3];
static WINLINE *winlines;
static unsigned int rpool[64];
static unsigned int rr;
static unsigned int rf;
static const int indices[5][3]
 = { { 3, 4, 5 },
     { 0, 1, 2 },
     { 6, 7, 8 },
     { 0, 4, 8 },
     { 6, 4, 2 } };
static int games;
static int sum[5];

#define Cisspace(x) isspace((unsigned char)(x))

static char *read_line(void)
{
 static char *b = 0;
 static int a = 0;
 int l;
 int c;

 void addc(unsigned char ch)
  { if (l >= a) b = realloc(b,a=l+8);
    b[l++] = ch;
  }

 l = 0;
 while (1)
  { c = getchar();
    if (c == EOF)
     { if (l > 0)
	{ fprintf(stderr,"%s: machine description ends with partial line\n",__progname);
	  exit(1);
	}
       return(0);
     }
    if (c == '\n')
     { addc('\0');
       return(b);
     }
    addc(c);
  }
}

static const char *skipwhite(const char *s)
{
 while (*s && Cisspace(*s)) s ++;
 return(s);
}

static const char *skipnonwhite(const char *s)
{
 while (*s && !Cisspace(*s)) s ++;
 return(s);
}

static void break_tokens(const char *line, void (*fn)(const char *, int))
{
 const char *t0;
 const char *t1;

 t1 = line;
 while (1)
  { t0 = skipwhite(t1);
    if (! *t0) break;
    t1 = skipnonwhite(t0);
    (*fn)(t0,t1-t0);
  }
}

static void win_set_mult(WINLINE *w, const char *s, int l)
{
 static char *b = 0;
 static int bl = 0;
 long int li;
 int i;
 char *ep;

 if (l+1 > bl)
  { free(b);
    bl = l + 1;
    b = malloc(bl);
  }
 bcopy(s,b,l);
 b[l] = '\0';
 li = strtol(b,&ep,0);
 if (ep == b)
  { fprintf(stderr,"%s: invalid multiplier on `win' line\n",__progname);
    exit(1);
  }
 if (*ep)
  { fprintf(stderr,"%s: trailing junk in multiplier on `win' line\n",__progname);
    exit(1);
  }
 if (li < 1)
  { fprintf(stderr,"%s: negative multiplier on `win' line\n",__progname);
    exit(1);
  }
 i = li;
 if (i != li)
  { fprintf(stderr,"%s: multiplier too large on `win' line\n",__progname);
    exit(1);
  }
 w->mult = i;
}

static int lookup_sym(const char *s, int l)
{
 int i;

 for (i=nsyms-1;i>=0;i--) if ((symnamelens[i] == l) && !bcmp(s,symnames[i],l)) return(i);
 return(-1);
}

static void win_set_sym(WINLINE *w, int sx, const char *s, int l)
{
 int i;

 if ((l == 1)  && (*s == '*'))
  { w->syms[sx] = -1;
    return;
  }
 i = lookup_sym(s,l);
 if (i < 0)
  { fprintf(stderr,"%s: invalid symbol on `win' line\n",__progname);
    exit(1);
  }
 w->syms[sx] = i;
}

static void add_win(const char *line)
{
 WINLINE *w;
 int nt;

 w = malloc(sizeof(WINLINE));
 nt = 0;
 break_tokens(line,({ void foo(const char *k, int l)
		       { switch (nt)
			  { case 0:
			       win_set_mult(w,k,l);
			       break;
			    case 1: case 2: case 3:
			       win_set_sym(w,nt-1,k,l);
			       break;
			    default:
			       fprintf(stderr,"%s: `win' line has too many fields\n",__progname);
			       exit(1);
			       break;
			  }
			 nt ++;
		       }
		      &foo;
		    }));
 if (nt != 4)
  { fprintf(stderr,"%s: `win' line has too few fields\n",__progname);
    exit(1);
  }
 w->link = winlines;
 winlines = w;
}

static void sort_wins(void)
{
 WINLINE *sort(WINLINE *list)
  { WINLINE *a;
    WINLINE *b;
    WINLINE *t;
    WINLINE **lp;
    if (!list || !list->link) return(list);
    a = 0;
    b = 0;
    while (list)
     { t = list;
       list = t->link;
       t->link = a;
       a = b;
       b = t;
     }
    a = sort(a);
    b = sort(b);
    lp = &list;
    while (a || b)
     { if (a && (!b || (a->mult > b->mult)))
	{ t = a;
	  a = a->link;
	}
       else
	{ t = b;
	  b = b->link;
	}
       *lp = t;
       lp = &t->link;
     }
    *lp = 0;
    return(list);
  }

 winlines = sort(winlines);
}

static void gen_wheel(int wx, const char *line)
{
 WHEEL *w;

 w = &wheels[wx];
 w->size = 0;
 w->syms = 0;
 break_tokens(line,({ void foo(const char *k, int l)
		       { int i;
			 i = lookup_sym(k,l);
			 if (i < 0)
			  { fprintf(stderr,"%s: invalid symbol on `wheel%d' line\n",__progname,wx+1);
			    exit(1);
			  }
			 w->syms = realloc(w->syms,(w->size+1)*sizeof(*w->syms));
			 w->syms[w->size++] = i;
		       }
		      &foo;
		    }));
}

static void read_machine(void)
{
 char *l;
 char *symline;
 char *wheelline[3];
 int nwins;
 char **wins;
 const char *p;
 const char *k0;
 const char *k1;

 symline = 0;
 wheelline[0] = 0;
 wheelline[1] = 0;
 wheelline[2] = 0;
 nwins = 0;
 wins = 0;
 while (1)
  { l = read_line();
    if (! l) break;
    k0 = skipwhite(l);
    switch (*k0)
     { case '\0':
       case '#':
       case ';':
	  continue;
	  break;
     }
    k1 = skipnonwhite(k0);
    p = skipwhite(k1);
    switch (k1-k0)
     { case 3:
	  if (! bcmp(k0,"win",3))
	   { wins = realloc(wins,(nwins+1)*sizeof(*wins));
	     wins[nwins++] = strdup(p);
	     break;
	   }
	  if (0)
	   {
       case 4:
	     if (! bcmp(k0,"syms",4))
	      { if (symline)
		 { fprintf(stderr,"%s: multiple `syms' lines\n",__progname);
		   exit(1);
		 }
		symline = strdup(p);
		break;
	      }
	   }
	  if (0)
	   { int wx;
       case 6:
	     if (! bcmp(k0,"wheel1",6))
	      { wx = 0;
	      }
	     else if (! bcmp(k0,"wheel2",6))
	      { wx = 1;
	      }
	     else if (! bcmp(k0,"wheel3",6))
	      { wx = 2;
	      }
	     else
	      { wx = -1;
	      }
	     if (wx >= 0)
	      { if (wheelline[wx])
		 { fprintf(stderr,"%s: multiple `%.*s' lines\n",__progname,(int)(k1-k0),k0);
		   exit(1);
		 }
		wheelline[wx] = strdup(p);
		break;
	      }
	   }
       default:
	  fprintf(stderr,"%s: unrecognized machine keyword `%.*s'\n",__progname,(int)(k1-k0),k0);
	  exit(1);
	  break;
     }
  }
 if (! symline)
  { fprintf(stderr,"%s: no `syms' line\n",__progname);
    exit(1);
  }
 if (! wheelline[0])
  { fprintf(stderr,"%s: no `wheel1' line\n",__progname);
    exit(1);
  }
 if (! wheelline[1])
  { fprintf(stderr,"%s: no `wheel2' line\n",__progname);
    exit(1);
  }
 if (! wheelline[2])
  { fprintf(stderr,"%s: no `wheel3' line\n",__progname);
    exit(1);
  }
 if (nwins < 1)
  { fprintf(stderr,"%s: no `win' lines\n",__progname);
    exit(1);
  }
 nsyms = 0;
 symnames = 0;
 symnamelens = 0;
 maxsymnamelen = 0;
 break_tokens(symline,({ void foo(const char *k, int l)
			  { int i;
			    i = lookup_sym(k,l);
			    if (i >= 0)
			     { fprintf(stderr,"%s: duplicate symbol `%s' on `syms' line\n",__progname,symnames[i]);
			       exit(1);
			     }
			    symnamelens = realloc(symnamelens,(nsyms+1)*sizeof(symnamelens));
			    symnames = realloc(symnames,(nsyms+1)*sizeof(symnames));
			    symnamelens[nsyms] = l;
			    if (l > maxsymnamelen) maxsymnamelen = l;
			    symnames[nsyms] = malloc(l+1);
			    bcopy(k,symnames[nsyms],l);
			    symnames[nsyms][l] = '\0';
			    nsyms ++;
			  }
			 &foo;
		       }));
 free(symline);
 gen_wheel(0,wheelline[0]);
 free(wheelline[0]);
 gen_wheel(1,wheelline[1]);
 free(wheelline[1]);
 gen_wheel(2,wheelline[2]);
 free(wheelline[2]);
 while (nwins > 0)
  { nwins --;
    add_win(wins[nwins]);
    free(wins[nwins]);
  }
 free(wins);
 sort_wins();
}

static void clear_stats(void)
{
 games = 0;
 sum[0] = 0;
 sum[1] = 0;
 sum[2] = 0;
 sum[3] = 0;
 sum[4] = 0;
}

static unsigned int rnd(void)
{
 unsigned int v;

 v = rpool[rf] += rpool[rr];
 rf = (rf + 1) & 63;
 rr = (rr + 1) & 63;
 return(v>>1);
}

static void init_rand(void)
{
 struct timeval tv;
 struct stat stb;
 int i;

 rpool[0] = getpid();
 rpool[1] = getppid();
 gettimeofday(&tv,0);
 rpool[2] = tv.tv_sec;
 rpool[3] = tv.tv_usec;
 rpool[4] = 1;
 stat("/",&stb);
 rpool[5] = stb.st_atimespec.tv_sec;
 rpool[6] = stb.st_atimespec.tv_nsec;
 rpool[7] = stb.st_mtimespec.tv_sec;
 rpool[8] = stb.st_mtimespec.tv_nsec;
 rpool[9] = stb.st_ctimespec.tv_sec;
 rpool[10] = stb.st_ctimespec.tv_nsec;
 stat("/tmp",&stb);
 rpool[11] = stb.st_atimespec.tv_sec;
 rpool[12] = stb.st_atimespec.tv_nsec;
 rpool[13] = stb.st_mtimespec.tv_sec;
 rpool[14] = stb.st_mtimespec.tv_nsec;
 rpool[15] = stb.st_ctimespec.tv_sec;
 rpool[16] = stb.st_ctimespec.tv_nsec;
 rr = 0;
 rf = 1;
 for (i=65536;i>0;i--) rnd();
}

static void run_one(void)
{
 int wp[3];
 int i;
 int j;
 int k;
 int ws[9];
 WINLINE *wl;

 games ++;
 for (i=3-1;i>=0;i--) wp[i] = rnd() % wheels[i].size;
 for (j=0;j<9;j+=3)
  { for (i=3-1;i>=0;i--)
     { ws[j+i] = wheels[i].syms[wp[i]];
       if (++wp[i] >= wheels[i].size) wp[i] = 0;
     }
  }
/*
 printf("---\n%*s %*s %*s\n%*s %*s %*s\n%*s %*s %*s\n",
	maxsymnamelen, symnames[ws[0]],
	maxsymnamelen, symnames[ws[1]],
	maxsymnamelen, symnames[ws[2]],
	maxsymnamelen, symnames[ws[3]],
	maxsymnamelen, symnames[ws[4]],
	maxsymnamelen, symnames[ws[5]],
	maxsymnamelen, symnames[ws[6]],
	maxsymnamelen, symnames[ws[7]],
	maxsymnamelen, symnames[ws[8]]);
*/
 for (j=0;j<5;j++) sum[j] -= j + 1;
 for (j=0;j<5;j++)
  { for (wl=winlines;wl;wl=wl->link)
     { if ( ((wl->syms[0] == ws[indices[j][0]]) || (wl->syms[0] < 0)) &&
	    ((wl->syms[1] == ws[indices[j][1]]) || (wl->syms[1] < 0)) &&
	    ((wl->syms[2] == ws[indices[j][2]]) || (wl->syms[2] < 0)) )
	{ // printf("line %d wins %d\n",j+1,wl->mult);
	  for (k=j;k<5;k++) sum[k] += wl->mult;
	  break;
	}
     }
  }
 if (! (games & 1048575)) printf("%d %g %g %g %g %g\n",
	games,
	sum[0]/(games*1.0),
	sum[1]/(games*2.0),
	sum[2]/(games*3.0),
	sum[3]/(games*4.0),
	sum[4]/(games*5.0));
}

int main(void);
int main(void)
{
 read_machine();
 clear_stats();
 init_rand();
 while (1) run_one();
}