'''
Il tris e' un popolarissimo gioco. Si gioca su una griglia quadrata di 3x3 caselle.
A turno, i due giocatori scelgono una cella vuota e vi disegnano il proprio simbolo 
(un giocatore ha come simbolo una "o" e l'avversario una 'x'). 
Vince il giocatore che riesce a disporre tre dei propri simboli in linea retta 
orizzontale, verticale o diagonale. Se la griglia viene riempita 
senza che nessuno dei giocatori sia riuscito a completare una linea 
retta di tre simboli, il gioco finisce in parita'. Nel caso in cui il gioco 
finisse in parita', la partita e' detta "patta". 
Per convenzione a griglia vuota la prima mossa spetta sempre al giocatore 'o'

Una configurazione del gioco e' dunque univocamente determinata  dal contenuto della griglia.

Nel seguito assumiamo che il contenuto della griglia sia  rappresentato tramite  lista di liste.
La dimensione della lista di liste M e'  3x3 ed   M[i][j] contiene  '', 'x', o 'o'  a seconda 
che la cella della griglia appartenente all'iesima riga e j-ma colonna sia ancora libera, 
contenga il simbolo 'x' o contenga il simbolo 'o'. 

Data una configurazione C del gioco, l'albero di gioco per C e' l'albero che 
si ottiene ricorsivamente partendo dalla configurazione C e assegnando come figli le configurazioni 
che e' possibile ottenere da C con una mossa ulteriore del gioco. Ovviamente  risulteranno 
foglie dell'albero i possibili esiti della partita vale a dire le diverse configurazioni cui e' 
possibile arrivare partendo da C e che rappresentano patte, vittorie per 'o' o vittorie per 'x'.
Se veda ad esempio l'immagine albero_di_gioco.png che mostra l' albero di gioco che si ottiene a partire 
dalla configurazione rappresentata da [['x', 'o', 'o'], ['x', 'x', 'o'], ['', '', '']]
 

Si consideri la seguente Classe di oggetti:


class NodoTris:
    def __init__(self, griglia):
        self.nome = griglia
        self.lista_figli = [] 


Bisogna progettare le seguente  funzione 

gen_tree(griglia)
che, data la configurazione di gioco griglia,  costruisce l'albero di gioco che si ottiene a partire 
dalla configurazione griglia e ne restituisce la radice. I nodi dell'albero devono essere 
oggetti della classe NodoTris.

Per testare la correttezza della vostra implementazione di gen_tree() il grade utilizzera' quattro metodi 
della   classe NodoTris che dovete comunque implementare: 

1)
tipo(self)
che, dato un nodo NodoTris, restituisce:
 'o' se la configurazione rappresentata dal nodo e' una configurazione di vittoria per il giocatore 'o'
 'x' se la configurazione rappresentata dal nodo e' una configurazione di vittoria per il giocatore 'x'
 '-' se la configurazione rappresentata dal nodo e' una configurazione di patta
 '?' se la configurazione rappresentata dal nodo e' una configurazione di gioco non ancora terminato

2)
esiti(self)
che, dato un nodo radice di un albero di gioco, restituisce una tripla con i possibili 
esiti della partita che ha come configurazione iniziale quella rappresentata dal nodo. 
Piu' precisamente: il primo elemento della tripla  e' il numero di  patte possibili, 
il secondo e' il numero di possibili vittorie  per il giocatore 'o' mentre  il terzo elemento 
e' il numero di possibili vittorie per il giocatore 'x'.

3)
vittorie_livello(self, giocatore, h)
che, dato un nodo radice di un albero di gioco, uno dei due giocatori ed un intero h,
restituisce il numero di nodi che rappresentano una vittoria per il giocatore e si 
trovano ad altezza h nell'albero. In altri termini restituisce il numero di vittorie possibili 
per giocatore in esattamente h mosse, nella partita che ha come configurazione iniziale 
quella rappresentata dalla radice dell'albero.

4)
strategia_vincente(self,giocatore)
che, dato un nodo radice di un albero di gioco ed uno dei due giocatori, restituisce True o False. 
Restituisce True  se  giocatore ha una strategia vincente  nella partita 
che ha come configurazione iniziale quella rappresentata dal nodo radice, False altrimenti.

Nota che un giocatore ha una strategia vincente rispetto ad una certa configurazione se, 
qualunque siano le mosse dell'avversario ha sempre la possibilita' di rispondere in modo 
che la partita termini con la sua vittoria.

Potete ovviamente definire ulteriori  funzioni e altri metodi per la   Classe NodiTris 
se li  ritenete utili al fine della risoluzione del compito.

Potete assumere che le configurazioni di gioco rappresentate da griglia siano sempre configurazioni 
lecite (vale a dire ottenute dopo un certo numero di mosse a parire dalla griglia vuota).


AVVERTENZE: non usare caratteri non ASCII, come le lettere accentate; non
importare moduli che non sono nella libreria standard.

ATTENZIONE: i test vengono eseguiti con un timeout globale di 2*N secondi (se il grader esegue N test).
'''

class NodoTris:
    def __init__(self, griglia):
        self.griglia = griglia
        self.lista_figli = [] #lista dei nodi figli
    
    def tipo(self):
        '''inserire qui il vostro codice'''
        vincex=['x']*3
        vinceo=['o']*3
        if vinceo in self.griglia:
            return 'o'
        if vincex in self.griglia:
            return 'x'
        colonne=[]
        for j in (0,1,2):
            colonne.append([self.griglia[i][j] for i in (0,1,2)])
        if vincex in colonne:
            return 'x'
        if vinceo in colonne:
            return 'o'
        diagonali=[[self.griglia[i][i] for i in (0,1,2)]]
        diagonali.append([self.griglia[2-i][i] for i in (0,1,2)])
        if vincex in diagonali:
            return 'x'
        if vinceo in diagonali:
            return 'o'
        if self.achitocca() == '-':
            return '-'
        return '?'
        
    def esiti(self):
        '''inserire qui il vostro codice'''
        t = self.tipo()
        if t!='?':
            if t == 'x':
                return (0, 0, 1)
            if t == 'o':
                return (0, 1, 0)                        
            return (1, 0, 0)
        res=[0,0,0]
        for f in self.lista_figli:
            e=f.esiti()
            res=[e[i]+res[i] for i in (0,1,2)]
        return tuple(res)
            
    
    def vittorie_livello(self, giocatore, h):
        '''inserire qui il vostro codice'''
        if h == 0:
            if self.tipo()==giocatore:
                return 1
            else:
                return 0
        else:
            res=0
            for figlio in self.lista_figli:
                res+=figlio.vittorie_livello(giocatore, h-1)
            return res
    
    def laltro(self, giocatore):
        d={'x':'o', 'o':'x'}
        return d[giocatore]

    def strategia_vincente(self,giocatore):
        '''inserire qui il vostro codice'''
        t=self.tipo()
        if t == giocatore:
            return True
        if t in ('-', self.laltro(giocatore)):
            return False
        if self.achitocca() ==giocatore:
            return any([figlio.strategia_vincente(giocatore) \
                        for figlio in self.lista_figli])
        else:
            return all([figlio.strategia_vincente(giocatore) \
                        for figlio in self.lista_figli])

    def achitocca(self):
        c=0
        for riga in self.griglia:
            for casella in riga:
                if casella != '':
                    c+=1
        if c == 9:
            return '-'
        if c % 2==0:
            return 'o'
        else:
            return 'x'

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        r=' {:1} | {:1} | {:1}\n'
        s='-----------\n'
        tris=r.format(*self.griglia[0])
        for i in (1,2):
            tris+=s+r.format(*self.griglia[i])
        return tris
        
def gen_tree(griglia):
    '''inserire qui il vostro codice'''
    albero=NodoTris(griglia)
    if albero.tipo() != '?':
        return albero
    giocatore = albero.achitocca()
    for i in (0,1,2):
        for j in (0,1,2):
            if griglia[i][j]=='':
                g2=[riga[:] for riga in griglia]
                g2[i][j]=giocatore         
                albero.lista_figli.append(gen_tree(g2))
    return albero
            
if __name__ == '__main__':
    g1=[['x', 'o', 'o'], ['x', 'x', 'o'], ['', '', '']]