Solveur du jeu le compte est bon

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:

---

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

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 ?

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

Citation:

---

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

---

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.

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

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:

---

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:

---

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:

---

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:

---

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:

---

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 } } } }

---

Merci Joel.drigo. C'est très gentil de vous être donné cette peine en construisant votre réponse avec en quelque sorte un niveau d'explication qui va créchendo. Je n'ai malheureusement pas encore compris la fin, mais je le sens bien, il faut que je manipule encore un peu. Mais je ne vais pas polluer plus longtemps cette discussion avec mes besoins personnels, donc, dés que j'ai tout compris, je m'attellerai à résoudre le problème de notre ami mty60000...
:D

P.S.
Petite précision, dans le premier bloc de code, la version en boucle, en ligne trois dans la déclaration de la boucle ce ne serait pas plutôt i-- ?
Et dans le dernier bloc de code, l'exemple de récursivité sur une arborescence, en ligne 8, c'est une erreur de syntaxe le /** qui devrait être //, ou bien c'est ce qui représente ce que vous appelé "en préfixé" ?
Quoi qu'il en soit, j'ai tenté de compiler ce code en remplaçant en l'occurence /** par //, mais je n'arrive pas à compiler, le compilateur me dit qu'il ne peut pas caster un child en Printstream en ligne 23, ce qui d'ailleurs me semble logique puisque child est un Node....:(

Citation:

---

Envoyé par yotta

Petite précision, dans le premier bloc de code, la version en boucle, en ligne trois dans la déclaration de la boucle ce ne serait pas plutôt i-- ?
Et dans le dernier bloc de code, l'exemple de récursivité sur une arborescence, en ligne 8, c'est une erreur de syntaxe le /** qui devrait être //, ou bien c'est ce qui représente ce que vous appelé "en préfixé" ?
Quoi qu'il en soit, j'ai tenté de compiler ce code en remplaçant en l'occurence /** par //, mais je n'arrive pas à compiler, le compilateur me dit qu'il ne peut pas caster un child en Printstream en ligne 23, ce qui d'ailleurs me semble logique puisque child est un Node....:(

---

A oui, pour la première remarque et la seconde. J'ai tout tapé en direct et l'éditeur du forum ne signale pas les erreurs ;)
Pour la ligne 23, c'est aussi une boulette.
Je corrige les trois dans le post.

Merci pour ces précisions Joel. Cependant, pour la ligne 23 ce ne serait pas plutôt :

Code:

---

child.println(out, currentIndent, indent);

---

au lieu de :

Code:

---

child.println(printstream, currentIndent, indent);

---

Sans quoi, je ne vois pas d'où vient printsream ?...

Citation:

---

Envoyé par yotta

Merci pour ces précisions Joel. Cependant, pour la ligne 23 ce ne serait pas plutôt :

Code:

---

child.println(out, currentIndent, indent);

---

---

Oui, en effet.

Salut à vous,

Désolé, c'était un peu difficile pour moi, le temps de digérer les explications de Joel.Drigo et d'à peu près comprendre la récursivité, et comme promis, voici ma solution pour le compte est bon.
Ce n'est probablement pas très propre, mais ça fonctionne plutôt bien, je l'ai testé avec plusieurs tirages et valeurs à chercher et j'ai toujours trouvé une solution.
Voilà le code, merci de votre indulgence :

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

package LeCompteEstBon;   import java.util.ArrayList; import java.util.List;   /**  *  * @author Thierry  */ public class Solveur {   static final String[] OPERATEURS = {"+", "-", "*", "/"}; static final int[] NOMBRES = {2, 7, 25, 4, 50, 9};// Tirage exemple avec 6 plaquettes static final int VALEUR = 624;// Valeur à trouver. static List<Integer> plaquettes, plaquettesTmp;   public static void main(String args[]) { plaquettes = new ArrayList(); plaquettesTmp = new ArrayList(); for (int i:NOMBRES) plaquettes.add(i); plaquettesTmp.addAll(plaquettes); int pointeurDebut = 0, pointeurFin; List<Object[]> operations = null; String[] valTmp; //for (int i = 1 ; i < NOMBRES.length ; i++) { for (int i = 1 ; i < 6 ; i++) { if (operations == null) operations = determineCalculs(""); pointeurFin = operations.size() - 1; for (int o = pointeurDebut ; o <= pointeurFin ; o++) { plaquettes.addAll(plaquettesTmp); valTmp = operations.get(o)[0].toString().split("\\D"); for (String s:valTmp) if (!s.isEmpty()) plaquettes.remove(Integer.valueOf(s)); plaquettes.add(0, (Integer)(operations.get(o)[1])); operations.addAll(determineCalculs(operations.get(o)[0].toString())); } pointeurDebut = pointeurFin+1; }   if (operations != null) { System.out.println("Tirage : 2 7 25 4 50 9"); System.out.println("Valeur à trouver : " + VALEUR); System.out.println("Nombre de calculs possibles pour ce tirage : " + operations.size()); Object[] resultat = null; for (Object[] o:operations) { if ((int)o[1] == VALEUR) resultat = o; } if (resultat != null) System.out.println("Solution trouvée :" + resultat[0] + " = " + resultat[1]); } }   private static List<Object[]> determineCalculs(String prefixe) { List<Object[]> reponse = new ArrayList(); Object[] element; int a; while (!plaquettes.isEmpty()) { a = (int)plaquettes.remove(0); if (prefixe.isEmpty()) prefixe = String.valueOf(a); //a = (int)plaquettes.get(0); for (int n:plaquettes) { for (String s: OPERATEURS) { element = new Object[2]; switch (s) { case "+": if (a+n == VALEUR) break; element[0] = prefixe + " + " + n; element[1] = a+n; break;   case "-": if (a != n) { if (a > n) { // a-n element[0] = prefixe+" - "+n; element[1] = a-n; } else { // n-a element[0] = n+" - "+prefixe; element[1] = n-a; } } break;   case "*": // a*n element[0] = prefixe+" x " + n; element[1] = a*n; break;   case "/": if (a != n) { if ((a > n) && (a%n==0)) { element[0] = prefixe+" / "+n; element[1] = a/n; } else { if ((a < n) && (n%a==0)) { element[0] = n+" / "+prefixe; element[1] = n/a; } } } else { // Dans le cas de la division, si a=(int)plaquettes.get(i) la division devient commutative et donne 1 element[0] = prefixe+" / "+n; element[1] = 1; } break; } if (element[1] != null && controleValeur(element[1])) reponse.add(element.clone()); } } reponse.addAll(determineCalculs("")); } return reponse; }   private static boolean controleValeur(Object object) { return ((Integer)object) < 1000 && ((Integer)object) > 99; } }

---

J'espère que cela vous aidera mty60000 :D