Solveur du jeu le compte est bon

**mty60000** · 12/04/2017, 15h32

Bonjour à tous, je suis entrain de programmer le jeu du compte est bon (tiré du jeu télévisé des chiffres et des lettres).

Le jeu consiste à trouver un résultat donné (ou de s'en rapprocher) avec des plaquettes tirées au hasard. Les joueurs disposent des opérations de base (+,-,*,/).

Ici, j'essaye de coder le solveur du jeu. Et pour cela, je voudrais construire un arbre en largeur dans lequel il y aura tous les calculs possibles.

Pour le moment, j'ai réussi à initialiser la racine et faire le niveau 1 de l'arbre (pas très compliqué vous me direz).

Voila le programme que j'ai pour le moment:

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
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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 
 
import java.io.*;
import java.util.ArrayList;
 
//Structure des informations d'un noeud
class Information {
    protected long P1;
    protected char operateur;
    protected long P2;
    protected long resultat;
    protected int niveau;
    protected ArrayList<Long> plaquettes;
    protected int nbplaquettes;
 
    public Information(long P1, char operateur, long P2, long resultat, int niveau, ArrayList<Long> plaquettes, int nbplaquettes) {
        this.P1 = P1;
        this.operateur = operateur;
        this.P2 = P2;
        this.resultat = resultat;
        this.niveau = niveau;
        this.plaquettes = plaquettes;
        this.nbplaquettes = nbplaquettes;
    }
    public Information(int niv, ArrayList<Long> pla, int nbpla) {
        this.P1 = -1;
        this.operateur = ' ';
        this.P2 = -1;
        this.resultat =
        this.niveau = niv;
        this.plaquettes = pla;
        this.nbplaquettes = nbpla;
    }
    public long getP1() {
        return P1;
    }
    public char getOperateur() {
        return operateur;
    }
    public long getP2() {
        return P2;
    }
    public long getResultat() {
        return resultat;
    }
    public int getNiveau() {
        return niveau;
    }
    public ArrayList<Long> getPlaquettes() {
        return plaquettes;
    }
    public int getNbPlaquettes() {
        return nbplaquettes;
    }
 
}
 
//class Noeud
class Noeud {
    protected Information info;
    protected Noeud pere;
 
    public Noeud(Information info, Noeud pere){
        this.info = info;
        this.pere = pere;
    }
    public Noeud(Information infor) {
        this.info = infor;
        this.pere = null;
    }
    public Noeud() {
        this.info = null;
        this.pere = null;
    }
    public Noeud setInfo(Information i) {
        this.info.P1 = i.P1;
        this.info.operateur = i.operateur;
        this.info.P2 = i.P2;
        this.info.resultat = i.resultat;
        this.info.niveau = i.niveau;
        this.info.plaquettes = i.plaquettes;
        this.info.nbplaquettes = i.nbplaquettes;
        return this;
    }
    public Noeud getPere() {
        return pere;
    }
    public Information getInfo() {
        return info;
    }
}
 
 
public class Solution {
 
    //Fonction d'affichage du meilleur résultat (résultat le plus proche de la cible avec les moins d'opérations)
    public static void Affiche(Noeud best) {
        int niv = best.info.niveau;
        while(niv>1) {
            System.out.println("op1: "+best.info.getP1()+"op2: "+best.info.getP2()+"resultat: "+best.info.getResultat());
            best.info.P1 = best.pere.info.getP1();
            best.info.operateur = best.pere.info.getOperateur();
            best.info.P2 = best.pere.info.getP2();
            niv--;
        }
    }
 
    static int i=0;
    static int j=0;
    static int o=0;
    static int calc = 0;
    static int niveau = 1;
 
    //Fonction de recherche de solution
    public static void Find(Noeud N, Noeud best, int cible) {
        long add = 0;
        long sous = 0;
        long mul = 0;
        long div = 0;
        char operateurs [] = {'+','-','*','/','^','%'};
        long test = 0;
        long test2 = 0;
        long op1 = 0;
        long op2 = 0;
        int nbplaques = 0;
 
 
        int max = N.info.getNbPlaquettes();
 
        //Si on arrive en bas de l'arbre, on rappel la fonction de recherche avec le père du noeud actuel
        if(max == 1) {
            Find (N.pere, best, cible);
        }
 
        //Sinon, il y a encore au moins une pair de plaquette dans la liste
        if(max>=2) {        
            Information infom = new Information(0,' ',0,100000,6,N.info.getPlaquettes(),1);
            ArrayList<Long> tmp = new ArrayList<Long>();
            tmp.addAll(N.info.getPlaquettes());
            *
            //Parcours des plaquettes
            for(i=0; i<max-1; i++) {
                for(j=i+1; j<max; j++) {
                    int actuelle = N.info.getNiveau() + 1;                    *
                    long p1 = tmp.get(i);
                    long p2 = tmp.get(j);
 
                    add = p1+p2;
                    mul = p1*p2;
                    if(p1>=p2) {
                        sous = p1-p2;
                        if(p1%p2 == 0) {
                            div = p1/p2;
                        }
                        else {
                            div = -1;
                        }
                    }
                    else {
                        sous = p2-p1;
                        if(p2%p1 == 0) {
                            div = p2/p1;
                        }
                        else {
                            div = -1;
                        }
                    }
 
                    ArrayList<Long> t1 = new ArrayList<Long>();
                    ArrayList<Long> t2 = new ArrayList<Long>();
                    ArrayList<Long> t3 = new ArrayList<Long>();
                    ArrayList<Long> t4 = new ArrayList<Long>();
 
                    t1.addAll(tmp);
                    t1.remove(0);
                    t1.remove(0);
 
                    t2.addAll(tmp);
                    t2.remove(0);
                    t2.remove(0);
 
                    t3.addAll(tmp);
                    t3.remove(0);
                    t3.remove(0);
 
                    t4.addAll(tmp);
                    t4.remove(0);
                    t4.remove(0);
 
                    t1.add(add);
                    t2.add(sous);
                    t3.add(mul);
                    t4.add(div);
 
                    //Création des noeuds fils
                    Information infor1 = new Information(p1,'+',p2,add,actuelle,t1,N.info.getNbPlaquettes()-1);
                    Noeud N1 = new Noeud(infor1);**
                    N1.pere = N;                ***
                    System.out.println("Operateur1: "+N1.info.getP1()+" Operation: "+N1.info.getOperateur()+" Operateur2: "+N1.info.getP2()+" Resultat: "+N1.info.getResultat());                        **
                    *
                    Information infor2 = new Information(p1,'-',p2,sous,actuelle,t2,N.info.getNbPlaquettes()-1);
                    Noeud N2 = new Noeud(infor2);
                    N2.pere = N;                    ***
                    System.out.println("Operateur1: "+N2.info.getP1()+" Operation: "+N2.info.getOperateur()+" Operateur2: "+N2.info.getP2()+" Resultat: "+N2.info.getResultat());
                    *
                    Information infor3 = new Information(p1,'x',p2,mul,actuelle,t3,N.info.getNbPlaquettes()-1);
                    Noeud N3 = new Noeud(infor3);**
                    N3.pere = N;                ***
                    System.out.println("Operateur1: "+N3.info.getP1()+" Operation: "+N3.info.getOperateur()+" Operateur2: "+N3.info.getP2()+" Resultat: "+N3.info.getResultat());
                    *
                    if(div != -1) {
                        Information infor4 = new Information(p1,'/',p2,div,actuelle,t4,N.info.getNbPlaquettes()-1);
                        Noeud N4 = new Noeud(infor4);
                        N4.pere = N;                    ***
                        System.out.println("Operateur1: "+N4.info.getP1()+" Operation: "+N4.info.getOperateur()+" Operateur2: "+N4.info.getP2()+" Resultat: "+N4.info.getResultat());
                    }
                    System.out.println("________________________________________________________");
                }
            }
        }
    }
 
    public static void main(String[] args) {
 
        ArrayList<Long> init = new ArrayList<Long>();
        long tmp = 0;
        tmp = 10;
        init.add(tmp);
 
        tmp = 5;
        init.add(tmp);
 
        tmp = 7;
        init.add(tmp);
 
        tmp = 2;
        init.add(tmp);
 
        tmp = 25;
        init.add(tmp);
 
        tmp = 9;
        init.add(tmp);
 
 
        int totalPlaquettes = 6;
        int target = 250;
        int valeurMax = 100000;
 
        //Innitialisation de la racine et du meilleur résultat
        Information infor = new Information(0,' ',0,0,1,init,totalPlaquettes);
        Information infom = new Information(0,' ',0,valeurMax,6,init,1);
        Noeud racine = new Noeud(infor,null);
        Noeud meilleur = new Noeud(infom,racine);
 
        Find(racine, meilleur, target);
    }
}

Je sais que le code n'est pas très propre.

Maintenant, je cherche comment continuer à descendre dans l'arbre. Je n'ai pas vraiment d'idée pour le moment et je commence un peu à désespérer.

Toute idée sera la bien venu et je vous serai reconnaissant de me venir en aide.

Merci d'avance

**joel.drigo** · 13/04/2017, 16h03

Salut,

Je t'ai déjà donnée un exemple de récursivité pour construire l'arbre des solutions ici. Qu'est-ce qui t'empêche de mettre en application ta récursivité par rapport à cet exemple ?

**yotta** · 15/04/2017, 12h48

Ne serait-il pas beaucoup plus simple de faire l'inverse ?
Pourquoi se casser la tête à déterminer de manière si compliquée quelque chose qui peut être très simple ?
De souvenir, le jeu du compte est bon consiste à tirer 5 ou 6 cartons, avec un nombre aléatoire compris entre 1 et 100 sur chaque carton. Après cela, on fait tourner un compteur représentant un nombre sur trois chiffres qui représente le résultat à trouver à l'aide des nombres sur les cartons tirés juste avant en faisant des additions, soustractions, multiplications ou divisions.
S'il y a six cartons tirés, il faut alors 5 opérateurs, on les prends au hasard et on résout le calcul pour obtenir le nombre que les joueurs devront chercher, comme ça, sans se casser la tête, on connaît déjà le résultat. Cependant, il est vrai que dans ces conditions, on s'éloigne un peu de la réalité puisqu'il y aurait toujours une solution, ce qui dans la réalité n'est pas toujours le cas, parfois, le bon compte ne peut être trouvé... Mais en guise de simulation l'idée me semblait pertinente.

**joel.drigo** · 19/04/2017, 11h06

Envoyé par yotta

S'il y a six cartons tirés, il faut alors 5 opérateurs, on les prends au hasard et on résout le calcul pour obtenir le nombre que les joueurs devront chercher, comme ça, sans se casser la tête, on connaît déjà le résultat. Cependant, il est vrai que dans ces conditions, on s'éloigne un peu de la réalité puisqu'il y aurait toujours une solution, ce qui dans la réalité n'est pas toujours le cas, parfois, le bon compte ne peut être trouvé... Mais en guise de simulation l'idée me semblait pertinente.

Oui, si le but est de faire un jeu du type "Le compte est bon", mais si le but est de résoudre le problème décrit : n plaques, m opérateurs, un résultat.

**yotta** · 20/04/2017, 00h45

Bonsoir,
Je cherchais à faire un peu d'humour en fait. Comme je suis fainéant du bulbe ma logique m'entraîne vers les solutions simples. Mais il est évident qu'ici il est question de résoudre le problème mathématiquement dans les mêmes conditions que le joueur. Je me suis intéressé à votre discussion parce que je n'ai jamais rien compris à ces histoires de récursivités. Pourtant, c'est plus qu'important, à un tel point que je ne sais pas comment faire pour par exemple simplement explorer une arborescence, ça a toujours été un vrai casse tête pour moi. Du coup, je me suis dit je vais suivre ça de près et j'ai pas pu résister.
Quoi qu'il en soit, si l'un de vous peut me filer une URL sympa qui me permettrait de comprendre cette histoire de récursivité une fois pour toute je suis preneur. Mais il faudrait un truc genre pour les nuls...

**joel.drigo** · 20/04/2017, 11h46

Pour commencer, http://recursivite.developpez.com/

Peut-être que la récusivité peut appaitre compliquée mais sur le principe, c'est assez simple. Il s'agit juste d'avoir une méthode qui s'appelle elle-même (On peut avoir des récursivtés indirectes, genre une méthode truc qui appelle machin qui appelle truc, c'est le même principe, mais restons sur le cas de base).

En terme fonctionnel, c'est une fonction qui s'appelle elle-même. En mathématiques, on a plusieurs exemples concrêts. Les suites par exemple, dont un terme de rang n (tel que n>=0) est exprimé comme une fonction s'appliquant sur le terme de rang n-1 : u_n = f(u_n-1). On transpose assez facilement en écrivant u₅₀₀=f(u₄₉₉), u₄₉₉=f(u₄₉₈)..., u₂=f(u₁), u₁=f(u₀). Là apparait une certaine évidence : comment détermine-t-on u₀, puisque u_-1 n'existe pas (puisque n=-1 n'existe pas). Dans une récursivité, il faut une condition d'arrêt, sinon on appellera infiniment la fonction. Comme la mémoire est finie (en tout cas aujourd'hui), il en résultera une StackOverflowError, un dépassement de pile. En mathématique, la condition d'arrêt est définie sous forme d'une constante : U₀ = K. Un exemple classique est la fonction factorielle. n! est le produit de tous les n>=1, et 0! est égal à 1. Il facilement démontrable que si n>1, alors n! = n * (n-1)! (et si n<=1, n!=1, on a une condition d'arrêt).
En Java, on peut écrire ça :

Code :

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

1
2
3
4
5
6
public static int factorielle(int n) {
int resultat=1;
for(int i=n; i>0; i--) {
   resultat*=n;
}
return resultat;

En récursivité, ça donnerait:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
public static int factorielle(int n) {
     if (n<0) {
          throw new IllegalArgumentException("Pas de factorielle d'un nombre négatif"); 
     }
     else if (n==0) { // condition d'arrêt.
         return 1; 
     }
     else {
         return n * factorielle(n-1); // appel récursif
     }
}

Il peut y avoir des variantes sur la condition d'arrêt. On peut par définition économiser une récursion. *

Code :

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

1
2
3
4
5
6
7
8
9
10
11
public static int factorielle(int n) {
     if (n<0) {
          throw new IllegalArgumentException("Pas de factorielle d'un nombre négatif"); 
     }
     else if (n<=1) { // condition d'arrêt.
         return 1; 
     }
     else {
         return n * factorielle(n-1); // appel récursif
     }
}

Souvent, une récursivité peut se mettre à plat, en boucle. Alors pourquoi l'utiliser. Parce que c'est souvent plus simple à écrire. Déjà, on utilise souvent moins de variables. Comme il y a un scope local, il n'y a pas à se soucier de la mémorisation du résultat intermédiaire : d'ailleurs souvent, dans le cas de la mise à plat d'une récursivité, on va devoir introduire une pile pour remplacer celle que Java nous procure naturellement lors de l'appel d'une méthode. A l'inverse, une boucle consistant à traiter un élément, puis tous ses suivants, on pourrait systématiquement écrire sous forme récursive toute boucle. Traiter chaque élément d'une liste successivement, c'est traiter le premier élément s'il existe, puis refaire ça sur la suite de la liste (la condition d'arrêt, c'est liste vide).

Code :

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

1
2
3
4
5
6
public static <T> void accept(List<T> list, Consumer<T> consumer) {
    if ( !list.isEmpty() ) { // s'il y a des éléments à traiter
        consumer.accept(list.get(0)); // on traite le premier
        accept(list.subList(1, list.size()), consumer); // on réapplique le truc à la suite de la liste
    }
}

Le parcours d'arbre se prête aisément à la récursivté : un nœud a des nœuds fils, qui eux-même ont des nœuds fils, qui eux-même ont.... (tout ce qui s'exprime de cette manière est propre au traitement récursif). Traiter tous les nœuds d'un arbre revient à traiter un nœud, puis à traiter ses fils. L'affichage d'un nœud pourra donc s'écrire (en préfixé) :

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
public class Node<T> {
      private T value;
      private Node[] children;
      /**...**/
      public String toString() {
            return String.valueOf(value);
      }
      /** écrit l'arbre dans le flux spécifié */
      public void println(PrintStream out) {
          println(out, 4);
      }
      public void println(PrintStream out, int indent) {
          println(out, 0, indent);
      }
      private void println(PrintStream out, int currentIndent, int indent) {
           for(int i=0; i<currentIndent; i++) {
                out.print(' ');
           }
           out.println(this);
           if ( children!=null ) { // condition d'arrêt explicite
               currentIndent+=indent; // la pile d'appel Java permet la sauvegarde de l'indentation à ce niveau, dé même que le node en cours de parcours
               for(Node child : children) { // condition d'arrêt implicite (si children.length==0, on n'entre pas dans la boucle, pas d'appel récursif
                    child.println(out, currentIndent, indent); // on n'appelle la même méthode mais pas sur la même instance
               }
           }
      }
}

Solveur du jeu le compte est bon

Java

Vue hybride

Discussions similaires

Partager

Partager