Homework on Dijkstra

What does (1, 7) mean?

g=[[(1,7),(2,13)],[(3,5),(5,2)],[(0,13),(4,6)],[(0,11)],[(5,5)],[(2,8)],[]]
#On utilise des graphes implémenté sous forme de liste d'adjacence
#Le premier nombre d'un couple est le sommet vers lequel l'arête pointe et le second est le poid de celle-ci

What is the complexity of this update?

def update(self, c):
        """Méthode de mise à jour
           Pour c = (a, b), remplace la première occurrence de a rencontrée lors d'un parcours en largeur du tas par b.

        Args:
            c (couple d'élément du tas): Le premier élément est l'élément à remplacer. Le deuxième élément est l'élément qui le remplace
        """
        a, b = c
        assert(a in self), "L'élément qu'on cherche à remplacer n'existe pas dans le tas."
        indice = self.data.index(a)
        self.data[indice] = b
        if b > a:
            while self.key(self.data[leftChild(indice)], self.data[indice]) or self.data[rightChild(indice)].key(self.data[indice]):
                echange = leftChild(indice) if self.key(self.data[leftChild(indice)], self.data(rightChild)) else rightChild(indice)
                self.__swap(indice, echange)
                indice = echange
        else:
            while self.key(self.data[indice], self.data[parent(indice)]):
                self.__swap(indice, parent(indice))
                indice = parent(indice)

What do you think about the variable path?

    def path(self, start, end, exclude_nodes=None):
        exclude_nodes = exclude_nodes or []
        if (start, end) in self.memoized_paths:
            return self.memoized_paths[(start, end)]

        # Initialisation de la file de priorité
        heap = HeapQueue(key=lambda x: x[0])  # Trie par coût
        heap.push((0, start, []))  # (coût, nœud courant, chemin)

        visited = set()

        while heap.heap:
            cost, current, path = heap.pop()

            if current in visited or current in exclude_nodes:
                continue
            visited.add(current)

            # Mise à jour du chemin
            path = path + [current]

            if current == end:
                self.memoized_paths[(start, end)] = path
                return path

            # Exploration des voisins (chaque connexion a un poids de 1)
            for neighbor in self.graph.get(current, []):
                if neighbor not in visited and neighbor not in exclude_nodes:
                    heap.push((cost + 1, neighbor, path))

        return None  # Pas de chemin trouvé

What about the complexity of this function?

def update(self, x: T, prev_key_x: float) -> None:
        """Updates an element's priority (aka `key`).
        This should be called AFTER updating the `key` function.

        Args:
            x (T): The element
            prev_key_x (float): The previous key for the element
        """
        assert x in self.items
        i = self.items.index(x)

        key_x = self.key(x)

        if key_x == prev_key_x: return

        if key_x < prev_key_x: self._sift_down(i)
        else: self._sift_up(i)

Do you like integers? What is a and b?

class Graph():
    """Une class qui represente un graph orienté"""
    def __init__(self,n):
        self.mat=[[-1 for i in range(n)] for i in range(n)]

    def len(self):
        """Renvoie le nombre de sommet du graph"""
        return len(self.mat)

    ...

def disjtra(graph:Graph,a,b):
    """Disjtra sur graph avec a,b: Renvoie la distance min entre a,b et le chemin qu'il faut prendre"""
    assert(graph.len()>a)
    assert(graph.len()>b)
    queue=HeapQueue()
    l=[-1 for i in range(graph.len())]
    for enfant in graph.enfant(a):
        queue.diminuer_prio(enfant,l,a)
    if queue.vide() :
        return -1,[]
    i,d=queue.pop()
    while i!=b :
        for enfant in graph.enfant_avec_offset(i,d) :
            queue.diminuer_prio(enfant,l,i)
        if queue.vide() :
            return -1,[]
        i,d=queue.pop()
    return d,l

Clever!

    @abstractmethod
    def update(self, k: K, p: float):
        """
        Modifies the priority of the given key.
        Behaves the same as removing and adding back and should be more efficient.
        """
        self.remove(k)
        self.add(k, p)

I prefer a good old-style concrete implementation!

from PriorityQueue2 import PriorityQueue
from typing import List, Dict, Callable

def reconstruct_path(origine: Dict[int, int], depart: int, arrivee: int) -> List[int]:
    """
    Reconstruit le chemin du départ à l'objectif.

    origine: Un dictionnaire représentant le chemin inverse.
    depart: Le noeud de départ.
    arrivee: Le noeud d'arrivée.
    Renvoie une liste représentant le chemin du départ à l'arrivée.
    """
    chemin:List[int] = []
    noeud_actuel:int = arrivee # On commence par l'arrivée et on va remonter jusqu'au début
    while noeud_actuel != depart: # Tant qu'on n'est pas arrivé au début du chemin
        chemin.append(noeud_actuel)
        noeud_actuel = origine[noeud_actuel] # On remonte dans le dictionnaire
    chemin.append(depart)
    return chemin[::-1] # On inverse finalement la liste pour la remettre dans l'ordre

def a_star(G: List[List[float]], depart: int, arrivee: int, heuristic: Callable[[int, int], float]) -> tuple[Dict[int, float], List[int]]:
    """
    Implémentation de l'algorithme A* pour un graphe représenté par une matrice d'adjacence.

    G: La matrice d'adjacence du graphe, où G[i][j] représente le poids de l'arête
                   entre les noeuds i et j et vaut infini si aucune arête n'existe.
    depart: Le noeud de départ.
    arrivee: Le noeud d'arrivée.
    heuristic: Une fonction heuristique prenant deux noeuds et retournant une estimation
                      du coût pour aller du premier au second.
    Renvoie une paire contenant :
             - Un dictionnaire avec la distance minimale de chaque noeud depuis le départ.
             - Une liste représentant le chemin le plus court trouvé.
    """
    # Nombre total de noeuds dans le graphe
    n:int = len(G)

    # Initialisation des distances minimales connues (g) et des estimations totales (f)
    g:Dict[int, float] = {i: float('inf') for i in range(n)} # Initialisation de toutes les distances à inf
    g[depart] = 0
    f:Dict[int, float] = {i: float('inf') for i in range(n)} # Initialisation de toutes les distances à inf
    f[depart] = heuristic(depart, arrivee)

    # File de priorité pour explorer les noeuds avec les plus faibles coûts estimés
    pq = PriorityQueue()
    pq.push(depart, f[depart])

    # Dictionnaire pour suivre les origines des noeuds (reconstruction de chemin)
    origine:Dict[int,int] = {}

    # Boucle principale : exploration des noeuds jusqu'à épuisement ou atteinte de l'arrivée
    while not pq.is_empty():
        # Récupération du noeud avec le plus faible coût estimé
        noeud_actuel = pq.pop()

        if noeud_actuel == arrivee: # Si le noeud actuel est le noeud d'arrivée, le chemin optimal est trouvé
            return g, reconstruct_path(origine, depart, arrivee)

        # Exploration des voisins du noeud actuel
        for voisin in range(n):
            if G[noeud_actuel][voisin] != float('inf'):# S'il existe une arrête
                poids = G[noeud_actuel][voisin]
                g_score = g[noeud_actuel] + poids # Calcul du coût réel pour atteindre ce voisin

                if g_score < g[voisin]: # Si un chemin plus court vers ce voisin est trouvé
                    origine[voisin] = noeud_actuel # Mise à jour de l'origine du voisin
                    g[voisin] = g_score # Mise à jour du coût réel
                    f[voisin] = g[voisin] + heuristic(voisin, arrivee) # Mise à jour du coût estimé
                    pq.push(voisin, f[voisin]) # Ajout du voisin à la file de priorité

    # Si aucun chemin n'est trouvé jusqu'à l'arrivée
    return g, []

How to make the update?

# Implémentation avec un tas binaire
class BinaryHeapPriorityQ(PriorityQueue):
    def __init__(self):
        self.heap = []

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        return heapq.heappop(self.heap)[1]

    def is_empty(self):
        return len(self.heap) == 0

Concrete implementation

# Fonction Dijkstra utilisant la file de priorité
def dijkstra(graph : dict, start : int):
    """
    graph: Dictionnaire représentant un graphe pondéré (liste d'adjacence').
                  Par exemple: {0: [(1, 2), (2, 4)], 1: [(2, 1), (3, 7)], 2: [(3, 3)], 3: []}

                  Les couples sont de la forme : (voisin,poids de l'arrête vers ce voisin)
    start: Sommet de départ.

    Retourne un dictionnaire des distances minimales depuis le sommet de départ.
    """

    # Initialisation
    pq = BinaryHeapPriorityQ() # Notre file de priorité pour le traitement
    distances = {node: float('inf') for node in graph} # TOut le monde est à distance infinie au début
    distances[start] = 0
    pq.push(start, 0)

    while not pq.is_empty():
        current_node = pq.pop()

        # Exploration des voisins
        for neighbor, weight in graph[current_node]:
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                pq.push(neighbor, new_distance)

    return distances

Never comment the code

class HeapQueue(PriorityQueue):
    def __init__(self):
        self.h = []
        self.pos = {}
    def swap(self,i:int,j:int):
        self.h[i],self.h[j] = self.h[j],self.h[i]
        self.pos[self.h[i]],self.pos[self.h[j]]=i,j
    def push(self,a):
        (self.h).append(a)
        elt = a
        n = len(self.h)-1
        while n > 0 and self.h[n] < self.h[parent(n)]:
            self.swap(n,parent(n))
            n = parent(n)
    def is_empty(self):
        return (len(self.h)==0)
    def pop(self):
        assert (not self.is_empty())
        min = self.h[0]
        n = len(self.h)-1
        if n == 0:
            self.h = []
            return min
        self.h[0] = self.h[n]
        self.h.pop()
        i = 0
        while (leftChild(i)<n and self.h[i] > self.h[leftChild(i)]) or(rightChild(i)<n and self.h[i] > self.h[rightChild(i)]):
            if rightChild(i) < n and self.h[leftChild(i)] > self.h[rightChild(i)]:
                self.swap(i,rightChild(i))
                i = rightChild(i)
            else:
                self.swap(i,leftChild(i))
                i = leftChild(i)
        return min
    def update(self,a1,a2):
        if a1 in self.pos.keys():
            i = self.pos[a1]
            del self.pos[a1]
            self.h[i] = a2
            self.pos[a2] = i
            n = len(self.h)
            while (leftChild(i)<n and self.h[i] > self.h[leftChild(i)]) or(rightChild(i)<n and self.h[i] > self.h[rightChild(i)]):
                if rightChild(i) < n and self.h[leftChild(i)] > self.h[rightChild(i)]:
                    self.swap(i,rightChild(i))
                    i = rightChild(i)
                else:
                    self.swap(i,leftChild(i))
                    i = leftChild(i)
            while i > 0 and self.h[i] < self.h[parent(i)]:
                self.swap(i,parent(i))
                i = parent(i)

Concrete implementation

'''
    applique l'algorithme de dijkstra au graphe G représenté par sa matrice de poids M

    M: matrice des poids des éléments de G, M[i][j] est le poids de l'arête (i,j)
    a: sommet de départ
    b: sommet d'arrivée
'''
#je pense que ce programme devrait marcher, mais le problème vient de remove
def dijkstra(M, a, b):
    n=len(M)
    Q=HeapQueue() #sommets non explorés sous forme de tas binaire
    Q.elems=[k for k in range(n)]
    Q.swap(0,a) #on commence par le sommet a
    Q.key=[math.inf for k in range(n)] #liste des distances
    Q.key[a]=0
    while Q.elems!=[]: #tous les sommets ne sont pas encore explorés
        i=Q.elems[0] #sommet de poids le plus faible
        for j in range(n):
            update_distances(i,j,M,Q.key)
        Q.remove(0) #on a exploré ce sommet
    return(Q.key[b]) #distance de a à b

Do not create magic functions

    def __swap__(self,i : int,j : int) -> None:
        self.tas[i],self.tas[j] = self.tas[j],self.tas[i]

Let us depend on the implementation

g2 = WeightedGraph(10, directed=True)
    g2.adj_matrix = [
        [0, 4, 0, 0, 0, 0, 0, 0, 8, 5],
        [0, 0, 5, 0, 0, 0, 0, 0, 6, 0],
        [0, 0, 0, 6, 0, 0, 0, 0, 4, 0],
        [0, 0, 0, 0, 4, 0, 0, 5, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 3, 0, 0],
        [0, 0, 0, 0, 2, 0, 3, 3, 0, 0],
        [0, 0, 0, 0, 0, 2, 0, 0, 5, 4],
        [0, 0, 0, 4, 0, 0, 0, 0, 0, 0],
        [0, 0, 4, 0, 0, 0, 5, 0, 0, 3],
        [0, 0, 0, 0, 0, 0, 3, 0, 0, 0],
    ]

Let us be very concrete

`

def djikstra(s :int, l):
    """given a start s
    and a weighted graph in the form of an adjacency list,

    returns the list of the lower distance to s, with
    the path as the form of a predecessor list

    Args:
        s (int): s < len(l), a node of the graph G
        l ( list[ list[(int, float)] ]): adjacency list of G

    Returns:
        list[float], list[int]: lower distance to a, predecessor list
    """
    file_prio = tasFile()
    d = [float('inf')] * len(l)
    pred = [-1] * len(l)

    file_prio.empile(0,s)
    while not file_prio.estVide() :
        dist,v = file_prio.depile()
        d[v] = dist
        print(dist,v)
        for (u, p) in l[v]:
            if d[u] > d[v] + p :
                d[u] = p + d[v]
                pred[u] =
                # Given tasFile.actualise is in O(n), this is clearly suboptimal.
                # We could note use the actualise method, but admettons que j'ai
                # implémenté un dictionnaire pour que ce soit en O(logn)
                # On pourrait ne faire qu'empiler, quitte à empiler plusieurs fois le même état, mais je suis fatigué
                file_prio.actualise(d[u], u)

    return d,pred

Let us have multiple responsabilities

@dataclass
class Element:
    val : int #valeur de l'élément
    prio : int #priorité de l'élément
    precedent : int #sommet d'où l'on vient, pour reconstruire le chemin

#Ni Dijkstra ni A_star n'utilise update
    def update(self, x : Element):
        index = self.find_index(x)
        if not index: #on ne percole que si x est dans self.A
            raise IndexError("udpate sur un élément inexistant")
        self.A[index] = x
        self.percole_bas(index)
        self.percole_haut(index)

#renvoie le couple (chemin, distances)
def dijkstra(source : int, destination : int, gphe : Graphe) -> (Tuple, List[int]):
    Pfile = HeapQueue(comp_fun = lambda x,y : x.prio - y.prio, key = lambda x : x.val)
    vus = [False for i in range(gphe.nb_sommets)]
    distances = [float('inf') for i in range(gphe.nb_sommets)]
    distances[source] = 0
    came_from = [None for i in range(gphe.nb_sommets)]
    chemin = ()

    Pfile.push(Element(source, 0, -1))
    while Pfile.A:
        x = Pfile.pop()
        if not vus[x.val]:
            vus[x.val] = True
            distances[x.val] = x.prio
            came_from[x.val] = x.precedent
            if x.val == destination:
                break
            voisins = gphe.voisins(x.val)
            for (voisin,poids) in voisins:
                if not vus[voisin]:
                    Pfile.push(Element(voisin,poids + x.prio, x.val)) #il peut y avoir plusieurs fois la même valeur dans le tas

    if distances[destination] != float('inf'):
        chemin = reconstruct_chemin(came_from, source, destination)

    return (chemin, distances)

Very funny

def path_length[V](g: Graph[V], path: list[V]) -> float:
    """Compute the length of `path` in `g`
    This code makes me hate Python and imperative programming in general
    """
    l = 0
    for i in range(len(path) - 1):
        v = path[i]
        n = g.outgoing_neighbors(v)
        for u in filter(lambda u: u[0] == path[i + 1], n):
            l += u[1]
            break
    return l

Let us do not use object-programming features

graphe = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 5), ("D", 10)],
    "C": [("A", 2), ("B", 5), ("D", 3)],
    "D": [("B", 10), ("C", 3)]
}

distances, predecesseurs = dijkstra(graphe, "A")
print("Distances :", distances)
print("Prédécesseurs :", predecesseurs)

Let us do not use standard docstrings!

class PriorityQueue: #classe de file de priorité basique
    def __init__(self):
        self.elt=[]
        self.nb_elt=0


    def order(self,x,y)->bool: #l'ordre sur les éléments de la file
        return x<y


    def head(self):#fonction pour consulter la tête de file
        try:
            return self.elt[-1]

        except:
            print("La file est vide")


    def est_vide(self)->bool:#fonction pour tester si la file est vide
        return self.elt==[]


    def push(self,x)->None:#ajout d'un élément
        self.nb_elt+=1
        i=len(self.__elt)
        self.elt.append(x)
        while i>0 and not self.order(self.__elt[i],self.__elt[i-1]):
            self.elt[i],self.elt[i-1]=self.elt[i-1],self.elt[i]
            i-=1


    def pull(self):#suppression d'un élément
        self.nb_elt-=1
        return self.__elt.pop()

Projects

def copy(self):
        """
        Creates a deepcopy of the grid with the same objects but a different position in memory.
        """
        new_grid = [[set() for j in range (self.w)] for _ in range (self.h)]

        for i,j in self.grid_indices():
                for elt in self.get(i,j):
                    name = elt.name

                    # Copy the object with the same properties
                    new_elt = None
                    if type(elt) == Actionnable:
                        new_elt = Actionnable(elt.design, elt.position)
                    elif type(elt) == TextActionnable:
                        new_elt = TextActionnable(elt.design, elt.position)
                    elif type(elt) == TextAction:
                        new_elt = TextAction(elt.design, elt.position)
                    elif type(elt) == TextLink:
                        new_elt = TextLink(elt.design, elt.position)
                    new_grid[i][j].add(new_elt)

        return Gamegrid(new_grid)

if event.type == pygame.MOUSEBUTTONDOWN:
                    # If the cursor is in the 'rules' tile
                    if (self.__is_in_rectangle__(self.center_x_rules, self.center_y_rules)) :
                        rules.start_rules()
                    # If the cursor is in the 'lvl1' tile
                    elif (self.__is_in_rectangle__(self.center_x_lv1, self.center_y_lv1)) :
                        levels.Levels("level1").run()
                    # If the cursor is in the 'lvl2' tile
                    elif (self.__is_in_rectangle__(self.center_x_lv2, self.center_y_lv2)) :
                        levels.Levels("level2").run()
                    # If the cursor is in the 'lvl3' tile
                    elif (self.__is_in_rectangle__(self.center_x_lv3, self.center_y_lv3)) :
                        levels.Levels("level3").run()
                    # If the cursor is in the 'lvl4' tile
                    elif (self.__is_in_rectangle__(self.center_x_lv4, self.center_y_lv4)) :
                        levels.Levels("level4").run()
                    # If the cursor is in the 'lvl5' tile
                    elif (self.__is_in_rectangle__(self.center_x_lv5, self.center_y_lv5)) :
                        levels.Levels("level5").run()

if not has_bottom_water and not has_top_water and not has_left_water and not has_right_water:
    text = "h_d_b_g_"
    rotate = 0

elif not has_bottom_water and not has_top_water:
    if has_left_water and not has_right_water:
        text = "one_side_"
        rotate = 0
    elif not has_left_water and has_right_water:
        text = "one_side_"
        rotate = 180
    elif has_left_water and has_right_water:
        text = "two_side_op_"
        rotate = 0

elif not has_top_water and has_bottom_water:
    if not has_left_water and not has_right_water:
        text = "one_side_"
        rotate = 90
    elif has_left_water and not has_right_water:
        if has_bottom_left_water:
            text = "two_side_"
        else:
            text = "two_side_corner_"
        rotate = 180
    elif not has_left_water and has_right_water:
        if has_bottom_right_water:
            text = "two_side_"
        else:
            text = "two_side_corner_"
        rotate = 270
    elif has_left_water and has_right_water:
        text = "two_side_op_"
        rotate = 90

elif has_top_water and not has_bottom_water:
    if not has_left_water and not has_right_water:
        text = "one_side_"
        rotate = 270
    elif has_left_water and not has_right_water:
        if has_top_left_water:
            text = "two_side_"
        else:
            text = "two_side_corner_"
        rotate = 90
    elif not has_left_water and has_right_water:
        if has_top_right_water:
            text = "two_side_"
        else:
            text = "two_side_corner_"
        rotate = 0
    elif has_left_water and has_right_water:
        text = "one_side_"
        rotate = 90

elif has_bottom_water and has_top_water and has_left_water and has_right_water:
    text = "one_side_"
    rotate = 90
else:
    print("Erreur, dans la gestion de l'eau: ", i, j)

def search(self, init_state, ite=1000):
    """@brief Runs the MCTS algorithm from the initial state.
    @param init_state The initial state of the game.
    @param ite The number of iterations to perform (default is 1000).
    @return The state corresponding to the best move found.
    """
    root = MCTSNode(state=init_state)
    for _ in range(ite):
        node = root
        # Selection
        while not node.u_actions and node.childs:
            node = node.best_child(self.exp)
        # Expansion
        if node.u_actions:
            action = random.choice(node.u_actions)
            new_state = node.state.do_action(action)
            node = node.add_child(action, new_state)
        # Simulation
        result = self.simulate(node.state)
        # Backpropagation
        while node is not None:
            node.update(result)
            node = node.parent
    return root.best_child(0).state

def check_horizontal(data):
    """Vérifie si il existe un vainqueur diagonal, renvoie son numéro dans ce cas, et renvoie 0 sinon"""
    counter_1 = 0
    counter_2 = 0
    for i in range(n):
        counter_1 = 0
        counter_2 = 0
        for j in range(n):
            if(data[i][j] == 1):
                counter_1 += 1
                counter_2 = 0
                if(counter_1 == 4):
                    return 1
                if(counter_2 == 4):
                    return 2
            elif(data[i][j] == 2):
                counter_1 = 0
                counter_2 += 1
                if(counter_1 == 4):
                    return 1
                if(counter_2 == 4):
                    return 2
            else:
                counter_1 = 0
                counter_2 = 0
    return 0