Article 13269 of alt.sources:
Path: nntpd.lkg.dec.com!pa.dec.com!news1.digital.com!decwrl!hookup!news.mathworks.com!tank.news.pipex.net!pipex!dispatch.news.demon.net!demon!news.u-net.com!news
From: a.hunger@hulmecc.nwnet.co.uk
Newsgroups: alt.sources
Subject: mmd - SOURCE mmd.cc 4/4
Date: Wed, 20 Mar 1996 21:06:29 GMT
Organization: Hulme Community Computing Ltd.
Lines: 2224
Message-ID: <4ipsda$rpp@nuntius.u-net.net>
Reply-To: a.hunger@hulmecc.nwnet.co.uk
NNTP-Posting-Host: hulmecc.u-net.com
X-Newsreader: Forte Free Agent 1.0.82

/* mmd.cc */

// mastermind program

#undef NDEBUG
#define NDEBUG

#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
// include stream.h if -DSTREAM on compile line, otherwise
// include iostream.h
#ifdef STREAM
#include <stream.h>
#else
#include <iostream.h>
#endif

static const char *copyright = "Copyright (c) A. Hunger 1996.";

static const char *version = "mmd V1.0.";

static const char *improper_switches =
   "Usage: [-depth <num>] [-gametree] [-human] [-noright] [-noscramble]\n"
   "[-pattern <pattern>] [-pipe] [-radix <num>] [-seed <num>] [-size
<num>]\n"
   "[-test] [-verbose].";

static const unsigned long default_radix = 6;
static const unsigned long default_size = 4;
static const unsigned long default_depth = 0;
static const unsigned long max_size = 10;
static const unsigned long max_depth = 9;
static const double eps = 1.e-6;

// error messages

static const char *bad_pattern = "Pattern not well formed.";
static const char *out_of_memory = "Out of memory.";
static const char *bad_variant = "Cannot solve - zero mutual information.";
static const char *unexpected_eof = "Unexpected EOF.";
static const char *io_error = "I/O error.";
static const char *no_info = "Impossible to solve.";
static const char *improper_usage = "Improper usage of class method.";
static const char *filename_too_long = "Filename too long.";
static const char *too_large = "Radix or size too large.";
static const char *cant_create = "Can't create data file.";
static const char *file_corrupted = "Data file corrupted.";
static const char *error_closing = "Error closing data file.";
static const char *file_read_only = "Can't modify data file - read only.";
static const char *cant_seek = "Error in data file random access.";
static const char *cant_open = "Can't open data file.";
static const char *error_reading = "Error reading data file.";
static const char *error_writing = "Error writing to data file.";
static const char *error_flushing = "Error updating data file.";
static const char *bad_score = "Score not well formed.";
static const char *pat_err = "Error reading pattern.";
static const char *char_err = "Error reading character.";
static const char *group_overflow = "Radix or size too big.";
static const char *pat_overflow = "Radix or size too big.";
static const char *sizet_err = "Error determining SIZE_T_MAX.";
static const char *ran_err = "Internal consistency error calling
uniform().";
static const char *long_too_big = "Data file too large.";

typedef int boolean;

#define false (0)
#define true (1)

boolean noright = false,verbose = false;

// err macro - similar to assert but cannot be removed,
// so expressions with side-effects are allowed
// usage:
// err(c,string);
// checks if c is true, otherwise it sends error message string
// to stderr and exits with status 1

#define err(c,s)  ((c) ? 0 : ___err(#c,s,__FILE__,__LINE__))

static int ___err(const char *cond,const char *err,
                  const char *file,unsigned long line) {
  if (verbose)
    cerr << "Fatal error: failed assertion (" << cond << ")\nin file \""
         << file << "\" at line " << line << ".\nProgrammer comment: "
         << err << "\n";
  else
    cerr << err << "\n";
  ::exit(1);
  return 0; // avoid warning from compiler
}

typedef char *p_type;

#define P_BUFSIZE (1024)

static const char nums[] = "0123456789";

static unsigned max_radix() {
  return ::strlen(nums);
  }

static int find(const char *s,char c) {
  const char *p = s;
  for(;;p++) {
    if (*p == '\000')
      return - 1;
    if (*p == c)
      return p - s;
  }
}

static void disp_pat(p_type p,unsigned rad,unsigned len) {
  char buf[2];
  buf[1] = '\000';
  for(unsigned i = 0;i != len;i++) {
    assert(0 <= p[i] && p[i] < rad);
    *buf = nums[p[i]];
    cout << buf;
    }
  }

// converts string buf to pattern p, returning true iff s valid pattern
static boolean s_to_p(char *buf,p_type p,unsigned rad,unsigned len) {
  assert(rad <= max_radix());
  for(unsigned i = 0;i != len;i++) {
    int pp;
    pp = find(nums,buf[i]);
    if (pp == - 1 || pp >= rad)
      return false;
    p[i] = (char) pp;
    }
  return (boolean) (buf[i] == '\0');
  }

static void get_pat(p_type p,unsigned rad,unsigned len) {
  char buf[P_BUFSIZE];
  assert(rad <= max_radix());
  err(! cin.eof(),unexpected_eof);
  cin >> buf;
  err(! cin.eof(),unexpected_eof);
  err(cin.good(),pat_err);
  err(s_to_p(buf,p,rad,len),bad_pattern);
  }

static boolean equal(p_type p1,p_type p2,unsigned len) {
  char *p_e = p1 + len;
  while(p1 != p_e)
    if (*p1++ != *p2++)
      return false;
  return true;
}

static unsigned long sizetmax() {
  size_t x = 1;
  while (x > 0)
    x <<= 1;
  x--;
  err(x > 0,sizet_err);
  return (unsigned long) x;
}

#define A 16807
#define M 2147483647
#define Q 127773      /* M div A */
#define R 2836        /* M mod A */
#define MAX_RAN (A - 1)

static long seed;

static boolean inited = false;

static void randomize();

/* this random number generator from Comm. ACM */
static unsigned long ran()
{
  long lo,hi,test;
  if (inited == false) {
    inited = true;
    randomize();
  }
  hi = seed / Q;
  lo = seed - Q * hi;
  test = (A * lo) - (R * hi);
  if (test > 0)
    seed = test;
  else
    seed = test + M;
  return (unsigned long) seed - 1;
}

static void seed_set(unsigned long s)
{
  unsigned i;
  seed = s % MAX_RAN + 1;
  for(i = 10;i != 0;i--)
    (void) ran();
}

/* this routine is necessary in order to accomodate 64 bit machines */
static unsigned long uniform(unsigned long i)
{
unsigned long l,j,k;
/* recursive routine to generate uniformly distributed random */
/* integers */
  if (i <= MAX_RAN) {
    err(i >= 1,ran_err);
    l = MAX_RAN / i;
    j = l * i;
    do {
      k = ran();
    } while (k >= j);
    return k % i; /* or k / l */
  } else {
    j = i / MAX_RAN;
    do {
      k = uniform(j) * MAX_RAN + ran();
    } while (k >= i);
    return k;
  }
}

static void randomize() {
  seed_set(time(NULL));
}

class p_node {

p_type pat;
p_node **pre;
p_node *post;

friend class p_list;

public:

p_type pattern() { return pat; }

};

class p_list {

p_node *l;
p_type pats;
p_node *h;
unsigned long ls,as,ps;
unsigned long *ref_count;

void init(p_list &pl);

void del();

public:

p_list(unsigned long num,unsigned long pat_size);

p_list(p_list &pl) { init(pl); }

p_list &operator=(p_list &pl);

~p_list() { del(); }

p_node *head() { return h; }

p_node *iterator(p_node *p) { return p->post; }

p_type operator[](unsigned long i) { return (pats + i * ps); }

void remove(p_node *p);

unsigned long psize() { return ps; }

unsigned long lsize() { return ls; }

unsigned long asize() { return as; }

};

void p_list::init(p_list &pl) {
  ps = pl.ps;
  ls = pl.ls;
  as = pl.as;
  pats = pl.pats;
  ref_count = pl.ref_count;
  (*ref_count)++;
  err((l = new p_node[ls]) != NULL,out_of_memory);
  h = l;
  p_node **pp = &h;
  p_node *p = pl.head();
  p_node *ppp = h;
  while(p != NULL) {
    ppp->pat = p->pat;
    ppp->pre = pp;
    ppp->post = ppp + 1;
    pp = &(ppp->post);
    ppp++;
    p = pl.iterator(p);
  }
  ppp--;
  ppp->post = NULL;
}

void p_list::del() {
  delete[] l;
  assert(*ref_count != 0);
  (*ref_count)--;
  if (*ref_count == 0) {
    delete ref_count;
    delete[] pats;
  }
}

p_list &p_list::operator=(p_list &pl) {
  if (this != &pl) {
    del();
    init(pl);
  }
  return *this;
}

void p_list::remove(p_node *p) {
  ls--; if ((*(p->pre) = p->post) != NULL) p->post->pre = p->pre;
}

p_list::p_list(unsigned long num,unsigned long pat_size) {
  ps = pat_size;
  ls = as = num;
  err((ref_count = new unsigned long) != NULL,out_of_memory);
  *ref_count = 1;
  double stm = (double) sizetmax();
  err((double) ps * (double) ls <= stm &&
      (double) sizeof(p_node) * (double) ls <= stm,pat_overflow);
  err((pats = new char[ps * ls]) != NULL,out_of_memory);
  err((l = new p_node[ls]) != NULL,out_of_memory);
  h = l;
  unsigned long i;
  p_node **pp = &h;
  p_type p = pats;
  p_node *ppp = h;
  for(i = 0;i != ls;i++) {
    ppp->pat = p;
    ppp->pre = pp;
    ppp->post = ppp + 1;
    p += ps;
    pp = &(ppp->post);
    ppp++;
  }
  ppp--;
  ppp->post = NULL;
}

struct table_node {
  double l;
  boolean def;
};

class log_table {

double miss(table_node *t,unsigned long n);

double enlarge(unsigned long n);

public:

log_table();

~log_table();

log_table(log_table &lg);

log_table &operator=(log_table &lg);

double log(unsigned long n);

};

static const unsigned size_step = 512;

static unsigned long ins_count = 0;

static table_node *tab = NULL;
static unsigned long max = 0;

static unsigned long hits = 0,misses = 0;

log_table::log_table() {
  if (! ins_count) {
    max = 0;
    tab = NULL;
    hits = misses = 0;
  }
  ins_count++;
}

log_table::log_table(log_table &dummy) {
  ins_count++;
}

log_table &log_table::operator=(log_table &dummy) {
  return *this;
}


inline double log_table::miss(table_node *t,unsigned long n) {
  t->def = true;
  return (t->l = ::log((double) n));
}

double log_table::enlarge(unsigned long n) {
  unsigned long m2 = ((n + size_step - 1) / size_step) * size_step;
  assert(m2 >= n);
  table_node *p;
  err((p = new table_node [m2]) != NULL,out_of_memory);
  if (max != 0UL)
    ::memcpy(p,tab,(size_t) (max * sizeof(table_node)));
  table_node *pp = &p[max];
  table_node *pq = &p[m2];
  while (pp != pq)
    (pp++)->def = false;
  if (tab != NULL)
    delete[] tab;
  tab = p;
  max = m2;
  return miss(&p[n],n);
}

log_table::~log_table() {
  assert(ins_count != 0UL);
  ins_count--;
  if (ins_count == 0UL) {
    if (tab != NULL)
      delete[] tab;
    if (verbose)
      cout << "\nLog table statistics:\nSize = " << max
           << "\nHits = " << hits << "\nMisses = " << misses << "\n";
  }
}

double log_table::log(unsigned long n) {
  assert(n != 0);
  if (n >= max) {
    misses++;
    return enlarge(n);
    }
  else {
    table_node *t = &tab[n];
    if (t->def) {
      hits++;
      return t->l;
      }
   else {
    misses++;
    return miss(t,n);
    }
  }
}

struct score_type {
  unsigned right,wrong;
};

static ostream& operator<<(ostream &s, score_type &sc) {
  if (noright)
    return s << sc.wrong;
  else
    return s << sc.right << " " << sc.wrong;
}

static istream& operator>>(istream &s,score_type &sc) {
  if (noright)
    sc.right = 0;
  else {
    err(! s.eof(),unexpected_eof);
    s >> sc.right;
  }
  err(! s.eof(),unexpected_eof);
  err(s.good(),bad_score);
  s >> sc.wrong;
  err(! s.eof(),unexpected_eof);
  err(s.good(),bad_score);
  return s;
}

class score_class {

char *hco;
char *htr;
char *hq;

unsigned radix;

unsigned n;

void cre(unsigned rad,unsigned num);

public:

score_class(unsigned rad,unsigned num) { cre(rad,num); }

score_class(score_class &sc);

score_class &operator=(score_class &sc);

~score_class();

void get_score(p_type co,p_type tr,score_type &sc);

};

void score_class::cre(unsigned rad,unsigned num) {
  n = num;
  radix = rad;
  err((hco = new char[rad + rad]) != NULL,out_of_memory);
  htr = &hco[rad];
  hq = &htr[rad]; // legitimised by ANSI standard
}

score_class::~score_class() {
  delete[] hco;
}

score_class::score_class(score_class &sc) {
  cre(sc.radix,sc.n);
}

score_class &score_class::operator=(score_class &sc) {
  if (this != &sc) {
    if (radix != sc.radix) {
      delete[] hco;
      cre(sc.radix,sc.n);
    }
    n = sc.n;
  }
  return *this;
}

void score_class::get_score(p_type co,p_type tr,score_type &sc) {
//
// this routine is the speed bottleneck
//
// the mastermind scoring system is symmetric - i.e. swapping
// co and tr does not change the score - reflected in the code

// declared practically everything as register, so given plenty of
// hints to the (possibly dumb) compiler about variable lifetimes

// don't bother writing loop-unrolled version,
// a la Duff's Device in Stroustrup - makes no difference

  {
    register char *rhco = hco;
    register char *rhq = hq;
    while (rhco != rhq)
      *rhco++ = 0;
  }
  {
  // shouldn't run out of registers except on poor old 8086
    register unsigned r = 0,rn = n;
    register p_type rco = co;
    register p_type rtr = tr;
    register char *rhco = hco;
    register char *rhtr = htr;
    for(register unsigned i = 0;i != rn;i++) {
      register unsigned tco,ttr;
      if ((tco = rco[i]) == (ttr = rtr[i]))
        r++;
      else {
        rhco[tco]++;
        rhtr[ttr]++;
      }
    }
    sc.right = (noright ? 0 : r);
  }
  {
    register unsigned w = 0;
    register char *rhco = hco;
    register char *rhtr = htr;
    register char *rhe = htr;
    while (rhco != rhe) {
      register char ta,tb;
      if ((ta = *rhco++) < (tb = *rhtr++))
        w += ta;
      else
        w += tb;
    }
    sc.wrong = w;
  }
  assert(sc.right + sc.wrong <= n);
}

class histogram {

unsigned long **h;
unsigned long *p;
unsigned long s,c,ps,psu,sz;
log_table logt;

void cons(unsigned long size);

void dest();

public:

void zero();

histogram(unsigned long size) { cons(size);zero(); }

histogram(histogram &hs);

histogram &operator=(histogram &hs);

~histogram() { dest(); }

void add(score_type score) { (*(h[score.right] + score.wrong))++; c++; }

unsigned operator[](score_type score) {
  return (*(h[score.right] + score.wrong));
}

double entropy();

unsigned long count() { return c; }

};

void histogram::cons(unsigned long size) {
  sz = size;
  s = size + 1;
  ps = (s * (s + 1)) / 2;
  psu = ps * sizeof(unsigned long);
  err((p = new unsigned long [ps]) != NULL,out_of_memory);
  err((h = new unsigned long *[s]) != NULL,out_of_memory);
  unsigned long i = 0;
  unsigned long **hp = h;
  unsigned long *pp = p;
  while (i != s) {
    *hp = pp;
    hp++;
    pp += s - i;
    i++;
  }
  assert(pp == &p[ps]);
}

histogram::histogram(histogram &hs) {
  cons(hs.sz);
  (void) ::memcpy((void *) p,(void *) (hs.p),(size_t) psu);
}

histogram &histogram::operator=(histogram &hs) {
  if (this != &hs) {
    if (sz != hs.sz) {
      dest();
      cons(hs.sz);
    }
    (void) ::memcpy((void *) p,(void *) (hs.p),(size_t) psu);
  }
  return *this;
}

void histogram::dest() {
  delete[] h;
  delete[] p;
}

void histogram::zero() {
  c = 0;
  (void) ::memset((void *) p,0,(size_t) psu);
}

double histogram::entropy() {
  double e = 0.0;
  unsigned long *pe = &p[ps];
  unsigned long *pp = p;
  assert(c != 0);
  for(;pp != pe;pp++) {
    unsigned long t;
    if ((t = *pp) != 0)
      e += ((double) t) * logt.log(t);
  }
  return logt.log(c) - e / (double) c;
}

class group_el {

  friend class group;

  group_el **pre;
  group_el *post;
  char *rp;
  char *np;

};

class group {
  group_el *gr;
  group_el *s;
  char *rg;
  char *ng;
  unsigned long n,r,ord;
  unsigned long *ref_count;

  void perm_gen(char *&ar,char *ref,unsigned long n,unsigned long d);
  void permify(char *ar,unsigned long n);
  void cons(group &g);
  void destroy();
  void del(group_el *g);

  public:

  group(unsigned long radix,unsigned long size);
  group(group &g) { cons(g); }
  ~group() { destroy(); }
  group &operator=(group &g);

  group_el *start() { return s; }
  group_el *iterator(group_el *g) { return g->post; }
  unsigned long order() { return ord; }
  void contract(p_type p);
  void apply(p_type pout,p_type pin,group_el *g);

};

static double dfac(unsigned long n) {
  double f = 1.;
  unsigned long i;
  for(i = 2;i <= n;i++)
    f *= (double) i;
  return f;
}

static unsigned long fac(unsigned long n) {
  unsigned long f = 1,i;
  err(dfac(n) <= (double) ULONG_MAX,group_overflow);
  for(i = 2;i <= n;i++)
    f *= i;
  return f;
}

void group::perm_gen(char *&ar,char *ref,unsigned long n,unsigned long d) {
  if (d == n) {
    register char *ar_p = ar;
    register char *ar_pe = ar + n;
    register char *ref_p = ref;
    while (ar_p != ar_pe)
      *ar_p++ = *ref_p++;
    ar = ar_pe;
    return;
  }
  unsigned long i;
  for(i = d;i != n;i++) {
    char t;
    t = ref[i];
    ref[i] = ref[d];
    ref[d] = t;
    perm_gen(ar,ref,n,d + 1);
    t = ref[i];
    ref[i] = ref[d];
    ref[d] = t;
  }
}

void group::permify(char *ar,unsigned long n) {
  char *ref;
  err((ref = new char[n]) != NULL,out_of_memory);
  for(unsigned long i = 0;i != n;i++)
    ref[i] = i;
  char *ar_copy = ar;
  perm_gen(ar_copy,ref,n,0);
  assert(ar_copy - ar == fac(n) * n);
  delete[] ref;
}

void group::cons(group &g) {
  n = g.n;
  r = g.r;
  ord = g.ord;
  ref_count = g.ref_count;
  rg = g.rg;
  ng = g.ng;
  (*ref_count)++;
  err((gr = new group_el[ord]) != NULL,out_of_memory);
  s = gr;
  group_el *g_e = gr + ord;
  group_el *g_p;
  group_el *og_p = g.start();
  group_el **prev = &s;
  for(g_p = gr;g_p != g_e;g_p++) {
    g_p->rp = og_p->rp;
    g_p->np = og_p->np;
    g_p->pre = prev;
    g_p->post = g_p + 1;
    prev = &(g_p->post);
    og_p = iterator(og_p);
  }
  assert(og_p == NULL);
  g_p--;
  g_p->post = NULL;
}

void group::destroy() {
  delete[] gr;
  assert(*ref_count != 0);
  (*ref_count)--;
  if (*ref_count == 0) {
    delete[] rg;
    delete[] ng;
    delete ref_count;
  }
}

void group::del(group_el *g) {
  *g->pre = g->post;
  if (g->post != NULL)
    g->post->pre = g->pre;
}

group::group(unsigned long radix,unsigned long size) {
  n = size;
  r = radix;
  err(dfac(n) * dfac(r) <= (double) ULONG_MAX,group_overflow);
  unsigned long facn,facr;
  facn = fac(n);
  facr = fac(r);
  ord = facn * facr;
  double stm = (double) sizetmax();
  err((double) ord * (double) sizeof(group_el) <= stm &&
      (double) facn * (double) n <= stm &&
      (double) facr * (double) r <= stm,
      group_overflow);
  err((gr = new group_el[ord]) != NULL,out_of_memory);
  err((rg = new char[facr * r]) != NULL,out_of_memory);
  err((ng = new char[facn * n]) != NULL,out_of_memory);
  err((ref_count = new unsigned long) != NULL,out_of_memory);
  *ref_count = 1;
  permify(rg,r);
  permify(ng,n);
  s = gr;
  group_el **p_pre = &s;
  group_el *p_g = gr;
  char *p_rg;
  char *p_rge = rg + r * facr;
  char *p_ng;
  char *p_nge = ng + n * facn;
  for(p_rg = rg;p_rg != p_rge;p_rg += r)
    for(p_ng = ng;p_ng != p_nge;p_ng += n) {
      p_g->pre = p_pre;
      p_g->post = p_g + 1;
      p_g->rp = p_rg;
      p_g->np = p_ng;
      p_pre = &(p_g->post);
      p_g++;
    }
  p_g--;
  p_g->post = NULL;
  if (verbose)
    cout << "Group order = " << ord << ".\n";
}


group &group::operator=(group &g) {
  if (&g != this) {
    destroy();
    cons(g);
  }
  return *this;
}

void group::contract(p_type p) {
  group_el *g = start();
  p_type temp_pat;
  err((temp_pat = new char[n]) != NULL,out_of_memory);
  while (g != NULL) {
    group_el *t;
    t = iterator(g);
    apply(temp_pat,p,g);
    if (! equal(temp_pat,p,n)) {
      del(g);
      assert(ord != 0);
      ord--;
    }
    g = t;
  }
  if (verbose)
    cout << "Group order = " << ord << ".\n";
}

void group::apply(p_type pout,p_type pin,group_el *g) {
  unsigned long i;
  for(i = 0;i != n;i++)
    pout[g->np[i]] = g->rp[pin[i]];
}

class move_gen {

histogram hist;
p_list *list;
score_class sc;
unsigned long size;
group g;
unsigned long *orbits;
log_table l;

unsigned long rad,len,depth,orb_count;

boolean orbits_created;

unsigned long power(unsigned long a,unsigned long b);

boolean test_move(p_type pat,unsigned long d,double best,double &h);

void b_move(unsigned long d,p_type &pat,double &h,boolean &solvable);

unsigned long pat_pos(p_type p);

unsigned long create_orbits();

void del();

void pre_bayes(p_type pattern,score_type &score);

void contract(p_type pat) { g.contract(pat);orbits_created = false; }

public:

move_gen(unsigned long radix,unsigned long length,unsigned long d);

move_gen(move_gen &mg);

move_gen &operator=(move_gen &mg);

virtual ~move_gen();

unsigned long radix() { return rad; }

unsigned long sz() { return len; }

// number of possible patterns left
unsigned long num_poss() { return list->lsize(); }

// true iff solution found
boolean found() { return (list->lsize() == 1); }

// returns solution - only call if found() true as a precondition
void solution(p_type pattern);

// log to base e of num_poss()
double entropy();

// gets best move
void best_move(p_type pattern,boolean &solvable);

// processes result of getting score "score" for pattern "pattern"
void bayes(p_type pattern,score_type &score) {
  pre_bayes(pattern,score);
  contract(pattern);
}

};

#define MAX_SIZE ((double) ULONG_MAX)

unsigned long move_gen::power(unsigned long a,unsigned long b) {
  err(::pow((double) a,(double) b)
      <= MAX_SIZE,too_large);
  unsigned long p = 1;
  while (b) {
    while (! (b % 2)) {
      b /= 2;
      a *= a;
    }
    p *= a;
    b--;
  }
  return p;
}

void move_gen::del() {
  delete[] orbits;
  delete list;
}

move_gen::~move_gen() {
  del();
}

boolean move_gen::test_move(p_type pat,unsigned long d,double best,
                            double &h) {
  score_type s;
  p_node *p = list->head();
  assert(p != NULL);
  hist.zero();
  while (p != NULL) {
    sc.get_score(pat,p->pattern(),s);
    hist.add(s);
    p = list->iterator(p);
  }
  double mutual = hist.entropy();
  if (mutual < eps || d == 0) {
    h = entropy() - mutual;
    return (h < best + eps);
  }
  assert(d > 0);
  best = best * (double) hist.count() + eps;
  move_gen m = *this;
  m.contract(pat);
  double hh = 0.;
  p_type pp;
  for(s.right = 0;s.right <= len;s.right++)
    for(s.wrong = 0;s.right + s.wrong <= len;s.wrong++) {
      unsigned long c;
      c = hist[s];
      if (c <= 1)
        continue;
      move_gen mm = m;
      mm.pre_bayes(pat,s);
      double ent;
      boolean poss;
      mm.b_move(d - 1,pp,ent,poss);
      hh += (double) hist[s] * ent;
      if (hh > best)
        return false;
    }
  h = hh / (double) hist.count();
  if (verbose) {
    cout << "Evaluating ";
    disp_pat(pat,rad,len);
    cout << ", entropy = ";
    cout << h << ", depth = " << d << ".\n";
    cout.flush();
  }
  return true;
}

unsigned long move_gen::pat_pos(p_type p) {
  unsigned long i = 0;
  char *pp = p + len - 1;
  for(;;) {
    assert(0 <= *pp && *pp < rad);
    i = i * rad + *pp;
    if (pp == p)
      return i;
    pp--;
  }
}

unsigned long move_gen::create_orbits() {
  (void) memset(orbits,0,(size_t) (size * sizeof(unsigned long)));
  unsigned long *orb_p = orbits;
  unsigned long *orb_p_e = orbits + size;
  unsigned long orb = 1;
  p_type temp_pat;
  err((temp_pat = new char[len]) != NULL,out_of_memory);
  for(;orb_p != orb_p_e;orb++) {
    p_type p;
    p = (*list)[orb_p - orbits];
    group_el *gg;
    gg = g.start();
    assert(gg != NULL);
    while (gg != NULL) {
      g.apply(temp_pat,p,gg);
      unsigned long i;
      i = pat_pos(temp_pat);
      assert(i < size);
      orbits[i] = orb;
      gg = g.iterator(gg);
    }
    while (orb_p != orb_p_e && *orb_p != 0)
      orb_p++;
  }
  delete[] temp_pat;
  return orb - 1;
}

move_gen::move_gen(unsigned long radix,unsigned long length,
                   unsigned long d)
          : sc(radix,length), g(radix,length), hist(length), l() {
  rad = radix;
  len = length;
  depth = d;
  orbits_created = false;
  err(rad != 0 && len != 0,improper_usage);
  size = power(radix,len);
  err((double) size * (double) sizeof(unsigned long) <= (double)
sizetmax(),
      too_large);
  err((orbits = new unsigned long[size]) != NULL,out_of_memory);
  err((list = new p_list(size,len)) != NULL,out_of_memory);
  p_type pt;
  err((pt = new char [len]) != NULL,out_of_memory);
  p_type p;
  unsigned long ppp = 0;
  ::memset(pt,0,(size_t) len);
  unsigned rd = rad - 1;
  unsigned i = 0;
  while (i != len) {
    p = (*list)[ppp];
    ::memcpy(p,pt,(size_t) len);
    ppp++;
    char *ppt;
    i = 0;
    ppt = pt;
    for(;;) {
      if (i == len)
        break;
      assert(0 <= *ppt && *ppt < rad);
      if (*ppt == rd) {
        *ppt = 0;
        ppt++;
        i++;
      }
      else {
        (*ppt)++;
        break;
      }
    }
  }
  assert(ppp == size);
  delete[] pt;
  if (verbose)
    cout << "Distribution size = " << size << ".\n";
}

move_gen::move_gen(move_gen &mg) : sc(mg.sc), g(mg.g), hist(mg.hist),
          l(mg.l) {
  rad = mg.rad;
  len = mg.len;
  size = mg.size;
  depth = mg.depth;
  orbits_created = false;
  err((orbits = new unsigned long[size]) != NULL,out_of_memory);
  err((list = new p_list(*(mg.list))) != NULL,out_of_memory);
}

move_gen &move_gen::operator=(move_gen &mg) {
  rad = mg.rad;
  len = mg.len;
  size = mg.size;
  depth = mg.depth;
  delete[] orbits;
  orbits_created = false;
  err((orbits = new unsigned long[size]) != NULL,out_of_memory);
  hist = mg.hist;
  *list = *(mg.list);
  sc = mg.sc;
  g = mg.g;
  l = mg.l;
  return *this;
}

double move_gen::entropy() {
  err(num_poss() != 0,improper_usage);
  return l.log(num_poss());
}

void move_gen::solution(p_type pattern) {
  assert(found());
  ::memcpy(pattern,list->head()->pattern(),(size_t) len);
}

// choose the best move, according to entropy criterion,
void move_gen::b_move(unsigned long d,p_type &pat,double &h,
                      boolean &solvable) {
  p_type pt = NULL;
  h = entropy();
  if (orbits_created == false) {
    orb_count = create_orbits();
    orbits_created = true;
  }
  unsigned long *orb_p = orbits;
  unsigned long orb;
  if (num_poss() == 1) {
    pat = (list->head())->pattern();
    h = 0.;
    solvable = true;
    return;
  }
  assert(num_poss() != 0);
  for(orb = 1;orb <= orb_count;orb++) {
    p_type p;
    for(;*orb_p != orb;orb_p++)
      assert(orb_p != orbits + size);
    p = (*list)[orb_p - orbits];
    double hh;
    if (test_move(p,d,h,hh)) {
      h = hh;
      pt = p;
    }
  }
  assert(pt != NULL);
  solvable = (fabs(h - entropy()) > eps);
  if (solvable)
    pat = pt;
}

void move_gen::best_move(p_type pattern,boolean &solvable) {
  p_type p;
  double h;
  b_move(depth,p,h,solvable);
  if (solvable)
    ::memcpy(pattern,p,(size_t) len);
}

void move_gen::pre_bayes(p_type pattern,score_type &score) {
  p_node *p = list->head();
  err(num_poss() != 0UL,improper_usage);
  assert((p == NULL) == (num_poss() == 0));
  while (p != NULL) {
    p_node *q;
    score_type s;
    q = list->iterator(p);
    sc.get_score(p->pattern(),pattern,s);
    if (s.right != score.right || s.wrong != score.wrong) {
      list->remove(p);
    }
    p = q;
  }
  if (depth != 0)
    depth--;
  if (verbose)
    cout << "Distribution size = " << list->lsize() << ".\n";

}

typedef unsigned long p_handle;

struct ref_f {
  unsigned ref_count;
  FILE *fptr;
};

class move_tree {

ref_f *rf;
unsigned long radix,n,rec_size,num_scores,depth;
p_type dummy_pat;
char *file_name;
boolean size_modified,read_only;
unsigned long file_pos,file_size;

// this method derives filename from radix and size and stores
// it in this->file_name
void get_file_name();

void get_file();

void get_data(unsigned char &valid,p_handle &posn,p_type pat);

void set_data(unsigned char valid,p_handle posn,p_type pat);

void write_long(long l);

long read_long();

void write_size(long l);

long read_size();

p_handle new_pos();

long offset(score_type &s);

void read(void *ptr,unsigned size);

void write(void *ptr,unsigned size);

void adj_size();

p_handle get_pos(); // return handle to current pos in tree

void set_pos(p_handle posn); // set pos in tree to handle posn

void enter();

void exit();

void create(unsigned long rad,unsigned long len,unsigned long d);

void destroy();

public:

move_tree(unsigned long rad,unsigned long len,unsigned long d);

move_tree(move_tree &mt);

move_tree &operator=(move_tree &mt);

virtual ~move_tree();

void home(); // goes to root

void set_pattern(p_type pat); // set pattern to pat at current pos

boolean get_pattern(p_type pat); // returns false iff no pattern there

void move(score_type &s); // move down to posn s

};

#ifndef SEEK_SET
#define SEEK_SET (0)
#endif

// size of posn var on disc
#define POSN_SIZE (3)

static const unsigned char VALID = 1;
static const unsigned char INVALID = 0;
static const p_handle NIL = (p_handle) 0;

static const char *mmd_path_env_var = "MMDPATH";

static char *default_path = "";

static boolean path_read = false;
static boolean prefix_read = false;

static char *path;
static char *file_prefix;

char *get_path() {
  if (! path_read) {
    path = getenv(mmd_path_env_var);
    if (path == NULL)
      path = default_path;
    path_read = true;
  }
  return path;
}

char *get_prefix() {
  return (noright ? "c" : "d");
}

// constants used by get_file_name() method

static const unsigned max_path_name_size = 128;
static const unsigned file_len_max = 8;

// the get_file_name() method derives filename
// from this->radix and this->size
// and stores it in this->file_name

void move_tree::get_file_name() {
  int countf;
  char *f_name;
  err((f_name = new char[max_path_name_size + 1]) != NULL,
       out_of_memory);
  (void) ::sprintf(f_name,"%s%lux%lux%lu",get_prefix(),radix,n,depth);
  countf = ::strlen(f_name);
  assert(countf > 0);
  err(countf <= file_len_max,filename_too_long);
  err(::strlen(get_path()) + countf <=
max_path_name_size,filename_too_long);
  (void)::strcpy(file_name,get_path());
  (void)::strcat(file_name,f_name);
  delete[] f_name;
  }


void move_tree::get_file() {
  err((file_name = new char[max_path_name_size + 1]) != NULL,
       out_of_memory);
  get_file_name();
  size_modified = false;
  file_pos = file_size = 0;
  // try to open first with rw permission, then read only permission
  read_only = ((rf->fptr = ::fopen(file_name,"r+b")) == NULL);
  if (read_only && (rf->fptr = ::fopen(file_name,"rb")) == NULL) {
    (void) ::memset(dummy_pat,0,n); //  clear
    err((rf->fptr = ::fopen(file_name,"wb")) != NULL,cant_create);
    read_only = false;
    write_long((long) POSN_SIZE);
    set_data(INVALID,NIL,dummy_pat);
    write_size(file_size);
    err(::fclose(rf->fptr) == 0,error_closing);
    err((rf->fptr = ::fopen(file_name,"r+b")) != NULL,cant_open);
    }
  delete[] file_name;
  }

void move_tree::create(unsigned long rad,unsigned long len,
                       unsigned long d) {
  n = len;
  radix = rad;
  depth = d;
  size_modified = false;
  rec_size = POSN_SIZE + 1 + n;
  num_scores = (n + 1) * (n + 2) / 2;
  err((dummy_pat = new char[n]) != NULL,out_of_memory);
  }

void move_tree::destroy() {
  if (--(rf->ref_count) == 0) {
    err(::fclose(rf->fptr) == 0,error_closing);
    delete rf;
    }
  delete[] dummy_pat;
  }

move_tree::move_tree(unsigned long rad,unsigned long len,unsigned long d) {
  err((rf = new ref_f) != NULL,out_of_memory);
  rf->ref_count = 1;
  create(rad,len,d);
  get_file();
  home();
  file_size = read_size();
  size_modified = false;
  }

move_tree::~move_tree() {
  destroy();
  }

move_tree::move_tree(move_tree &mt) {
  create(mt.radix,mt.n,mt.depth);
  read_only = mt.read_only;
  rf = mt.rf;
  (rf->ref_count)++;
  set_pos(mt.get_pos());
  file_size = read_size();
  size_modified = false;
  }

move_tree &move_tree::operator=(move_tree &mt) {
  if (this != &mt) {
    destroy();
    create(mt.radix,mt.n,mt.depth);
    read_only = mt.read_only;
    size_modified = false;
    rf = mt.rf;
    (rf->ref_count)++;
    set_pos(mt.get_pos());
    file_size = read_size();
    size_modified = false;
    }
  return *this;
  }

void move_tree::read(void *ptr,unsigned size) {
  err(::fread(ptr,size,1,rf->fptr) == 1,error_reading);
  file_pos += size;
  adj_size();
  }

void move_tree::write(void *ptr,unsigned size) {
  err(! read_only,file_read_only);
  err(::fwrite(ptr,size,1,rf->fptr) == 1,error_writing);
  file_pos += size;
  adj_size();

  }

void move_tree::set_pos(p_handle posn) { // set pos in tree to handle posn
  file_pos = posn;
  err(::fseek(rf->fptr,posn,SEEK_SET) == 0,cant_seek);
  }

void move_tree::adj_size() {
  if (file_pos > file_size) {
    size_modified = true;
    file_size = file_pos;
    }
  }

void move_tree::enter() {
  set_pos(file_pos);
  file_size = read_size();
  }

void move_tree::exit() {
  if (size_modified) {
    write_size(file_size);
    size_modified = false;
    }
  }

void move_tree::write_long(long l) {
  unsigned char buf[POSN_SIZE];
  for(int i = POSN_SIZE - 1;i != - 1;i--) {
    buf[i] = (unsigned char) (l & 0xff);
    l >>= 8;
    }
  err(l == 0,long_too_big);
  write(buf,POSN_SIZE);
  }

long move_tree::read_long() {
  unsigned char buf[POSN_SIZE];
  read(buf,POSN_SIZE);
  long l = 0;
  for(unsigned i = 0;i != POSN_SIZE;i++) {
    l <<= 8;
    l |= (long) (buf[i]);
    }
  return l;
  }

void move_tree::get_data(unsigned char &valid,p_handle &posn,p_type pat) {
  read(&valid,1);
  err(valid == VALID || valid == INVALID,file_corrupted);
  posn = (p_handle) read_long();
  read(pat,n);
  for (unsigned i = 0;i != n;i++) {
    err(((unsigned) (*pat)) < radix,file_corrupted);
    pat++;
    }
  }

void move_tree::set_data(unsigned char valid,p_handle posn,p_type pat) {
  assert(valid == VALID || valid == INVALID);
  write(&valid,1);
  write_long((long) posn);
  write(pat,n);
  }

void move_tree::home() {
  set_pos((p_handle) POSN_SIZE);
  }

p_handle move_tree::get_pos() {
  return file_pos;
  }

void move_tree::write_size(long l) {
  p_handle pos;
  pos = get_pos();
  set_pos((p_handle) 0);
  write_long(l);
  set_pos(pos);
  err(::fflush(rf->fptr) == 0,error_flushing);
  }

long move_tree::read_size() {
  p_handle pos;
  pos = get_pos();
  set_pos((p_handle) 0);
  long l = read_long();
  set_pos(pos);
  return l;
  }

long move_tree::offset(score_type &s) {
  assert(s.right + s.wrong <= n);
  // get index from score
  return ((n + n + 3 - s.right) * s.right / 2 + s.wrong) * rec_size;
  }

boolean move_tree::get_pattern(p_type pat) {
  // returns false iff no pattern there
  unsigned char valid;
  p_handle posn,dummy;
  enter();
  posn = get_pos();
  set_pos(posn); // fseek before I/O
  get_data(valid,dummy,pat);
  set_pos(posn); // return to orig posn
  exit();
  return (valid == VALID);
  }

void move_tree::set_pattern(p_type pat) {
  unsigned char valid;
  p_handle posn,dummy;
  enter();
  posn = get_pos();
  set_pos(posn); // fseek before I/O
  get_data(valid,dummy,dummy_pat);
  set_pos(posn); // return to orig posn
  valid = VALID;
  set_data(valid,dummy,pat);
  set_pos(posn); // return to orig posn
  exit();
  }

p_handle move_tree::new_pos() {
  return (p_handle) file_size;
  }

void move_tree::move(score_type &s) { // move down to posn s
  unsigned char valid;
  p_handle posn,child_pos;
  enter();
  posn = get_pos();
  set_pos(posn);
  get_data(valid,child_pos,dummy_pat);
  set_pos(posn);
  assert(valid == VALID);
  if (child_pos == NIL) {
    child_pos = new_pos(); // extend file
    set_pos(posn);
    set_data(valid,child_pos,dummy_pat);
    (void) ::memset(dummy_pat,0,n); // for neatness, clear
    set_pos(child_pos);
    for(unsigned i = 0;i != num_scores;i++) // create empty records
      set_data(INVALID,NIL,dummy_pat);
    }
  set_pos(child_pos + offset(s));
  exit();
  }

class d_move_gen : public move_gen,private move_tree {

p_type worst_pat;
unsigned depth;
unsigned worst_depth;
unsigned long depth_sum;
unsigned long pat_count;
unsigned long *hist;

void partial_closure(d_move_gen *me,score_type &sc,
                     p_type pat);

void local_best_move(p_type pattern,boolean &possible);

public:

d_move_gen(unsigned long rad,unsigned long length,unsigned long d);

d_move_gen(d_move_gen &mg);

// default C++ operator= is sufficient

~d_move_gen();

// gets best move
void best_move(p_type pattern);

// processes result of getting score "score" for pattern "pattern"
void bayes(p_type pattern,score_type &score);

void closure(unsigned &w_depth,p_type w_pat,double &ave_depth,
             unsigned long *h);

};

d_move_gen::d_move_gen(unsigned long rad,unsigned long length,unsigned long
d)
  : move_tree(rad,length,d),move_gen(rad,length,d) {
  }

d_move_gen::~d_move_gen() {
  }

d_move_gen::d_move_gen(d_move_gen &mg) : move_tree(mg),move_gen(mg) {
  }

void d_move_gen::local_best_move(p_type pattern,boolean &possible) {
  if (! get_pattern(pattern)) {
    move_gen::best_move(pattern,possible);
    if (possible)
      set_pattern(pattern);
    }
  }

void d_move_gen::best_move(p_type pattern) {
  boolean possible;
  local_best_move(pattern,possible);
  err(possible,no_info);
  }

void d_move_gen::bayes(p_type pattern,score_type &score) {
  move_gen::bayes(pattern,score);
  if (num_poss() != 0)
    move(score);
  }

void d_move_gen::partial_closure(d_move_gen *me,score_type &sc,
                                 p_type pat) {
  score_type s;
  d_move_gen *new_me;
  p_type new_pat;
  boolean possible;
  if (me->num_poss() == 0)
    return;
  if (me->found()) {
    pat_count++;
    depth_sum += depth;
    if (depth > worst_depth) {
      worst_depth = depth;
      me->solution(worst_pat);
    }
  }
  err((new_me = new d_move_gen(*me)) != NULL,out_of_memory);
  new_me->bayes(pat,sc);
  if (new_me->num_poss() == me->num_poss()) {
    delete new_me;
    return;
  }
  err((new_pat = new char [sz()]) != NULL,out_of_memory);
  if (new_me->num_poss() != 0) {
    if (new_me->found()) {
      unsigned t = depth + 1;
      pat_count++;
      depth_sum += t;
      hist[t]++;
      if (t > worst_depth) {
        worst_depth = t;
        new_me->solution(worst_pat);
      }
    } else {
      new_me->local_best_move(new_pat,possible);
      if (possible) {
        for(s.right = 0;s.right != sz() + 1;s.right++)
          for(s.wrong = 0;s.wrong + s.right != sz() + 1;s.wrong++) {
            depth++;
            partial_closure(new_me,s,new_pat);
            depth--;
          }
      }
    }
  }
  delete[] new_pat;
  delete new_me;
}

void d_move_gen::closure(unsigned &w_depth,p_type w_pat,
                         double &ave_depth,unsigned long *h) {
  score_type s;
  p_type new_pat;
  boolean possible;
  worst_depth = 0;
  worst_pat = w_pat;
  depth_sum = 0;
  pat_count = 0;
  hist = h;
  assert(num_poss() != 0);
  if (found()) {
    solution(w_pat);
    w_depth = 1;
    ave_depth = 1.;
    h[1] = 1;
    return;
  }
  err((new_pat = new char [sz()]) != NULL,out_of_memory);
  if (num_poss() != 0) {
    local_best_move(new_pat,possible);
    if (possible) {
      depth = 0;
      for(s.right = 0;s.right != sz() + 1;s.right++)
       for(s.wrong = 0;s.wrong + s.right != sz() + 1;s.wrong++) {
         partial_closure(this,s,new_pat);
       }
    }
  }
  delete[] new_pat;
  w_depth = worst_depth;
  ave_depth = ((double) depth_sum) / (double) pat_count;
}

class perm {

unsigned n;

unsigned long seed;

char *mapping;
char *inverse;

unsigned ran();

void permute();

void gen_inv();

void create(unsigned size,unsigned long seed_val);

void destroy();

public:

// seed = 0 chooses identity permutation
perm(unsigned size,unsigned long seed_val);

perm(perm &pm);

perm &operator=(perm &pm);

~perm() {
  destroy();
  }

unsigned map(unsigned i);

unsigned inv(unsigned i);

};

void perm::permute() {
  unsigned i,j,t;
  for(i = 0; i != n;i++)
    mapping[i] = i;
  if (seed == 0) // seed == 0 selects identity
    return;
  seed_set(seed);
  // mix em up so each permutation is equally likely
  for(i = 0;i != n;i++) {
    j = i + uniform(n - i);
    t = mapping[i];
    mapping[i] = mapping[j];
    mapping[j] = t;
  }
}

void perm::gen_inv() {
  unsigned i;
  for(i = 0;i != n;i++)
    inverse[mapping[i]] = i;
  }

void perm::create(unsigned size,unsigned long seed_val) {
  n = size;
  seed = seed_val;
  err((mapping = new char [n]) != NULL,out_of_memory);
  err((inverse = new char [n]) != NULL,out_of_memory);
  }

void perm::destroy() {
  delete[] inverse;
  delete[] mapping;
  }

// seed = 0 chooses identity permutation
perm::perm(unsigned size,unsigned long seed_val) {
  create(size,seed_val);
  permute();
  gen_inv();
  }

perm::perm(perm &pm) {
  create(pm.n,pm.seed);
  ::memcpy(mapping,pm.mapping,(size_t) n);
  ::memcpy(inverse,pm.inverse,(size_t) n);
  }

perm &perm::operator=(perm &pm) {
  if (this != &pm) {
    destroy();
    create(pm.n,pm.seed);
    ::memcpy(mapping,pm.mapping,(size_t) (n * sizeof(unsigned)));
    ::memcpy(inverse,pm.inverse,(size_t) (n * sizeof(unsigned)));
    }
  return *this;
  }

unsigned perm::map(unsigned i) {
  err(i < n,improper_usage);
  return mapping[i];
  }

unsigned perm::inv(unsigned i) {
  err(i < n,improper_usage);
  return inverse[i];
  }

static boolean s_eq(const char *s1,const char *s2) {
  char c1,c2;
  for(;;) {
    c1 = *s1++;
    c2 = *s2++;
    if (tolower(c1) != tolower(c2))
      return false;
    if (c1 == '\0')
      return true;
  }
}
static void process_cmd(int argc,char **argv,
                        boolean &test,
                        p_type test_pat,
                        boolean &pseudo,
                        boolean &closure,
                        boolean &comp_solves,
                        unsigned long &radix,
                        unsigned long &size,
                        unsigned long &seed,
                        unsigned long &depth) {
  // set defaults
  noright = false;
  test = false;
  pseudo = false;
  closure = false;
  verbose = false;
  comp_solves = true;
  radix = default_radix;
  size = default_size;
  depth = default_depth;
  seed = (unsigned long) ::time(NULL);
  char *pat = NULL;
  // read cmd line
  argc--;
  argv++;
  int i;
  while (argc > 0) {
    if (**argv == '\0') {
      argc--;
      argv++;
      continue;
    }
    if (s_eq(*argv,"-pipe")) {
      pseudo = true;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-gametree")) {
      closure = true;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-human")) {
      comp_solves = false;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-verbose")) {
      verbose = true;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-radix")) {
      err(argc > 0,"Missing radix.");
      err(sscanf(argv[1],"%lu",&radix) == 1,"Bad radix.");
      argc -= 2;
      argv += 2;
    } else if (s_eq(*argv,"-size")) {
      err(argc > 0,"Missing size.");
      err(sscanf(argv[1],"%lu",&size) == 1,"Bad size.");
      argc -= 2;
      argv += 2;
    } else if (s_eq(*argv,"-seed")) {
      err(argc > 0,"Missing seed.");
      err(sscanf(argv[1],"%lu",&seed) == 1,"Bad seed.");
      argc -= 2;
      argv += 2;
    } else if (s_eq(*argv,"-test")) {
      test = true;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-pattern")) {
      test = true;
      err(argc > 0,"Missing pattern.");
      pat = argv[1];
      argc -= 2;
      argv += 2;
    } else if (s_eq(*argv,"-noright")) {
      noright = true;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-noscramble")) {
      seed = 0;
      argc--;
      argv++;
    } else if (s_eq(*argv,"-depth")) {
      err(argc > 0,"Missing depth.");
      err(sscanf(argv[1],"%lu",&depth) == 1,"Bad depth.");
      argc -= 2;
      argv += 2;
    }  else
      err(false,improper_switches);
  }
  err((noright ? 1 : 0) < size && size <= max_size,"Incorrect -size
usage.");
  err(0 < radix && radix <= max_radix(),"Incorrect -radix usage.");
  err(0 <= depth && depth <= max_depth,"Incorrect -depth usage.");
  err(! (test && pat != NULL && closure),
      "Can't have -pattern and -gametree simultaneously.");
  err(! (test && pat == NULL && closure),
      "Can't have -test and -gametree simultaneously.");
  err((test && pat != NULL) <= comp_solves,
      "Can't have -pattern and -human simultaneously.");
  err((test && pat == NULL) <= comp_solves,
      "Can't have -test and -human simultaneously.");
  err(closure <= comp_solves,
      "Can't have -gametree and -human simultaneously.");
  err(! (closure && pseudo),"Can't have -gametree and -pipe
simultaneously.");
  err(! (test && pat == NULL && pseudo),
      "Can't have -test and -pipe simultaneously.");
  err(! (test && pat != NULL && pseudo),
      "Can't have -pattern and -pipe simultaneously.");
  err(! (verbose && pseudo),
      "Can't have -verbose and -pipe simultaneously.");
  if (test)
    if (pat == NULL)
      *test_pat = (char) radix;
    else
      err(s_to_p(pat,test_pat,radix,size),bad_pattern);
  }

static void rand_pat(p_type pat,unsigned radix,unsigned size) {
  for(unsigned i = 0;i != size;i++) {
    pat[i] = (char) uniform(radix);
    }
  }

static void xlate(p_type dest,p_type src,unsigned len,
                  perm &n_perm,perm &r_perm) {
  for(unsigned i = 0;i != len;i++)
    dest[n_perm.map(i)] = (char) r_perm.map((unsigned) src[i]);
  }

static score_type get_sc_interactive(p_type dummy1,p_type dummy2,
                              unsigned dummy3,
                              unsigned dummy4) {
  score_type sc;
  cin >> sc;
  return sc;
  }

static score_type get_sc_auto(p_type right,p_type guess,
                              unsigned radix,
                              unsigned size) {
  score_type sc;
  score_class s(radix,size);
  s.get_score(right,guess,sc);
  cout << sc << "\n";
  return sc;
}

static void solve(unsigned long radix,unsigned long size,
                  unsigned long depth,
                  boolean pseudo,
                  unsigned long seed,
                  p_type true_pat,
                  score_type
(*get_sc_func)(p_type,p_type,unsigned,unsigned)) {
  d_move_gen *mg;
  p_type guess_pat,temp_pat;
  unsigned np;
  perm n_perm(size,seed);
  perm r_perm(radix,seed);
  err((guess_pat = new char[size]) != NULL,out_of_memory);
  err((temp_pat = new char[size]) != NULL,out_of_memory);
  if (! pseudo) {
    cout << "Radix = " << radix << ", size = " << size << ", depth = "
         << depth
         << ", seed = "
         << seed << ".\nGuessing...\n";
    }
  cout.flush();
  err((mg = new d_move_gen(radix,size,depth)) != NULL,out_of_memory);
  while (mg->num_poss() > 1) {
    score_type s;
    mg->best_move(guess_pat);
    xlate(temp_pat,guess_pat,size,n_perm,r_perm);
    if (pseudo)
      cout << "?";
    else
      cout << "Guess ";
    ::disp_pat(temp_pat,radix,size);
    if (pseudo)
      cout << "\n";
    else
      if (noright)
        cout << ": (wrong) ? ";
      else
        cout << ": (right) (wrong) ? ";
    cout.flush();
    s = get_sc_func(true_pat,temp_pat,radix,size);
    cout.flush();
    np = mg->num_poss();
    mg->bayes(guess_pat,s);
    err(mg->num_poss() < np,bad_variant);
    }
  if (mg->found()) {
    mg->solution(guess_pat);
    xlate(temp_pat,guess_pat,size,n_perm,r_perm);
    if (pseudo)
      cout << "!";
    else
      cout << "Unless you made a mistake in your scoring, pattern is: ";
    ::disp_pat(temp_pat,radix,size);
    if (! pseudo)
      cout << ".";
    cout << "\n";
    }
  else {
    if (pseudo)
      cout << "%\n";
    else
      cerr << "Inconsistency detected - "
              "you made a mistake in your scoring.\n";
    }
  delete mg;
  delete[] temp_pat;
  delete[] guess_pat;
  }

static void set(unsigned radix,unsigned size,boolean pseudo) {
  p_type set_pat,guess_pat;
  unsigned count = 0;
  char c = '\0';
  err((set_pat = new char[size]) != NULL,out_of_memory);
  err((guess_pat = new char[size]) != NULL,out_of_memory);
  randomize();
  rand_pat(set_pat,radix,size);
  score_type s;
  score_class sc(radix,size);
  if (! pseudo)
    cout << "Radix = " << radix << ", size = " << size
         << ".\nPlease enter your first guess.\n";
  do {
    char buf[P_BUFSIZE];
    char *buf_p;
    err(! cin.eof(),unexpected_eof);
    cin >> buf;
    err(cin.good(),io_error);
    if (pseudo) {
      err(*buf != '\0',char_err);
      buf_p = buf + 1;
      }
    else
      buf_p = buf;
    err(s_to_p(buf_p,guess_pat,radix,size),bad_pattern);
    sc.get_score(set_pat,guess_pat,s);
    if (! pseudo) {
      disp_pat(guess_pat,radix,size);
      if (noright)
        cout << ": (wrong) : ";
      else
        cout << ": (right) (wrong) : ";
      }
    cout << s << "\n";
    count++;
    }
  while (! equal(set_pat,guess_pat,size));
  if (! pseudo) {
    cout << "Congratulations!\nYou found the pattern in "
         << count << " go(es).\n";
    }
  delete[] guess_pat;
  delete[] set_pat;
  }

static void do_test(p_type test_pat,unsigned long radix,unsigned long size,
                    unsigned long depth,
                    unsigned long seed) {
  if (*test_pat == (char) radix) {
    randomize();
    rand_pat(test_pat,radix,size);
    }
  cout << "Testing using pattern: ";
  ::disp_pat(test_pat,radix,size);
  cout << ".\n";
  cout.flush();
  solve(radix,size,depth,false,seed,test_pat,get_sc_auto);
  }

#define HBUF_SZ (100)
static void do_closure(unsigned long radix,unsigned long size,
                       unsigned long d) {
  unsigned long t1 = time(NULL);
  d_move_gen *mg;
  p_type worst_pat;
  unsigned depth = 0;
  double ave_depth = 0.;
  unsigned long h[HBUF_SZ];
  ::memset(h,0,(size_t) (HBUF_SZ * sizeof(unsigned long)));
  err((worst_pat = new char[size]) != NULL,out_of_memory);
  err((mg = new d_move_gen(radix,size,d)) != NULL,out_of_memory);
  cout << "Radix = " << radix << ", size = " << size
       << ", depth = " << d
       << ".\nCompleting datafile.\nPlease wait...\n";
  cout.flush();
  mg->closure(depth,worst_pat,ave_depth,h);
  unsigned long t2 = time(NULL);
  cout << "Done!\nMax number of tries = " << depth
       << ".\nAve number of tries = " << ave_depth
       << ".\nWorst pattern: ";
  ::disp_pat(worst_pat,radix,size);
  cout << ".\nRun time = " << t2 - t1 << " seconds.\n";
  delete mg;
  unsigned i;
  for(i = 1;i <= depth;i++)
    cout << "Number solved in " << i << " = " << h[i] << ".\n";
  cout.flush();
  solve(radix,size,d,false,0,worst_pat,get_sc_auto);
  delete[] worst_pat;
  }

int main(int argc,char** argv) {
  boolean test;
  p_type test_pat;
  boolean pseudo;
  boolean closure;
  boolean comp_solves;
  unsigned long radix;
  unsigned long size;
  unsigned long depth;
  unsigned long seed;
  err((test_pat = new char[max_size]) != NULL,out_of_memory);
  process_cmd(argc,argv,test,test_pat,pseudo,closure,comp_solves,
              radix,size,seed,depth);
  if (! pseudo)
    cout << "Welcome to mastermind.\n";
  if (verbose)
    cout << version << "\n";
  if (test) {
    do_test(test_pat,radix,size,depth,seed);
    delete[] test_pat;
    return 0;
    }
  delete[] test_pat;
  if (closure) {
    do_closure(radix,size,depth);
    return 0;
    }
  if (comp_solves) {
    if (! pseudo)
      cout << "My turn to guess, your turn to score.\n";
    solve(radix,size,depth,pseudo,seed,(p_type) NULL,get_sc_interactive);
    return 0;
    }
  if (! pseudo)
    cout << "Your turn to guess, my turn to score.\n";
  set(radix,size,pseudo);
  return 0;
  }




