/* Copyright (C) 2003  Robert, dummy@csoft.net */

/*
  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.
  
  This program 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 General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#include <stdio.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

char everything[2000000];
struct word {
	char*	word;
	int	chars[26];
	int	uniqchars;
	int	len;
} words[200000];

void setchar(char c, int chars[26], int* numuniq)
{
	if (c >= 'a' && c <= 'z') {
		if(chars[c-'a'] == 0)
			(*numuniq)++;
		chars[c-'a']++;
	}
}

int testchar(char c, int chars[26])
{
	if (c >= 'a' && c <= 'z')
		return(chars[c-'a']);
	return(0);
}

inline void addchars(int dest[26], const int chars1[26], const int chars2[26])
{
	register int	i;

	for(i=0; i<26; i++)
		dest[i]=chars1[i]+chars2[i];
}

int	maxcount;
char	maxchar;

int alldoubled(const int chars[26])
{
	int	i;
	int	countof1;

	for(maxcount=maxchar=countof1=i=0; i<26; i++) {
		if (chars[i]==1) {
			countof1++;
			if (countof1>1)
				return(0);
		} else if (chars[i]<2)
			return(0);
		if (maxcount<chars[i]) {
			maxcount=chars[i];
			maxchar=i+'a';
		}
	}
	return(1);
}

int checkpalin(const struct word** wordcombin, int numcombinwords)
{
	int	i;
	int	k;
	int	l;
	char	word[10000];

	strcpy(word, wordcombin[0]->word);
	for(i=1; i<numcombinwords; i++)
		strcat(word, wordcombin[i]->word);
	l=strlen(word);
	for(k=0; k<l/2; k++) {
		if (word[k] != word[l-1-k])
			break;
	}
	if(k==l/2) {
		return(1);
	}
	return(0);
}

int eachchardoubled(const struct word** wordcombin, int numcombinwords)
{
	char	word[10000];
	int	charcounts[26];
	int	i;
	int	numlessthan2;

	strcpy(word, wordcombin[0]->word);
	for(i=1; i<numcombinwords; i++)
		strcat(word, wordcombin[i]->word);
	for(i=0; i<26; i++)
		charcounts[i]=0;
	for(i=0; i<strlen(word); i++) {
		charcounts[word[i]-'a']++;
	}
	for(numlessthan2=i=0; i<26; i++) {
		if (charcounts[i]<2)
			numlessthan2++;
		if (numlessthan2>1)
			return(0);
	}
	return(1);
}

void findpalin1(const struct word** words, int numwords,
		const struct word** wordcombin, int numcombinwords)
{
	int	i;
	int	j;
	const struct word* word;

	if (numcombinwords == numwords) {
		if (checkpalin(wordcombin, numcombinwords)) {
			for (i=0; i<numcombinwords; i++)
				printf(" %s", wordcombin[i]->word);
			putchar('\n');
		}
	} else {
		for(i=0; i<numwords; i++) {
			for(j=0; j<numcombinwords; j++)
				if (wordcombin[j] == words[i])
					break;
			if(j==numcombinwords) {
				wordcombin[numcombinwords]=words[i];
				findpalin1(words, numwords,
					   wordcombin, numcombinwords+1);
			}
		}
	}
}

int minwordnum=1520;
//int minwordlen=2399;
//int minwordlen=9999;
//int minwordlen=78;
// optimize
int minwordlen=51;

void findpalin(const struct word** words, int numwords, int charlen)
{
	const struct word* alphabetwords[1520];
	int	i;
	int	significant;

	significant=0;
	//if(eachchardoubled(words, numwords)) {
		if (numwords<minwordnum) {
			minwordnum=numwords;
			printf("%d minwordnum\n",
			       minwordnum);
			significant++;
		}
		if (charlen<minwordlen) {
			minwordlen=charlen;
			printf("%d minwordlen\n",
			       minwordlen);
			significant++;
		}
		if (significant) {
			printf("maxcount=%d, maxchar=%c\n", maxcount,
			       maxchar);
			for (i=0; i<numwords; i++)
				printf(" %s", words[i]->word);
			putchar('\n');
		}
		// findpalin1(words, numwords, alphabetwords, 0);
		if (significant) {
			printf(" -- done\n");
		}
	//}
}

int iter=0;

int findwords(const int chars[26], const struct word* allwords,
	      int numallwords, const struct word** words, int wordnum)
{
	int	i;
	int	j;
	int	len;
	int	totuniq;
	int	newchars[26];
	int	foundword;
	int	printeddiag;

	// optimization
	//if (wordnum>1)
	//	return(0);
	if (wordnum>1500) {
		//printf("length=%d\n", len);
		return(0);
	}
	for(totuniq=len=j=0; j<wordnum; j++) {
		//printf("%s ", words[j]->word);
		len+=words[j]->len;
		totuniq+=words[j]->uniqchars;
	}
	//putchar('\n');
	if (wordnum>0)
		// continue with the next word
		i=(words[wordnum-1]-allwords)+1;
	else
		i=0;
	if (len+allwords[i].len>minwordlen) {
		// binary search
		int	beg;
		int	end;
		int	uniqneeded;

		for (uniqneeded=j=0; j<26; j++)
			if (chars[j] < 2)
				uniqneeded++;
		for(beg=i,end=numallwords; beg<=end;) {
			j=(end+beg)/2;
			if (len+allwords[j].len<minwordlen) {
				end=j-1;
			} else if (len+allwords[j].len>minwordlen) {
				beg=j+1;
			} else {
				break;
			}
		}
		if (beg>end) {
			return(0);
		}
		while (len+allwords[j].len==minwordlen)
			j--;
		i=j+1;
		if (totuniq+allwords[i].uniqchars<26) {
			return(0);
		}
		if (allwords[i].uniqchars<uniqneeded) {
			return(0);
		}
	//} else {
	//	for(j=0; j<wordnum; j++) {
	//		printf("%s ", words[j]->word);
	//	}
	//	putchar('\n');
	}
	for(printeddiag=0; allwords[i].word; i++) {
		if (iter++ > 50000000) {
			exit(0);
		}
		if (totuniq&&allwords[i].len<26-totuniq) {
			printf("breaking at ");
			for(j=0; j<wordnum; j++) {
				printf("%s ", words[j]->word);
			}
			printf("%s\n", allwords[i].word);
			break;
		}
		if(wordnum==0)
			printf("%d %d %s\n", i, allwords[i].uniqchars,
			       allwords[i].word);
		addchars(newchars, chars, allwords[i].chars);
		if (alldoubled(newchars)) {
			words[wordnum] = allwords+i;
			findpalin(words, wordnum+1, len);
		} else {
			// optimization to add:
			//  cache "best uniq chars" to avoid recursive
			//  call
			words[wordnum] = allwords+i;
			//printf("not too long: ");
			//for(j=0; j<wordnum; j++) {
			//	printf("%s ", words[j]->word);
			//}
			//printf("%s\n", allwords[i].word);
			foundword=findwords(newchars, allwords,
					    numallwords, words,
					    wordnum+1);
		}
	}
}

int sortwordfunc(void* a, void* b)
{
	struct word* aa=a;
	struct word* bb=b;

	//return(bb->len - aa->len);
	//return(((bb->uniqchars*30+bb->len) - (aa->uniqchars*30+aa->len)));
	return(((bb->len*32+bb->uniqchars) - (aa->len*32+aa->uniqchars)));
}

void sortwords(struct word* words, int numwords)
{
	qsort(words, numwords, sizeof* words, sortwordfunc);
}

int main()
{
	int	i;
	int	j;
	int	k;
	int	l;
	FILE	*fp;
	const struct word* alphabetwords[755];
	int	chars[26];

	fp=fopen("WORD.LST","r");
	if(!fp){
		perror("WORD.LST");
		return(1);
	}
	i=0;
	j=0;
	while (fgets(everything+i, BUFSIZ, fp)) {
		words[j].word=everything+i;
		l=words[j].len=strlen(words[j].word);
		for(k=0; k<l; k++)
			setchar(words[j].word[k], words[j].chars,
				&words[j].uniqchars);
		j++;
		i+=strlen(everything+i);
		everything[i-1]='\0';
	}
	sortwords(words, j);
	for(i=0;i<26;i++)
		chars[i]=0;
	findwords(chars, words, j, alphabetwords, 0);
	printf("minwordnum=%d\n", minwordnum);
	printf("minwordlen=%d\n", minwordlen);
	fclose(fp);
}