/* Crozzodile v1.0
 * compile with gcc
 * by Chad Hurritz churritz@cts.com
 */
#define CSK 10
#define SSK 3
#define SDSK 2
#define ESK 5

#define RAND(_r) (lrand48()%(_r))

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define MAXTAKE 50
#define MAXTIMESECS 555
#define SEED (time(0)-800000000)
#define MAXWORDS 200
#define MAXWORDSIZE 20
#define GRIDX 20
#define GRIDY 20
#define CHLET 'a'
#define CHLAST 'z'
#define MAXLETTERS (CHLAST-CHLET+1)
#define MAXLETTERSINWORD (MAXWORDS*2*MAXLETTERS)
#define CHINDX(_c) ((int)(unsigned char)(_c) - ((int)(unsigned char)CHLET))
#define CHCHAR(_i) (CHLET+(char)(_i))
#define MAXMATRIXSPACE 200000

#define XMATLOC(_x) (_x)
#define YMATLOC(_y,_size) (((_y)*(2*(_size)-(_y)-1))/2-(_y)-1)
#define MATLOC(_x,_y,_size) (XMATLOC(_x)+YMATLOC(_y,_size))

#define LSTATUS_OUT 0x0
#define LSTATUS_IN 0x1
#define LSTATUS_INTO 0x2

typedef struct letter_t {
	struct letter_t *nextblock, *nextliw, **prevblock, **llob;
	short wordi, pos, matpos;
	char lstatus, c, bc, ec;
} letter_t;

typedef struct word_t {
	letter_t *letters, **wlob;
	long score;
	short wdir, len;
	char str[MAXWORDSIZE+1];
} word_t;

typedef struct alphabet_t {
	letter_t *in_word, *out_word;
	char *matrix;
	int matlen;
} alphabet_t;

#define LOBB(_x,_y) (lob_block+3*((_x)+GRIDX*(_y)))
static letter_t *lob_block[GRIDX*GRIDY*3], liw_block[MAXLETTERSINWORD];
static alphabet_t alphabet[MAXLETTERS];
static word_t the_words[MAXWORDS], *wplaced[MAXWORDS];
static char matspace[MAXMATRIXSPACE], bustbuf[10];
static long matspace_size, word_count, liw_count, wplaced_count = 0;

static void read_words(char *filename)
{
	FILE *fp = fopen(filename, "r");
	char buf[MAXWORDSIZE+2], *str, *end;
	letter_t *liw, **letters, *ll = NULL;
	word_t *w;
	int len, y;
	alphabet_t *alph;

	bzero(alphabet, sizeof(alphabet_t)*MAXLETTERS);
	for (liw_count=word_count=0; fgets(buf, MAXWORDSIZE+2, fp); word_count++) {
		w = the_words + word_count;
		w->len = len = strlen(buf)-1;
		w->score = 1 + SSK*((MAXWORDSIZE-w->len)/SDSK);
		buf[len] = 0;
		strcpy(w->str, buf);
		letters = &w->letters;
		for (end = (str = buf) + len; str < end; str++) {
			len = CHINDX(*str);
			liw = alphabet[len].in_word;
			ll = *letters = alphabet[len].in_word = liw_block+liw_count++;
			ll->matpos = alphabet[len].matlen++;
			letters = &(ll->nextliw);
			ll->c = *str;
			if ((ll->nextblock = liw) != NULL)
				liw->prevblock = &ll->nextblock;
			ll->prevblock = &alphabet[len].in_word;
			ll->wordi = word_count;
			ll->pos = str-buf;
			ll->lstatus = LSTATUS_OUT;
		}
		*letters = NULL;
	}
	for (matspace_size=y=0; yout_word = alph->in_word;
		alph->matrix = matspace+matspace_size;
		len = alph->matlen;
		matspace_size += ((len-1)*len)/2;
	}
	fclose(fp);
}

#define UPL(_l,_i) ((_l)-GRIDX*3*(_i))
#define DOWNL(_l,_i) ((_l)+GRIDX*3*(_i))
#define IUS(_l,_i) ((UPL(_l,_i)-lob_block+GRIDX*3)/(GRIDX*3))
#define IDS(_l,_i) ((DOWNL(_l,_i)-lob_block+GRIDX*3)/(GRIDX*3))
#define IS_UPEVEN(_l,_i) (IUS(_l,_i) == 1)
#define IS_DOWNEVEN(_l,_i) (IDS(_l,_i) == GRIDY)
#define IS_UPSAFE(_l,_i) (IUS(_l,_i) > 0)
#define IS_DOWNSAFE(_l,_i) (IDS(_l,_i) <= GRIDY)
#define LEFTL(_l,_i) ((_l)-3*(_i))
#define RIGHTL(_l,_i) ((_l)+3*(_i))
#define ILS(_l,_i) ((((_l)-lob_block)%(GRIDX*3))-3*(_i))
#define IRS(_l,_i) ((((_l)-lob_block)%(GRIDX*3))+3*(_i))
#define IS_LEFTEVEN(_l,_i) (ILS(_l,_i) == 0)
#define IS_RIGHTEVEN(_l,_i) (IRS(_l,_i) == 3*(GRIDX-1))
#define IS_LEFTSAFE(_l,_i) (ILS(_l,_i) >= 0)
#define IS_RIGHTSAFE(_l,_i) (IRS(_l,_i) < 3*GRIDX)
static int can_place_word(word_t *, int, letter_t **, int);

#define LOBV(_l, _i) (*(long*)(lob+2+(_i)))

static void take_word(word_t *w, letter_t**lob, int dir, letter_t*liwend, int b)
{
	letter_t *liw = w->letters;
	alphabet_t *alph;

	for (; liw != liwend; liw = liw->nextliw) {
		alph = alphabet+CHINDX(liw->c);

		lob = liw->llob;
		if (b) {
			if (liw->nextblock == alph->out_word)
				alph->out_word = liw;
			else {
				*liw->prevblock = liw->nextblock;
				liw->nextblock->prevblock = liw->prevblock;

				if (alph->out_word == NULL) {
					letter_t *ll;
					for (ll = liw; ll->nextblock != NULL; ll = ll->nextblock)
						;
					liw->prevblock = &ll->nextblock;
					ll->nextblock = liw;
					liw->nextblock = NULL;
				}
				else {
					*(liw->prevblock = alph->out_word->prevblock) = liw;
					liw->nextblock = alph->out_word;
					alph->out_word->prevblock = &liw->nextblock;
				}
				alph->out_word = liw;
			}
		}
		liw->lstatus = LSTATUS_OUT;
		if (lob[1] == NULL) {
			*lob = NULL;
		}
		else {
			if (lob[1] != liw) {
				*lob = lob[1];
			}
			lob[1] = NULL;
		}
	}
}

static void take_words(word_t **wpl, letter_t *liwend)
{
	letter_t *liw, **lob;
	word_t *w;

	do {
		--wplaced_count;
		w = wplaced[wplaced_count];
		for (liw = w->letters; liw != liwend; liw = liw->nextliw) {
			liw->lstatus = LSTATUS_OUT;
			lob = liw->llob;
			if (lob[1] == NULL) {
				*lob = NULL;
			}
			else {
				if (lob[1] != liw) {
					*lob = lob[1];
				}
				lob[1] = NULL;
			}
		}
		liwend = NULL;
	} while (wplaced+wplaced_count != wpl);
}

static void print_grid(c, f, best)
	int *c, *f; char *best;
{
	letter_t **lob;
	int x, y;

	*c = 0;
	*f = 0;
	for (y=0; y < GRIDY; y++) {
		for (x=0; x < GRIDX; x++) {
			lob = LOBB(x,y);
			if (*lob == NULL) {
				if (best)
					best[x+y*GRIDX] = '-';
			}
			else {
				(*f)++;
				if (lob[1] != NULL)
					(*c)++;
				if (best)
					best[x+y*GRIDX] = (*lob)->c;
			}
		}
	}
}

static void place_word(word_t *w, letter_t **lob, int dir)
{
	letter_t *liw = w->letters, **lob0, *lw;
	alphabet_t *alph;
	int inc;

	w->wlob = lob;
	if ((w->wdir = dir))
		inc = 3;
	else
		inc = 3*GRIDX;
	do {
		lw = (alph = alphabet+CHINDX(liw->c))->in_word;
		liw->llob = lob;
		if (liw == alph->out_word) {
			alph->out_word = liw->nextblock;
		}
		else {
			alph->in_word = liw;
			*liw->prevblock = liw->nextblock;
			if (liw->nextblock != NULL)
				liw->nextblock->prevblock = liw->prevblock;
			liw->nextblock = lw;
			lw->prevblock = &liw->nextblock;
			liw->prevblock = &alph->in_word;
		}
		liw->lstatus = LSTATUS_IN;
		if (*(lob0 = lob) != NULL) {
			lob0++;
			if (*lob0 != NULL) {
				continue;
			}
		}
		*lob0 = liw;
	} while (lob += inc, (liw = liw->nextliw) != NULL);
}

static letter_t *initial_conflicts(register letter_t *liw,
	register letter_t **lob0, int *ret, int dir)
{
	register letter_t *ll;
	register letter_t **lob2, **lob4, **lob;
	int left_safe, right_safe;
	alphabet_t *alph;
	letter_t *lw;

	if (dir) {
		left_safe = IS_UPSAFE(lob0,1);
		right_safe = IS_DOWNSAFE(lob0,1);
		for (; liw != NULL; liw = liw->nextliw, lob0+=3) {
			if ((ll = *lob0) != NULL
			 && (ll->c != liw->c || the_words[ll->wordi].wdir == dir
			  || ((ll = lob0[1]) != NULL && the_words[ll->wordi].wdir == dir)))
				break;
			liw->bc = liw->ec = 0;
			if (*(liw->llob=lob=lob0) == NULL) {
				if (left_safe) {
					if ((ll = *(lob2 = UPL(lob0,1))) != NULL) {
						liw->bc = ll->c;
						if ( ! (the_words[ll->wordi].wdir) || lob2[1] != NULL)
							break;
					}
				}
				if (right_safe) {
					if ((ll = *(lob4 = DOWNL(lob0,1))) != NULL) {
						liw->ec = ll->c;
						if ( ! (the_words[ll->wordi].wdir) || lob4[1] != NULL)
							break;
					}
				}
			}
			else {
				(*ret) += CSK;
				lob++;
			}
			lw = (alph = alphabet+CHINDX(liw->c))->in_word;
			liw->lstatus = LSTATUS_IN;
			*lob = liw;
		}
	}
	else {
		left_safe = IS_LEFTSAFE(lob0,1);
		right_safe = IS_RIGHTSAFE(lob0,1);
		for (; liw != NULL; liw = liw->nextliw, lob0+=3*GRIDX) {
			if ((ll = *lob0) != NULL
			 && (ll->c != liw->c || the_words[ll->wordi].wdir == dir
			  || ((ll = lob0[1]) != NULL && the_words[ll->wordi].wdir == dir)))
				break;
			liw->bc = liw->ec = 0;
			if (*(liw->llob=lob=lob0) == NULL) {
				if (left_safe) {
					if ((ll = *(lob2 = LEFTL(lob0,1))) != NULL) {
						liw->bc = ll->c;
						if ( (the_words[ll->wordi].wdir) || lob2[1] != NULL)
							break;
					}
				}
				if (right_safe) {
					if ((ll = *(lob4 = RIGHTL(lob0,1))) != NULL) {
						liw->ec = ll->c;
						if ( (the_words[ll->wordi].wdir) || lob4[1] != NULL)
							break;
					}
				}
			}
			else {
				(*ret) += CSK;
				lob++;
			}
			lw = (alph = alphabet+CHINDX(liw->c))->in_word;
			liw->lstatus = LSTATUS_IN;
			*lob = liw;
		}
	}
	return liw;
}

static int recursive_check(register letter_t *liw, int ret, int dir, int spec)
{
	int cp, tmpret;
	word_t **wpl;
	letter_t **lob, *lll;
	register letter_t *ll;
	char *ymatlock, *matlock, c2, c3;
	alphabet_t *alph;

	for (; liw != NULL; liw = liw->nextliw) {
		if (liw->bc || liw->ec) {
			lob = liw->llob;
			if (lob[1] != NULL)
				continue;
			alph = alphabet+CHINDX(liw->c);
			if (liw->bc) {
				ll = alphabet[CHINDX(liw->bc)].out_word;
				c2 = liw->c;
				c3 = liw->ec;
			}
			else {
				ll = alph->out_word;
				c2 = liw->ec;
				c3 = 0;
			}
			ymatlock = alph->matrix+YMATLOC(liw->matpos,alph->matlen);
			for (; ll != NULL; ll = ll->nextblock) {
				if (ll->lstatus == LSTATUS_OUT && ll->nextliw != NULL
				 && ll->nextliw->c == c2 && (c3 ? ll->nextliw->nextliw != NULL
				 && ll->nextliw->nextliw->c == c3 : 1)) {
					wpl = wplaced+wplaced_count;
					lll = (liw->bc) ? ll->nextliw : ll;
					if (liw->matpos < lll->matpos)
						matlock = ymatlock+lll->matpos;
					else {
						cp = lll->matpos;
						matlock = alph->matrix+MATLOC(liw->matpos,cp,alph->matlen);
					}
					if (*matlock)
						continue;
					if ((cp = can_place_word(the_words+ll->wordi, lll->pos, lob,
					 !dir))) {
						if (spec) {
							take_words(wpl, NULL);
							ret = 2;
							break;
						}
						else
						if ((tmpret=recursive_check(liw->nextliw, ret+4*cp/3,dir,0))){
							liw = NULL;
							ret = tmpret;
							break;
						}
						else
							take_words(wpl, NULL);
					}
				}
			}
			if (ll == NULL) {
				ret = 0;
				break;
			}
		}
		if (liw == NULL)
			break;
	}
	return ret;
}

static int can_place_word(word_t *w, int i, letter_t **lob, int dir)
{
	letter_t *liw, **lob0;
	int ret;
	word_t **wpl;

	if (dir ? ((IS_LEFTSAFE(lob0=LEFTL(lob,i),1) ? *LEFTL(lob0,1) == NULL
	  : IS_LEFTEVEN(lob,i)) && (IS_RIGHTSAFE(lob0,w->len)
		? *RIGHTL(lob0,w->len) == NULL : IS_RIGHTEVEN(lob0,w->len-1)))
	 : ((IS_UPSAFE(lob0=UPL(lob,i),1) ? *UPL(lob0,1) == NULL
	  : IS_UPEVEN(lob,i)) && (IS_DOWNSAFE(lob0,w->len)
		? *DOWNL(lob0,w->len) == NULL : IS_DOWNEVEN(lob0,w->len-1)))
	 ) {
		ret = w->score;
		if (dir) {
			ret += (IS_LEFTEVEN(lob,i)?ESK:0)+(IS_RIGHTEVEN(lob0,w->len-1)?ESK:0);
		}
		else {
			ret += (IS_UPEVEN(lob,i)?ESK:0)+(IS_DOWNEVEN(lob0,w->len-1)?ESK:0);
		}
		wpl = wplaced+wplaced_count++;
		*wpl = w;
		w->wdir = dir;
		w->wlob = lob0;
		if ((liw = initial_conflicts(w->letters, lob0, &ret, dir)) == NULL) {
			switch (recursive_check(w->letters, 1, dir, 1)) {
			case 0: ret = 0; break;
			case 2: ret = recursive_check(w->letters, ret, dir, 0); break;
			}
		}
		else
			ret = 0;
		if (ret == 0)
			take_words(wpl, liw);
	}
	else
		ret = 0;
	return ret;
}

static void shuffle()
{
	int i;
	letter_t *liw;
	alphabet_t *alph;

	bzero(lob_block, sizeof(letter_t*)*3*GRIDX*GRIDY);
	for (i = 0; i < MAXLETTERS; i++) {
		alph = alphabet+i;
		liw = alph->in_word;
		for (; liw != NULL && liw->lstatus == LSTATUS_IN; ) {
			liw->lstatus = LSTATUS_OUT;
			liw = liw->nextblock;
		}
		alph->out_word = alph->in_word;
	}
}

static int try()
{
	word_t wbest[MAXTAKE], *wp;
	int wbest_count, wbest_cp, words = 1, i, y;
	letter_t *beg;
	word_t *woid;
	char *wbest_matlock;
	register letter_t *liw = NULL, *ll;
	register char *ymatlock, *matlock;
	register alphabet_t *alph;
	register int cp, liwoidir;

	shuffle();
	wp = the_words+RAND(word_count);
	if (RAND(2))
		place_word(wp, LOBB(RAND(GRIDX), RAND(GRIDY-wp->len+1)), 0);
	else
		place_word(wp, LOBB(RAND(GRIDX-wp->len+1), RAND(GRIDY)), 1);
	bzero(matspace, matspace_size*sizeof(char));
	for (;;) {
		wbest_count = wbest_cp = 0;
		for (i=0; iout_word;
			if (beg == NULL)
				continue;
			liw = alphabet[i].in_word;
			for (; liw != NULL && liw->lstatus == LSTATUS_IN;
			 liw = liw->nextblock) {
				if (liw->llob[1] != NULL)
					continue;
				liwoidir = !the_words[liw->wordi].wdir;
				ymatlock = alph->matrix+YMATLOC(liw->matpos,alph->matlen);
				for (ll = beg; ll != NULL; ll = ll->nextblock) {
					if (liw->matpos < ll->matpos)
						matlock = ymatlock+ll->matpos;
					else {
						y = ll->matpos;
						matlock = alph->matrix+MATLOC(liw->matpos,y,alph->matlen);
					}
					if (*matlock)
						continue;
					if ((cp = can_place_word(the_words+ll->wordi,
					 ll->pos, liw->llob, liwoidir))) {
						if (cp > wbest_cp) {
							wbest_count = wplaced_count;
							wbest_cp = cp;
							wbest_matlock = matlock;
							while (wplaced_count) {
								woid = wplaced[--wplaced_count];
								take_word(woid, woid->wlob, woid->wdir, NULL, 0);
								wbest[wplaced_count] = *woid;
							}
						}
						else {
							while (wplaced_count) {
								woid = wplaced[--wplaced_count];
								take_word(woid, woid->wlob, woid->wdir, NULL, 0);
							}
						}
					}
					else
						*matlock = 1;
				}
			}
		}
		if (wbest_count) {
			words += wbest_count;
			while (wbest_count--) {
				woid = &(wbest[wbest_count]);
				place_word(the_words+woid->letters->wordi, woid->wlob, woid->wdir);
			}
		}
		else
			break;
	}
	return words;
}

int main(int argc, char *argv[])
{
	int crosses = 0, filled = 0, words = 0, c = SEED, f, w, x;
	char best[GRIDX*GRIDY];
	float Hertz=sysconf(_SC_CLK_TCK);
	struct tms TMS;

	wplaced_count = 0;
	sprintf(bustbuf, "%%-%d.%ds\n", GRIDY, GRIDY);
	srand48(c);
	read_words(argv[1]);
	for (;;) {
		times(&TMS);
		if ((float)(TMS.tms_stime + TMS.tms_utime)/Hertz >= MAXTIMESECS)
			break;
		w = try();
		print_grid(&c, &f, NULL);
		if (w > words || (w == words && (c > crosses || (c == crosses
		 && f > filled)))) {
			words = w;
			crosses = c;
			filled = f;
			print_grid(&c, &f, best);
		}
	}
	for (x=0; x < GRIDY; x++)
		printf(bustbuf, best+x*GRIDX);
	return 0;
}












Make your own free website on Tripod.com