main.py

import numpy as np
from queue import Queue
from Tree import TreeNode
import time
from Voiture import Voiture
from rendu_graphique import rendu_graphique
import pygame

liste_index = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
dictionnaire_index = {"A":1,"B":2,"C":3,"D":4,"E":5,"F":6,"G":7,"H":8,"I":9,
                      "J":10,"K":11,"L":12,"M":13,"N":14,"O":15,"P":16,"Q":17,"R":18,"S":19,
                      "T":20,"U":21,"V":22,"W":23,"X":24,"Y":25,"Z":26}

def test_case_libre(coordonnées_case, game) :
    """
    Cette fonction prend une case et une chaine de caractère représentant une partie.
    Elle renvoie un bolléen indiquant si la case est libre ou non
    """ 
    x_case_test = coordonnées_case[0]
    y_case_test = coordonnées_case[1]
    index = 1
    horizontale = True
    end = True
    case_libre = True
    if len(game) == 15 :
        end = False
    while end :
        c0 = game[0 + index*5]
        if c0 == "V"  :
            horizontale = False
            index += 1
        elif c0 == "E" :
            end = False
        else : 
            c1 = int(game[2 + index*5])
            c2 = int(game[3 + index*5])
            c3 = int(game[4 + index*5])
            if horizontale :
                if (c3 == y_case_test) and (x_case_test >= c2 and x_case_test <= c2 + (c1-1) ) :
                    case_libre = False   
            else :
                if (c2 == x_case_test) and (y_case_test >= c3 and y_case_test <= c3 + (c1-1)) :
                    case_libre = False  
            index += 1 
    return case_libre  

def test_fichier_game_possible (nom_du_fichier) :
    """
    Cette fonction prend un fichier test au format donnée par le prof.
    Elle renvoie un bolléen qui indique si la partie proposée est possible 
    et la chaine de carcatère représentant la partie
    """
    f = open (nom_du_fichier, 'r')
    taille  = f.readline().strip('\n')
    nb_voiture = f.readline().strip('\n')
    gameH = taille + liste_index[int(nb_voiture)-1] + '///'
    gameV = 'V////'
    game_possible = True

    for j in range (1,int(nb_voiture)+1) :
        ligne = f.readline()
        ligne = ligne.strip("\n")
        ligne = ligne.split(" ")
        index = ligne[0] ## Pas trop utile 
        orientation = ligne[1]
        taille = ligne[2]
        x_init = ligne[3] 
        y_init = ligne[4] 
        cases_voiture_libre = True

        if orientation == 'h' : 
            for i in range (int(taille)) :
                if not(test_case_libre((int(x_init)+i,int(y_init)), gameH  + gameV + 'E////')) :
                    cases_voiture_libre = False
                    game_possible = False
            if cases_voiture_libre :
                gameH += '/' + liste_index[j-1] + taille + x_init + y_init ## Forcer l'indice permet de classer les voitures toujours de la même façons
        
        elif orientation == 'v' :
            for i in range (int(taille)) :
                if not(test_case_libre((int(x_init),int(y_init)+i), gameH + gameV + 'E////')) :
                    cases_voiture_libre = False
                    game_possible = False
            if cases_voiture_libre :
                gameV += '/' + liste_index[j-1] + taille + x_init + y_init
    
    game = gameH + gameV + 'E////'
    
    ## Remettre les bons indices (dans l'ordre croissant)
    new_game = game[:5]
    end = True
    horizontale = 0 
    index = 1
    while end :
        c0 = game[0 + index*5+horizontale]
        if c0 == "V"  :
            horizontale = 5
            new_game += 'V////'
        elif c0 == "E" :
            end = False
        else :
            new_game += '/' + liste_index[index-1] + game[2+index*5 + horizontale:5+index*5 + horizontale]
            index += 1
    new_game += 'E////'
    return game_possible,new_game 

def affichage_basique (game) : 
    """
    Cette fonction prend une chaine de carcatère qui représente l'état de la partie 
    Elle affiche cette partie dans une matrice numpy 
    """
    taille_board = int(game[0])
    nb_voiture = dictionnaire_index[game[1]] # pas utile je pense mais bon c'est la 
    board = np.zeros((taille_board,taille_board), dtype = int)
    horizontal = True
    end = True
    index = 1

    while end :
        c0 = game[0 + index*5]
        if c0 == "V"  :
            horizontal = False
            index += 1
        elif c0 == "E" :
            end = False
        else : 
            index_voiture = game[1+index*5]
            taille_voiture = int(game[2+index*5])
            x_init_voiture = int(game[3+index*5]) - 1
            y_init_voiture = int(game[4+index*5]) - 1
            if horizontal :
                for i in range (taille_voiture) :
                    board[y_init_voiture][x_init_voiture+i] = dictionnaire_index[index_voiture]
            else :
                for i in range(taille_voiture) :
                    board[y_init_voiture+i][x_init_voiture] = dictionnaire_index[index_voiture]
            index += 1
    print(board)

def affichage_mieux(game,liste_moves, nombre_min_moves) :
    """
    Cette fonction prend en arguments une chaine de caractère qui représente la partie, la liste des
    mouvements pour résoudre le puzzle et le nombre minimum de mouvement nécessaire pour le faire
    Elle affiche la partie initiale, le nombre de mouvement minimlal et ces mouvements
    """
    rendu_graphique(game, liste_moves, nombre_min_moves)

def find_all_possible_moves (game) :
    """
    Cette fonction prend une chaine de caractère qui représente la partie en arguments.
    Elle renvoie une liste de l'ensemble des mouvements possibles pour toutes les voitures
    """
    taille_board = int(game[0])
    nb_voiture = dictionnaire_index[game[1]]
    possible_moves = []
    index = 1
    end = True
    horizontal = True

    while end :
        c0 = game[0 + index*5]
        if c0 == "V"  :
            horizontal = False
            index += 1
        elif c0 == "E" :
            end = False
        else : 
            index_voiture = game[1+index*5]
            taille_voiture = int(game[2+index*5])
            x_init_voiture = int(game[3+index*5]) 
            y_init_voiture = int(game[4+index*5])
            if horizontal :
                x_new_move = x_init_voiture-1
                y_new_move = y_init_voiture
                while x_new_move>0 and test_case_libre((x_new_move,y_new_move),game) :
                    new_move = index_voiture + 'l' + str(x_init_voiture-x_new_move)
                    possible_moves.append(new_move)
                    x_new_move -=1 

                x_new_move = x_init_voiture + taille_voiture
                y_new_move = y_init_voiture
                while x_new_move <= taille_board and test_case_libre((x_new_move,y_new_move),game) :
                    new_move = index_voiture + 'r' + str(x_new_move-(x_init_voiture+taille_voiture-1))
                    possible_moves.append(new_move)
                    x_new_move +=1

                ## La suite ne sert que au traitement du mouvement de sortie de la voiture rouge
                if index_voiture == 'A' and  x_new_move > taille_board : 
                    new_move = 'ArE' 
                    possible_moves.append(new_move)

            else :
                x_new_move = x_init_voiture
                y_new_move = y_init_voiture-1
                while y_new_move>0 and test_case_libre((x_new_move,y_new_move),game) :
                    new_move = index_voiture + 'u' + str(y_init_voiture-y_new_move)
                    possible_moves.append(new_move)
                    y_new_move -=1 
                
                x_new_move = x_init_voiture
                y_new_move = y_init_voiture + taille_voiture
                while y_new_move <= taille_board and test_case_libre((x_new_move,y_new_move),game) :
                    new_move = index_voiture + 'd' + str(y_new_move-(y_init_voiture+taille_voiture-1))
                    possible_moves.append(new_move)
                    y_new_move +=1                 
            index += 1
    return possible_moves

def creation_un_etage (Node : TreeNode) :
    """
    Cette fonction prend un noeud (qui a donc un état de partie)
    Elle ajoute l'ensemble des parties accesibles en partant de celle initiales avec tous les mouvements possibles 
    Elle vérifie aussi que les nouveaux états n'ont pas déja été observé (a ce moment la ne crée par d'enfant associé)
    De plus renvoie un bolléen indiquant si il est possible de finir la partie (faire sortir la voiture rouge)
    """
    game = Node.get_game()
    all_possible_moves = find_all_possible_moves(game)
    partie_terminee = False
    for move in all_possible_moves :
        if move == 'ArE' : ## Partie terminée
            partie_terminee = True
            break 
        else :
            index_voiture = dictionnaire_index[move[0]]
            direcion = move[1]
            nombre_case = int(move[2])
            match direcion :
                case 'r' : 
                    new_game = game[:index_voiture*5+3] + str(int(game[index_voiture*5 + 3]) + nombre_case) + game[index_voiture*5+4:]
                case 'l' :
                    new_game = game [:index_voiture*5+3] + str(int(game[index_voiture*5 + 3]) - nombre_case) + game[index_voiture*5+4:]
                case 'd' :
                    new_game = game [:(index_voiture+1)*5+4] + str(int(game[(index_voiture+1)*5 + 4]) + nombre_case) + game[(index_voiture+1)*5+5:]
                case 'u' :
                    new_game = game [:(index_voiture+1)*5+4] + str(int(game[(index_voiture+1)*5 + 4]) - nombre_case) + game[(index_voiture+1)*5+5:]
            New_node = TreeNode(new_game, move)
            Node.add_child(New_node)
    return partie_terminee

def solve_game (initial_game_state) :
    """
    Cette fonction prend une chaine de caractère représentant une partie et cherche le nombre de mouvement 
    minimum pour résoudre le puzzle (utilise une file pour parcourir l'arbre en largeur)
    """
    Node_already_explored = {}
    partie_terminee = False  
    compteur_node_explored = 0 
    File_Node_to_Explore = Queue()
    File_Node_to_Explore.put(initial_game_state)
    while not(partie_terminee) and compteur_node_explored < 10000 :  
        actual_node = File_Node_to_Explore.get()        
        if actual_node.get_game() in Node_already_explored.keys() :
            pass
        else : 
            compteur_node_explored+=1
            Node_already_explored[actual_node.get_game()] = actual_node.get_profondeur()
            partie_terminee = creation_un_etage(actual_node)
            for i in range(len(actual_node.children)) :
                File_Node_to_Explore.put(actual_node.children[i])
    return compteur_node_explored, actual_node.get_profondeur() + 1, actual_node

def reconstruire_moves (last_node) :
    """
    Cette fonction permet de retrouver les mouvements fait pour résoudre le puzzle en partant du noeud finale 
    C'est à dire le noeud à partir du quel la voiture rouge peut quitter le board
    """
    liste_moves = []
    current_node = last_node
    while current_node.parent :
        liste_moves.append(current_node.get_last_move())
        current_node = current_node.parent
    liste_moves = liste_moves[::-1]
    liste_moves.append('ArE')
    return liste_moves

def solve_fichier (nom_fichier, affichage) :
    """
    Fonction a qui on donne le fichier test.
    Vérifie que la partie est possible puis calcule la solution (nombre de mouvements min et ces mouvements)
    Puis affiche le tout. 
    Renvoie, nombre mouv min, ces mouv, le nombre de noeud explorés et le temps pour faire ça
    Affichage est un bolléen qui dit si on veut afficher la solution ou pas 
    """
    start_time = time.time()
    fichier_possible, initialisation_game = test_fichier_game_possible(nom_fichier) 
    if not(fichier_possible) :
        raise Exception ("Le fichier n'est pas valide")
    
    Node_Initial = TreeNode(initialisation_game)
    nombre_node_explored, nombre_min_move, last_node = solve_game(Node_Initial)
    liste_moves = reconstruire_moves(last_node)
    end_time = time.time()
    time_running = end_time-start_time
    if affichage :
        affichage_mieux(initialisation_game,liste_moves, nombre_min_move)
    return nombre_min_move, liste_moves, nombre_node_explored, time_running


#print(solve_fichier("ExRushHour/GameP00.txt"))
#print(solve_fichier("ExRushHour/GameP01.txt"))
#print(solve_fichier("ExRushHour/GameP02.txt"))
#print(solve_fichier("ExRushHour/GameP03.txt"))
#print(solve_fichier("ExRushHour/GameP04.txt"))
#print(solve_fichier("ExRushHour/GameP05.txt"))
#print(solve_fichier("ExRushHour/GameP06.txt"))
#print(solve_fichier("ExRushHour/GameP07.txt"))
#print(solve_fichier("ExRushHour/GameP08.txt"))
#print(solve_fichier("ExRushHour/GameP09.txt"))
#print(solve_fichier("ExRushHour/GameP10.txt"))
#print(solve_fichier("ExRushHour/GameP11.txt"))
#print(solve_fichier("ExRushHour/GameP12.txt"))
#print(solve_fichier("ExRushHour/GameP13.txt"))
#print(solve_fichier("ExRushHour/GameP14.txt"))
#print(solve_fichier("ExRushHour/GameP41.txt"))

for i in range(42) :
    if i < 10 :
        nom_fichier = "ExRushHour/GameP0" + str(i) + ".txt"
    else : 
        nom_fichier = "ExRushHour/GameP" + str(i) + ".txt"
    print(solve_fichier(nom_fichier, False))