import random

def Creator(rows=25,columns=25):
    """Generator macierzy rows x columns "#" """
    plane = [['#']*columns for i in range(rows)]            #generacja macierzy 25x25 "#"
    plane[0][int(columns/2)] = 'F'                          #ustawienie mety
    plane[rows-1][int(columns/2)] = 'S'                     #ustawienie startu
    return plane

def Input(file = 'lab.txt'):
    plane = []
    file = open(file,'r')
    a = file.readline()
    steps = 0
    while len(a) != 0:
        plane.append([])
        for i in range(len(a)-1):
            plane[steps].append(a[i])
        a = file.readline()
        steps += 1
    return plane

def Copy(plane):
    """Funkcja kopiująca macierze"""
    output = []
    for x in range(len(plane)):
        output.append([])
        for y in range(len(plane)):
            output[x].append(plane[x][y])
    return output

def Viewer(plane):
    """Druk macierzy labiryntu w zwartej formie"""
    for i in plane:
        print(''.join(i))
    print("\n")

def Obstacle(plane,lvl):
    """Wstawienie do labiryntu #lvl przeszkód losowo na parzystych polach.
    Wartość lvl najlepiej na poziomie rzędu macierzy."""
    p_range = len(plane)-1
    for i in range(lvl):
        row = random.randint(0,int(p_range/2))*2            #parzyste wartości row i col
        col = random.randint(0,int(p_range/2))*2
        if not ((plane[row][col] == "S") or (plane[row][col] == "F")):
            plane[row][col] = 'X'
    return plane

def Walker(plane):
    """Tyczenie labiryntu poprzez losową probę dojścia od (S)tartu do (F)inishu.
    Skok co dwa pola, żeby nie tworzyć pustych przestrzeni."""
    print("###WALKER###")
    p_range = len(plane)-1
    current = [p_range,int(p_range/2)]              #aktualna pozycja walkera
    steps = 0                                       #licznik pętli
    while plane[current[0]][current[1]] != "F":     #pętla dopóki nie znajdzie finisha
        temp = current[:]                           #wartość tymczasowa pozycji żeby sprawdzić prawilność następnego ruchu
        direct = random.randint(0,3)                #losowy kierunek ruchu 0-góra, 1-prawo, 2-dół, 3-lewo
        A = [[-2,0],[0,2],[2,0],[0,-2]]             #wektor przemieszczeń, indeks odpowiada kierunkowi
        temp[0] += A[direct][0]
        temp[1] += A[direct][1]
        if not ((temp[0] < 0) or (temp[1] < 0)) or ((temp[0] > p_range) or (temp[1]> p_range)):         #sprawdzenie czy indeksy nie są ujemne lub poza obszarem
            try:
                fwd_1 = plane[int((temp[0]+current[0])/2)][int((temp[1]+current[1])/2)]                 #sprawdzenie pierwszego pola na kierunku ruchu
                fwd_2 = plane[temp[0]][temp[1]]                                                         #sprawdzenie drugiego pola na kierunku ruchu
            except IndexError:                                                                          #nie powinno wystąpić, zbędny test (chyba)
                pass
            else:
                if ((fwd_1 == "#") or (fwd_1 == " ")) and ((fwd_2 == "#") or (fwd_2 == " ")):           #Jeśli pola fwd_1 i fwd_2 są ok:
                    plane[temp[0]][temp[1]] = ' '                                                       #zastąp je pustymi polami,
                    plane[int((temp[0]+current[0])/2)][int((temp[1]+current[1])/2)] = " "
                    current = temp[:]                                                                   #zaktualizuj pozycję
                elif fwd_2 == "F":                                                                      #Jeśli meta
                    plane[int((temp[0]+current[0])/2)][int((temp[1]+current[1])/2)] = " "
                    current = temp[:]
                    break
        steps += 1
    print(steps)                                                                                        #wypisz liczbę pętli
    return plane

def XClearer(plane):
    """Funkcja czyszcząca macierz labiryntu z "X"ów"""
    for i in range(len(plane)):
        for j in range(len(plane)):
            if plane[i][j] == "X":
                plane[i][j] = "#"
    return plane

def Nose(x,y,plane):
    """Funkcja analizuje sąsiednie pola i określa ich zawartość.
    Zwraca True kiedy można wejść na dane pole, "o" kiedy już się było na danym polu, False kiedy nie można wejść.
    Zwraca listę, w której indeksy odpowiadają kierunkom 0-góra, 1-prawo, 2-dół, 3-lewo"""
    nose = [0]*4
    A = [[-1,0],[0,1],[1,0],[0,-1]]                                     #wektor kierunków zgodnie z konwencją
    for i in A:
        try:
            temp = plane[x+i[0]][y+i[1]]                                #dla każdego kierunku test
            if (x+i[0] >= 0) and (y+i[1] >= 0):                         #indexerror nie łapie ujemnych
                if (temp == " ") or (temp == "F"):
                    nose[A.index(i)] = True
                elif temp == "o":
                    nose[A.index(i)] = "o"
                else:
                    nose[A.index(i)] = False
            else:
                nose[A.index(i)] = False
        except IndexError:
            nose[A.index(i)] = False
    return nose

def Solver(plane):
    """Funkcja losowo znajdująca drogę w labiryncie przy pomocji funkcji Nose()"""
    print("###SOLVER###")
    start = []
    finish = []
    A = [[-1,0],[0,1],[1,0],[0,-1]]                                     #wektor kierunkowy zgodnie z konwencją
    for i in range(len(plane)):
        for j in range(len(plane)):
            if plane[i][j] == "S":                                      #zlokalizowanie punktu startu i mety
                start = [i,j]
            if plane[i][j] == "F":
                finish = [i,j]
    current = start[:]                                                  #ustawienie się na starcie
    steps = 0
    while current != finish:
        temp = Nose(current[0],current[1],plane)                        #odpalamy nos
        ways = temp.count(True)                                         #ile jest możliwych dróg gdzie nie byliśmy
        plane[current[0]][current[1]] = "o"                             #zaznaczenie, że już się było na tym polu
        if ways == 1:                                                   #zawsze najpierw idzie tam gdzie nie był,
            direction = temp.index(True)
        elif (ways == 2) or (ways == 3):
            junction = [i for i in range(len(temp)) if temp[i] == True] #na skrzyżowaniach wybiera najpierw puste drogi
            direction = random.choice(junction)
        else:
            junction = [i for i in range(len(temp)) if temp[i] == "o"]  #jak już trzeba to wraca po śladach
            direction = random.choice(junction)
        current[0] += A[direction][0]
        current[1] += A[direction][1]
        steps += 1
    plane[start[0]][start[1]] = "S"                                     #ponowne wrzucenie punktów (S) i (F), które Solver zastępuje "o"
    plane[finish[0]][finish[1]] = "F"
    print(steps)
    return plane

def ReSolve(plane,init_steps = 10**6):
    steps = 0                                                   #liczba kroków (literek "o") w rozwiązanym labiryncie
    #Viewer(plane)
    for x in range(len(plane)):                                 #tworzenie nowego, zmodyfikowanego labiryntu
        for y in range(len(plane)):
            if plane[x][y] == "o":
                steps += 1
                plane[x][y] = " "
            elif (plane[x][y] == " ") or (plane[x][y] == "#"):
                plane[x][y] = "#"
    Solver(plane)                                               #rozwiązanie zmodyfikowanego labiryntu
    #Viewer(plane)
    if init_steps <= steps:                                     #jeśli nie osiągnięto poprawy kroków zakończenie funkcji
        return plane
    else:
        ReSolve(plane,init_steps = steps)   #rekurencja"""

def SolutionCopy(plane,solvedplane):
    """Funkcja nanosząca rozwiązanie na wyjściowy labirynt."""
    for x in range(len(solvedplane)):
        for y in range(len(solvedplane)):
            if solvedplane[x][y] == "o":
                plane[x][y] = "o"
    return plane

def main():
    op = input("Witaj! Chcesz żebym rozwiązał Twój labirynt (1), czy wygenerował losowy (2)?")
    if op == 1:
        plane = Input()
    else:
        rows = int(input("Podaj wysokość labiryntu (liczba nieparzysta)"))
        cols = int(input("Podaj szerokość labiryntu (Liczba nieparzysta)"))
        if rows%2 == 0:
            rows += 1
        if cols%2 == 0:
            cols += 1
        plane = Creator(rows,cols)
        Obstacle(plane, rows)
        Walker(plane)
        XClearer(plane)
    Lab = Copy(plane)
    print("###Oto wygenerowany labirynt:\n")
    Viewer(Lab)
    Solver(Lab)
    for i in range(3):
        ReSolve(Lab)
    print("###A oto rozwiązanie. Nienajlepsze, ale też nienajtańsze!")
    SolutionCopy(plane,Lab)
    Viewer(plane)

main()