Discussion :

[Tudko]

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)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# 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) ; print()
 
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) ) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
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. .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
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 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#Tours de Hanoi
 
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 !!

[Arioch]

Bonjour.

C'est tout bonnement illisible.

Vous pouvez encapsuler votre code entre les balises # en éditant votre message ?

[Tudko]

J'ai essayé de rechercher le balisage. Ce n'est pas les chevrons. J'ai aussi tenter markdown ```

[marco056]

Dur dur : les balises #

[Sve@r]

Bonjour

Tu mets ton code entre balises [code] et [/code]. Pourtant ce n'est pas ta première visite dans le forum Python. Tu n'as donc pas regardé comment on faisait dans les autres posts???
Sinon j'ai dans l'idée que tu es confronté à un souci analogue à celui-ci

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
space = []
temp = ["toto",]
space.append(temp)
temp[0]="titi"
space.append(temp)
print(space)

Bien que l'auteur cherche apparemment à obtenir [['toto'], ['titi']] il obtient [['titi'], ['titi']].

Solution

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
space = []
temp = ["toto",]
space.append(list(temp))
temp[0]="titi"
space.append(list(temp))
print(space)

=> on n'injecte pas dans "space" la liste "temp" originelle mais une copie à chaud de cette liste.

[Invité]

singularité

@Sve@r a probablement raison, c'est une erreur fréquente, voici quelques solutions :
• Brute force
• Slicing LISTE = liste[:].
• copy() LISTE = liste.copy().
• list() LISTE = list(liste).
• List comprehension LISTE = [i for i in liste].
• Starred Expression LISTE = [*liste].

Explications ici : https://therenegadecoder.com/code/ho...multiplication

Attention aussi aux listes imbriquées dans des listes de listes de listes de ... ;-) La fonction deepcopy() du module copy est prévu pour ce cas là !

[Tudko]

Bonjour

Tu mets ton code entre balises [code] et [/code]. Pourtant ce n'est pas ta première visite dans le forum Python. Tu n'as donc pas regardé comment on faisait dans les autres posts???
Sinon j'ai dans l'idée que tu es confronté à un souci analogue à celui-ci

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
space = []
temp = ["toto",]
space.append(temp)
temp[0]="titi"
space.append(temp)
print(space)

Bien que l'auteur cherche apparemment à obtenir [['toto'], ['titi']] il obtient [['titi'], ['titi']].

Solution

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
space = []
temp = ["toto",]
space.append(list(temp))
temp[0]="titi"
space.append(list(temp))
print(space)

=> on n'injecte pas dans "space" la liste "temp" originelle mais une copie à chaud de cette liste.

cela donne

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
[[3, 2], [], [1]]
 
0
 
[[3, 2], [], [1]]
 
 
[[[3, 2, 1], [], []], [[[3, 2], [], [1]], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]]
 
 
 
[[3], [2], [1]]
 
1
 
[[3], [2], [1]]
 
 
[[[3, 2, 1], [], []], [[[3], [2], [1]], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []], [[[3], [2], [1]], [[3], [2], [1]], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]]

[MPython Alaplancha]

Bonjour,
ce n'est effectivement pas un souci de copie de liste, mais un problème avec ton code.(je viens de le vérifier en appliquant deepcopy() sur tes listes)
Je n'ai cependant pas l'envie de me pencher dessus pour voir comment le modifier pour correspondre à tes attentes...
Tu y arriveras seul en utilisant pythontutors qui te montrera, en exécutant ton programme pas à pas, l'état de tes variables.
https://pythontutor.com/visualize.html#mode=edit

[tyrtamos]

Bonjour,

Ah ce problème des tours de Hanoï!

A titre de source d'inspiration, je m'étais penché sur la question, et voilà ce que j'ai fait:

Version récursive:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/python3
# -*- coding: utf-8 -*-
 
#############################################################################
def _hanoi(nbdisques, orig, dest, inter):
    global nbcoups
 
    if nbdisques>0:
 
        _hanoi(nbdisques-1, orig, inter, dest)
 
        # procède au déplacement
        dest[1].append(orig[1].pop())
 
        # affichage du déplacement
        nbcoups += 1
        tours = {1:"origine", 2:"intermédiaire", 3:"destination"}
        print("coup", nbcoups, " - déplace disque de ", tours[orig[0]], " à ", tours[dest[0]], "(", orig[0]+dest[0], ")")
        tours = sorted([orig] + [inter] + [dest], key=lambda v: v[0])
        print(tours[0][1], tours[1][1], tours[2][1])
        print()
 
        _hanoi(nbdisques-1, inter, dest, orig)
 
#============================================================================
def hanoi(nbdisques):
 
    # crée les tours avec les disques demandés sur la tour d'origine
    orig = [1, [i for i in range(nbdisques, 0, -1)]]
    inter = [2, []]
    dest = [3, []]
 
    # affiche la situation de départ pour les 3 tours
    print("Etat des 3 tours au départ, avec", nbdisques, "disques sur la tour origine:")
    print("origine:", orig[1], "intermédiaire:", inter[1], "destination:", dest[1])
    print()
 
    _hanoi(nbdisques, orig, dest, inter)
 
############################################################################# 
if __name__ == "__main__":
 
    # pour compter le nombre de déplacements nécessaires (var globale)
    nbcoups = 0
 
    n = 3 # nombre de disques à déplacer
 
    hanoi(n)

Affichage pour n=3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Etat des 3 tours au départ, avec 3 disques sur la tour origine:
origine: [3, 2, 1] intermédiaire: [] destination: []
 
coup 1  - déplace disque de  origine  à  destination ( 4 )
[3, 2] [] [1]
 
coup 2  - déplace disque de  origine  à  intermédiaire ( 3 )
[3] [2] [1]
 
coup 3  - déplace disque de  destination  à  intermédiaire ( 5 )
[3] [2, 1] []
 
coup 4  - déplace disque de  origine  à  destination ( 4 )
[] [2, 1] [3]
 
coup 5  - déplace disque de  intermédiaire  à  origine ( 3 )
[1] [2] [3]
 
coup 6  - déplace disque de  intermédiaire  à  destination ( 5 )
[1] [] [3, 2]
 
coup 7  - déplace disque de  origine  à  destination ( 4 )
[] [] [3, 2, 1]

On a bien la bonne quantité de déplacements: 2**3-1 => 7

Autre exemple avec n=5:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
Etat des 3 tours au départ, avec 5 disques sur la tour origine:
origine: [5, 4, 3, 2, 1] intermédiaire: [] destination: []
 
coup 1  - déplace disque de  origine  à  destination ( 4 )
[5, 4, 3, 2] [] [1]
 
coup 2  - déplace disque de  origine  à  intermédiaire ( 3 )
[5, 4, 3] [2] [1]
 
coup 3  - déplace disque de  destination  à  intermédiaire ( 5 )
[5, 4, 3] [2, 1] []
 
coup 4  - déplace disque de  origine  à  destination ( 4 )
[5, 4] [2, 1] [3]
 
coup 5  - déplace disque de  intermédiaire  à  origine ( 3 )
[5, 4, 1] [2] [3]
 
coup 6  - déplace disque de  intermédiaire  à  destination ( 5 )
[5, 4, 1] [] [3, 2]
 
coup 7  - déplace disque de  origine  à  destination ( 4 )
[5, 4] [] [3, 2, 1]
 
coup 8  - déplace disque de  origine  à  intermédiaire ( 3 )
[5] [4] [3, 2, 1]
 
coup 9  - déplace disque de  destination  à  intermédiaire ( 5 )
[5] [4, 1] [3, 2]
 
coup 10  - déplace disque de  destination  à  origine ( 4 )
[5, 2] [4, 1] [3]
 
coup 11  - déplace disque de  intermédiaire  à  origine ( 3 )
[5, 2, 1] [4] [3]
 
coup 12  - déplace disque de  destination  à  intermédiaire ( 5 )
[5, 2, 1] [4, 3] []
 
coup 13  - déplace disque de  origine  à  destination ( 4 )
[5, 2] [4, 3] [1]
 
coup 14  - déplace disque de  origine  à  intermédiaire ( 3 )
[5] [4, 3, 2] [1]
 
coup 15  - déplace disque de  destination  à  intermédiaire ( 5 )
[5] [4, 3, 2, 1] []
 
coup 16  - déplace disque de  origine  à  destination ( 4 )
[] [4, 3, 2, 1] [5]
 
coup 17  - déplace disque de  intermédiaire  à  origine ( 3 )
[1] [4, 3, 2] [5]
 
coup 18  - déplace disque de  intermédiaire  à  destination ( 5 )
[1] [4, 3] [5, 2]
 
coup 19  - déplace disque de  origine  à  destination ( 4 )
[] [4, 3] [5, 2, 1]
 
coup 20  - déplace disque de  intermédiaire  à  origine ( 3 )
[3] [4] [5, 2, 1]
 
coup 21  - déplace disque de  destination  à  intermédiaire ( 5 )
[3] [4, 1] [5, 2]
 
coup 22  - déplace disque de  destination  à  origine ( 4 )
[3, 2] [4, 1] [5]
 
coup 23  - déplace disque de  intermédiaire  à  origine ( 3 )
[3, 2, 1] [4] [5]
 
coup 24  - déplace disque de  intermédiaire  à  destination ( 5 )
[3, 2, 1] [] [5, 4]
 
coup 25  - déplace disque de  origine  à  destination ( 4 )
[3, 2] [] [5, 4, 1]
 
coup 26  - déplace disque de  origine  à  intermédiaire ( 3 )
[3] [2] [5, 4, 1]
 
coup 27  - déplace disque de  destination  à  intermédiaire ( 5 )
[3] [2, 1] [5, 4]
 
coup 28  - déplace disque de  origine  à  destination ( 4 )
[] [2, 1] [5, 4, 3]
 
coup 29  - déplace disque de  intermédiaire  à  origine ( 3 )
[1] [2] [5, 4, 3]
 
coup 30  - déplace disque de  intermédiaire  à  destination ( 5 )
[1] [] [5, 4, 3, 2]
 
coup 31  - déplace disque de  origine  à  destination ( 4 )
[] [] [5, 4, 3, 2, 1]

Conforme aussi avec 2**5-1 => 31 déplacements

Si ça intéresse quelqu'un, je dois avoir aussi une version non-récursive.

[Sve@r]

Malheureusement cela ne donne pas les listes voulues

Je crois qu'on attend de toi un peu plus que "ça marche pas"...

Je n'ai cependant pas l'envie de me pencher dessus pour voir comment le modifier pour correspondre à tes attentes...

Mouais, moi non plus. Je crois que c'est parce qu'il y a trop de commentaires

Tu y arriveras seul en utilisant pythontutors qui te montrera, en exécutant ton programme pas à pas, l'état de tes variables.
https://pythontutor.com/visualize.html#mode=edit

Ah ce fameux pythontutor. Toujours au top.

Ah ce problème des tours de Hanoï!

Moi aussi au début je pensais à ça. Mais en relisant son topic j'ai changé d'avis. Je pense en fait qu'il cherche à créer plutôt un truc IA qui "apprend" à résoudre par essais/echecs. Et là ce n'est plus pareil...

Si ça intéresse quelqu'un, je dois avoir aussi une version non-récursive.

https://www.developpez.net/forums/d2.../#post11571450

[Tudko]

Bonjour,
ce n'est effectivement pas un souci de copie de liste, mais un problème avec ton code.(je viens de le vérifier en appliquant deepcopy() sur tes listes)
Je n'ai cependant pas l'envie de me pencher dessus pour voir comment le modifier pour correspondre à tes attentes...
Tu y arriveras seul en utilisant pythontutors qui te montrera, en exécutant ton programme pas à pas, l'état de tes variables.
https://pythontutor.com/visualize.html#mode=edit

Merci pour pythontutor je connaissais pas
...

en effet en exécutant dedans la visualisation est monstrueusement complexe..

[MPython Alaplancha]

Je t'ai invité à utiliser pythontutor, mais c'est plutôt un outil pédagogique.
Il n'a pas été conçu pour débugger un code. Sur un code qui manipule trop de variables ou des variables à rallonge, j'imagine que sa sortie est vite difficilement lisible...
Si c'est le cas, et que l'on ne s'en sort pas avec de simple print(), il serait probablement plus pertinent d'utiliser des outils comme pdb:
https://docs.python.org/fr/3/library/pdb.html

[papajoker]

Plus simple d'utilisation que pdb dans un terminal,
certains ide python on un débuggeur intégré : pont d'arrêt, visualisation des variables globales et locale... vs code par exemple (cette url uniquement pour ces copies écran), pycharm et d'autres