Discussion :

[Benduroy]

Bonjour à tous,

Je suis en train de développer une version java du jeu des "chiffres" issu de l'émission tv "des chiffres et des lettres".
Je rappelle brièvement les règles: - un résultat aléatoire est demandé entre 101 et 999
- il faut retrouver ce résultat grâce à 6 opérandes, les entiers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 en deux exemplaires chacun et les entiers 25, 50, 75, 100 en un seul exemplaire
- grâce à ces opérandes on peut effectuer les 4 opérations de base: +, -, *, / (division entière)

Le jeu fonctionne bien, le joueur propose ses étapes jusqu'à ce qu'il arrive au résultat, se trompe, où n'est plus d'opérandes dans sa liste. Ensuite un score lui est donné.

Maintenant l'étape où je bloque c'est l'étape de la recherche de toutes les solutions possibles pour ce résultat aléatoire donnée et ses opérandes donnés. Le joueur pourrait ainsi toutes les consulter à la fin de la partie.

J'ai commencé en recherchant pour le début uniquement les solutions utilisant tout les opérandes, soit en 5 étapes (= 5 opérations). J'ai basé ma réflexion sur un algorithme en arbre dont la racine serait le premier opérande de la liste et chaque nœud additionne, soustrait, multiplie et divise (si possible) cette racine par l'opérande suivant. Et ainsi de suite... On devrait ainsi parvenir à toutes les résultats possibles en 5 étapes. J'ai donc pensé à une méthode récursive. Cette méthode s'appelle 4 fois, une fois pour chaque opérations. Seulement j'ai ce premier problème pourtant basique je pense qui est que je ne passe que dans une seule branche à chaque appelle. Je ne fais qu'additionner tout les opérandes.

Un peu de code pour vous laisser apprécier (Plaque.java)

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
public class Plaque {
 
    /**
     * <p>La borne infèrieure où la solution va être générée</p> 
     */
    private static int BORNE_INF = 0;
 
    /**
     * <p>La borne supèrieure où la solution va être générée</p> 
     */
    private static int BORNE_SUP = 0;
 
    /**
     * <p>Une liste contenant 5 entiers entre 1 et 10 pouvant être en 2
     * exemplaire et 1 entier (soit 25, 50, 75 ou 100) en un seul 
     * exemplaire</p>
     * <p>La liste des opérandes à la disposition du joueur.
     * Au début cette liste sera la même que celle générée aléatoirement
     * par la classe Plaque, puis les opérandes seront enlevés et ceux
     * calculés seront rajoutés au fur et à mesure.</p>
     */
    private LinkedList<Integer> operandeSource;
 
    /**
     * <p>Un entier généré aléatoirement à trouver entre 101 et 999</p>
     */
    private static int nbATrouver;
 
    /**
     * <p>Le nombre de solution possible compte tenu du résultat et des 
     * opérandes disponibles</p>
     */
    private int nbSolution;
 
    /**
     * <p>Une liste de toutes les solutions possibles compte tenu du 
     * résultat et des opérandes disponibles</p>
     */
    private LinkedList<String> solution;
 
    /**
     * <p>Le constructeur par défaut va initialiser aléatoirement 
     * la liste d'opérandes, et une solution entre 101 et 999</p>
     */
    Plaque(int borneinf, int bornesup) {
        BORNE_INF = borneinf;
        BORNE_SUP = bornesup;
        operandeSource = new LinkedList<Integer>();
        InitOperandeSource();
        InitNbATrouver();
        nbSolution = 0;
    }
 
public void chercherSolutions(LinkedList<Integer> copyOperandeSource,
                                  int resultatEnCours,
                                  int compteur) {
 
        if (resultatEnCours != nbATrouver && compteur < 10) {
            System.out.println(resultatEnCours);
            compteur++;
            resultatEnCours +=  copyOperandeSource.get(compteur);
            chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
 
            if (resultatEnCours > copyOperandeSource.get(compteur)) {
                resultatEnCours -=  copyOperandeSource.get(compteur);
            }
            chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
 
            resultatEnCours *=  copyOperandeSource.get(compteur);
            chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
 
            if (resultatEnCours % copyOperandeSource.get(compteur) == 0) {
                resultatEnCours /=  copyOperandeSource.get(compteur);
                chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
            } else if (copyOperandeSource.get(compteur) % resultatEnCours == 0) {
                resultatEnCours =  copyOperandeSource.get(compteur)/resultatEnCours;
                chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
            }
 
        } else {
            System.out.println("fin des traitements");
        }
    }
}

testRechercheSolutions.java

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 public static void main(String[] args) {
        Partie testPartie = new Partie(101, 999);           
        System.out.println("Liste d'opérandes restants: "+
                testPartie.getOperande());
        System.out.println("Résultat à trouver: "+
                testPartie.getResultat());
 
        LinkedList<Integer> copyOperandeSource = new LinkedList<Integer>();
        copyOperandeSource = testPartie.getOperande();
        int compteur = 0;
        int resultatEnCours = copyOperandeSource.get(0);
        testPartie.getTirage().chercherSolutions(copyOperandeSource, resultatEnCours, compteur);
    }

en console j'obtiens par exemple:

Liste d'opérandes restants: [5, 10, 5, 9, 3, 25]
Résultat à trouver: 787
5
15
20
29
32
57
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 6, Size: 6
at java.util.LinkedList.entry(Unknown Source)
at java.util.LinkedList.get(Unknown Source)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:174)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.jeu.Plaque.chercherSolutions(Plaque.java:175)
at lpd2i.test.testRechercheSolution.main(testRechercheSolution.java:35)

Et une belle erreur! La ligne 174 étant:

Code :

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

    resultatEnCours +=  copyOperandeSource.get(compteur);

Si je n'est pas été clair sur un point n'hésitez pas ^^. Après je ne suis pas franchement sur que cette solution soit très appropriée. Je vous laisse me dire ce que vous en pensez. Surtout que je suis obligé pour lancer la recherche de solution de passer par mon programme de test.

[tchize_]

vous esayez de lire au dela de la taille de la liste. Elle a une taille de 6 et vous essayez de lire le 7ème élément (index 6).

[Benduroy]

Maintenant la console me renvoie un StackOverflowError. Soit ma condition d'arrêt n'est jamais réalisée soit elle le serait au bout d'un trop grand nombre d'appels de méthodes.

Donc bon il va falloir que je passe par autre chose qu'une méthode récursive.

[bhamp0]

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
public List<String> chercherSolutions(Integer resultatAObtenir, List<Integer> operandesRestantes, Integer resultatEnCours, String calcul) {
 
	List<String> res = new ArrayList<String>();
 
	if(resultatAObtenir.equals(resultatEnCours)) {
		res.add(calcul);
	} else {
		Iterator<Integer> itOp = operandesRestantes.iterator();
		while(itOp.hasNext()) {
			Integer tmp = itOp.next();
			String tmpS = tmp.toString();
			List<Integer> tmpL = new ArrayList<Integer>(operandesRestantes);
			tmpL.remove(tmp);
 
			if(resultatEnCours == null) {
				res.addAll(chercherSolutions(resultatAObtenir, new ArrayList<Integer>(tmpL), tmp, tmpS));
			} else {
				res.addAll(chercherSolutions(resultatAObtenir, new ArrayList<Integer>(tmpL), resultatEnCours + tmp, calcul + "+" + tmpS));
				res.addAll(chercherSolutions(resultatAObtenir, new ArrayList<Integer>(tmpL), resultatEnCours - tmp, calcul + "-" + tmpS));
				res.addAll(chercherSolutions(resultatAObtenir, new ArrayList<Integer>(tmpL), resultatEnCours * tmp, calcul + "*" + tmpS));
				if(resultatEnCours % tmp == 0) {
					res.addAll(chercherSolutions(resultatAObtenir, new ArrayList<Integer>(tmpL), resultatEnCours / tmp, calcul + "/" + tmpS));
				}
			}
		}
	}
 
	return res;
 
}

Ca devrait répondre en partie au problème.
Il faut appeler cela avec :

Code :

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

chercherSolutions(total, operandes, null, null);

[Benduroy]

Ok merci bhamp0. J'ai un peu regardé ca me semble bien. Cependant penses-tu que toutes les solutions possibles y sont?

Bon réveillon à tous ^^

[bhamp0]

Non, il n'y a pas toutes les solutions.

Exemple : si j'ai 1, 2, 3 et 4, pour faire 21, on ferait : 1+2 = 3 ; 3+4 = 7 ; 3*7=21
Mais l'algorithme que je t'ai donné ne fait pas ça ... il faudrait envisager de définir qu'on remplace un lot de deux opérandes par une seule opérande, et rappeler la méthode.
(Si je trouve le temps, j'écrirai l'algorithme et je testerai.)

[Benduroy]

Oui je vois le problème en effet. Merci en tout cas de ton aide.