class Sokoban :
    """
    definition du probleme de sokoban avec une seule caisse

    etat
    - position du personnage (x,y)
    - position de la caisse (cx,cy)

    action possibles
    - deplacements du personnage
    """

    def __init__(self):
        # donnees du probleme - labyrinthe utilise
        # 0 = vide
        # 1 = mur
        self.labyrinthe = []
        self.labyrinthe += [[1,1,1,1,1]]
        self.labyrinthe += [[1,1,1,0,1]]
        self.labyrinthe += [[1,0,0,0,1]]
        self.labyrinthe += [[1,0,0,0,1]]
        self.labyrinthe += [[1,1,1,1,1]]

        # transposer labyrinthe
        self.labyrinthe = self.transpose(self.labyrinthe)

        # etat de depart (posx, posy, caissex, caissey)
        # position initiale du personnage
        xDep = 3
        yDep = 1
        xCaisse = 2
        yCaisse = 2
        self.depart = (xDep, yDep, xCaisse, yCaisse)

        # position d'arrivee desiree
        # -le personnage est en bas a gauche
        # -la caisse est en 3,1 (dans le trou dans le mur)
        self.arrivee = (1, 3, 3, 1)


    def actions(self):
        """
        les actions possibles de sokoban
        """
        return(['nord','sud','est','ouest'])


    def transition(self,s,a):
        """
        regles du jeu
        - s etat du monde (px, py, cx, cy)
            - px,py : position du personnage
            - cx,cy : position de la caisse
        - a action envisagee
        - return etat d'arrivee

        Principe
        - si la case d'arrivee est vide, le personnage se deplace
        - si la case d'arrivee contient un mur, rien ne se passe
        - si la case d'arrivee contient une caisse, le personnage la pousse si possible
        """
        # recupere info des etats
        (posX, posY, caisseX, caisseY) = s

        # gestion des directions en fonction des actions
        directions = {}
        directions ["nord"] = 0, -1
        directions ["sud"] = 0, 1
        directions ["est"] = 1, 0
        directions ["ouest"] = -1, 0

        # regarder la case suivante
        suivX = posX + directions[a][0]
        suivY = posY + directions[a][1]

        # si la case d'arrivee contient un mur
        if self.labyrinthe[suivX][suivY] ==1 :
            # rien ne se passe, on retourne le meme etat
            return s

        # sinon => case d'arrivee ne contient pas de mur
        elif  (suivX, suivY) != (caisseX, caisseY) :
            # deplacement effectif sans bouger la caisse
            return suivX, suivY, caisseX, caisseY

        # sinon la case d'arrivee contient la caisse
        else :
            # on regarde la case derriere la caisse
            derriereCaisseX = suivX + directions[a][0]
            derriereCaisseY = suivY + directions[a][1]
            # si c'est vide
            if self.labyrinthe[derriereCaisseX][derriereCaisseY] == 0 :
                # on deplace la personne et la caisse
                return (suivX,suivY,derriereCaisseX,derriereCaisseY)
            # sinon, il y a mur derriere la caisse
            else :
                # on ne bouge pas
                return s

#########################################################
# Methodes intermediaires (affichage et transpose)
#########################################################

    def transpose(self,laby):
        """
        permet d'inverser lignes et colonnes d'un labyrinthe
        (utile pour la creation simple)
        """
        # nouveau laby
        laby2=[]
        for i in range(0,len(laby[0])):
            ligne=[]
            for j in range(0,len(laby)):
                ligne+=[0]
            laby2+=[ligne]

        # transposition
        for i in range(0,len(laby[0])):
            for j in range(0,len(laby)):
                laby2[i][j]=laby[j][i]
        return laby2


    def toString(self, etat):
        """
        retourne descriptif de l'etat
        """
        res = ""

        # parcourir le tableau
        # par ligne
        for j in range(len(self.labyrinthe[0])):
            # par colonne
            for i in range(len(self.labyrinthe)):
                # le caractere a ajouter (par defaut vide)
                car ='.'
                # si c'est un mur mettre '#'
                if self.labyrinthe[i][j] == 1 :
                    car ='#'
                # ajouter personage P et caisse C
                if i == etat[0] and j== etat [1] :
                    car ='P'
                # ajouter personage P et caisse C
                if i == etat[2] and j== etat [3] :
                    car ='C'
                # ajouter le caractere
                res = res + car

            # saut de ligne
            res = res +"\n"
        return res