/* mines.c   by Michael Thorpe and Graham Hughes   2011-04-11 */

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <curses.h>

#define USAGE "usage: mines [-dfh] [-ms <#>]\n"

#define MAX_GUESSES  100
#define SLEEP_LEN    2500
#define GUESS_LEN    1000000
#define CHAR_THINK   '+'
#define CHAR_NOLONG  '_'
#define CHAR_BLANK   ' '
#define CHAR_FLAG    'F'

unsigned short board_width=80,board_height=24;

typedef void (*atexitfunc)(void);

int togo;
int minestogo;
int nummines=-1;
int dolongscan=1;
int slow_mode=0; /* Pauses SLEEP_LEN usec after each automatic guess */
int demomode=0; /* Guesses and sleeps GUESS_LEN usec over and over*/
int numshortscans=0,numlongscans=0;
char **board,**imagined;

int shortscan();
int longscan();
int clickat(int y,int x);
void flagat(int y,int x);

int shortscan() {
	int x,y,flags,blanks;
	int doagain=0;

	numshortscans++;
	for(y=0;y<board_height;y++) {
		for(x=0;x<board_width;x++) { 
			if (imagined[y][x] >= '0' && imagined[y][x] <= '9') {
				flags=imagined[y][x]-'0';
				blanks=0;
				if(y>0) {
					if(x>0 && CHAR_FLAG==imagined[y-1][x-1]) flags--;
					if(CHAR_FLAG==imagined[y-1][x]) flags--;
					if(x<board_width-1 && CHAR_FLAG==imagined[y-1][x+1]) flags--;
				}
				if(x>0 && CHAR_FLAG==imagined[y][x-1]) flags--;
				if(x<board_width-1 && CHAR_FLAG==imagined[y][x+1]) flags--;
				if(y<board_height-1) {
					if(x>0 && CHAR_FLAG==imagined[y+1][x-1]) flags--;
					if(CHAR_FLAG==imagined[y+1][x]) flags--;
					if(x<board_width-1 && CHAR_FLAG==imagined[y+1][x+1]) flags--;
				}

				if(y>0) {
					if(x>0 && CHAR_BLANK==imagined[y-1][x-1]) blanks++;
					if(CHAR_BLANK==imagined[y-1][x]) blanks++;
					if(x<board_width-1 && CHAR_BLANK==imagined[y-1][x+1]) blanks++;
				}
				if(x>0 && CHAR_BLANK==imagined[y][x-1]) blanks++;
				if(x<board_width-1 && CHAR_BLANK==imagined[y][x+1]) blanks++;
				if(y<board_height-1) {
					if(x>0 && CHAR_BLANK==imagined[y+1][x-1]) blanks++;
					if(CHAR_BLANK==imagined[y+1][x]) blanks++;
					if(x<board_width-1 && CHAR_BLANK==imagined[y+1][x+1]) blanks++;
				}
				if(flags==0) {
					if(y>0) {
						if(x>0 && CHAR_BLANK==imagined[y-1][x-1])
							clickat(y-1,x-1), doagain=1;
						if(CHAR_BLANK==imagined[y-1][x]) clickat(y-1,x), doagain=1;
						if(x<board_width-1 && CHAR_BLANK==imagined[y-1][x+1])
							clickat(y-1,x+1), doagain=1;
					}
					if(x>0 && CHAR_BLANK==imagined[y][x-1]) clickat(y,x-1), doagain=1;
					if(x<board_width-1 && CHAR_BLANK==imagined[y][x+1])
						clickat(y,x+1), doagain=1;
					if(y<board_height-1) {
						if(x>0 && CHAR_BLANK==imagined[y+1][x-1])
							clickat(y+1,x-1), doagain=1;
						if(CHAR_BLANK==imagined[y+1][x]) clickat(y+1,x), doagain=1;
						if(x<board_width-1 && CHAR_BLANK==imagined[y+1][x+1])
							clickat(y+1,x+1), doagain=1;
					}
				} else if (blanks <= flags) {
					if(y>0) {
						if(x>0 && CHAR_BLANK==imagined[y-1][x-1])
							flagat(y-1,x-1), doagain=1;
						if(CHAR_BLANK==imagined[y-1][x]) flagat(y-1,x), doagain=1;
						if(x<board_width-1 && CHAR_BLANK==imagined[y-1][x+1])
							flagat(y-1,x+1), doagain=1;
					}
					if(x>0 && CHAR_BLANK==imagined[y][x-1]) flagat(y,x-1), doagain=1;
					if(x<board_width-1 && CHAR_BLANK==imagined[y][x+1])
						flagat(y,x+1), doagain=1;
					if(y<board_height-1) {
						if(x>0 && CHAR_BLANK==imagined[y+1][x-1])
							flagat(y+1,x-1), doagain=1;
						if(CHAR_BLANK==imagined[y+1][x]) flagat(y+1,x), doagain=1;
						if(x<board_width-1 && CHAR_BLANK==imagined[y+1][x+1])
							flagat(y+1,x+1), doagain=1;
					}
				}
			}
		}
	}
	return doagain;
}

typedef struct ls ls;
struct ls {
	ls *next,*prev;
	int n,min,max;
	int x[8],y[8];
};

ls *base,*last;
int numalloced=0;
#ifdef DEBUG
FILE *debug=0;
#endif

void fputls(FILE *f,ls *a) {
	int i;

	fprintf(f,"{%p:%d-%d",a,a->min,a->max);
	for(i=0;i<a->n;i++)
		fprintf(f,",(%d,%d)",a->x[i],a->y[i]);
	fprintf(f,"}");
}

ls *newls(int min,int max) {
	ls *new;

	if(0==(new=(ls *)malloc(sizeof(ls))))
		return(0);
	new->next=0;
	new->prev=last;
	if(base) {
		last->next=new;
		last=new;
	} else
		base=last=new;
	new->min=min;
	new->max=max;
	new->n=0;
	numalloced++;
	return(new);
}

void rmls(ls *a) {
	if(a==0)
		return;
	if(a->prev)
		a->prev->next=a->next;
	if(a->next)
		a->next->prev=a->prev;
	if(a==base)
		base=a->next;
	if(a==last)
		last=a->prev;
	numalloced--;
	free(a);
}

int lsintsize(ls *a,ls *b) {
	int i,j,k=0;

	for(i=0;i<a->n;i++)
		for(j=0;j<b->n;j++)
			if(a->x[i]==b->x[j] && a->y[i]==b->y[j])
				k++;
#ifdef DEBUG
	if(k) {
		fprintf(debug,"lsintsize(");
		fputls(debug,a);
		fprintf(debug,",");
		fputls(debug,b);
		fprintf(debug,")=%d\n",k);
	}
#endif
	return(k);
}

ls *lssub(ls *a,ls *b) {
	int i,j;
	ls *t;

	t=newls(a->min-b->max,a->max-b->min);
	for(i=j=0;i<a->n;i++) {
		if(j<b->n && a->x[i]==b->x[j] && a->y[i]==b->y[j])
			j++;
		else
			t->x[t->n]=a->x[i],t->y[t->n++]=a->y[i];
	}
#ifdef DEBUG
	if(j != b->n) {
		fprintf(debug,"Whathefuck? lssub(%p,%p) {j=%d}\na=",a,b,j,b->n);
		fputls(debug,a);
		fprintf(debug,"\nb=");
		fputls(debug,b);
		fprintf(debug,"\nt=");
		fputls(debug,t);
		fprintf(debug,"\n");
	}
	fprintf(debug,"lssub(");
	fputls(debug,a);
	fprintf(debug,",");
	fputls(debug,b);
	fprintf(debug,")=");
	fputls(debug,t);
	fprintf(debug,"\n");
#endif
	return(t);
}

int longscan() {
	int i,j,x,y,res=0;
	ls *a,*b,*c,*d;

	numlongscans++;
	base=last=0;
	for(y=0;y<board_height;y++) {
		for(x=0;x<board_width;x++) {
			j=0;
			if(!isdigit(imagined[y][x]))
				continue;
			if(y>0) {
				if(x>0 && CHAR_BLANK==imagined[y-1][x-1]) j++;
				if(CHAR_BLANK==imagined[y-1][x]) j++;
				if(x<board_width-1 && CHAR_BLANK==imagined[y-1][x+1]) j++;
			}
			if(x>0 && CHAR_BLANK==imagined[y][x-1]) j++;
			if(x<board_width-1 && CHAR_BLANK==imagined[y][x+1]) j++;
			if(y<board_height-1) {
				if(x>0 && CHAR_BLANK==imagined[y+1][x-1]) j++;
				if(CHAR_BLANK==imagined[y+1][x]) j++;
				if(x<board_width-1 && CHAR_BLANK==imagined[y+1][x+1]) j++;
			}
			if(j==0)
				continue;
			i=imagined[y][x]-'0';
			if(y>0) {
				if(x>0 && CHAR_FLAG==imagined[y-1][x-1]) i--;
				if(CHAR_FLAG==imagined[y-1][x]) i--;
				if(x<board_width-1 && CHAR_FLAG==imagined[y-1][x+1]) i--;
			}
			if(x>0 && CHAR_FLAG==imagined[y][x-1]) i--;
			if(x<board_width-1 && CHAR_FLAG==imagined[y][x+1]) i--;
			if(y<board_height-1) {
				if(x>0 && CHAR_FLAG==imagined[y+1][x-1]) i--;
				if(CHAR_FLAG==imagined[y+1][x]) i--;
				if(x<board_width-1 && CHAR_FLAG==imagined[y+1][x+1]) i--;
			}
#ifdef DEBUG
			if(i<=0 || i>=j) {
				fprintf(debug,"Whatthefuck?!?!? Why is i=%d,j=%d at (%d,%d)?\n",i,j,x,y);
				fprintf(debug,"board=\"");
				for(j=y-1;j<y+2;j++)
					for(i=x-1;i<x+2;i++)
						fprintf(debug,"%c",(i>=0&&j>=0&&i<board_width&&j<board_height?board[j][i]:'?'));
				fprintf(debug,"\",imagined=\"");
				for(j=y-1;j<y+2;j++)
					for(i=x-1;i<x+2;i++)
						fprintf(debug,"%c",(i>=0&&j>=0&&i<board_width&&j<board_height?imagined[j][i]:'?'));
				fprintf(debug,"\"\n");
			}
#endif
			if(0==(a=newls(i,i)))
				goto cleanup;
			if(y>0) {
				if(x>0 && CHAR_BLANK==imagined[y-1][x-1]) a->x[a->n]=x-1,a->y[a->n++]=y-1;
				if(CHAR_BLANK==imagined[y-1][x]) a->x[a->n]=x,a->y[a->n++]=y-1;
				if(x<board_width-1 && CHAR_BLANK==imagined[y-1][x+1]) a->x[a->n]=x+1,a->y[a->n++]=y-1;
			}
			if(x>0 && CHAR_BLANK==imagined[y][x-1]) a->x[a->n]=x-1,a->y[a->n++]=y;
			if(x<board_width-1 && CHAR_BLANK==imagined[y][x+1]) a->x[a->n]=x+1,a->y[a->n++]=y;
			if(y<board_height-1) {
				if(x>0 && CHAR_BLANK==imagined[y+1][x-1]) a->x[a->n]=x-1,a->y[a->n++]=y+1;
				if(CHAR_BLANK==imagined[y+1][x]) a->x[a->n]=x,a->y[a->n++]=y+1;
				if(x<board_width-1 && CHAR_BLANK==imagined[y+1][x+1]) a->x[a->n]=x+1,a->y[a->n++]=y+1;
			}
#ifdef DEBUG
			fprintf(debug,"Created    ");fputls(debug,a);fprintf(debug,"\n");
#endif
		}
	}
	for(a=base;a != last;a=a->next) {
		c=last;
		for(b=a->next;b != c->next;b=b->next) {
			if(a->n==0 || b->n==0)
				continue;
			if(a->n==b->n)
				continue;
			i=lsintsize(a,b);
			if(i==a->n && i<b->n)
				d=lssub(b,a);
			else if(i==b->n && i<a->n)
				d=lssub(a,b);
			else
				continue;
			if(d->max==0) {
				for(i=0;i<d->n;i++)
					if(imagined[d->y[i]][d->x[i]]==CHAR_BLANK) {
						clickat(d->y[i],d->x[i]);
						res++;
					}
				rmls(d);
			} else if(d->min==d->n) {
				for(i=0;i<d->n;i++)
					if(imagined[d->y[i]][d->x[i]]==CHAR_BLANK) {
						flagat(d->y[i],d->x[i]);
						res++;
					}
				rmls(d);
			}
		}
	}
cleanup:
	if(base) {
		for(a=(b=base)->next;a;a=(b=a)->next) {
			free(b);
			numalloced--;
		}
		free(b);
		numalloced--;
	}
	return(res);
}

int clickat(int y,int x) {
	int i,j;

#ifdef DEBUG
	fprintf(debug,"clickat(%d,%d)\n",y,x);
#endif
	if(board[y][x]=='*') {
		imagined[y][x]='X';
		for(i=0;i<board_height;i++)
			for(j=0;j<board_width;j++)
				mvaddch(i,j,imagined[i][j]==CHAR_BLANK?board[i][j]:
					(y==i && x==j)?'X':
					((board[i][j]=='*') != (imagined[i][j]==CHAR_FLAG))?'!':
					imagined[i][j]);
		move(y,x);
		togo=0;
		minestogo=0;
	} else if (imagined[y][x]==CHAR_FLAG || imagined[y][x]==CHAR_BLANK) {
		if(imagined[y][x]==CHAR_BLANK)
			togo--;
		i=0;
		if(y>0) {
			if(x>0 && '*'==board[y-1][x-1]) i++;
			if('*'==board[y-1][x]) i++;
			if(x<board_width-1 && '*'==board[y-1][x+1]) i++;
		}
		if(x>0 && '*'==board[y][x-1]) i++;
		if(x<board_width-1 && '*'==board[y][x+1]) i++;
		if(y<board_height-1) {
			if(x>0 && '*'==board[y+1][x-1]) i++;
			if('*'==board[y+1][x]) i++;
			if(x<board_width-1 && '*'==board[y+1][x+1]) i++;
		}
		imagined[y][x]='0'+i;
		mvaddch(y,x,'0'+i);
		if(slow_mode) {
			refresh();
			usleep(SLEEP_LEN);
		}
		return(1);
	}
	return(0);
}

void flagat(int y, int x) {
	if(imagined[y][x]<'0' || imagined[y][x]>'9') {
		if(imagined[y][x] == CHAR_FLAG) {
			imagined[y][x] = CHAR_BLANK;
			togo++;
			minestogo++;
		} else {
			imagined[y][x] = CHAR_FLAG;
			togo--;
			minestogo--;
		}
		mvaddch(y,x,imagined[y][x]);
	}
}

void ponder(int y,int x) {
	move(board_height,0);
	printw("%c",CHAR_THINK);
	move(y,x);
	refresh();
	while(0<togo && (shortscan() || (dolongscan && longscan())))
		;
}

int parseargs(int argc,char **argv) {
	int c;
	char *s;

	while(EOF != (c=getopt(argc,argv,"+dhlm:r:s")) && (c != '?')) {
		switch(c) {
		case 'd':
			demomode=1;
			break;
		case 'h':
			fputs(USAGE,stdout);
			fputs(
"   -d      demo mode\n"
"   -h      show this help message\n"
"   -l      turn off longscan\n"
"   -m <#>  set number of mines in play\n"
"   -r <#>  set initial random seed\n"
"   -s      slow down automatic guesses\n"
			,stdout);
			exit(0);
			break;
		case 'l':
			dolongscan=0;
			break;
		case 'm':
			nummines=strtoul(optarg,&s,10);
			if(*s)
				goto badargs;
			break;
		case 'r':
			srand(strtoul(optarg,&s,10));
			if(*s)
				goto badargs;
			break;
		case 's':
			slow_mode=1;
			break;
		default:
			fprintf(stderr,"Error: getopt returned '%c'\n",c);
			return(1);
			break;
		}
	}
	if(optind<argc) {
badargs:
		fputs(USAGE,stderr);
		return(1);
	}
	return(0);
}

int main(int argc,char **argv) {
	int c,i,j,k,x=0,y=0;
	char *tmp;

	srand(time(0)+getpid());
#ifdef DEBUG
	if(0==(debug=fopen("debug.log","w"))) {
		fprintf(stderr,"Couldn't open debug.log\n");
		exit(-1);
	}
#endif
	if(parseargs(argc,argv))
		return(1);
	initscr();
	board_height=LINES-1;
	board_width=COLS;
	atexit((atexitfunc)endwin);
	if(nummines<0)
		nummines=(board_width*board_height/5);
	if(0==(tmp=(char *)malloc(board_width*board_height))) {
		fprintf(stderr,"Couldn't alloc %d bytes\n",(int)board_width*board_height);
		return(-1);
	}
	if(0==(board=(char **)malloc(board_height*sizeof(char *)))) {
		fprintf(stderr,"Couldn't alloc %d bytes\n",(int)board_height*sizeof(char *));
		return(-1);
	}
	for(i=0;i<board_height;i++) {
		board[i]=&tmp[i*board_width];
		for(j=0;j<board_width;j++)
			board[i][j]=' ';
	}
	if(0==(tmp=(char *)malloc(board_width*board_height))) {
		fprintf(stderr,"Couldn't alloc %d bytes\n",(int)board_width*board_height);
		return(-1);
	}
	if(0==(imagined=(char **)malloc(board_height*sizeof(char *)))) {
		fprintf(stderr,"Couldn't alloc %d bytes\n",(int)board_height*sizeof(char *));
		return(-1);
	}
	for(i=0;i<board_height;i++) {
		imagined[i]=&tmp[i*board_width];
		for(j=0;j<board_width;j++)
			imagined[i][j]=CHAR_BLANK;
	}
	togo=board_height*board_width;
	minestogo=0;
/* FIXME: Either place or remove mines, whichever will be faster */
	for(i=0;i<nummines;i++) {
		do {
			j=rand()%board_height;
			k=rand()%board_width;
		} while(board[j][k]=='*');
		board[j][k]='*';
	}
	minestogo=nummines;
	cbreak();
	atexit((atexitfunc)echo);
	noecho();
	for(i=0;i<board_height;i++) {
		move(i,0);
		for(j=0;j<board_width;j++)
			addch(CHAR_BLANK);
	}
	move(board_height,0);
	printw("%c%d,%d (%d,%d)",(dolongscan?' ':CHAR_NOLONG),x,y,togo,minestogo);
	move(y,x);
	refresh();
	c='g';
	while(0<togo && (demomode || EOF != (c=getch()))) {
		switch(c) {
		case 12: /* Ctrl-L */
			wrefresh(curscr);
			break;
		case 'h': case 'D':
			if(x>0)
				x--;
			break;
		case 'j': case 'B':
			if(y<board_height-1)
				y++;
			break;
		case 'k': case 'A':
			if(y>0)
				y--;
			break;
		case 'l': case 'C':
			if(x<board_width-1)
				x++;
			break;
		case 'q':
			togo=0;
			break;
		case 'x':
			if(clickat(y,x))
				ponder(y,x);
			break;
		case 'f':
			flagat(y,x);
			ponder(y,x);
			break;
		case 'g':
/* FIXME: How do we merge this in with ponder()? */
			move(board_height,0);
			printw("%c",CHAR_THINK);
			move(y,x);
			refresh();
			for(k=0;k<MAX_GUESSES;k++) {
				i=rand()%board_height;
				j=rand()%board_width;
				if(board[i][j]==' ' && imagined[i][j]==CHAR_BLANK) {
					if(clickat(i,j))
						while(0<togo && (shortscan() || (dolongscan && longscan())))
							;
					k=MAX_GUESSES;
				}
			}
			break;
		case 'L':
			dolongscan^=1;
			ponder(y,x);
			break;
		default:
			break;
		}
		move(board_height,0);
		printw("%c%d,%d (%d,%d)",(dolongscan?' ':CHAR_NOLONG),x,y,togo,minestogo);
		clrtoeol();
		move(y,x);
		refresh();
		if(demomode && 0<togo)
			usleep(GUESS_LEN);
	}
	move(board_height,0);
	clrtoeol();
	refresh();
	endwin();
	if(numalloced)
		fprintf(stderr,"numalloced=%d\n",numalloced);
	return(0);
}