// Mastermind Program.
//
// Copyright 2013 by Thomas R. Davis.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
// USA.
//

// Here's how it works (assuming PEGS=4 and COLORS=6):
//
// Set any compile options (See "Compile options", below).
// Compile it like this:
// >cc mind.c -o mind -O3
//
// Run as:
// >mind x
// where x=1, 2, 3 or 4.
//
// If x=1 or x=5, program will select at random a secret code and you
// guess its value, as RRBG (red,red,blue,green). The program will
// reply with a pattern like BWW (one perfect match, 2 correct
// colors, but out of correct position). Continue until you get BBBB.
// If x=5, a list of possible patterns will also be printed.
//
// If x=2 or x=6, you pick a secret code, machine tries to guess it. You
// reply to each guess with entries like BWW, et cetera. Just type
// <return> if there are no matches. If x=6, a list of possible
// patterns will also be printed.
// Here's an example where the secret code you selected was RBGY:
//
//	>mind 2
//	Guess: YPRC  B-W response: WW
//	Guess: GYPB  B-W response: WWW
//	Guess: CBGP  B-W response: BB
//	Guess: PBYP  B-W response: BW
//	Solution: RBGY 
//
// If x=3, you enter a secret pattern and a series of guesses. Based
// on the pattern and the guesses, the machine will print a list of
// all possible patterns that could still be valid, based on the
// results of the secret and your guesses. As a trivial example, suppose
// you type:
//
// >RRGB YYYY PPPP
//
// With that secret, the responses would have been empty (no whites,
// no blacks), so It would be certain that the pattern contains only
// four possible colors: red, green, blue and cyan. But still all
// possible combinations of those might be the secret, so you'd get
// a list of 4^4 = 256 such patterns. You will also be told what the
// computer thinks would be your best guess would be: once if you're
// restricted to guessing possible positions, and the other, if not.
// (They may be the same.) Here's an example:
//
//	>mind 3
//	Input format: secret guess1 guess2 ...
//	>>RGBY YGBB GPPR
//	8 total positions:
//	RGBY RGYB BGRB BGBP PGBY PGYB YRBG YRGB 
//	Best guess (restricted): RGYB 
//	Best guess (unrestricted): RGYB 
//
// If x=4, you enter a series of guesses and responses and again the
// machine will print a list of patterns that are still possible. For
// example, you type:
//
// >RRRR B GGGG BB YYYY 0 PPPP B
// (note that there is a 0 (zero) for no matches)
//
// In this case, you can conclude that there are two greens, one red
// and one purple, so all combinations with that mix of colors would
// be printed. It will also tell you what it thinks the best next
// guess would be: once if you're restricted to guessing possible
// positions, and the other, if not. (They may be the same.) In the
// example above, here's what you'd get:
//
//	>mind 4
//	Input format: guess1 rep1 guess2 rep2 ...
//	>>RRRR B GGGG BB YYYY 0 PPPP B
//	12 total positions:
//	RPGG RGPG RGGP PRGG PGRG PGGR GRPG GRGP GPRG GPGR GGRP GGPR 
//	Best guess (restricted): GGPR 
//	Best guess (unrestricted): RRGG 
//
// The code that interprets your typed input is fairly fragile: be
// sure to get it exactly right. Or fix the darn code!
//
// With large numbers of colors and/or pegs, startup can take some
// time, since all possible pair interactions are computed at the
// get-go.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

// Compile options follow:

#define DEBUG 0
#define USECOLORS 0 // if 1, use R,B,G, ...; otherwise, use 1,2,3,4,...
int RESTRICT = 0; // if 1, restrict guesses to possible positions
int printpossiblepatterns = 0; // if 1, print possible configs after each guess

// PEGS can be 2, 3, 4 or 5
// COLORS can be 4, 5, 6, 7, 8 or 9 (easy to extend, but 9 is pretty big!)

#define PEGS 4
#define COLORS 6

// End of compile options

#if (PEGS==2)
#define POSITIONS (COLORS*COLORS)
#define CODECOUNT 5
#endif
#if (PEGS==3)
#define POSITIONS (COLORS*COLORS*COLORS)
#define CODECOUNT 9
#endif
#if (PEGS==4)
#define POSITIONS (COLORS*COLORS*COLORS*COLORS)
#define CODECOUNT 14
#endif
#if (PEGS==5)
#define POSITIONS (COLORS*COLORS*COLORS*COLORS*COLORS)
#define CODECOUNT 20
#endif

// Machine stores colors from 0 to COLORS-1, but humans specify them as 1 to COLORS
// If COLORS=6 and PEGS=4, for example:
// compact colors range from 0 to 5
// Save position ABCD as A*6^3 + B*6^2 + C*6 + D

#define splitcode2(a,b,x) b=x%COLORS; a=(x-b)/COLORS;
#define splitcode3(a,b,c,x) c=x%COLORS; x=(x-c)/COLORS; b = x%COLORS; a=(x-b)/COLORS;
#define splitcode(a,b,c,d,x) d = x%COLORS; x=(x-d)/COLORS; c=x%COLORS; x=(x-c)/COLORS; b = x%COLORS; a=(x-b)/COLORS;
#define splitcode5(a,b,c,d,e,x) e = x%COLORS; x=(x-e)/COLORS; d = x%COLORS; x=(x-d)/COLORS; c = x%COLORS; x=(x-c)/COLORS; b = x%COLORS; a=(x-b)/COLORS;
#define minimum(a,b) ((a>b) ? b : a)

char table[POSITIONS][POSITIONS]; // stores the B-W match result for any pair of positions

int possible[POSITIONS]; // 1 if position is still possible

// initgame() sets all patterns to "possible" (= 1)

void initgame()
{
	int i;
	for (i = 0; i < POSITIONS; i++) possible[i] = 1;
}

// printpattern() prints a compact pattern as numbers 1 through COLORS

void printpattern(int x)
{
	int x1,x2,x3,x4,x5;
	if (PEGS==2) {
		splitcode2(x1,x2,x);
		printf("%d%d ",x1+1,x2+1);
	} else if (PEGS==3) {
		splitcode3(x1,x2,x3,x);
		printf("%d%d%d ",x1+1,x2+1,x3+1);
	} else if (PEGS==4) {
		splitcode(x1,x2,x3,x4,x);
		printf("%d%d%d%d ",x1+1,x2+1,x3+1,x4+1);
	} else if (PEGS==5) {
		splitcode5(x1,x2,x3,x4,x5,x);
		printf("%d%d%d%d%d ",x1+1,x2+1,x3+1,x4+1,x5+1);
	}
}

// The following is for printcolors(), below. Use whatever letters you want

#if (USECOLORS==1)
#if (COLORS == 4)
char *ccc = "RBYG";
#endif
#if (COLORS == 5)
char *ccc = "RBPYG";
#endif
#if (COLORS == 6)
char *ccc = "RBPCYG";
#endif
#if (COLORS==7)
char *ccc = "RBPCYGZ";
#endif
#if (COLORS==8)
char *ccc = "RBPCYGAE";
#endif
#if (COLORS==9)
char *ccc = "RBPCYGAET";
#endif
#endif
#if (USECOLORS==0)
#if (COLORS == 4)
char *ccc = "1234";
#endif
#if (COLORS == 5)
char *ccc = "12345";
#endif
#if (COLORS == 6)
char *ccc = "123456";
#endif
#if (COLORS==7)
char *ccc = "1234567";
#endif
#if (COLORS==8)
char *ccc = "12345678";
#endif
#if (COLORS==9)
char *ccc = "123456789";
#endif
#endif

// printcolors() prints a compact pattern as colors R through G

void printcolors(int x)
{
	int x1,x2,x3,x4,x5;
	if (PEGS==2) {
		splitcode2(x1,x2,x);
		printf("%c%c ",ccc[x1],ccc[x2]);
	} else if (PEGS==3) {
		splitcode3(x1,x2,x3,x);
		printf("%c%c%c ",ccc[x1],ccc[x2],ccc[x3]);
	} else if (PEGS==4) {
		splitcode(x1,x2,x3,x4,x);
		printf("%c%c%c%c ",ccc[x1],ccc[x2],ccc[x3],ccc[x4]);
	} else if (PEGS==5) {
		splitcode5(x1,x2,x3,x4,x5,x);
		printf("%c%c%c%c%c ",ccc[x1],ccc[x2],ccc[x3],ccc[x4],ccc[x5]);
	}
}

// unpack() is for reading string data from human input and turning it
// into a packed (internal) number.

int unpack(char *line)
{
	int i, j, numbers[40], retval = 0;
	for (i = 0; i < PEGS; i++) {
		numbers[i] = -1;
		for (j = 0; j < COLORS; j++)
			if (ccc[j] == line[i]) numbers[i] = j;
		if (numbers[i] == -1) {
			//fprintf(stderr, "Bad guess: %s\n", line);
			return -1;
		}
	}
	for (j = 0; j < PEGS; j++)
		retval = retval * COLORS + numbers[j];
	return retval;
}

// codes for patterns; B's always before W's

void printcode(int i)
{
#if (PEGS==2)
	switch(i) {
		case 0: printf("none"); break;
		case 1: printf("W"); break;
		case 2: printf("WW"); break;
		case 3: printf("B"); break;
		case 4: printf("BB"); break;
	}
#endif
#if (PEGS==3)
	switch(i) {
		case 0: printf("none"); break;
		case 1: printf("W"); break;
		case 2: printf("WW"); break;
		case 3: printf("WWW"); break;
		case 4: printf("B"); break;
		case 5: printf("BW"); break;
		case 6: printf("BWW"); break;
		case 7: printf("BB"); break;
		case 8: printf("BBB"); break;
	}
#endif
#if (PEGS==4)
	switch(i) {
		case 0: printf("none"); break;
		case 1: printf("W"); break;
		case 2: printf("WW"); break;
		case 3: printf("WWW"); break;
		case 4: printf("WWWW"); break;
		case 5: printf("B"); break;
		case 6: printf("BW"); break;
		case 7: printf("BWW"); break;
		case 8: printf("BWWW"); break;
		case 9: printf("BB"); break;
		case 10: printf("BBW"); break;
		case 11: printf("BBWW"); break;
		case 12: printf("BBB"); break;
		case 13: printf("BBBB"); break;
	}
#endif
#if (PEGS==5)
	switch(i) {
		case 0: printf("none"); break;
		case 1: printf("W"); break;
		case 2: printf("WW"); break;
		case 3: printf("WWW"); break;
		case 4: printf("WWWW"); break;
		case 5: printf("WWWWW"); break;
		case 6: printf("B"); break;
		case 7: printf("BW"); break;
		case 8: printf("BWW"); break;
		case 9: printf("BWWW"); break;
		case 10: printf("BWWWW"); break;
		case 11: printf("BB"); break;
		case 12: printf("BBW"); break;
		case 13: printf("BBWW"); break;
		case 14: printf("BBWWW"); break;
		case 15: printf("BBB"); break;
		case 16: printf("BBBW"); break;
		case 17: printf("BBBWW"); break;
		case 18: printf("BBBB"); break;
		case 19: printf("BBBBB"); break;
	}
#endif
}

int getcode(char *s)
{
	char *p = s;
	while (*p) {*p = toupper(*p); p++;}
#if (PEGS==2)
		if (*s == '\n') return 0;
		if (strcmp(s, "W\n")==0) return 1;
		if (strcmp(s, "WW\n")==0) return 2;
		if (strcmp(s, "B\n")==0) return 3;
		if (strcmp(s, "BB\n")==0) return 4;
		return -1;
#endif
#if (PEGS==3)
		if (*s == '\n') return 0;
		if (strcmp(s, "W\n")==0) return 1;
		if (strcmp(s, "WW\n")==0) return 2;
		if (strcmp(s, "WWW\n")==0) return 3;
		if (strcmp(s, "B\n")==0) return 4;
		if (strcmp(s, "BW\n")==0) return 5;
		if (strcmp(s, "BWW\n")==0) return 6;
		if (strcmp(s, "BB\n")==0) return 7;
		if (strcmp(s, "BBB\n")==0) return 8;
		return -1;
#endif
#if (PEGS==4)
		if (*s == '\n') return 0;
		if (strcmp(s, "W\n")==0) return 1;
		if (strcmp(s, "WW\n")==0) return 2;
		if (strcmp(s, "WWW\n")==0) return 3;
		if (strcmp(s, "WWWW\n")==0) return 4;
		if (strcmp(s, "B\n")==0) return 5;
		if (strcmp(s, "BW\n")==0) return 6;
		if (strcmp(s, "BWW\n")==0) return 7;
		if (strcmp(s, "BWWW\n")==0) return 8;
		if (strcmp(s, "BB\n")==0) return 9;
		if (strcmp(s, "BBW\n")==0) return 10;
		if (strcmp(s, "BBWW\n")==0) return 11;
		if (strcmp(s, "BBB\n")==0) return 12;
		if (strcmp(s, "BBBB\n")==0) return 13;
		return -1;
#endif
#if (PEGS==5)
		if (*s == '\n') return 0;
		if (strcmp(s, "W\n")==0) return 1;
		if (strcmp(s, "WW\n")==0) return 2;
		if (strcmp(s, "WWW\n")==0) return 3;
		if (strcmp(s, "WWWW\n")==0) return 4;
		if (strcmp(s, "WWWWW\n")==0) return 5;
		if (strcmp(s, "B\n")==0) return 6;
		if (strcmp(s, "BW\n")==0) return 7;
		if (strcmp(s, "BWW\n")==0) return 8;
		if (strcmp(s, "BWWW\n")==0) return 9;
		if (strcmp(s, "BWWWW\n")==0) return 10;
		if (strcmp(s, "BB\n")==0) return 11;
		if (strcmp(s, "BBW\n")==0) return 12;
		if (strcmp(s, "BBWW\n")==0) return 13;
		if (strcmp(s, "BBWWW\n")==0) return 14;
		if (strcmp(s, "BBB\n")==0) return 15;
		if (strcmp(s, "BBBW\n")==0) return 16;
		if (strcmp(s, "BBBWW\n")==0) return 17;
		if (strcmp(s, "BBBB\n")==0) return 18;
		if (strcmp(s, "BBBBB\n")==0) return 19;
		return -1;
#endif
}

int ctable[51] = {0,1,2,3,4,5,0,0,0,0,
                  6,7,8,9,10,0,0,0,0,0,
                  11,12,13,14,0,0,0,0,0,0,
                  15,16,17,0,0,0,0,0,0,0,
                  18,0,0,0,0,0,0,0,0,0,19};

int compare(int a, int b) // compares positions a and b, returning the B-W encoding
{
	static int a1,a2,a3,a4,a5, lasta=-1;
	int b1,b2,b3,b4,b5,white,black,i;
	int ca[COLORS], cb[COLORS];

#if (PEGS==2)
	white = black = 0;
	splitcode2(a1,a2,a);
	splitcode2(b1,b2,b);
	for (i = 0; i < COLORS;i++) {ca[i] = cb[i] = 0;}
	if (a1==b1) { black++; a1=b1=-1;} else {ca[a1]++; cb[b1]++;}
	if (a2==b2) { black++; a2=b2=-1;} else {ca[a2]++; cb[b2]++;}
	if (a3==b3) { black++; a3=b3=-1;} else {ca[a3]++; cb[b3]++;}
	for (i = 0; i < COLORS; i++)
		if (ca[i] > 0 && cb[i] > 0) white += minimum(ca[i],cb[i]);
	switch(10*black+white) {
		case 0: return 0;
		case 1: return 1;
		case 2: return 2;
		case 10: return 3;
		case 20: return 4;
	}
	return -1;
#endif
#if (PEGS==3)
	white = black = 0;
	splitcode3(a1,a2,a3,a);
	splitcode3(b1,b2,b3,b);
	for (i = 0; i < COLORS;i++) {ca[i] = cb[i] = 0;}
	if (a1==b1) { black++; a1=b1=-1;} else {ca[a1]++; cb[b1]++;}
	if (a2==b2) { black++; a2=b2=-1;} else {ca[a2]++; cb[b2]++;}
	if (a3==b3) { black++; a3=b3=-1;} else {ca[a3]++; cb[b3]++;}
	for (i = 0; i < COLORS; i++)
		if (ca[i] > 0 && cb[i] > 0) white += minimum(ca[i],cb[i]);
	switch(10*black+white) {
		case 0: return 0;
		case 1: return 1;
		case 2: return 2;
		case 3: return 3;
		case 10: return 4;
		case 11: return 5;
		case 12: return 6;
		case 20: return 7;
		case 30: return 8;
	}
	return -1;
#endif
#if (PEGS==4)
	white = black = 0;
	splitcode(a1,a2,a3,a4,a);
	splitcode(b1,b2,b3,b4,b);
	for (i = 0; i < COLORS;i++) {ca[i] = cb[i] = 0;}
	if (a1==b1) { black++; a1=b1=-1;} else {ca[a1]++; cb[b1]++;}
	if (a2==b2) { black++; a2=b2=-1;} else {ca[a2]++; cb[b2]++;}
	if (a3==b3) { black++; a3=b3=-1;} else {ca[a3]++; cb[b3]++;}
	if (a4==b4) { black++; a4=b4=-1;} else {ca[a4]++; cb[b4]++;}
	for (i = 0; i < COLORS; i++)
		if (ca[i] > 0 && cb[i] > 0) white += minimum(ca[i],cb[i]);
	switch(10*black+white) {
		case 0: return 0;
		case 1: return 1;
		case 2: return 2;
		case 3: return 3;
		case 4: return 4;
		case 10: return 5;
		case 11: return 6;
		case 12: return 7;
		case 13: return 8;
		case 20: return 9;
		case 21: return 10;
		case 22: return 11;
		case 30: return 12;
		case 40: return 13;
	}
	return -1;
#endif
#if (PEGS==5)
	white = black = 0;
	if (lasta != a) {
		splitcode5(a1,a2,a3,a4,a5,a);
		lasta = a;
	}
	splitcode5(b1,b2,b3,b4,b5,b);
	for (i = 0; i < COLORS;i++) {ca[i] = cb[i] = 0;}
	if (a1==b1) { black++; } else {ca[a1]++; cb[b1]++;}
	if (a2==b2) { black++; } else {ca[a2]++; cb[b2]++;}
	if (a3==b3) { black++; } else {ca[a3]++; cb[b3]++;}
	if (a4==b4) { black++; } else {ca[a4]++; cb[b4]++;}
	if (a5==b5) { black++; } else {ca[a5]++; cb[b5]++;}
	for (i = 0; i < COLORS; i++)
		if (ca[i] > 0 && cb[i] > 0) white += minimum(ca[i],cb[i]);
	return ctable[10*black+white];
	switch(10*black+white) {
		case 0: return 0;
		case 1: return 1;
		case 2: return 2;
		case 3: return 3;
		case 4: return 4;
		case 5: return 5;
		case 10: return 6;
		case 11: return 7;
		case 12: return 8;
		case 13: return 9;
		case 14: return 10;
		case 20: return 11;
		case 21: return 12;
		case 22: return 13;
		case 23: return 14;
		case 30: return 15;
		case 31: return 16;
		case 32: return 17;
		case 40: return 18;
		case 50: return 19;
	}
	return -1;
#endif
}

void inittable()
{
	int i, j;
	for (i = 0; i < POSITIONS; i++)
		for (j = i; j < POSITIONS; j++)
			table[i][j] = table[j][i] = compare(i,j);
}

// converttopacked() takes an integer like 1234 (4 pegs, 6 colors) and converts
// it to internal format (internal colors 0, 1, 2 and 3, and then packed)

int converttopacked(int x)
{
	int a,b,c,d,e;
#if (PEGS==2)
	a = x%10; b = (x-a)/10;
	// sanity check:
	if (a>COLORS || b>COLORS || a<1 || b<1) {
		fprintf(stderr, "Screwed up number: %d%d\n", b,a);
		return -1;
	}
	a--; b--;
	return a + COLORS*b;
#endif
#if (PEGS==3)
	a = x%10; x = (x-a)/10;
	b = x%10; c = (x-b)/10;
	// sanity check:
	if (a>COLORS || b>COLORS || c>COLORS || a<1 || b<1 || c<1) {
		fprintf(stderr, "Screwed up number: %d%d%d\n", c,b,a);
		return -1;
	}
	a--; b--; c--;
	return a + COLORS*(b + COLORS*c);
#endif
#if (PEGS==4)
	a = x%10; x = (x-a)/10;
	b = x%10; x = (x-b)/10;
	c = x%10; d = (x-c)/10;
	// sanity check:
	if (a>COLORS || b>COLORS || c>COLORS || d>COLORS || a<1 || b<1 || c<1 || d<1) {
		fprintf(stderr, "Screwed up number: %d%d%d%d\n", d,c,b,a);
		return -1;
	}
	a--; b--; c--; d--;
	return a + COLORS*(b + COLORS*(c+ COLORS*d));
#endif
#if (PEGS==5)
	a = x%10; x = (x-a)/10;
	b = x%10; x = (x-b)/10;
	c = x%10; x = (x-c)/10;
	d = x%10; e = (x-d)/10;
	// sanity check:
	if (a>COLORS || b>COLORS || c>COLORS || d>COLORS || e>COLORS ||
	                                a<1 || b<1 || c<1 || d<1 || e<1) {
		fprintf(stderr, "Screwed up number: %d%d%d%d%d\n", e,d,c,b,a);
		return -1;
	}
	a--; b--; c--; d--; e--;
	return a + COLORS*(b + COLORS*(c+ COLORS*(d+ COLORS*e)));
#endif
}

// eliminate() assumes that you make a guess to determine the secret value.
// Given guess and secret, the response will eliminate a lot of possibilities.
// This routine sets those impossible patterns to zero in the array possible[].

void eliminate(int secret, int guess)
{
	int i;
	int res = table[secret][guess];
	if (DEBUG) {
		printf("guess: ");
		printpattern(guess);
		printf("res: %d ", res); 
		printcode(res); 
		printf("\n");
	}
	for (i = 0; i < POSITIONS; i++)
		if (table[guess][i] != res) possible[i] = 0;
}

void printpossibles()
{
	int i, rowcount = 0, endrow;
	if (PEGS==5) endrow = 10; else endrow = 12;
	for (i = 0; i < POSITIONS; i++) if (possible[i]) {
		printpattern(i);
		if (++rowcount == endrow) {
			printf("\n");
			rowcount = 0;
		}
	}
	printf("\n");
}

void printcolorpossibles()
{
	int i, rowcount = 0, endrow;
	if (PEGS==5) endrow = 10; else endrow = 12;
	for (i = 0; i < POSITIONS; i++) if (possible[i]) {
		printcolors(i);
		if (++rowcount == endrow) {
			printf("\n");
			rowcount = 0;
		}
	}
	printf("\n");
}

int solved() // returns -1 if not solved; otherwise, a possible pattern
{
	int i, count = 0, pos;
	for (i = 0; i < POSITIONS; i++)
		if (possible[i]) {count++; pos = i; if (count == 2) return -1; }
	if (count == 0) return -2;
	if (DEBUG) {printf("Solution: "); printpattern(pos); printf("\n");}
	return pos;
}

// Given a position in the possible[] array, the function entropy() calculates
// the entropy associated with some particular guess. Generally, the larger the
// entropy, the better the move in the sense that it spreads out the possible
// responses maximally.

double entropy(int move)
{
	int i;
	int bins[CODECOUNT];
	double H = 0.0, p;
	int count = 0;
	
	for (i = 0; i < CODECOUNT; i++) bins[i] = 0;
	for (i = 0; i < POSITIONS; i++)
		if (possible[i]) { bins[table[i][move]]++; count++; }
	for (i = 0; i < CODECOUNT; i++)
		if (bins[i]) { p = (float)bins[i]/count; H -= p*log(p); }
	return H;
}

// bestguess() gives the best guess in the entropy sense: what guess will
// divide the remaining possibilities into piles that are as equal as possible.

int bestguess()
{
	int i, j;
	int bins[CODECOUNT];
	int besti = -1;
	float H, bestH = -1.0; // entropy
	
	for (i = 0; i < POSITIONS; i++) if (RESTRICT==0 || possible[i]) {
		for (j = 0; j < CODECOUNT; j++) bins[j] = 0; H = 0.0;
		H = entropy(i);
		if (H == bestH && possible[i]) { besti = i; } // try a possible, if possible
		if (H > bestH) { bestH = H; besti = i; }

	}
	return besti;
}

void shuffle(int *a, int count)
{
	int i, i1, i2, tmp;
	for (i = 0; i < 200; i++) {
		i1 = random()%count;
		i2 = random()%count;
		tmp = a[i1]; a[i1] = a[i2]; a[i2] = tmp;
	}
}

int randomfirstguess() // not great for PEGS==3
{
	int move[PEGS+10];
	int colors[COLORS];
	int i;
	for (i = 0; i < COLORS; i++) colors[i] = i;
	shuffle(colors, COLORS);
	switch (random()%3) {
		case 0: move[0] = 0; move[1]= 1; move[2] = 2; move[3] = 3; move[4] = 4; break;
		case 1: move[0] = 0; move[1]= 0; move[2] = 2; move[3] = 3; move[4] = 4; break;
		case 2: move[0] = 0; move[1]= 0; move[2] = 2; move[3] = 2; move[4] = 3; break;
	}
	shuffle(move, PEGS);
	for (i = 0; i < PEGS; i++) move[i] = colors[move[i]];
	int retval = 0;
	for (i = 0; i < PEGS; i++)
		retval = retval*COLORS + move[i];
	return retval;
}

// The average game length below is calculated assuming that the
// highest-entropy move is made each time

double averagegamelength()
{
	int i, secret, m, len, done, total=0, first, fg;
	double tot;
	int dist[20];
	
	for (i = 0; i < 20; i++) dist[i] = 0;
	dist[1] = 1;
	dist[3] = 42;
	dist[4] = 479;
	dist[5] = 3431;
	dist[6] = 3606;
	dist[7] = 191;
	if (PEGS==4) fg = 1122;
	if (PEGS==5) fg = 11234;
	
	//printf("Best first guess: "); printpattern(bestguess()); printf("\n");
	
	for (secret = 7750; secret < POSITIONS; secret++) {
		printf("secret: "); printpattern(secret); printf("guesses: ");
		initgame();
		len = 0;
		done = 0;
		first = 1;
		while (done == 0) {
			if (first == 1) {m = converttopacked(fg); first = 0; }
			else m=bestguess();
			len++;
			eliminate(secret, m);
			if (m == solved()) done = 1;
			printpattern(m);
		}
		printf(" len: %d\n", len);
		total += len;
		dist[len]++;
		if (secret%50==49) 	for (i = 0; i < 20; i++)
		if (dist[i]>0) printf("games of length %d: %d\n", i, dist[i]);
	}
	printf("total: %d; positions: %d\n", total, POSITIONS);
	for (i = 0; i < 20; i++)
		if (dist[i]>0) printf("games of length %d: %d\n", i, dist[i]);
	return (double)total/POSITIONS;
}

int randomguess()
{
	int i, count = 0, num;
	for (i = 0; i < POSITIONS; i++)
		if (possible[i]) count++;
	num = random() % count;
	for (i = 0; i < POSITIONS; i++)
		if (possible[i]) {
			if (num==0) return i;
			num--;
		}
	return -1;
}

double averageeasylength()
{
	int i, secret, m, len, done, total=0, first, fg,k;
	double tot;
	int dist[20];
	
	for (i = 0; i < 20; i++) dist[i] = 0;
	if (PEGS==4) fg = 1122;
	if (PEGS==5) fg = 12345;
	
	//printf("Best first guess: "); printpattern(bestguess()); printf("\n");
	for (k = 0; k < 10; k++) {
		for (secret = 0; secret < POSITIONS; secret++) {
			//printf("secret: "); printpattern(secret); printf("guesses: ");
			initgame();
			len = 0;
			done = 0;
			while (done == 0) {
				m=randomguess();
				len++;
				eliminate(secret, m);
				if (m == solved()) done = 1;
				//printpattern(m);
			}
			//printf(" len: %d\n", len);
			total += len;
			dist[len]++;
			//if (secret%50==49) 	for (i = 0; i < 20; i++)
			//if (dist[i]>0) printf("games of length %d: %d\n", i, dist[i]);
		}
		printf("total: %d; positions: %d\n", total, POSITIONS);
		for (i = 0; i < 20; i++)
			if (dist[i]>0) printf("games of length %d: %d\n", i, dist[i]);
	}
	return (double)total/POSITIONS;
}

char *getpair(char *line, int *pattern, int *code)
{
	char *s, *send;
	char dummy[10];
	int i;
	s = line;
	while (*s && *s == ' ') s++;
	for (i = 0; i < PEGS; i++)
		if (strchr(ccc, s[i]) == 0) {
			return 0;
		}
	*(s+PEGS) = 0;
	*pattern = unpack(s);
	if (*pattern == -1) return 0;
	s = s+PEGS+1;
	while (*s && *s == ' ') s++;
	if (*s == '0') { *code = 0; return s+1; }
	send = s;
	while (strchr("BW", *send)) send++;
	*send = 0;
	strcpy(dummy, s);
	strcat(dummy, "\n");
	*code = getcode(dummy);
	//printf("pattern: %d, code: %d, %s\n", *pattern, *code, s);
	return send+1;
}

int main(int argc, char **argv)
{
	int secret, guess, moves, done, s, max = 0, g, res, pat, code;
	int secrets[POSITIONS], scount = 0;
	int bins[CODECOUNT];
	char line[1000];
	int totalmoves = 0;
	int i, j, k;
	double H;
	
	if (argc != 2) {
		printf("Usage:\n%s 1: Guess machine's pattern\n"
			   "%s 2: Machine guesses your pattern\n"
			   "%s 3: Find possible patterns knowing secret\n"
			   "%s 4: Find patterns with guesses, responses\n"
			   "%s 5: Guess machine's pattern; show possible responses\n"
			   "%s 6: Machine guesses your pattern; show possible responses\n",
			   argv[0], argv[0], argv[0], argv[0], argv[0], argv[0]);
		return 0;
	}
	res = atoi(argv[1]);
	if (res > 4) { printpossiblepatterns = 1; res -= 4; }

	inittable();
	initgame();
	srandomdev();

	if (res==1) { // standard game
newg:	printf("Guess patterns from colors: %s\n", ccc);
		secret = random()%POSITIONS;
		while (1) {
			g = -1;
			while (g == -1) {
				fgets(line, 99, stdin);
				while ((g = unpack(line)) == -1) {
					fgets(line, 99, stdin);
				}
			}
			printcode(res = table[secret][g]); printf("\n");
			if (printpossiblepatterns) {
				eliminate(secret, g);
				printf("-------- Possible patterns --------\n");
				printcolorpossibles();
				printf("-----------------------------------\n");
			}
			if (res == CODECOUNT-1) {initgame(); goto newg;}
		}
	} else if (res==2) {
newg1:	guess = randomfirstguess();
		printf("Guess: "); printcolors(guess); printf(" B-W response: ");fflush(stdout);
		while (1) {
			fgets(line, 99, stdin);
			while ((g = getcode(line)) == -1)
				fgets(line, 99, stdin);
			if (g == 13) {initgame(); goto newg1;}
			for (i = 0; i < POSITIONS; i++)
				if (table[i][guess] != g) possible[i] = 0;
			res = solved();
			if (res == -2) {
				fprintf(stderr, "Impossible secret position\n");
				initgame(); goto newg1;
			}
			if (res != -1) {
				printf("Solution: "); printcolors(res); printf("\n");
				initgame(); goto newg1;
			}
			if (printpossiblepatterns) {
				printf("-------- Possible patterns --------\n");
				printcolorpossibles();
				printf("-----------------------------------\n");
			}
			printf("Guess: ");
			printcolors(guess = bestguess());
			printf(" B-W response: ");
			fflush(stdout);
		}
	} else if (res == 3) { // Find possible patterns with fixed secret
		char *s, *send;
		int guesses[20], guesscount, done, noguess;
newg2:	initgame();	
		guesscount = 0, noguess = 0;
		printf("Input format: secret guess1 guess2 ...\n>>");
		fflush(stdout);
		fgets(line, 1000, stdin);
		s = send = &line[0];
		while (*send && *send != ' ' && *send != '\n') send++;
		if (*send == '\n') noguess = 1;
		*send = 0;
		secret = unpack(s);
		if (secret == -1) goto newg2;
		s = send = send+1;
		done = 0;
		if (noguess==0) while (done == 0) {
			while (*send && *send != ' ' && *send != '\n') send++;
			if (*send == '\n') done =1;
			*send = 0;
			g = guesses[guesscount++] = unpack(s);
			if (g == -1) goto newg2;
			s = send = send+1;
		}
		for (i = 0; i < guesscount; i++)
			eliminate(secret, guesses[i]);
		scount = 0;
		for (i = 0; i < POSITIONS; i++)
			if (possible[i]) scount++;
		printf("%d total positions:\n", scount);
		printcolorpossibles();
		printf("Best guess (restricted): ");
		RESTRICT = 1;
		printcolors(bestguess()); printf("\n");
		printf("Best guess (unrestricted): ");
		RESTRICT = 0;
		printcolors(bestguess()); printf("\n");
		goto newg2;
	} else if (res == 4) { // Find possible answers with unknown secret
		// input looks like:
		// RGBY BB BRPP BW ...
		char *s, *send;
		int guesses[20], guesscount, done;
newg4: 	initgame();
		guesscount = 0;
		printf("Input format: guess1 rep1 guess2 rep2 ...\n>>");
		fflush(stdout);
		fgets(line, 1000, stdin);
		s = line;
		while (*s) { *s = toupper(*s); s++; }
		s = &line[0];
		done = 0;
		while (done == 0) {
			s = getpair(s, &pat, &code);
			if (s) {
				for (i = 0; i < POSITIONS; i++)
					if (table[i][pat] != code) possible[i] = 0;
			} else done = 1;
		}
		scount = 0;
		for (i = 0; i < POSITIONS; i++)
			if (possible[i]) scount++;
		printf("%d total positions:\n", scount);
		printcolorpossibles();
		printf("Best guess (restricted): ");
		RESTRICT = 1;
		printcolors(bestguess()); printf("\n");
		printf("Best guess (unrestricted): ");
		RESTRICT = 0;
		printcolors(bestguess()); printf("\n");
		goto newg4;
	}
	printf("Unrecognized option: %d\n", res);
	return 1;
	//printf("Average: %g\n", averageeasylength());
	printf("Average: %g\n", averagegamelength());
	return 1;
}