class Sokoban :
    """
    definition du probleme de sokoban avec plusieurs caisses

    etat
    - position du personnage (x,y)
    - position des caisses sous la forme d'un tuple (caisse1, caisse2, ...)
        - chaque caisse ayant deux coordonnees (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,1,1]]
        self.labyrinthe += [[1,1,1,1,0,0,1]]
        self.labyrinthe += [[1,1,1,1,0,0,1]]
        self.labyrinthe += [[1,1,0,0,0,0,1]]
        self.labyrinthe += [[1,1,0,0,0,0,1]]
        self.labyrinthe += [[1,1,1,1,0,0,1]]
        self.labyrinthe += [[1,1,1,1,0,0,1]]
        self.labyrinthe += [[1,1,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 = 5
        yDep = 1
        # on trie les caisses selon leur position (pour ne pas avoir id de caisse)
        caisses = ((3,3),(4,2))
        caisses = tuple(sorted(caisses))
        self.depart = (xDep, yDep, caisses)

        # position d'arrivee desiree
        # les deux caisses sont en diagonale au milieu
        caisseArr = ((4,3),(5,4))
        caisseArr = tuple(sorted(caisseArr))
        self.arrivee = (4, 2, caisseArr)



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



    def transition(self,s,a):
        """
        regles du jeu
        - s etat du monde (px, py, caisses)
            - px,py : position du personnage
            - caisses : position des caisses
        - 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, caisses) = s

        # passe par une liste pour effectuer les operations
        liste_caisses = list(caisses)

        # 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
        # si la case d'arrivee n'a pas de caisse non plus
        elif  not (suivX, suivY) in caisses :
            # deplacement du personnage sans bouger les caisses
            return suivX, suivY, caisses

        # 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 et pas de caisse
            if self.labyrinthe[derriereCaisseX][derriereCaisseY] == 0 and not (derriereCaisseX,derriereCaisseY) in liste_caisses :
                # on deplace la caisse en deux etapes
                # 1. on retire ancienne caisse
                liste_caisses.remove((suivX,suivY))
                # 2. on ajoute la nouvele
                liste_caisses.append((derriereCaisseX, derriereCaisseY),)
                # on trie la liste (poue ne pas dependre de l'ordre)
                liste_caisses = sorted(liste_caisses)

                # on deplace la personne et la caisse
                return (suivX,suivY,tuple(liste_caisses))

            # sinon, il y a mur derriere la caisse
            else :
                # on ne bouge pas
                return s


    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,j) in  etat[2]  :
                    car ='C'
                # ajouter le caractere
                res = res + car


            res = res +"\n"
        return res