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

#define NO	0
#define YES	!NO
#define TABS	"                                        "

#define MAXCOLORS	3

#define STRING(len)	((char *) Malloc(len + 1))
#define NEWN		((struct tree *) Malloc(sizeof(struct tree)));\
			printf("*")

#define BADARGS	1

struct tree {
  char bad;
  struct tree *away[MAXCOLORS];
  } *root;

int colors, maxlen;
int gotten = 0;

main(argc,argv)
int argc;
char *argv[];
{
void makenodes(), prstrs(), *Malloc();

if (argc < 2)
  {
  fprintf(stderr,"Usage: %s maxlen [colors]\n",argv[0]);
  exit(BADARGS);
  }
else if (argc > 2)
  colors = atoi(argv[2]);
else
  colors = 2;

if (colors > MAXCOLORS)
  {
  fprintf(stderr,"Sorry, but I'm configured for at most %d ",MAXCOLORS);
  fprintf(stderr,"colors.\nRecompile with MAXCOLORS increased to %d.\n",colors);
  exit(BADARGS);
  }

maxlen = atoi(argv[1]);

root = NEWN;
makenodes(root,maxlen,"");
/* prstrs(root,""); */
}

/***********************************************************************/
void
makenodes(n,howfar,s)
struct tree *n;
int howfar;
char *s;
{
int i, apchk(), ls;
char *newarg;
void *Malloc(), Free();

#ifdef DIAG
printf("%s makenoding with string %s, depth %d.\n",
	TABS+12-maxlen+howfar,s,maxlen-howfar);
#endif

/* if (n->bad) return; * Shouldn't be necessary. */

if (!howfar)
  {
  for (i=0; i<colors; i++)
    n->away[i] = NULL;
#ifdef DIAG
  printf("Hit bottom at %s.\n",s);
#endif
  return;
  }

for (i=0; i<colors; i++)
  {
  n->away[i] = NEWN;
  n->away[i]->bad = 0;
  if (apchk(s,'A'+i))
    {
#ifdef DIAG
    printf("%s%c is bad.\n",s,'A'+i);
#endif
    n->away[i]->bad = 1;
    }
  else
    {
    ls = strlen(s);
    newarg = STRING(ls + 1);
    if (!newarg) 
      {
      fprintf(stderr,"Couldn't get %d bytes for newarg in makenodes\n",ls+2);
      fprintf(stderr,"Total get was %d.\n",gotten);
      fprintf(stderr,"P\n L\n  O\n   P\n    !\n");
      abort();
      }
    strcpy(newarg,s);
    newarg[ls+1] = '\0';
    newarg[ls] = 'A' + i;
    makenodes(n->away[i],howfar-1,newarg);
    Free(newarg,ls+2);
    Free(n->away[i],sizeof(struct tree));
    }
  }
}

/***********************************************************************/
int
apchk(qq,q)
char *qq ,q;
{
int lqq, f, s, t;

t = lqq = strlen(qq);
if (lqq < 2) return NO;

for (f=lqq % 2; f <= lqq - 2; f += 2)
  {
  s = (f + t) / 2;
  if ((qq[f] == qq[s]) && (qq[s] == q))
    {
#ifdef DIAG
    printf("%s%c is rejected for %c in positions %d,%d,%d.\n",
	qq,q,q,f,s,t);
#endif
    return YES;
    }
  }
return NO;
}

void prstrs(n,s)
struct tree *n;
char *s;
{
int ls, i;
char *newarg;
void *Malloc(), Free();

if (n == NULL) return;
if (n->bad) return;

ls = strlen(s);
#ifdef DIAG
if (ls == maxlen) printf("%s\n",s);
#endif
newarg = STRING(ls + 1);
for (i=0; i<colors; i++)
  {
  strcpy(newarg,s);
  newarg[ls+1] = '\0';
  newarg[ls] = 'A' + i;
  prstrs(n->away[i],newarg);
  }
Free(newarg,ls+2);
return;
}

void *
Malloc(c)
unsigned c;
{
void *p;

p = (void *) malloc(c);
if (p == NULL)
  {
  fprintf(stderr,"Couldn't get %d bytes.\n",c);
  fprintf(stderr,"Total get was %d.\n",gotten);
  fprintf(stderr,"P\n L\n  O\n   P\n    !\n");
  abort();
  }
gotten += c;
/*
printf("%d gotten at 0x%x.\tTotal = %d.\n",c,p,gotten);
*/
return(p);
}

void
Free(where,howmuch)
void *where;
unsigned howmuch;
{
free(where);
gotten -= howmuch;
/*
printf("%d freed at 0x%x.\tTotal = %d.\n",howmuch,where,gotten);
*/
}