Optimiser une imbrication de boucle for

Version imprimable

Voir 40 message(s) de cette discussion en une page

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:

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)

05/07/2022, 11h59
wiztricks

Salut,

Citation:

Envoyé par ___Obi___

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
05/07/2022, 12h11
___Obi___

Nota : Le langage est bien en Python.
05/07/2022, 12h24
Sve@r

Bonjour

Citation:

Envoyé par ___Obi___

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...:weird:

Citation:

Envoyé par ___Obi___

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.

Citation:

Envoyé par ___Obi___

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).
05/07/2022, 13h47
Invité

1 pièce(s) jointe(s)

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 :
Pièce jointe 621798
05/07/2022, 14h07
Sve@r

Citation:

Envoyé par LeNarvalo

Pièce jointe 621798

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

Citation:

Envoyé par LeNarvalo

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" :P
05/07/2022, 14h35
Invité

1 pièce(s) jointe(s)

Citation:

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

Vive photoshop ! =)

Citation:

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
Pièce jointe 621803
05/07/2022, 14h44
___Obi___

1 pièce(s) jointe(s)

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.
Pièce jointe 621804

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.
05/07/2022, 15h23
Sve@r

Citation:

Envoyé par LeNarvalo

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.

Citation:

Envoyé par ___Obi___

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.

Citation:

Envoyé par ___Obi___

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.

Citation:

Envoyé par ___Obi___

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...
05/07/2022, 16h00
wiztricks

Citation:

Envoyé par Sve@r

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))).

A partir du moment où pour faire le set, on doit parcourir le tuple, pas sûr que ce soit dramatiquement plus rapide qu'un "sum".
Après pour pouvoir utiliser des fonctions qui bouclent "en interne" (et en C), sur lignes, colonnes et diagonales, il faudrait pouvoir les appliquer à une ligne, une colonne, une diagonale (plutôt que parcourir le cube pour en extraire les items qui vont bien dans la plupart des cas).

- W

Je suis à fond sur le truc !!
Pour l'instant je n'en suis qu'à la seconde étape de ma réflexion, plus qu'une (ou deux ou trois ou ...) !

Code:

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
#import numpy as np
import time, random
 
#RETURN ALL THE POSSIBILITIES OF ROW
def create_row():
        '''
        (0, 0, 0, 1)   (0, 0, 0, 2)    (1, 1, 1, 2)
        (0, 0, 1, 1)   (0, 0, 2, 2)    (1, 1, 2, 2)
        (0, 1, 1, 1)   (0, 2, 2, 2)    (1, 2, 2, 2)
                               
                               
        (0, 0, 1, 0)   (0, 0, 2, 0)    (1, 1, 2, 1)
        (0, 1, 1, 0)   (0, 2, 2, 0)    (1, 2, 2, 1)
        (1, 1, 1, 0)   (2, 2, 2, 0)    (2, 2, 2, 1)
                               
        (0, 1, 0, 0)   (0, 2, 0, 0)    (1, 2, 1, 1)
        (1, 1, 0, 0)   (2, 2, 0, 0)    (2, 2, 1, 1)
        (1, 1, 0, 1)   (2, 2, 0, 2)    (2, 2, 1, 2)
                               
                               
        (1, 0, 0, 0)   (2, 0, 0, 0)    (2, 1, 1, 1)
        (1, 0, 0, 1)   (2, 0, 0, 2)    (2, 1, 1, 2)
        (1, 0, 1, 1)   (2, 0, 2, 2)    (2, 1, 2, 2)
                               
        (0, 1, 0, 1)   (0, 2, 0, 2)    (1, 2, 1, 2)
        (1, 0, 1, 0)   (2, 0, 2, 0)    (2, 1, 2, 1)
        '''
        ROWS = []
        #DICO = {}
        for color in ((0,1), (0,2), (1,2)):
                for w in color:
                        for x in color:
                                for y in color:
                                        for z in color:
                                                liste = (w,x,y,z)
                                                if set(liste) == set(color):
                                                        ROWS.append(liste)
                                                        #DICO.setdefault(liste[0],[]).append(liste[1:])
 
        return ROWS #, DICO
 
 
def create_array(ROWS):
        ARRAYS = []
        #empty = [[0 for _ in range(4)] for _ in range(3)]        
        #for row in ROWS:
                #for col in DICO[row[0]]:
                        #array = np.array([row]+empty)
                       # for column in range(4):   
                                #array[1:, column] = col
        for row0 in ROWS:
                for row1 in ROWS:
                        for row2 in ROWS:
                                for row3 in ROWS:
                                        #array = np.array((row0, row1, row2, row3))
                                        array = (row0, row1, row2, row3)
                                        broken = False
                                        for c in range(4):
                                                column = (array[0][c], array[1][c], array[2][c], array[3][c])
                                                if len(set(column)) != 2:
                                                         broken=True
                                                         break
                                        if not broken:
                                                #diag_l = np.diag(array)
                                                diag_l = (array[0][0], array[1][1], array[2][2], array[3][3])
                                                if len(set(diag_l)) == 2:
                                                        diag_r = (array[0][3], array[1][2], array[2][1], array[3][0])
                                                        if len(set(diag_r)) == 2:
                                                                ARRAYS.append(array)
 
 
        return ARRAYS                                                       
 
def test():
        start=time.time()
        ARRAYS = create_array(create_row())	
        delai = time.time() - start
        nb = len(ARRAYS)
        i = random.randint(0,nb-1)
        print(delai, nb,ARRAYS[i][0],ARRAYS[i][1],ARRAYS[i][2],ARRAYS[i][3],sep='\n')
        #return ARRAYS
 
test()

Dites-moi si je me plante mais j'obtiens 101274 faces possibles sans prendre en considération les autres faces.

PS : Bon ben c'était sûrement pas une bonne idée, beaucoup trop de cas de figure par la suite...

Je pense que j'ai relevé quelques problèmes dans la première partie de ton script :
C'est normal :

Code:

1
2
3
4
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):

Et non pas 42 au lieu de 40 ?

Et ligne 28 c'est pas une erreur : CT[3][0]=TBL[z][0] au lieu de CT[3][0]=TBL[w][0] ?

Et ligne 32 l'indentation est correcte ?

Je pense que tu t'es un peu viandé ! ^^

Code:

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
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]]
 
CT= [[0 for _ in range(4)] for _ in range(4)] 
 
def test(line):
    if line==0  or line==4 or line==11 or line==12  or line==21 or line==40:
        return False
    return True
 
BC = 0
for x in range(0,42):
    for y in range(0,42):
        for z in range(0,42):
            for w in range(0,42):
                CT = [TBL[x].copy(), TBL[y].copy(), TBL[z].copy(), TBL[w].copy()]
 
                diag1 = CT[0][0]+CT[1][1]+CT[2][2]+CT[3][3]
                if not test(diag1):
                    continue
 
                diag2 = CT[0][3]+CT[1][2]+CT[2][1]+CT[3][0]
                if not test(diag2):
                    continue
 
                broken = False
                for r in range(4):
                    row = CT[0][r]+CT[1][r]+CT[2][r]+CT[3][r]
                    if not test(row):
                        broken = True
                        break
                if broken:
                    continue
                else:
                    BC+=1
 
print('Bonnes couches :', BC)

Je trouve 101274 bonnes couches du coup !

1 pièce(s) jointe(s)

Je propose un script, histoire d'économiser prêt de 1E20 possibilités (101274**4), mais le nombre de calcul est encore énorme aux alentours de 1E+17 dans le pire des cas (101274*(≈2500)*(≈300)*(≈300)*(≈2500)*(≈1)) voire beaucoup beaucoup moins si mes tests_intermédiaires ne sont pas plus gourmands qu'utiles...
Voici comment j'ai découpé le cube :
Pièce jointe 621829

Il y a très probablement des bourdes dans mon script et des solutions beaucoup plus efficaces, en mettant des prints(len(....)) partout j'ai constaté des redondances qui laissent imaginer une logique dans la répartition des faces qui permettrait d'économiser encore un bon paquet de calcul.

Code:

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
#len(ARRAYS_2) len(ARRAYS_4) len(ARRAYS_5)
280 277 2721
280 277 2265
255 277 2287
255 277 2299
280 277 2721
280 238 2299
280 262 2604
280 238 2287
280 262 2604
280 238 2287
280 262 2214
280 238 2299
255 262 2233
255 238 2265
255 262 2221
255 238 2721
255 262 2221
255 238 2721
255 262 2199
280 277 2721
280 277 2721
280 277 2265
255 277 2299
255 277 2287
255 277 2287
255 277 2299
... ... ...

NOUVELLE VERSION ANNOTEE ET CORRIGEE

Code:

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
import numpy as np
import time, random
 
#RETURN ALL THE POSSIBILITIES OF ROW
def create_rows():
        '''
        (0, 0, 0, 1)   (0, 0, 0, 2)    (1, 1, 1, 2)
        (0, 0, 1, 1)   (0, 0, 2, 2)    (1, 1, 2, 2)
        (0, 1, 1, 1)   (0, 2, 2, 2)    (1, 2, 2, 2)
                               
                               
        (0, 0, 1, 0)   (0, 0, 2, 0)    (1, 1, 2, 1)
        (0, 1, 1, 0)   (0, 2, 2, 0)    (1, 2, 2, 1)
        (1, 1, 1, 0)   (2, 2, 2, 0)    (2, 2, 2, 1)
                               
        (0, 1, 0, 0)   (0, 2, 0, 0)    (1, 2, 1, 1)
        (1, 1, 0, 0)   (2, 2, 0, 0)    (2, 2, 1, 1)
        (1, 1, 0, 1)   (2, 2, 0, 2)    (2, 2, 1, 2)
                               
                               
        (1, 0, 0, 0)   (2, 0, 0, 0)    (2, 1, 1, 1)
        (1, 0, 0, 1)   (2, 0, 0, 2)    (2, 1, 1, 2)
        (1, 0, 1, 1)   (2, 0, 2, 2)    (2, 1, 2, 2)
                               
        (0, 1, 0, 1)   (0, 2, 0, 2)    (1, 2, 1, 2)
        (1, 0, 1, 0)   (2, 0, 2, 0)    (2, 1, 2, 1)
        '''
        ROWS = []
        #DICO = {}
        for color in ((0,1), (0,2), (1,2)):
                for w in color:
                        for x in color:
                                for y in color:
                                        for z in color:
                                                liste = (w,x,y,z)
                                                if len(set(liste)) == 2:
                                                        ROWS.append(liste)
                                                        #DICO.setdefault(liste[0],[]).append(liste[1:])
 
        return ROWS #, DICO
 
 
def create_arrays(ROWS):
        ARRAYS = [] #Contiendra toutes les faces possibles
        DICO_BOTTOM = {} #Contiendra toutes les faces dont la première ligne commence par (0,0,0,1) ou (0,0,1,0)...
        DICO_TOP = {} #Contiendra toutes les faces dont la dernière ligne commence par (0,0,0,1) ou (0,0,1,0)...
        DICO_LEFT = {} #Contiendra toutes les faces dont la première colonne commence par (0,0,0,1) ou (0,0,1,0)...
        DICO_RIGHT = {} #Contiendra toutes les faces dont la dernière colonnecommence par (0,0,0,1) ou (0,0,1,0)...
 
        for row0 in ROWS:
                for row1 in ROWS:
                        for row2 in ROWS:
                                for row3 in ROWS:
                                        array = (row0, row1, row2, row3)
                                        for c in range(4):
                                                column = (array[0][c], array[1][c], array[2][c], array[3][c])
                                                if len(set(column)) != 2: #On teste si la colonne répond au règle
                                                         break
                                        else:
                                                #On teste si les diagonales répondent aux règles
                                                diag_l = (array[0][0], array[1][1], array[2][2], array[3][3])
                                                if len(set(diag_l)) == 2:
                                                        diag_r = (array[0][3], array[1][2], array[2][1], array[3][0])
                                                        if len(set(diag_r)) == 2:
                                                                ARRAYS.append(array)
 
                                                                DICO_TOP.setdefault(array[0],[]).append(array)
                                                                DICO_BOTTOM.setdefault(array[3],[]).append(array)                                                                
                                                                DICO_LEFT.setdefault((array[0][0],array[1][0], array[2][0], array[3][0]),[]).append(array)
                                                                DICO_RIGHT.setdefault((array[0][3],array[1][3], array[2][3], array[3][3]),[]).append(array)
        print('Nombre de bonnes couches :',len(ARRAYS))
        DICOS = {"TOP":DICO_TOP, "BOTTOM":DICO_BOTTOM, "LEFT":DICO_LEFT, "RIGHT":DICO_RIGHT}                                    
        return ARRAYS, DICOS                                                       
 
 
#RETURN ALL POSSIBILITIES OF CUBES
def create_cubes(ARRAYS, DICOS):
        '''                  array_1
                array_2      array_3        array_4
                             array_5
                             array_6
        '''
        st = time.time()
        iteration = 0
        CUBES = []
        #101274 arrays
        for a, array_1 in enumerate(ARRAYS): 
                #Top of array_3 == Bottom of array_1 #Environ 2500 arrays +/- 300
                for b, array_3 in enumerate(DICOS["TOP"][array_1[3]]):
                        ARRAYS_2, ARRAYS_4 = get_arrays_2_4(array_1, array_3, DICOS) 
                        if  ARRAYS_2:
                                #Environ 300 arrays
                                for c, array_2 in enumerate(ARRAYS_2):
                                        #Environ 300 arrays
                                        for d, array_4 in enumerate(ARRAYS_4): 
                                                if test_intermediaire(array_1, array_2, array_3, array_4):                                                        
                                                        ARRAYS_5 = get_arrays_5(array_2, array_3, array_4, DICOS)
                                                        if ARRAYS_5:                                       
                                                                #De 1 à 45 arrays environ
                                                                for e, array_5 in enumerate(ARRAYS_5): 
                                                                        if test_intermediaire(array_1, array_2, array_3, array_4, array_5):
                                                                                ARRAYS_6 = get_arrays_6(array_1, array_2, array_4, array_5, DICOS)
                                                                                if ARRAYS_6:                                                     
                                                                                        for f, array_6 in enumerate(ARRAYS_6): #Top of array_6 == Bottom of array_5
                                                                                                cube = test_intermediaire(array_1, array_2, array_3, array_4, array_5, array_6)
                                                                                                if cube:
                                                                                                        CUBES.append(cube)
                                                                                                        print('IDS in arrays: ',a,'/101274',b,'/',len(DICOS["TOP"][array_1[3]]),c,'/',len(ARRAYS_2),d,'/',len(ARRAYS_4),e,'/',len(ARRAYS_5),f,'/',len(ARRAYS_6))
                                                                                                        iteration = max(1,a)*max(1,b)*max(1,c)*max(1,d)*max(1,e)*max(1,f)-iteration
 
                                                                                                        print('Soit :',iteration,'itérations avant de trouver une bonne')
 
                                                                                                        print('\n'.join(str(array) for array in cube))
                                                                                                        print('TIME TO FIND ONE CUBE',time.time()-st)
                                                                                                        input('PRESS ENTER TO CONTINUE')
                                                                                                        st = time.time()
 
        return CUBES
 
#RETURN COMPATIBLES ARRAYS_2 & ARRAYS_4 WITH array_1 and array_3
def get_arrays_2_4(array_1, array_3, DICOS):
        ARRAYS_2_R = DICOS["RIGHT"][(array_3[0][0], array_3[1][0], array_3[2][0], array_3[3][0])]       #Arrays_2 compatibles avec array_3
        ARRAYS_2_T = DICOS["TOP"][(array_1[0][0], array_1[1][0], array_1[2][0], array_1[3][0])]         #Arrays_2 compatibles avec array_1
        ARRAYS_2 = set(ARRAYS_2_R).intersection(set(ARRAYS_2_T))                                        #Arrays_2 compatibles avec array_1 et array_3
 
        if not ARRAYS_2:
                return False, False                        
 
        ARRAYS_4_L = DICOS["LEFT"][(array_3[0][3], array_3[1][3], array_3[2][3], array_3[3][3])]        #Arrays_4 compatibles avec array_3
        ARRAYS_4_T = DICOS["TOP"][(array_1[0][3], array_1[1][3], array_1[2][3], array_1[3][3])]         #Arrays_4 compatibles avec array_1
        ARRAYS_4 = set(ARRAYS_4_L).intersection(set(ARRAYS_4_T))                                        #Arrays_4 compatibles avec array_1 et array_3
 
        if not ARRAYS_4:
                return False, False
 
        #print('NB OF ARRAYS_2:', len(ARRAYS_2), 'NB OF ARRAYS_4:', len(ARRAYS_4))
        return ARRAYS_2, ARRAYS_4
 
#RETURN COMPATIBLES ARRAYS_5  WITH array_2 and array_3 and array_4
def get_arrays_5(array_2, array_3, array_4, DICOS):
        ARRAYS_5_T = DICOS["TOP"][array_3[3]]                                                           #Arrays_5 compatibles avec array_3
        ARRAYS_5_L = DICOS["LEFT"][array_2[3][::-1]]                                                    #Arrays_5 compatibles avec array_2 inversé
        ARRAYS_5_R = DICOS["RIGHT"][array_4[3]]                                                         #Arrays_5 compatibles avec array_4
        ARRAYS_5 = set(ARRAYS_5_L).intersection(set(ARRAYS_5_R)).intersection(set(ARRAYS_5_T))          #Arrays_5 compatibles avec array_2 et array_3 et array_4
 
        #print('NB OF ARRAYS_5:', len(ARRAYS_5))
        return ARRAYS_5
 
#RETURN COMPATIBLES ARRAYS_6  WITH array_1 and array_2 and array_4 and array_5
def get_arrays_6(array_1, array_2, array_4, array_5, DICOS):
        ARRAYS_6_T = DICOS["TOP"][array_5[3]]                                                           #Arrays_6 compatibles avec array_5
 
        ARRAYS_6_L = DICOS["LEFT"][(array_2[3][0], array_2[2][0], array_2[1][0], array_2[0][0])]        #Arrays_6 compatibles avec array_2 inversé    
        ARRAYS_6_R = DICOS["RIGHT"][(array_4[3][3], array_4[2][3], array_4[1][3], array_4[0][3])]       #Arrays_6 compatibles avec array_4 inversé 
 
        ARRAYS_6_B = DICOS["BOTTOM"][array_1[0]]                                                        #Arrays_6 compatibles avec array_1 
 
        ARRAYS_6 = set(ARRAYS_6_T).intersection(set(ARRAYS_6_L)).intersection(set(ARRAYS_6_R)).intersection(set(ARRAYS_6_B)) #Arrays_6 compatibles avec array_1 et array_2 et array_4 et array_5
 
        if not ARRAYS_6:
                return False
 
        #print('NB OF ARRAYS_6:', len(ARRAYS_6))
        return ARRAYS_6        
 
#COUNT NB OF 0, 1 and 2 IN THE CUBE, RETURN FALSE IF NB > 21 or 22
def test_intermediaire(array_1, array_2, array_3, array_4=((None,),), array_5=((None,),), array_6=((None,),)):
        array_2 = (array_2[1][1:3], array_2[2][1:3])
        array_3 = array_3[1:]    
        if array_4:
                array_4 = (array_4[1][1:3], array_4[2][1:3])
                if array_5:
                        array_5 = array_5[1:]
                        if array_6:
                                array_6 = array_6[1:3]
 
        cube = (array_1, array_2, array_3, array_4, array_5, array_6)
 
        count_0 = 0
        count_1 = 0
        count_2 = 0
        for array in cube:
                for row in array:
                        count_0+=row.count(0)
                        count_1+=row.count(1)
                        count_2+=row.count(2)
 
        if count_0 <= 21 and count_1 <= 21 and count_2 <= 22:
                return cube     
 
        #if not array_4:
        #        print('3. NOT GOOD', string_cube.count('0'), string_cube.count('1'), string_cube.count('2'))
        #if not array_5:
        #        print('4. NOT GOOD')
        #if not array_6:
        #        print('5. NOT GOOD')
        return False
 
def test():
        start=time.time()
        ARRAYS, DICOS = create_arrays(create_rows())     
        CUBES = create_cubes(ARRAYS, DICOS)	
        delai = time.time() - start
        i = random.randint(0,len(CUBES)-1)
        cube = CUBES[i]
        print(delai)
        print(cube)
        return cube
 
result = test()

Citation:

Envoyé par LeNarvalo

Code:

1
2
3
4
5
        for color in ((0,1), (0,2), (1,2)):
                for w in color:
                        for x in color:
                                for y in color:
                                        for z in color:

J'ai pas bien pigé le but précis (je pense qu'il s'agit de positionner toutes les combinaisons de cases sur 4 couleurs) mais

tu génères deux fois les suites "0 0 0 0", "1 1 1 1" et "2 2 2 2"
tu sautes la motié des possibilités comme "0 0 1 2", "0 1 0 2", "0 1 1 2" et tant d'autres

Code:

1
2
3
import itertools
for x in itertools.product((0, 1, 2), repeat=4):
	print(x)

Citation:

Envoyé par LeNarvalo

Code:

1
2
3
4
5
6
for c in range(4):
	if len(set(column)) != 2:
        broken=True
        break
if not broken:
	... (action par défaut)...

Code:

1
2
3
4
5
for c in range(4):
	if len(set(column)) != 2:
        break
else:
	... (action par défaut)...

06/07/2022, 10h18
Invité

Citation:

J'ai pas bien pigé le but précis (je pense qu'il s'agit de positionner toutes les combinaisons de cases sur 4 3 couleurs)

Non pas vraiment, toutes les combinaisons de cases sur 2 couleurs différentes pour les 3 couleurs.
06/07/2022, 10h34
Sve@r
Ok, pigé. Juste que tu génères quand-même 2 fois "0, 0, 0, 0", "1, 1, 1, 1" et "2, 2, 2, 2".
Code:

1 2 3 for x in itertools.product((0, 1, 2), repeat=4): if len(set(x)) > 2: continue print(x)

~~-DOUBLONS-~~

Citation:

tu génères deux fois les suites "0 0 0 0", "1 1 1 1" et "2 2 2 2"

Oui effectivement mais c'est plus lent avec un truc qui itère tout ! Il y a sûrement une fonction dans itertools qui permet d'obtenir le même résultat. Après à cet endroit c'est ultra négligeable ! On va gagner 12 msec sur les 15 jours que le script va prendre ! ^^

Code:

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
>>> def test():
	listes=[]
	counter = 0
	for w in (0,1,2):
		for x in (0,1,2):
			for y in (0,1,2):
				for z in (0,1,2):
					counter+=1
					liste = (w,x,y,z)
					if len(set(liste)) == 2:
						listes.append(liste)
	return counter, len(listes), listes
 
>>>def toto():
    ROWS=[]
    counter = 0
    for color in ((0,1), (0,2), (1,2)):
                for w in color:
                        for x in color:
                                for y in color:
                                        for z in color:
                                                counter+=1
                                                liste = (w,x,y,z)
                                                if set(liste) == set(color):
                                                    ROWS.append(liste)
 
    return counter, len(ROWS), ROWS
 
>>> toto()
(48, 42, [(0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (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), (0, 0, 0, 2), (0, 0, 2, 0), (0, 0, 2, 2), (0, 2, 0, 0), (0, 2, 0, 2), (0, 2, 2, 0), (0, 2, 2, 2), (2, 0, 0, 0), (2, 0, 0, 2), (2, 0, 2, 0), (2, 0, 2, 2), (2, 2, 0, 0), (2, 2, 0, 2), (2, 2, 2, 0), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 2, 2), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 2, 2), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 2, 2), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 1)])
>>> test()
(81, 42, [(0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 1, 0), (0, 0, 1, 1), (0, 0, 2, 0), (0, 0, 2, 2), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (0, 2, 0, 0), (0, 2, 0, 2), (0, 2, 2, 0), (0, 2, 2, 2), (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, 2), (1, 1, 2, 1), (1, 1, 2, 2), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 2, 2, 2), (2, 0, 0, 0), (2, 0, 0, 2), (2, 0, 2, 0), (2, 0, 2, 2), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 1, 2, 2), (2, 2, 0, 0), (2, 2, 0, 2), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 2, 0), (2, 2, 2, 1)])
>>> c, r, R = toto()
>>> v, l, L = test()
>>> set(R) == set(L)
True

Par contre il serait plus intéressant de jeter un oeil sur la suite du script ;) même si c'est carrément plus complexe (et le bordel).

PS : create_array c'est sûrement améliorable, mais ça me prend moins de 2.5 secondes sur mon ordi...
PS2 : Pour le broken effectivement, je me rendais bien compte que c'était un truc de noob que j'utilisais là...
PS3 : J'ai commencé à annoter le script que j'ai partagé plus haut !

Résultats partiels, il y a des "zones" où il n'y a aucun résultat et d'autres où il y en a plein, ainsi sur les 400 000 premiers test il n'y a que 2 solutions, puis une palanquée dans les milliers qui suivent :

Code:

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
Nombre de bonnes couches : 101274
IDS in arrays:  5 /101274 1 / 2721 101 / 280 110 / 277 3 / 4 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((2, 2), (2, 2))
((0, 0, 0, 1), (0, 0, 0, 1), (0, 1, 1, 0))
((2, 1), (1, 1))
((2, 1, 2, 1), (2, 2, 1, 1), (2, 2, 2, 1))
((2, 2, 0, 2), (2, 0, 2, 2))
TIME TO FIND ONE CUBE 21.023174047470093
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 71 / 280 226 / 238 0 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((0, 2), (2, 2))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((2, 1, 1, 2), (2, 1, 1, 2), (2, 1, 1, 1))
((2, 1, 1, 2), (2, 1, 1, 2))
TIME TO FIND ONE CUBE 43.930623292922974
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 101 / 280 226 / 238 0 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((2, 2), (2, 2))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((2, 1, 1, 2), (2, 1, 1, 2), (2, 1, 1, 1))
((2, 1, 1, 2), (2, 1, 1, 2))
TIME TO FIND ONE CUBE 0.5753700733184814
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 7 / 238 1 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 2))
TIME TO FIND ONE CUBE 2.124941825866699
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 57 / 238 0 / 1 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((1, 2, 2, 2), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 2))
TIME TO FIND ONE CUBE 0.03871321678161621
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 112 / 238 1 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 1))
TIME TO FIND ONE CUBE 0.04090166091918945
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 122 / 238 0 / 1 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((1, 2), (2, 2))
((1, 2, 2, 2), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 1))
TIME TO FIND ONE CUBE 0.034931182861328125
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 132 / 238 0 / 1 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((1, 2), (2, 2))
((1, 2, 2, 2), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 2))
TIME TO FIND ONE CUBE 0.03784346580505371
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 136 / 238 1 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((1, 2), (2, 2))
((1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 1))
 
TIME TO FIND ONE CUBE 0.03495144844055176
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 147 / 238 1 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((1, 2), (2, 2))
((1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 2))
 
TIME TO FIND ONE CUBE 0.03592395782470703
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 215 / 280 159 / 238 0 / 1 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((1, 1), (0, 1))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((1, 2, 2, 2), (1, 2, 2, 2), (1, 2, 2, 2))
((1, 2, 2, 2), (1, 2, 2, 1))
 
TIME TO FIND ONE CUBE 0.037019968032836914
PRESS ENTER TO CONTINUE
IDS in arrays:  5 /101274 5 / 2721 218 / 280 226 / 238 0 / 2 0 / 1
((0, 0, 0, 1), (0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 1))
((2, 2), (2, 0))
((0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 0, 1))
((2, 2), (2, 2))
((2, 1, 1, 2), (2, 1, 1, 2), (2, 1, 1, 1))
((2, 1, 1, 2), (2, 1, 1, 2))
TIME TO FIND ONE CUBE 0.1533825397491455
PRESS ENTER TO CONTINUE

06/07/2022, 12h41
___Obi___

Merci à tous pour vos réponses. Je n'ai pas encore pu toutes exploiter mais j'ai de bonnes pistes d'optimisation.

@Narvalo : oui c’est bien 42. J’obtiens 2299 bonnes couches, avec ta correction sur la ligne 28.
Effectivement ton code donne un plus bien plus grand nombre de bonne couches. J’ai contrôlé par échantillonnage tes bonnes sorties de bonnes couches et à priori, par d’erreur chez, donc je dois avoir un problème dans mes contrôles (que je n'ai pas encore identifié).
06/07/2022, 12h46
Invité

Citation:

Envoyé par ___Obi___

@Narvalo : oui c’est bien 42. J’obtiens 2299 bonnes couches, avec ta correction sur la ligne 28.
Effectivement ton code donne un plus bien plus grand nombre de bonne couches. J’ai contrôlé par échantillonnage tes bonnes sorties de bonnes couches et à priori, par d’erreur chez, donc je dois avoir un problème dans mes contrôles (que je n'ai pas encore identifié).

Il n'y a pas que la ligne 28 à corriger, regarde la correction de la première partie de ton script #12. Le gros du pb c'est l'indentation.

Perso, je pense qu'il va falloir turbiner grave pour trouver une logique qui permettent de limiter les tests... Par exemple, rattacher préalablement les sommes des couleurs à chaque faces, histoire de savoir si une face qui a 10 rouges et une autre qui a 5 rouges et une autre qui a 8 rouges sont compatibles (ici non).
06/07/2022, 13h20
Sve@r

Citation:

Envoyé par LeNarvalo

Perso, je pense qu'il va falloir turbiner grave pour trouver une logique qui permettent de limiter les tests...

J'ai pas bien compris si la recherche ne s'applique qu'à une face ou bien si la ligne de la face A se continue sur la face B.
Mais si les faces sont indépendantes, alors on fait le code "pour une face" et on l'applique 6 fois...

Voir 40 message(s) de cette discussion en une page