import sys
import string
import time
import pickle
import psyco
psyco.full()
class Setdb:
        def __init__(self, filename, readonly=False):
                self.filename=filename
                self.readonly=readonly
                self.load()
                self.waittime=0
        def load(self):
                f=open(self.filename,'r')
                up=pickle.Unpickler(f)
                self.db=up.load()
                f.close()
        def lookup(self, X):
                t1=time.time()
                X=reorder(X)
                t2=time.time()
                self.waittime+=t2-t1
                return self.db.get(str(X),'Unknown')
        def store(self, X, avoidable):
                t1=time.time()
                X=reorder(X)
                t2=time.time()
                self.waittime+=t2-t1
                if str(X) not in self.db.keys(): self.db[str(X)]=avoidable
        def save(self):
                if self.readonly: return
                f=open(self.filename,'w')
                p = pickle.Pickler(f)
                p.dump(self.db)
                f.close()
        def subset(self,X,Y):
                for x in X:
                        if x not in Y: return False
                return True

def type1factors(x,y):
	for i in range(len(y)):
		if y[i]==x[0]:
			if type2compat(y[i:len(x)+i],[x],[]):return True
	return False        
def ifactors(w1,w2,A):
        """Check to see if w1 and w2 are compatible"""
        if len(w1)!=len(w2): return False
        for i in range(len(w1)):
                if w1[i]!=w2[i] and w1[i]!='^' and w2[i]!='^': return False
        return True

def type2in(word, X, A):
        for w2 in X:
                if ifactors(word, w2,A):
                        return True, word, w2
                else: continue
        return False, None, None

def type2compat(word,X,A):
        for w2 in X:
                match=True
                if len(word)!=len(w2): continue
                for i in range(len(word)):
                        if word[i]==w2[i] or w2[i]=='^': continue
                        else:
                                match=False
                                break
                if match: return True
        return False               
        
def type2split(word,w2,A, debug):
        newwords=[]
        blankspots=[]
        if word==w2: return newwords
        d=len(word)-len(w2)
        for i in range(len(w2)-1):
                if word[i+d]==w2[i]:continue
                elif word[i+d]=='^':
                        blankspots.append(i+d)
                        for letter in A:
                                nw = word[:i+d]+letter+word[i+d+1:]
                                newwords.append(nw)
                elif debug: print 'prefix hits a diamond', word, w2, i
        bword=word[:]
        for i in blankspots:
                bword=bword[:i]+'*'+bword[i+1:]
        newwords=fillblanks(bword,'*',A)
        return newwords

def type1(X,A, debug):
        res = False
        Y=X[:]
        removals=[]
        for word in X:
                for otherword in X:
                        if word==otherword: continue
                        elif type1factors(word,otherword):
                                #used to be: word in otherword
                                removals.append(otherword)
                                res = True
                                if debug: print 'type 1 on', word, otherword
        for r in removals:
                try: Y.remove(r)
                except: pass
        return Y, res
def type2(X,A, debug):
        for word in X:
                prefix = word[:-1]
                works = True
                pads = []
                for letter in A:
                        if letter==word[-1]:continue
                        temp = False
                        for i in range(len(prefix)+1):
                                suffix = prefix[i:]+letter
                                if not type2compat(suffix,X,A): continue
                                else: 
                                        temp = True
                                        break
                        if not temp: works=False
                if works: 
                        Y=X[:]
                        Y.remove(word)
                        Y.append(prefix)
                        if debug: print 'type 2 on',prefix
                        return Y, True
        return X, False
def type2x(X,A, debug):
        for word in X:
                prefix = word[:-1]
                works = True
                pads = []
                for letter in A:
                        if letter==word[-1]:continue
                        temp = False
                        for i in range(len(prefix)+1):
                                suffix = prefix[i:]+letter
                                t2in, w1, w2 = type2in(suffix,X,A)
                                if not t2in: continue
                                else: 
                                        temp = True
                                        pads+=type2split(word,w2,A, debug)
                                        Y=X[:]
                                        Y.remove(word)
                                        for p in pads: Y.append(p)
                                        if debug: print 'expansion for type 2'
                                        return Y, True
                                        break
                        if not temp: works=False
                if works:
                        pass
                        #Y=X[:]
                        #Y.remove(word)
                        #for p in pads: Y.append(p)
                        #if debug: print 'expansion for type 2'
                        #return Y, True
        return X, False

def type3(X,A, debug):
        Y = X[:]
        for word in X:
                t = word.strip('^')
                Y.remove(word)
                Y.append(t)
        return Y
def makeXhat(X,A):
        Y = X[:]
        for word in X:
                l = fillblanks(word,A)
                for w in l: Y.append(w)
                if l: Y.remove(word)
        return Y
def reorder(X):
        X.sort(key=len, reverse=True)
        return X
def fillblanks(word,b,A):
        flist = []
        if b in word:
                i = word.find(b)
                for a in A:
                        w = word[:i] + a + word[i+1:]
                        flist.append(w)
                for newword in flist:
                        rlist=fillblanks(newword,b,A)
                        for item in rlist: flist.append(item)
                        pass
        res =  flist[:]
        for w in flist:
                if b in w: res.remove(w)
        return res

def addtodb(allSteps, key, setdict):
        if setdict.readonly:return 0
        t1=time.time()
        for s in allSteps:
                setdict.store(s,key)
        t2=time.time()
        return t2-t1
def checkAvoidable(X,A,setdict, debug=False, addtimelost=0):
        res = True
        allSteps=[]
        ludelay=-1
        while res:
                ludelay+=1
                ludelay=ludelay%25
                allSteps.append(X)
                if '' in X: return True, addtimelost
                if not ludelay:
                        lu = setdict.lookup(X)
                if lu=='Unknown':
                        if debug: print X
                        X=type3(X,A, debug)
                        X, res=type1(X,A, debug)
                        if res: continue
                        X, res=type2(X,A, debug)
                        if res:continue
                        X, res=type2x(X,A, debug)
                else:
                        if debug: print 'X looked up to be ' + str(lu)
                        addtimelost+=addtodb(allSteps, lu, setdict)
                        return lu, addtimelost
        if X==['']:
                addtimelost+=addtodb(allSteps, True, setdict)
                return True, addtimelost
        addtimelost+=addtodb(allSteps, False, setdict)
        return False, addtimelost   

def getX(A):
        x=raw_input("""Please enter the first element of X. """)
        X = [x]
        while x:
                x=raw_input("""Please enter the next element of X. """)
                if x: X.append(x)
        return X
def defineA():
        A=[]
        a = raw_input("Please input the alphabet as a string (Ex: abc). ")
        for letter in a:
                A.append(letter)
        return A

def makeTemplates(holes,choose):
        t=[]
        if choose==0: return holes
        for h in holes:
                f=holes[:]
                f.remove(h)
                f = makeTemplates(f,choose-1)
                t+=f
        return t
def convertTemplates(templates, tlen,holes):
        t = []
        u = []
        if tlen==0:
                u = ['a'+holes*'*'+'b']
                return u
        for i in range(len(templates)/tlen):
                t.append(templates[tlen*i:tlen*(i+1)])
        for template in t:
                un=holes*'*'
                for index in template:
                        un=un[:index]+'^'+un[index+1:]
                u.append('a'+un+'b')
        return u

def trialrun(readonly=True):
        setdict=Setdb('dummy.txt', readonly)
        A = defineA()
        print A
        X = getX(A)
        print checkAvoidable(X,A,setdict, True)
        if not readonly: setdict.save()
def decompose(X):
	s = X[2]
	count=0
	components=[]
	checks = []
	for i in range(len(s)-2):
		if s[i+1] != '^':
			count +=1
			components.append(s[:i+1]+'^'+s[i+2:])
	if count<=1:return checks
	for c in components:
		checks.append(X[:-1]+[c])
	return checks

def processList(s,A,setdict, logfile,holes):
        timelost=0
        for w in s:
                setdict.readonly=False
                skip = False
                X=[]
                X.append('a'+holes*'^'+'a')
                X.append('b'+holes*'^'+'b')
                X.append(w)
                print w
                #print timelost
                for Z in decompose(X):
                        setdict.readonly=True
                        res, timelost = checkAvoidable(Z,A,setdict,False,timelost)
                        if not res:
                                #print 'substring avoidable'
                                skip = True
                                break
                if not skip:
                        result, timelost = checkAvoidable(X,A,setdict, False, timelost)
                        if result:
                                #print '--------------TRUE---------------'
                                logfile.write(w + ' - True \n')

###---short run ---###
##trialrun()
        
###---long run code---###
t = []
setdict=Setdb('3dict.txt',True)
dummydict=Setdb('dummydict.txt',True)
holes = 5
A=['a','b','c']
##u = makeTemplates(range(holes),1)
##u = convertTemplates(u,holes-1,holes)
##for item in u:
##        if item not in t: t.append(item)
##u = makeTemplates(range(holes),2)
##u = convertTemplates(u,holes-2,holes)
##for item in u:
##        if item not in t: t.append(item)
##s= []
##for template in t: s+=fillblanks(template,'*',A)

timelost = 0
timestr = time.strftime('%m%d%H%M')
fileout = open('results'+timestr+'.txt','w')
done = []
B=['a','b']
C=['a','c']
D=['b','c']
for a in range(holes):
        for b in range(holes):
                print a,b
                if a==b: continue
                for c in range(holes):
                               if a==c or b==c: continue
                               #print a,b,c
                               if c<=3*a+3: continue
                               if c<=2*a+b+3: continue
                               dummy = [a,b,c]
                               dummy.sort()
                               if dummy in done: continue
                               done.append(dummy)
                               #print a,b,c
                               X = ['a'+'^'*a+'a','b'+'^'*b+'b','c'+'^'*c+'c']
                               result, timelost = checkAvoidable([X[0],X[1]],B,dummydict,False)
                               if not result: continue
                               result, timelost = checkAvoidable([X[0],X[2]],C,dummydict,False)
                               if not result: continue
                               result, timelost = checkAvoidable([X[1],X[2]],D,dummydict,False)
                               if not result: continue
                               result, timelost = checkAvoidable(X,A,setdict, False, timelost)
                               if result: print '--------------TRUE---------------'
                               fileout.write(str(X) + ' - ' + str(result)+ '\n')
        fileout.flush()
                               
##for holes in range(20):
##        s = []
##        for i in range(holes):
##                s.append('a'+'^'*i+'b')
##        fileout.write(str(holes)+'\n')
##        processList(s,A,setdict,fileout,holes)
fileout.close()
setdict.save()
#setdict.save() #Im out of space, can't afford to save it to disk.  Use only with r/w toggle