Discussion :

[___Obi___]

Bonjour,

Je suis débutant. Je commence à me ré-intéresser à la programmation après 25 ans (j'avais fait du C pendant mes études).
Aujourd'hui j'essaie de fabriquer un casse-tête IRL; dont le principe est: un grand cube de 4 x4x4 , composé de 64 petits cubes indépendants, dont 21 de couleur bleu (code 0), 21 de couleur rouge (code 1) et 22 de couleur jaune (10). Il faut agencer de manière à ce que chaque ligne (verticales, horizontales, diagonales) ne soit jamais composé de 3 couleurs, ou de 1 seule couleur.

J'ai écrit le programme, mais il est trop à exécuter. A cause d'une imbrication de 4 boucle de 1 à 2264, soit 2.5E+13.



Auriez-vous une piste d'optimisation à me donner ?

Obi

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
# 4x4x4, 2 couleurs, bonnes lignes en 3/1 et 2/2
#Définition des bonnes lignes, qui sont composées de 2 couleurs différentes, soit 2/2 soit 1/3
TBL=[[0,0,0,1],[0,0,0,10],[0,0,1,0],[0,0,1,1],[0,0,10,0],[0,0,10,10],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[0,10,0,0],[0,10,0,10],[0,10,10,0],[0,10,10,10],[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,10],[1,1,10,1],[1,1,10,10],[1,10,1,1],[1,10,1,10],[1,10,10,1],[1,10,10,10],[10,0,0,0],[10,0,0,10],[10,0,10,0],[10,0,10,10],[10,1,1,1],[10,1,1,10],[10,1,10,1],[10,1,10,10],[10,10,0,0],[10,10,0,10],[10,10,1,1],[10,10,1,10],[10,10,10,0],[10,10,10,1]]
print (TBL)
print (TBL[1][2])
TBC = [[0 for _ in range(16)] for _ in range(2247)]
CT= [[0 for _ in range(4)] for _ in range(4)]
c=0
BC=0
#Boucles afin de déterminer les bonnes couches, composées de 4  bonnes lignes
for x in range(0,40,1):
    for y in range(0,40,1):
        for z in range(0,40,1):
            for w in range(0,40,1):
                CT[0][0]=TBL[x][0]
                CT[0][1]=TBL[x][1]
                CT[0][2]=TBL[x][2]
                CT[0][3]=TBL[x][3]
                CT[1][0]=TBL[y][0]
                CT[1][1]=TBL[y][1]
                CT[1][2]=TBL[y][2]
                CT[1][3]=TBL[y][3]
                CT[2][0]=TBL[z][0]
                CT[2][1]=TBL[z][1]
                CT[2][2]=TBL[z][2]
                CT[2][3]=TBL[z][3]
                CT[3][0]=TBL[z][0]
                CT[3][1]=TBL[w][1]
                CT[3][2]=TBL[w][2]
                CT[3][3]=TBL[w][3]
            TD1=1
            V1=CT[0][0]+CT[1][1]+CT[2][2]+CT[3][3]
            if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                TD1=0
            TD2=1
            V1= (CT[0][3]+CT[1][2]+CT[2][1]+CT[3][0])  
            if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
               TD2=0
            TV1=1
            V1=(CT[0][0]+CT[1][0]+CT[2][0]+CT[3][0])
            if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                TV1=0
            TV2=1
            V1=(CT[0][1]+CT[1][1]+CT[2][1]+CT[3][1])
            if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                TV2=0
            TV3=1
            V1=(CT[0][2]+CT[1][2]+CT[2][2]+CT[3][2])
            if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                TV3=0
            TV4=1
            V1=(CT[0][3]+CT[1][3]+CT[2][3]+CT[3][3])
            if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                TV4=0
            if TD1==1 and TD2==1 and TV1==1 and TV2==1 and TV3==1 and TV4==1:
                #print (CT, TD1, TD2, TV1, TV2, TV3, TV4)
                BC=BC+1
                TBC[BC][0]=CT[0][0]
                TBC[BC][1]=CT[0][1]
                TBC[BC][2]=CT[0][2]
                TBC[BC][3]=CT[0][3]
                TBC[BC][4]=CT[1][0]
                TBC[BC][5]=CT[1][1]
                TBC[BC][6]=CT[1][2]
                TBC[BC][7]=CT[1][3]
                TBC[BC][8]=CT[2][0]
                TBC[BC][9]=CT[2][1]
                TBC[BC][10]=CT[2][2]
                TBC[BC][11]=CT[2][3]
                TBC[BC][12]=CT[3][0]
                TBC[BC][13]=CT[3][1]
                TBC[BC][14]=CT[3][2]
                TBC[BC][15]=CT[3][3]
print ("nombre de bonnes couches ",BC)
Cube= [[0 for _ in range(16)] for _ in range(4)]
c1=0
c2=0
c3=0
c4=0
tot=0
sol=0
#Boucles pour ttester les bonnes couches, 
for c1 in range(1,2246,1):
    print(c1)
    for c2 in range(1,2246,1):
        print(c2)
        for c3 in range(1,2246,1): 
            for c4 in range(1,2246,1):
                #Tests afin de vérifier que le grand cube est composé au global du bon nombre total de 0 (21) , de 1 (21) et donc forcément de 10 (22)
                nb0C1=TBC[c1].count(0)
                nb0C2=TBC[c2].count(0)
                nb0C3=TBC[c3].count(0)
                nb0C4=TBC[c4].count(0)
                nb0=nb0C1+nb0C2+nb0C3+nb0C3
                if nb0==21:
                    test=1
                    nb1C1=TBC[c1].count(1)
                    nb1C2=TBC[c2].count(1)
                    nb1C3=TBC[c3].count(1)
                    nb1C4=TBC[c4].count(1)
                    nb1=nb1C1+nb1C2+nb1C3+ nb1C4
                    if nb1==21:
                        tot=tot+1
                        #print (tot)
                        #test du cube, 36 lignes restantes, 16 verticales, 16 diagonales et 4 grandes diagonales
                        test=1
                        V1=TBC[c1][0]+TBC[c2][0]+TBC[c3][0]+TBC[c4][0]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][1]+TBC[c2][1]+TBC[c3][1]+TBC[c4][1]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][2]+TBC[c2][2]+TBC[c3][2]+TBC[c4][2]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][3]+TBC[c2][3]+TBC[c3][3]+TBC[c4][3]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        #2eme verticlaes
                        V1=TBC[c1][4]+TBC[c2][4]+TBC[c3][4]+TBC[c4][4]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][5]+TBC[c2][5]+TBC[c3][5]+TBC[c4][5]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][6]+TBC[c2][6]+TBC[c3][6]+TBC[c4][6]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][7]+TBC[c2][7]+TBC[c3][7]+TBC[c4][7]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        #3eme verticlaes
                        V1=TBC[c1][8]+TBC[c2][8]+TBC[c3][8]+TBC[c4][8]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][9]+TBC[c2][9]+TBC[c3][9]+TBC[c4][9]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][10]+TBC[c2][10]+TBC[c3][10]+TBC[c4][10]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][11]+TBC[c2][11]+TBC[c3][11]+TBC[c4][11]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                         #4eme verticlaes
                        V1=TBC[c1][12]+TBC[c2][12]+TBC[c3][12]+TBC[c4][12]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][13]+TBC[c2][13]+TBC[c3][13]+TBC[c4][13]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][14]+TBC[c2][14]+TBC[c3][14]+TBC[c4][14]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        V1=TBC[c1][15]+TBC[c2][15]+TBC[c3][15]+TBC[c4][15]
                        if V1==0  or V1==4 or V1==11 or V1==12  or V1==21 or V1==40:
                            test=0
                        if test==1:
                            print(TBC[c1], TBC[c2], TBC[c3], TBC[c4])
                            sol=sol+1
print("fin de programme")
print(sol)

[wiztricks]

Salut,

Auriez-vous une piste d'optimisation à me donner ?

On ne saura pas faire aller plus vite des boucles... sauf à éviter de les faire.
Ce qui suppose d'abord de trouver un meilleur algorithme (et poser la question dans le forum ad hoc) puis utiliser des fonctionnalités any, all, listes en compréhension du langage qui "poussent" les boucles dans le code C de l'interpréteur (ça ira plus vite) ou des bibliothèques externes comme numpy qui seront optimisées côté "tableaux" (mais il faut passer du temps pour apprendre à les utiliser).

- W

[___Obi___]

Nota : Le langage est bien en Python.

[Sve@r]

Bonjour

A cause d'une imbrication de 4 boucle de 1 à 2264, soit 2.5E+13.

Hé oui, c'est expliqué dans la théorie des jeux. Un ordinateur a ses limites. Par exemple il ne peut pas encore calculer toutes les possibilités d'une partie d'échecs. Le million ça va, le milliard il arrive à gérer mais 10 milliards (1E10) c'est la limite. Alors 1E13...

Auriez-vous une piste d'optimisation à me donner ?

Ben à minima optimiser les tests. Quand je vois if V1==0 or V1==4 or V1==11 or V1==12 or V1==21 or V1==40 ligne 34 puis de nouveau if V1==0 or V1==4 or V1==11 or V1==12 or V1==21 or V1==40 ligne 38...
Accessoirement tu peux utiliser "in", pas plus rapide mais plus lisible (if V1 in (0, 4, 11, 12, 21, 40)) et supprimer les parenthèses inutiles (V1=(CT[0][0]+CT[1][0]+CT[2][0]+CT[3][0]) ligne 41). Une parenthèse ben ça a aussi un coût, et quel qu'il soit il est toujours plus cher que pas de parenthèse quand ce n'est pas nécessaire.
Ensuite tu peux regarder le module itertools qui peut te générer des boucles de ton choix. Comme il est écrit en C (enfin je pense) il ira beaucoup plus vite que Python. Ensuite t'as le module numpy, dédié à la gestion des matrices. Si tu arrives à convertir ton algorithme en matrice ensuite il peut te réduire certaines étapes.

dont 21 de couleur bleu (code 0), 21 de couleur rouge (code 1) et 22 de couleur jaune (10)

Je reconnais là la "patte" du prog C, avec ces valeurs si typiquement binaires permettant de par exemple les combiner (un cube 11 serait à la fois rouge et jaune = orange). Toutefois dans ces valeurs, on commence généralement à 1, le 0 étant plutôt réservé à l'info "pas de valeur". De plus, là comme en C t'as le droit de travailler en hexa et écrire bleu=0x0001, rouge=0x0010, jaune=0x0100 (je sais pas si ça sera utile ici ou pas mais ça ne coûte rien).

[Invité]

Salut !

Questions bêtes :
- chaque petit cube a une couleur unie ou c'est comme le Rubik's cube ?
- dans le premier cas, sauf erreur de ma part c'est impossible :
Dans cet exemple partiel si je veux caser du bleu ben c'est mort :

[Sve@r]

C'est toi qui a dessiné ça???

Dans cet exemple partiel si je veux caser du bleu ben c'est mort :

Oui, c'est pour ça qu'on appelle ça un "casse-tête"

[Invité]

C'est toi qui a dessiné ça???

Vive photoshop ! =)

Oui, c'est pour ça qu'on appelle ça un "casse-tête"

J'ai mal réfléchi effectivement, je pensais qu'il était impossible d'avoir 3 couleurs sur une face

[___Obi___]

Voici un développé du grand cube, avec des essais de remplissage pour les cubes en surface. C'est bien possible de caser les 3 couleurs, le programme trouve 2264 bonnes couches.


Ce casse-tête 4x4x4 est une variante que j’étudie, à partir du casse-tête 49lines (d’ailleurs si quelqu’un sait ou en trouver…). C’est la même chose mais en 3x3x3. J’ai écrit le programme pour le résoudre et trouver les solutions.
Mais en passant au 4x4x4 (dont je ne sais pas si il y a une solution) je me retrouve face au problème car il y a par exemple 2264 bonnes couches.

Ce n’est pas du C (même si mon cerveau en a gardé ne forte empreinte)
Pensez-vous qu’il va tourner plus vite en C qu’en python ?
Quant aux valeurs 0, 1, 10 ; ce sont des valeurs qui me permettent de vérifier facilement si la ligne est bonne car je fais l’addition des 4 et je je la compare aux sommes des mauvaises lignes. C’est le moyen le plus simple que j’ai trouvé. Mais il y a aurait aussi la possibilité de tester une ligne en la comparant à la ligne des bonnes lignes. Pensez-vous que cela soit plus rapide ?
OK, je vais rationaliser les parenthèse, et utiliser la fonction « in ».

J'ai parcouru le sommaire de "itertools", i y a bien la fonction "permutation" qui pourrait m'aider.

[Sve@r]

Vive photoshop ! =)

Et ceux qui savent s'en servir parce que ça, je sais pas faire (enfin tout s'apprend).
Moi Photoshop je l'utilise pour claquer ma signature sur des documents numérisés ou mettre une phrase en filigrane sur ma CNI quand je dois l'envoyer à un tiers. J'écris en général un truc ressemblant à "document envoyé à machin (+n° tel éventuellement) pour telle raison" en tout petit sur toute la surface. Ca évite qu'elle se retrouve sur le darkweb à servir de caution pour monter des sociétés écran.

Pensez-vous qu’il va tourner plus vite en C qu’en python ?

Attention, j'ai pas parlé de le faire en C (même si un langage compilé est plus rapide qu'un interprété et que le C, qui est principalement axé sur la vitesse est le plus rapide des compilés), j'ai parlé de modules.
Car bien que Python soit de l'interprété (ou du semi-compilé), il peut importer des modules écrits en C (étant lui-même écrit en C). Donc quand il utilise un module qui fait "truc", le truc est plus vite fait que s'il le faisait lui.

Quant aux valeurs 0, 1, 10 ; ce sont des valeurs qui me permettent de vérifier facilement si la ligne est bonne car je fais l’addition des 4 et je je la compare aux sommes des mauvaises lignes.

J'ai pas parlé des autres, j'ai parlé de la valeur "0" qui est souvent une valeur à garder "à part". Parce que le système de la somme marchera aussi avec 1, 10 et 100 (ou 1, 2 et 4 si on prend ça en hexa). Le souci (ou l'avantage, ça dépend comment on voit ça) du 0 c'est qu'il est le booléen opposé aux autres valeurs (il vaut False alors que les autres valent True). Ainsi avec ta convention "bleu=0", any(ligne) ne verra rien si la ligne ne contient que du bleu.

C’est le moyen le plus simple que j’ai trouvé. Mais il y a aurait aussi la possibilité de tester une ligne en la comparant à la ligne des bonnes lignes. Pensez-vous que cela soit plus rapide ?

Ben... au lieu de chercher les "bonnes lignes", n'aurais-tu pas avantage à chercher les mauvaises? D'après ce que j'ai compris, une mauvaise ligne serait une ligne composée d'une seule couleur ou de plus de trois couleurs. En Python t'as un outil assez pratique: le "set" (ensemble). C'est comme un tableau sauf qu'il ne contient aucun élément dupliqué (si tu tentes d'en rajouter un, l'opération est ignorée). Exemple print(set((1, 2, 3, 4, 3, 2, 1))).
Donc si len(set(ligne)) vaut 1, c'est que tu n'as qu'une seule couleur ; et si ça dépasse 3 c'est que tu as plus de trois couleurs sur la ligne...