# -*- coding: cp1252 -*-

from xturtle import *
import time

# Spielstand ist Liste von Codezahlen (Typ):
# 1 = bewegt sich nach rechts, 0 = Leerfeld, -1 = bewegt sich nach links

class FrogPlay:
    def __init__(self,n=2,doplay=True):
        self.size = 2*n+1
        self.start = n*[1]+[0]+n*[-1]       # start [1,1,..,1,0,-1,-1,...,-1]
        self.ziel = self.start[:]
        self.ziel.reverse()                 # ziel ist umgedrehter Start

        self.FERTIG = False
        self.solve(self.start[:],[])        # löse das Puzzle

        # Animierte Lösung abspielen
        if doplay: self.animate(self.start[:],self.solution)
        
    # return possible move or None
    def can_move(self,state,pos):
        value = state[pos]
        if value ==0 : return
        # Verschiebung möglich?
        pos1 = pos+value
        if pos1>=0 and pos1<self.size:
            if state[pos1]==0:
                state[pos],state[pos1] = state[pos1],state[pos]
                return state,pos
        # Sprung möglich?
        pos2 = pos+2*value
        if pos2>=0 and pos2<self.size:
            if state[pos2]==0 and state[pos1]==-state[pos]:
                state[pos],state[pos2] = state[pos2],state[pos]
                return state,pos
        # keine Bewegung war möglich
        return None        

    # solve the puzzle
    def solve(self,state,moves):
        if self.FERTIG: return      # eine Lösung genügt
        
        if state==self.ziel:        # Lösung gefunden
            self.solution = moves
            self.FERTIG = True
            return
        # alle möglichen moves durchprobieren
        for pos in range(self.size):
            result = self.can_move(state[:],pos)
            if result:
                newstate,move = result
                # rekursiv weiterversuchen
                self.solve(newstate[:],moves+[move])

    # animate the game
    def animate(self,state,moves):
        self.show(state)
        for m in moves:
            v = state[m]
            if state[m+v]==0:
                state[m],state[m+v] = state[m+v],state[m]
            else:
                state[m],state[m+2*v] = state[m+2*v],state[m]
            self.show(state)
        print "solved in",len(moves),"moves"    # should be (n+1)**2 - 1

    # aktuellen Zustand anzeigen
    def show(self,state):
        s = ""
        for x in state:
            if x==0: s += " "
            elif x==1: s += "A"
            else: s += "B"
        print s

#########################################################################
# xturtle Animation
#########################################################################        

class Frogs_GUI:
    def __init__(self,num):
        D = self.D = 75
        self.num = num
        reset()
        winsize((2*num+2)*D+10,2.75*D+10,50,50)
        screensize((2*num+2)*D,2.75*D)
        self.frogs = []
        for i in range(num,0,-1): self.frogs.append(Frog(1,D,i))
        self.frogs.append(Frog(0,D,0))
        for i in range(1,num+1): self.frogs.append(Frog(-1,D,i))
        self.frogsave = self.frogs[:]
        ht()
        
        #self.showsolution(solution)
        onClick(self.action,1)
        self.BUSY = False

    # geclickte Turtle bewegen 
    def action(self,x,y):
        if self.BUSY: return
        self.BUSY = True
        if abs(y)<self.D/2:
            xx = int((x+self.num*self.D+self.D/2)//self.D)
            if 0<=xx<self.num*2+1:
                self.move(xx)
        self.BUSY = False

    # Turtle bewegen, falls möglich
    def move(self,n):
        f = self.frogs[n]
        if f.typ==0: return # Leerstelle
        mytyp = f.typ
        n1 = n+mytyp
        if n1<0 or n1>=self.num*2+1:
            self.frogs[n].blocked()
            return
        if self.frogs[n1].typ==0:
            self.frogs[n].walk()
            self.frogs[n1].shift(-mytyp)
            self.frogs[n],self.frogs[n1] = self.frogs[n1],self.frogs[n]
        else:
            n2 = n+2*f.typ
            if n2<0 or n2>=self.num*2+1:
                self.frogs[n].blocked()
                return
            if (self.frogs[n2].typ==0) and self.frogs[n1].typ==-mytyp:
                self.frogs[n].hop()
                self.frogs[n2].shift(-2*mytyp)
                self.frogs[n],self.frogs[n2] = self.frogs[n2],self.frogs[n]
            else:
                self.frogs[n].blocked()

    def animate(self):
        fplay = FrogPlay(self.num,False)
        solution = fplay.solution

        time.sleep(1)
        self.frogs = self.frogsave[:]
        for f in self.frogs: f.home()
        for s in solution:
            self.move(s)

        
class Frog(Pen):
    # typ 0,1,-1, step=Feldgröße, pos=ort, id=Nummer
    def __init__(self,typ,step,pos):
        Pen.__init__(self)
        self.typ = typ
        self.D = step
        self.pos = -pos*typ

        self.speed(0)
        self.tracer(False)
        self.pu()
        self.setpos(-typ*step*pos,0)
        self.homepos = -typ*step*pos
        # Quadrat zeichnen
        self.bk(step/2); self.lt(90); self.bk(step/2);self.pd()
        for i in range(4):
            self.fd(step)
            self.rt(90)
        self.pu();self.fd(step/2); self.rt(90); self.fd(step/2)

        # Shape setzen
        if typ==0: self.shape("blank")
        else:
            self.resizemode("user")
            self.turtlesize(2,2)
            #self.width(2)
            if typ==-1:
                self.color("red")
                self.rt(180)
            else: self.color("green")
            self.shape("turtle")
     
        self.tracer(True)    

    def home(self):
        self.speed(0)
        self.setpos(self.homepos,0)

    def shift(self,direction):
        self.speed(0)
        self.ht()
        self.fd(self.D*direction)
        self.st()

    def walk(self):
        self.speed(1)
        self.fd(self.D/3)
        time.sleep(0.1)
        self.fd(self.D/3)
        time.sleep(0.1)
        self.fd(self.D/3)
        
    def hop(self):
        self.speed(1)
        self.lt(90*self.typ)
        self.circle(-self.D*self.typ,180)
        self.lt(90*self.typ)
                
    def blocked(self):
        self.speed(1)
        self.fd(self.D/4)
        time.sleep(0.25)
        self.bk(self.D/4)
        
f1 = FrogPlay(3)
f2 = Frogs_GUI(3)

if __name__ == '__main__':
    f2.animate()
    time.sleep(2)