import Timer
import copy
import graphics
import psyco
import sys
psyco.full()

bestscore=-999999999
    
def calc_score(place, map, protein):
    global bestscore, winner
    score=0

    for i in place:
        x, y = i
        if map[x][y]=='H':
            if map[x-1][y]==' ': score-=1
            if map[x][y-1]==' ': score-=1
            if map[x+1][y]==' ': score-=1
            if map[x][y+1]==' ': score-=1

    if(score>bestscore):
        bestscore=score
        winner=copy.copy(place)
        g.show_protein(winner, protein)

    return score


def fold(protein, map, place):
    res=0
    best=-99999999

    cnt = len(place)
    if cnt==len(protein):
        return calc_score(place, map, protein)

    if cnt>3:
        newx, newy = place[-1]
        newx=newx-1
        if map[newx][newy]==' ':           
            map[newx][newy] = protein[cnt]
            place.append((newx, newy))
            res=fold(protein, map, place)
            map[newx][newy] = ' '
            place.pop()
        if res>best: best=res
       
    if cnt>2:
        newx, newy=place[-1]
        newy=newy-1
        if map[newx][newy]==' ':
            map[newx][newy] = protein[cnt]
            place.append((newx, newy))
            res=fold(protein, map,  place)
            map[newx][newy] = ' '
            place.pop()
        if res>best: best=res

    if cnt>1:
        newx, newy = place[-1]
        newx=newx+1
        if map[newx][newy]==' ':           
            map[newx][newy] = protein[cnt]
            place.append((newx, newy))
            res=fold(protein, map,  place)
            map[newx][newy] = ' '
            place.pop()
        if res>best: best=res

    newx, newy = place[-1]
    newy=newy+1
    if map[newx][newy]==' ':          
        map[newx][newy] = protein[cnt]
        place.append((newx, newy))
        res=fold(protein, map,  place)
        map[newx][newy] = ' '
        place.pop()
    if res>best: best=res
    
    return best

    

timer = Timer.StopWatch()
protein='HHHHPPPPPPPPPPPPPPHHHH'
if len(sys.argv)>1: protein=sys.argv[1]
plen = len(protein)
map = []

g = graphics.graphicsScreen((2*plen+1)*10,(2*plen+1)*10)
winner = []
 

for i in range(2*plen+1):
    map.append((2*plen+1)*[' '])

r=map[plen]
r[plen]=protein[0]
place=[(plen, plen)]
timer.Start()

fold(protein, map, place)
print('Best is %d'%bestscore)
timer.Stop()
print("Time taken: "+timer.timeString())
g.show_protein(winner, protein)
timer.Sleep(5)
