from collections import defaultdict
import re
from math import factorial

class Word:
	def __init__(self, word):
		self.word = word
		self.r = ''
		self.x = ''
		self.guessed = ''
		self.mask = re.sub(r'[a-z]', '_', word)
		self.remaining = word
		self.index = 0
		self.won = False
		self.lost = False
		self.indexes = []
	def isEnded(self):
		return self.won or self.lost
	def move(self, d):
		while d[self.index] in self.guessed:
			if d[self.index] in self.r:
				self.index += 1
			else:
				R = 12-len(self.r)
				X = 6-len(self.x)
				try:
					self.index += factorial(X+R)/factorial(R)/factorial(X)
				except:
					print self.word, self.guessed, self.r, self.x, self.index, self.mask, self.remaining
					raise
			self.index = (self.index%len(d))
	def update(self, d):
		# bestLetter may already have been guessed for this word
		self.move(d)
		while d[self.index] != '.' and not self.isEnded():
			if d[self.index] in self.remaining:
				self.r += d[self.index]
			else:
				self.x += d[self.index]
			self.guessed += d[self.index]
			self.indexes.append(self.index)
			for letterIndex in range(len(self.mask)):
				if self.word[letterIndex] == d[self.index]:
					self.mask = self.mask[:letterIndex]+d[self.index]+self.mask[letterIndex+1:]
			self.remaining = self.remaining.replace(d[self.index], '_')
			if len(self.x) == 6:
				self.lost = True
			elif '_' not in self.mask:
				self.won = True
			else:
				self.move(d)

class Words:
	def __init__(self, words):
		self.words = []
		for word in words:
			self.words.append(Word(word))
	def allEnded(self):
		for word in self.words:
			if not word.isEnded():
				return False
		return True
	def getBestIndex(self):
		count = defaultdict(int)
		bestCount = 0
		bestIndex = 0
		for word in self.words:
			if not word.isEnded():
				count[word.index]+=1
				if count[word.index] > bestCount:
					bestCount = count[word.index]
					bestIndex = word.index
		return bestIndex
	def getBestLetter(self, index):
		count = defaultdict(int)
		bestCount = 0
		bestLetter = ''
		for word in self.words:
			if word.isEnded() or word.index != index:
				continue
			for letter in word.remaining.replace('_',''):
				count[letter] += 1
				if count[letter] > bestCount:
					bestCount = count[letter]
					bestLetter = letter
		return bestLetter
	def update(self, bestIndex, bestLetter, d):
		for word in self.words:
			if not word.isEnded():
				word.update(d)
	def wins(self):
		w = 0
		for word in self.words:
			if word.won:
				w+=1
		return w


def is_prime(n):
	for i in range(3,n):
		if n%i == 0:
			return False
	return True

bestWins = 0
bestD={}

for length in range(4001,1500,-2):
	if not is_prime(length):
		continue
	d = ['.']*length

	fff = open('wordlist.txt')
	lines = fff.readlines()
	fff.close()
	ww = []
	for line in lines:
		w=line.strip()
		if re.match(r'^[a-z]*$', w):
			ww.append(w)
	words = Words(ww)

	while not words.allEnded():
		bestIndex = words.getBestIndex()
		bestLetter = words.getBestLetter(bestIndex)
		# Update d
		d[bestIndex] = bestLetter
		# Move words
		words.update(bestIndex, bestLetter, d)
	wins = words.wins()
	counts = defaultdict(int)
	for l in d:
		if l != '.':
			counts[l]+=1
			if counts[l] == max(counts.values()):
				bestL=l
	encoded = ''.join(d).replace('.',bestL).encode('zip').encode('base64')
	newEntry = (len(encoded), length, encoded, ''.join(d).replace('.',bestL))
	toRemove = []
	include = True
	for oldWins, oldEntry in bestD.items():
		if oldWins < wins and oldEntry[0] >= newEntry[0]:
			toRemove.append(oldWins)
		if oldWins > wins and oldEntry[0] <= newEntry[0]:
			include = False
	for oldWins in toRemove:
		bestD.pop(oldWins)
	if include:
		bestD[wins] = newEntry
		print wins, len(encoded), length
for k in sorted(bestD.keys()):
	print '    %d  | %d                     | %s'%(k, bestD[k][0], bestD[k][3])