Partage
  • Partager sur Facebook
  • Partager sur Twitter

Je suis face à une singularité (listes python)

Tours de Hanoi

    24 mars 2022 à 12:53:33

    (edit: désolé pour l'espace d'inserrage de code qui te supprime toutes tes tabulations et indentations à chaque fois, il faut faire quelque chose, le corriger...)
    Bonjour,
    J'avais codé un programme récursif Tours de Hanoi qui imprime chaque étape (sous forme de listes) du jeu
    (toutes les étapes de résolution les unes à la suite des autres)
    # Tours de Hanoi
    
    n = 3 # nombre de disques
    depart = [ n-i for i in range(n)]
    intermediaire = []
    arrivee = []
    tours = [depart, intermediaire, arrivee]
    
    def deplacer(depart, arrivee) :
        sommet_depart = 0
        sommet_arrivee = 0
        if len(tours[depart]) > 0 :
            sommet_depart = tours[depart][len(tours[depart]) - 1]
        if sommet_depart > sommet_arrivee and sommet_arrivee != 0 :
            print("erreur : sommet", depart, " > sommet", arrivee) # règles du Jeu
        else:
            tours[depart].pop(len(tours[depart]) - 1)
            tours[arrivee].append(sommet_depart)
            print(tours) 
    def Hanoi(n, depart = 0, intermediaire = 1, arrivee = 2):
        if n > 0 :
            Hanoi(n - 1, depart, arrivee, intermediaire)
            deplacer(depart, arrivee)
            Hanoi(n - 1, intermediaire, depart, arrivee)
    Hanoi(n)
    
    # Résulat :
    [[3, 2], [], [1]]
    [[3], [2], [1]]
    [[3], [2, 1], []]
    [[], [2, 1], [3]]
    [[1], [2], [3]]
    [[1], [], [3, 2]]
    [[], [], [3, 2, 1]]
    Maintenant, pour un projet d'apprentissage par renforcement (paradigme différent de la récursion donc),
    j'ai besoin de créer une liste d'états (ou étapes si vous voulez) du jeu, liste qui se remplit au fur et
    à mesure que mon agent d'apprentissage explore (ce sera par un random() dans un premier temps dans le cas du 
    Quality-learning justement) son environnement des Tours de hanoi (les règles ayant été correctement implémentées
    comme je l'ai fait).
    Donc j'aimerais obtenir ceci par exemple (dans le cas idéal ou l'agent remplit sa "liste d'exploration" (ordonnée) en
    réussissant le jeu en une seule partie s'il connaît le principe de récursivité (ce n'est pas le cas) ) :
    Espace_des_etats_explorés =  [ [[3, 2], [], [1]] ,
    [[3], [2], [1]] ,
    [[3], [2, 1], []] ,
    [[], [2, 1], [3]] ,
    [[1], [2], [3]] ,
    [[1], [], [3, 2]] ,
    [[], [], [3, 2, 1]] ]
    Pour expliquer le problème auquel je suis confronté, je vous montre ce qui marche avec ce code test suivant
    puis ce qui ne marchera pas avec le même raisonnement par la suite. .
    space = []
    temp = [[] for i in range(4)]
    j = -1
    
    print(j)
    temp[j] = []
    print(temp[j]) 
    space.append(temp[j])
    print(space) ; print()
    j += 1
    
    print(j) 
    temp[j] = [0]
    print(temp[j]) 
    space.append(temp[j])
    print(space) ; print()
    j += 1
    
    print(j) 
    temp[j] = [1]
    print(temp[j]) 
    space.append(temp[j])
    print(space) ; print()
    j += 1
    
    print(j) 
    temp[j] = [2]
    print(temp[j]) 
    space.append(temp[j])
    print(space) 
    
    #sortie:
    -1
    []
    [[]]
    
    0
    [0]
    [[], [0]]
    
    1
    [1]
    [[], [0], [1]]
    
    2
    [2]
    [[], [0], [1], [2]]
    Quand vous examinez ce code ci-dessus vous observez bien que la liste "space" se remplit au fur et à mesure de 
    l'incrémentation du compteur j, et ce avec des listes différentes les unes des autres.
    Cependant si j'injecte le même processus dans le programme suivant :
    n = 3
    Depart = [ n - i for i in range(n)]
    Intermediaire = []
    Arrivee = []
    Tours = [ Depart, Intermediaire, Arrivee]
    
    Space = [ [[ n - i for i in range(n)], [], []] ]
    Temp = [ [] for i in range(n**3)]
    j = 0
    def move(Depart, Arrivee):
        sommet_D = 0
        sommet_A = 0
        if len(Tours[Depart]) > 0 :
            sommet_D = Tours[Depart][len(Tours[Depart]) - 1]
        if len(Tours[Arrivee]) > 0 :
            sommet_A = Tours[Arrivee][len(Tours[Arrivee]) - 1]
        if sommet_D > sommet_A and sommet_A != 0 :
            print("Error")
        else :
            global j    #on oublie pas le global
            Tours[Depart].pop(len(Tours[Depart]) - 1)
            Tours[Arrivee].append(sommet_D)
            print(Tours) # La liste Tours change à chaque fois
            print(j) # Vérification de j bien incrémenté
            Temp[j] = Tours # affectation :
            print(Temp[j]) # On vérifie bien qu'on place Tours
            # (à chaque fois une liste différente) à une variable incrémentée également 
            # différente à chaque fois (j ième élément de la liste globale Temp)
            Space.append(Temp[j]) # La liste est donc censée se remplir au fur et 
            # à mesure avec des listes Tours différentes (comme dans le code test plus haut)
    
            print(Space) 
            # MAIS on se retrouve avec j +1 fois la même liste Tours (à 
            # l'état/étape correspondant/e du jeu) à chaque 
            # incrémentation de j
    
            j += 1 # compteur j incrémenté pour la phase suivante....
    
    def hanoi(n, Depart = 0, Intermediaire = 1, Arrivee = 2):
        if n > 0 :
            hanoi(n - 1, Depart, Arrivee, Intermediaire)
            move(Depart, Arrivee)
            hanoi(n - 1, Intermediaire, Depart, Arrivee)
    hanoi(n)
    
    Out :
    
    [[3, 2], [], [1]] #Première étape du jeu (liste Tours)
    
    0                 # vérification du compteur j
    
    [[3, 2], [], [1]] # vérification de la variable Temp[j] ainsi différente à chaque phase, contenant alors Tours 
    
    # Space :
    
    [[[3, 2, 1], [], []], [[3, 2], [], [1]]] # jusqu'ici tout va bien avec .append( Temp[0])
    
    [[3], [2], [1]] # état (étape) suivant(e) du jeu des tours de Hanoi, liste différente de la précédente
    
    1               # idem compteur vérifié
    
    [[3], [2], [1]] # idem la NOUVELLE variable Temp[j = 1] contient le NOUVEL état du jeu (liste Tours actualisée),c'est vérifié
    
    # print(Space.append(Temp[1] = Tours) ):
    
    [[[3, 2, 1], [], []], [[3], [2], [1]], [[3], [2], [1]]] #??
    
    # pas logique, 
    
    # 2 fois la même liste Tours ajoutée à l'étape 3
    
    # (ensuite ce sera 6 fois la même liste à l'étape finale 7 juste à la suite de l'élément initial)
    
    # On devrait à mon sens obtenir:
    
    [[[3, 2, 1], [], []], [[3, 2], [], [1]], [[3], [2], [1]]] # Des listes différentes comme prévu (?)
    
    ... puis même observation
    
    ... rien ne va plus pour toute la suite et fin, même problème !
    Des idées ? 
    Merci !!

    -
    Edité par Rambert111 24 mars 2022 à 13:22:49

    • Partager sur Facebook
    • Partager sur Twitter
      24 mars 2022 à 13:11:11

      La ligne en cause est Temp[j] = Tours  qui ne copie pas les valeurs de Tours mais créé une référence à Tours (une modification de Temp[j] affectera Tours et inversement).

      Il faut faire une copie profonde (deepcopy) de Tours 

      • Partager sur Facebook
      • Partager sur Twitter
        24 mars 2022 à 17:00:03

        Est-ce que utiliser le slicing [:] est équivalent à deepcopy?
        Pour la singularité, c'est peut-être que ton code est trop lourd. C'est devenu un trou noir. :)

        Si j'ai une liste de listes, le slicing ne sera pas suffisant. Oui, Ça prend deepcopy

        -
        Edité par PierrotLeFou 24 mars 2022 à 17:03:05

        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

          24 mars 2022 à 17:13:44

          le slicing fait du shadow copy.
          En fait, avec le slicing (ou la fonction copy()) il n'y aurait pas de problème si la liste n'était pas composée de listes (ou plus généralement d'objets composés)
          • Partager sur Facebook
          • Partager sur Twitter
            25 mars 2022 à 0:52:35

            J'y ai pensé après car je me suis fait jouer un tour avec des listes de listes.
            • Partager sur Facebook
            • Partager sur Twitter

            Le Tout est souvent plus grand que la somme de ses parties.

            Je suis face à une singularité (listes python)

            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
            • Editeur
            • Markdown