import heapq
import math

filas = 5
columnas = 5

inicio = (0, 0)
objetivo = (4, 4)

def vecinos(nodo):
    x, y = nodo

    movimientos = [
        (-1, 0),  # arriba
        (1, 0),   # abajo
        (0, -1),  # izquierda
        (0, 1)    # derecha
    ]

    resultado = []

    for dx, dy in movimientos:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < filas and 0 <= ny < columnas:
            resultado.append((nx, ny))

    return resultado

def peso(u, v):
    return (u[0] + v[0] + u[1] + v[1]) % 5 + 1

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def euclidiana(a, b):
    return math.sqrt(
        (a[0] - b[0]) ** 2 +
        (a[1] - b[1]) ** 2
    )

def a_estrella(heuristica):

    cola = []

    # (f, contador, nodo)
    contador = 0

    heapq.heappush(
        cola,
        (0, contador, inicio)
    )

    costos = {
        inicio: 0
    }

    padres = {
        inicio: None
    }

    visitados = set()

    iteraciones = 0

    while cola:

        _, _, actual = heapq.heappop(cola)

        if actual in visitados:
            continue

        visitados.add(actual)
        iteraciones += 1

        if actual == objetivo:
            break

        for vecino in vecinos(actual):

            nuevo_costo = (
                costos[actual] +
                peso(actual, vecino)
            )

            if (
                vecino not in costos
                or nuevo_costo < costos[vecino]
            ):

                costos[vecino] = nuevo_costo
                padres[vecino] = actual

                f = (
                    nuevo_costo +
                    heuristica(vecino, objetivo)
                )

                contador += 1

                heapq.heappush(
                    cola,
                    (f, contador, vecino)
                )

    if objetivo not in padres:
        return [], float("inf"), iteraciones

    ruta = []

    actual = objetivo

    while actual is not None:
        ruta.append(actual)
        actual = padres[actual]

    ruta.reverse()

    return ruta, costos[objetivo], iteraciones

def ucs():
    return a_estrella(
        lambda a, b: 0
    )

ruta_ucs, costo_ucs, it_ucs = ucs()

ruta_man, costo_man, it_man = a_estrella(
    manhattan
)

ruta_euc, costo_euc, it_euc = a_estrella(
    euclidiana
)

print("=" * 50)
print("RESULTADOS")
print("=" * 50)

print("\nUCS")
print("Ruta:", ruta_ucs)
print("Costo:", costo_ucs)
print("Iteraciones:", it_ucs)

print("\nA* Manhattan")
print("Ruta:", ruta_man)
print("Costo:", costo_man)
print("Iteraciones:", it_man)

print("\nA* Euclidiana")
print("Ruta:", ruta_euc)
print("Costo:", costo_euc)
print("Iteraciones:", it_euc)

print("\n" + "=" * 50)
print("REDUCCIÓN DE ITERACIONES")
print("=" * 50)

if it_ucs > 0:

    reduccion_man = (
        (it_ucs - it_man) /
        it_ucs
    ) * 100

    reduccion_euc = (
        (it_ucs - it_euc) /
        it_ucs
    ) * 100

    print(
        "Manhattan:",
        round(reduccion_man, 2),
        "%"
    )

    print(
        "Euclidiana:",
        round(reduccion_euc, 2),
        "%"
    )

print("\n" + "=" * 50)
print("MAPA")
print("=" * 50)

print("S = Inicio")
print("G = Objetivo")
print("* = Ruta A* Manhattan")
print()

for x in range(filas):

    linea = ""

    for y in range(columnas):

        nodo = (x, y)

        if nodo == inicio:
            simbolo = "S"

        elif nodo == objetivo:
            simbolo = "G"

        elif nodo in ruta_man:
            simbolo = "*"

        else:
            simbolo = "."

        linea += simbolo + " "

    print(linea)