#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Nov 29 10:28:50 2019

@author: andrea
"""

from rtrace import trace

class NodoBinario:
    def __init__(self, V, SX=None, DX=None):
        self.valore = V
        self.sx = SX
        self.dx = DX

    def __str__(self, livello=0):
        risultato = ''
        if self.sx:
            risultato += '\n' + '\t'*livello + self.sx.__str__(livello+1)
        risultato += '\n' + '\t'*livello + f"{self.valore}"
        if self.dx:
            risultato += '\n' + '\t'*livello + self.dx.__str__(livello+1)
        return risultato

    def altezza(self):
        hs = 0
        hd = 0
        if self.sx:
            hs = self.sx.altezza()
        if self.dx:
            hd = self.dx.altezza()
        return max(hs, hd)+1

# calcolo le eprmutazioni di una lista di elementi diversi
def permuta(L):
    if len(L) < 2:
        return [L]
    perm = []
    for simbolo in L:
        resto = L[:]
        resto.remove(simbolo)
        for p in permuta(resto):
            resto.append([simbolo] + p)
    return perm     

# per esercizio: calcolate le permutazioni se i simboli 
# possono ripetersi (hint: usate i set)


# costruisco un albero binario di livello N
# con i nodi numerati da sinistra a destra
# ricordando l'ultimo valore usato nel sottoalbero sinistro
# per valorizzare la radice e poi il sottoalbero destro
# torno l'albero E l'ultimo numero usato
def genera_albero_completo(N, parti_da=0):
    if N == 0:
        return None, parti_da
    sx, dove_sono_arrivato_sx = genera_albero_completo(N-1,parti_da)
    valore_radice = dove_sono_arrivato_sx+1
    nodo = NodoBinario(valore_radice,sx)
    dx, dove_sono_arrivato_dx = genera_albero_completo(N-1, valore_radice)
    nodo.dx = dx
    return nodo, dove_sono_arrivato_dx


class Nodo:
    def __init__(self, V, figli=None):
        self.valore = V
        if figli:
            self.figli = figli
        else:
            self.figli = []
        
    
    def __str__(self, livello=0):
        risultato = '\t'*livello + f"{self.valore}"
        for figlio in self.figli:
            risultato += '\n' + '\t'*livello + figlio.__str__(livello+1)
        return risultato
    
    def altezza(self):
        if not self.figli:
            return 1
        return 1 + max( figlio.altezza() for figlio in self.figli )

#             / (1)
#            / 
# (5) -- (4) -- (3)
#            \
#             \ (2)

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4, [nodo1, nodo3, nodo2])
nodo5 = Nodo(5, [nodo4])


# calcolo il percorso più lungo nell'albero binario
#def diametro(tree):
    
def aggiungi_altezza(tree):
    if tree == None:
        return 0
    sx = aggiungi_altezza(tree.sx)
    dx = aggiungi_altezza(tree.dx)
    tree.H = max(sx, dx) +1
    return tree.H    

nb1 = NodoBinario(1)
nb2 = NodoBinario(2)
nb3 = NodoBinario(3, nb2, nb1)
nb4 = NodoBinario(4, nb3)
nb5 = NodoBinario(5, None, nb4)

aggiungi_altezza(nb5)

def diametro(tree):
    if tree == None:
        return 0
    Dsx = diametro(tree.sx)
    Ddx = diametro(tree.dx)
    mio_diametro = 1
    if tree.sx:
        mio_diametro += tree.sx.H
    if tree.dx:
        mio_diametro += tree.dx.H
    return max(Dsx, Ddx, mio_diametro)

import copy
    
class NodoTris:
    def __init__(self, scacchiera=None):
        if not scacchiera:
            self.scacchiera = [ [ '', '', '' ],
                                [ '', '', '' ],
                                [ '', '', '' ],]
        else:
            self.scacchiera = scacchiera
    
    def vincente(self, simbolo):
        return ([simbolo] * 3 == self.scacchiera[0] 
                or
                [simbolo] * 3 == self.scacchiera[1] 
                or
                [simbolo] * 3 == self.scacchiera[2] 
                or
                [simbolo] * 3 == [self.scacchiera[0][0], self.scacchiera[1][0], self.scacchiera[2][0], ]
                or
                [simbolo] * 3 == [self.scacchiera[0][1], self.scacchiera[1][1], self.scacchiera[2][1], ]
                or
                [simbolo] * 3 == [self.scacchiera[0][2], self.scacchiera[1][2], self.scacchiera[2][2], ]
                or
                [simbolo] * 3 == [self.scacchiera[0][0], self.scacchiera[1][1], self.scacchiera[2][2], ]
                or
                [simbolo] * 3 == [self.scacchiera[0][2], self.scacchiera[1][1], self.scacchiera[2][0], ]
                )

    def piena(self):
        for line in self.scacchiera:
            for casella in line:
                if casella == '':
                    return False
        return True

    def mosse(self, simbolo):
        if self.piena():
            return []
        elenco = []
        for y,linea in enumerate(self.scacchiera):
            for x,casella in enumerate(linea):
                if casella == '':
                    nuova_scacchiera = copy.deepcopy(self.scacchiera)
                    nuova_scacchiera[y][x] = simbolo
                    elenco.append(NodoTris(nuova_scacchiera))
        return elenco
    def __repr__(self):
        ris = ''
        for linea in self.scacchiera:
            for casella in linea:
                if casella == '':
                    ris += ' '
                else:
                    ris += casella
            ris += '\n'
        return ris


x = NodoTris( [['', '1', '1'],
               ['o', 'o', ''],
               ['o', '1', '']])