import random

alfabeto = "abcdefghi"
nome_um = "\N{WHITE CIRCLE}"
nome_dois = "\N{BLACK CIRCLE}"
exemplo = {
    "tamanho": 4,
    "jogadas": ["1ab", "23a", "12a", "12c", "1bc", "12b", "2ab","2bc"],
    nome_um: ["1b"],
    nome_dois: ["1c"],
}


def cria_jogo(tamanho):
    pass


def jogadas_válidas(jogo):
    pass


def arestas_do_quadrado(quadrado):
    pass


def jogo_acabou(jogo):
    pass
    

def jogador_humano(jogo, vez):
    pass


def jogador_aleatório(jogo, vez):
    pass


# você pode mudar o nome da próxima função se quiser
def jogador_guloso(jogo, vez):
    pass


# você pode mudar o nome da próxima função se quiser
def jogador_que_você_criou(jogo, vez):
    pass


#############################################
####### Funções prontas (não editar): ####### 
#############################################

def mostra(jogo):
    """
    Imprime na tela uma representação gráfica da situação atual do jogo de Dots and Boxes
    """
    p = "\N{MIDDLE DOT}"
    h = "\N{HORIZONTAL BAR}" * 3
    v = "\N{VERTICAL LINE}"

    s = "\n"
    tamanho = jogo["tamanho"]
    for i in range(tamanho):
        # imprimir arestas horizontais na linha de rótulo tamanho-i
        s += f"{tamanho - i:<{1 + len(str(tamanho))}}"
        s += p
        for j in range(tamanho - 1):
            letra_atual = alfabeto[j]
            próxima_letra = alfabeto[j + 1]
            if f"{tamanho - i}{letra_atual}{próxima_letra}" in jogo["jogadas"]:
                s += h
            else:
                s += " " * len(h)
            s += p
        s += "\n"

        # imprimir arestas verticais entre linhas tamanho-i e tamanho-i-1
        s += " " * (1 + len(str(tamanho)))
        if i < tamanho - 1:
            for j, letra in enumerate(alfabeto[:tamanho]):
                if j > 0:
                    if f"{tamanho - i - 1}{letra}" in jogo[nome_um]:
                        s += f" {nome_um} "
                    elif f"{tamanho - i - 1}{letra}" in jogo[nome_dois]:
                        s += f" {nome_dois} "
                    else:
                        s += " " * len(h)

                if f"{tamanho - i - 1}{tamanho - i}{letra}" in jogo["jogadas"]:
                    s += v
                else:
                    s += " "
            s += "\n"
        else:
            for letra in alfabeto[: tamanho - 1]:
                s += letra
                s += " " * len(h)
            s += alfabeto[tamanho - 1]

    print(s)


def quadrados_contendo(aresta, tamanho):
    quadrados = []
    if aresta[1].isdigit():
        # jogada vertical
        linha_baixo = int(aresta[0])
        linha_cima  = int(aresta[1])
        coluna = aresta[2]
        indice_coluna = alfabeto.find(coluna)

        if indice_coluna > 0:
            # tem quadrado à esquerda
            quadrados.append(f'{linha_baixo}{coluna}')
        if indice_coluna < tamanho-1:
            # tem quadrado à direita
            prox_coluna = alfabeto[indice_coluna +1]
            quadrados.append(f'{linha_baixo}{prox_coluna}')
    else:
        linha = int(aresta[0])
        coluna_direita = aresta[2]
        
        if linha > 1:
            # tem quadrado abaixo
            quadrados.append(f'{linha-1}{coluna_direita}')
        if linha < tamanho:
            # tem quadrado acima
            quadrados.append(f'{linha}{coluna_direita}')
            
    return quadrados
       

def quadrados_capturados(jogada, jogo):
    candidatos = quadrados_contendo(jogada, jogo['tamanho'])
    return [quadrado for quadrado in candidatos if all(aresta in jogo['jogadas'] for aresta in arestas_do_quadrado(quadrado))]


def outro(vez):
    "Retorna o nome do _outro_ jogador"
    if vez == nome_um:
        return nome_dois
    return nome_um


def jogar(primeiro, segundo, tamanho=4, interativo=True):
    """
    Roda um jogo de Dots and Boxes entre os jogadores  primeiro
    e  segundo , em uma malha de lado  tamanho.
    Se  interativo  for True, o estado do jogo é exibido a cada
    rodada, e o resultado é impresso na tela (sem retorno).
    Se  interativo  for False, nada é exibido na tela, e o resultado
    do jogo é retornado pela função (o vencedor, caso haja, ou a
    string 'empate')
    """

    J = cria_jogo(tamanho)
    vez = nome_um

    # Loop principal do jogo: mostra o jogo na tela e pede a próxima jogada do jogador da vez.
    while True:
        if interativo:
            mostra(J)
        capturou = False

        while True:
            # Recebe a jogada do jogador da vez em loop até que seja uma jogada válida
            if vez == nome_um:
                jogada = primeiro(J, vez)
            else:
                jogada = segundo(J, vez)

            if jogada in jogadas_válidas(J):
                # jogada aceita, podemos sair do loop!
                break

        # Registra a jogada
        J["jogadas"].append(jogada)

        # Verificamos se a jogada capturou quadrados, e em caso positivo, registramos esse fato:
        capturados = quadrados_capturados(jogada, J)
        if len(capturados) > 0:
            for quadrado in capturados:
                J[vez].append(quadrado)

        # Verificamos se o jogo acabou de ser vencido
        resultado = jogo_acabou(J)
        if resultado in {nome_um, nome_dois}:
            if interativo:
                mostra(J)
                print(f"!!! {resultado} venceu !!!")
                return
            else:
                return resultado
        elif resultado == "empate":
            # Verificamos se o jogo acabou em empate
            if interativo:
                mostra(J)
                print("Empate...")
                return
            else:
                return "empate"

        # Vejamos se a vez troca para a próxima rodada
        if len(capturados) == 0:
            vez = outro(vez)


def torneio(jogador_um, jogador_dois, número_partidas=10**2, tamanho=None):
    """
    Roda um 'torneio' de 2*número_partidas jogos entre os jogadores passados como argumento (metade como cada um sendo o primeiro a jogar).
    Se for passado o argumento  tamanho  , todos os jogos são jogados na malha com o tamanho especificado; senão, as partidas são jogadas em malhas de tamanho aleatório de 3 a 9.
    O valor retornado é um dicionário com as porcentagens de vezes em que cada resultado foi obtido nos jogos.
    """
    s = ""
    if jogador_um == jogador_dois:
        # Vamos usar asteriscos para diferencias as duas "cópias" do mesmo jogador
        s = "*"

    um = f"{jogador_um.__name__}{s}"
    dois = f"{jogador_dois.__name__}{s * 2}"

    resultados = {um: 0, dois: 0, "empate": 0}

    for _ in range(número_partidas):
        if tamanho is None:
            tamanho = random.randint(3, 9)

        res = jogar(jogador_um, jogador_dois, tamanho, interativo=False)
        if res == nome_um:
            resultados[um] += 1
        elif res == nome_dois:
            resultados[dois] += 1
        else:
            resultados["empate"] += 1

        res = jogar(jogador_dois, jogador_um, tamanho, interativo=False)
        if res == nome_um:
            resultados[dois] += 1
        elif res == nome_dois:
            resultados[um] += 1
        else:
            resultados["empate"] += 1

    for c in resultados:
        resultados[c] = f"{100 * resultados[c] / (2 * número_partidas):.2f}%"
    return resultados