# Univerzitet u Novom Sadu, Fakultet tehničkih nauka, Novi Sad, Srbija
# Studijski program OAS Informacioni inženjering
# Predmet Metode i tehnike nauke o podacima

# Pomoćni sadržaj


# %% Implementacija lavirinta

POLJE_POČETAK = "A"
POLJE_CILJ = "Z"
POLJE_PROHODNO = " "
POLJE_TRAG = "."
POLJE_PREPREKA = "#"
POLJA_PROHODNA = [POLJE_POČETAK, POLJE_CILJ, POLJE_PROHODNO, POLJE_TRAG]

class Lavirint:
    def __init__(self, struktura):
        self.struktura = struktura

    def očitavanje_dimenzija(self):
        return (len(self.struktura[0]) - 2, len(self.struktura) - 2)

    def očitavanje_sadržaja(self, x, y):
        širina, visina = self.očitavanje_dimenzija()

        if x >= 0 and x < širina and y >= 0 and y < visina:
            return self.struktura[y + 1][x + 1]

    def popunjavanje_sadržaja(self, x, y, vrednost):
        širina, visina = self.očitavanje_dimenzija()

        if x >= 0 and x < širina and y >= 0 and y < visina:
            red = self.struktura[y + 1]
            self.struktura[y + 1] = red[0:(x + 1)] + vrednost + red[(x + 2):]

    def proveravanje_prohodnosti(self, x, y):
        return self.očitavanje_sadržaja(x, y) in POLJA_PROHODNA

    def nalaženje_suseda(self, x, y):
        okolina = []

        širina, visina = self.očitavanje_dimenzija()

        if x >= 0 and x < širina and y >= 0 and y < visina:
            if x + 1 < širina:
                okolina.append((x + 1, y))
            if y - 1 >= 0:
                okolina.append((x, y - 1))
            if x - 1 >= 0:
                okolina.append((x - 1, y))
            if y + 1 < visina:
                okolina.append((x, y + 1))

        return okolina

    def nalaženje_elementa(self, element=POLJE_PROHODNO):
        for j, red in enumerate(self.struktura):
            for i, e in enumerate(red):
                if(e == element):
                    return (i - 1, j - 1)

    def nalaženje_početka(self):
        return self.nalaženje_elementa(POLJE_POČETAK)

    def nalaženje_cilja(self):
        return self.nalaženje_elementa(POLJE_CILJ)
    
    def __str__(self):                
        return "\n".join(self.struktura)
    
    def dodavanje_tragova(self, tragovi):
        for trag in tragovi:
            if self.očitavanje_sadržaja(trag[0], trag[1]) == POLJE_PROHODNO:
                self.popunjavanje_sadržaja(trag[0], trag[1], POLJE_TRAG)

    def uklanjanje_tragova(self):
        for i, red in enumerate(self.struktura):
            if POLJE_TRAG in red:
                self.struktura[i] = red.replace(POLJE_TRAG, POLJE_PROHODNO)


# %% Primer lavirinta

specifikacija = [
    "-----------------",
    "|A    #        #|",
    "|   ###  ####  #|",
    "|  ##    #      |",
    "|  ##    #   #  |",
    "|  ##  ###   #  |",
    "|  ##      ###  |",
    "|      #     # Z|",
    "-----------------"
]

lavirint = Lavirint(specifikacija)
print("Lavirint:")
print(lavirint)
print("")

print("Dimenzije lavirinta:", lavirint.očitavanje_dimenzija())

print("Sadržaj za (0, 0): <", lavirint.očitavanje_sadržaja(0, 0), ">")
print("Sadržaj za (14, 0): <", lavirint.očitavanje_sadržaja(14, 0), ">")
print("Sadržaj za (5, 0): <", lavirint.očitavanje_sadržaja(5, 0), ">")
print("Sadržaj za (5, 5): <", lavirint.očitavanje_sadržaja(5, 5), ">")
print("Sadržaj za (0, 6): <", lavirint.očitavanje_sadržaja(0, 6), ">")
print("Sadržaj za (14, 6): <", lavirint.očitavanje_sadržaja(14, 6), ">")

print("Prohodnost za (0, 0):", lavirint.proveravanje_prohodnosti(0, 0))
print("Prohodnost za (1, 0):", lavirint.proveravanje_prohodnosti(1, 0))
print("Prohodnost za (5, 0):", lavirint.proveravanje_prohodnosti(5, 0))
print("Prohodnost za (14, 6):", lavirint.proveravanje_prohodnosti(14, 6))

print("Susedi za (0, 0):", lavirint.nalaženje_suseda(0, 0))
print("Susedi za (14, 0):", lavirint.nalaženje_suseda(14, 0))
print("Susedi za (5, 0):", lavirint.nalaženje_suseda(5, 0))
print("Susedi za (5, 5):", lavirint.nalaženje_suseda(5, 5))
print("Susedi za (0, 6):", lavirint.nalaženje_suseda(0, 6))
print("Susedi za (14, 6):", lavirint.nalaženje_suseda(14, 6))

print("Nalaženje elementa <", POLJE_PROHODNO, ">:", 
      lavirint.nalaženje_elementa())
print("Nalaženje elementa <", POLJE_PREPREKA, ">:", 
      lavirint.nalaženje_elementa(POLJE_PREPREKA))

print("Početak:", lavirint.nalaženje_početka())
print("Cilj:", lavirint.nalaženje_cilja())
print("")

lavirint.dodavanje_tragova([(1, 0), (2, 0), (3, 0), (4, 0)])
print("Lavirint posle dodavanja tragova:")
print(lavirint)
print("")

lavirint.uklanjanje_tragova()
print("Lavirint posle uklanjanja tragova:")
print(lavirint)
print("")


# %% Implementacija rešavača lavirinta

def učitavanje_lavirinta(putanja):
    with open(putanja) as dat:     
        tekst = [red.replace("\n", "") for red in dat]
    return Lavirint(tekst)

def snimanje_lavirinta(putanja, lavirint):
    with open(putanja, "w") as dat:
        for red in lavirint.struktura:
            dat.write(red + "\n")

class ČvorPretrage:
    def __init__(self, x, y, nadređeni, vrednost):
        self.x = x
        self.y = y
        self.nadređeni = nadređeni
        self.vrednost = vrednost

    def __str__(self):
        return ("Čvor (<{},{}> | {} | {})".format(
            self.x, 
            self.y, 
            self.nadređeni if self.nadređeni is not None else "/", 
            self.vrednost))

class RešavačLavirinta:
    def __init__(self, zadatak, heuristika):
        self.zadatak = zadatak
        self.heuristika = heuristika
        self.neobrađeno = []
        self.obrađeno = {}

    def rešavanje(self, prikaz=True):
        self.neobrađeno = []
        self.obrađeno = {}

        početak = self.zadatak.nalaženje_početka()
        cilj = self.zadatak.nalaženje_cilja()

        self.neobrađeno.append(
            ČvorPretrage(početak[0], početak[1], None,
                         self.heuristika(početak[0], početak[1])))

        korak = 0
        
        while self.neobrađeno:
            korak += 1
            trenutni_čvor = self.neobrađeno.pop(0)

            if prikaz:
                print("\t", "{}. trenutni čvor: {}".format(
                    korak, trenutni_čvor))

            if trenutni_čvor.x == cilj[0] and trenutni_čvor.y == cilj[1]:
                rešenje = []
                cena = 0
                while trenutni_čvor is not None:
                    rešenje.append((trenutni_čvor.x, trenutni_čvor.y))
                    if trenutni_čvor.nadređeni is not None:
                        cena += 1
                    trenutni_čvor = trenutni_čvor.nadređeni
                rešenje.reverse()
                return (rešenje, cena)

            okolina = self.zadatak.nalaženje_suseda(
                trenutni_čvor.x, trenutni_čvor.y)

            for sused in okolina:
                if self.zadatak.proveravanje_prohodnosti(sused[0], sused[1]):
                    if ((sused[0], sused[1]) not in self.obrađeno and
                        not [a for a in self.neobrađeno if (
                            a.x == sused[0] and a.y == sused[1])]):
                        
                        novi_čvor = ČvorPretrage(
                            sused[0], sused[1], trenutni_čvor,
                            self.heuristika(sused[0], sused[1]))
                        
                        for i, a in enumerate(self.neobrađeno):
                            if novi_čvor.vrednost < a.vrednost:
                                self.neobrađeno.insert(i, novi_čvor)
                                break
                        else:
                            self.neobrađeno.append(novi_čvor)
            
            self.obrađeno[(trenutni_čvor.x, trenutni_čvor.y)] = trenutni_čvor

        return None


# %% Primer rešavanja lavirinta A

lavirint_a = Lavirint(struktura=[
    "-----------------",
    "|A    #        #|",
    "|   ###  ####  #|",
    "|  ##    #      |",
    "|  ##    #   #  |",
    "|  ##  ###   #  |",
    "|  ##      ###  |",
    "|      #     # Z|",
    "-----------------"
])

print("Lavirint A:")
print(lavirint_a)
print("")

cilj_a = lavirint_a.nalaženje_cilja()

def heuristika_a(x, y):
    return abs(x - cilj_a[0]) + abs(y - cilj_a[1])

print("Heuristika (0, 0): {}".format(heuristika_a(0, 0)))
print("Heuristika (0, 6): {}".format(heuristika_a(0, 6)))
print("Heuristika (7, 4): {}".format(heuristika_a(7, 4)))
print("Heuristika (14, 6): {}".format(heuristika_a(14, 6)))
print("")

rešavač_a = RešavačLavirinta(lavirint_a, heuristika_a)
print("Rešavanje")
rešenje_a = rešavač_a.rešavanje()
print("")

print("Rešenje: ", rešenje_a if rešenje_a is not None else "/")
print("")

if rešenje_a is not None:
    lavirint_a.dodavanje_tragova(rešenje_a[0])
    print("Lavirint A s rešenjem:")
    print(lavirint_a)
    print("")


# %% Primer rešavanja lavirinta B

lavirint_b = učitavanje_lavirinta("v13-05-lavirint.txt")

print("Lavirint B:")
print(lavirint_b)
print("")

cilj_b = lavirint_b.nalaženje_cilja()

def heuristika_b(x, y):
    return abs(x - cilj_b[0]) + abs(y - cilj_b[1])

rešavač_b = RešavačLavirinta(lavirint_b, heuristika_b)
rešenje_b = rešavač_b.rešavanje(prikaz=False)

if rešenje_b is not None:
    lavirint_b.dodavanje_tragova(rešenje_b[0])
    print("Lavirint B s rešenjem:")
    print(lavirint_b)

snimanje_lavirinta("v13-05-lavirint-rešenje.txt", lavirint_b)