Discussion :

[Timothy142857]

Bonjour à tous,

je joues depuis quelques semaines à un jeu ou l'on doit programmer des IA de poireaux qui ensuite se combattent entre eux. ( https://leekwars.com). Le language ressemble à du javascript

A mon niveau, mon poireau a 2 armes équipées et 7 puces, ce qui me fait un arsenal de 9 items. Chacun peut etre utilisé moyennant un cout en points de tour (= TP). Et a chaque tour, j'ai à ma disposition 10 TP.

Je cherche à déterminer l'ensemble des combos disponibles que j'ai avec mes 10 TP

Exemple:

Si j'ai l'arme A qui coute 4 TP a chaque utilisation

l'arme B qui coute 3 TP

la puce C qui coute 2 TP

mes combos pourraient etre :

2 x arme A + 1 x puce C

1 x arme A + 2 x arme B

5 x arme C

1 x arme B + 3 x puce C

...

Je sais à peu près bien coder, mais je n'ai jamais vraiment pratiquer d'algorithme combinatoire. J'ai essayer de me faire une fonction récursive( cest ce qui m'est venu en tete en premier), mais de meme la recursivité est quelque chose de très nouveau pour moi.

En m'inspirant d'une fonction que j'ai trouvé sur internet j'ai codé ceci:

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
 
global elements = arrayFlatten([getChips(), getWeapons()]); //Fonctions natives qui me renvoient toutes mes armes/puces équipées
global totalTP = 10; //Mon total de points de tour
global arrayCombos; //Mon tableau ou je veux stocker mes combos
if (arrayCombos == null) {
    arrayCombos = [];
}
 
 
/////////////////////////////      MAIN        ////////////////////////////////
if (getTurn() == 1) {
    arrayCombos = combinaisonsFn(elements, 5);
    debug('c: ' + count(arrayCombos));
}
 
debug(getOperations());
 
////////////////////////////     FUNCTIONS      /////////////////////////////////
function combinaisonsFn(tab, taille) {
    //Cas de base
 
    if (taille == 1) {
        return arrayMap(tab, function(@x) {
            return [x];
        });
    }
 
     else {
        var result = [];
 
        var combinaisons = combinaisonsFn(tab, taille - 1);
 
        for (var item in tab) { //Item=item à rajouter
            for (var combinaison in combinaisons) { //Combinaison=debut du combo deja existant
                var sumTp = 0;
                for (var elm in combinaison) {
                    sumTp += getCostItem(elm);
                }
                sumTp += getCostItem(item);
                if (sumTp <= totalTP) {
                    push(result, arrayFlatten([item, combinaison]));
                }
            }
        }
        result = arrayConcat(combinaisons, result);
        return result;
    }
}
 
 
/////////////////    OUTILS      ////////////////////////////////
function getCostItem(elm) {
    if (typeOf(elm) == TYPE_ARRAY) {
        var cost = 0;
        for (var item in elm) {
            cost += getCostItem(item);
        }
        return cost;
    } else if (isChip(elm)) {
        return getChipCost(elm);
    } else {
        return getWeaponCost(elm);
    }
}
 
//-----------------------------------------------------------------------------------------------
//Renvoit un tableau d'items triés par leur cout en TP
//Prend un paramètre un tableau d'items'
//array[0] est le moins couteux
function sortElementsByCost(array) {
    array = arraySort(array, function(x, y) {
        if (getCostItem(x) > getCostItem(y)) {
            return 1;
        } else if (getCostItem(x) < getCostItem(y)) {
            return -1;
        } else {
            return 0;
        }
    });
    return array;
}

La fonction me génère un beau tableau avec pas mal de combos.

Mais j'ai deux soucis.

D'une, en partant du principe que le combo composé du plus grand nombre d'éléments sera celui qui sera compose de l'item le moins cher utilisé au maximum de fois. (Dans mon exemple, 5 fois la puce C).

Du coup, mon parametre taille qui correspond au nombre d'éléments de mon combo devrait avoir une valeur seuil au dela de laquelle, on a plus de combo qui ne depassent pas le nombre total de TP. (dans mon exemple, il n'y aura jamais un combo avec 6 é"léments puisque ca depasserait forcément le nombre de TP total).

Hors, ma fonction continue de générer des combos supplémentaires quand je passe au dessus de cette valeur seuil(j'ai pas comparé les combos un par un, juste comparer la taille du tableau) et je ne comprends pas pk.

Mon deuxième problème est que le jeu impose une limite de 20M d'opérations par tour . Or ici pour générer mes combos avec 9 armes/puces, une limite de 5 éléments et un total de 10 TP, j'utilise deja 4M d'opérations.

Hors en augmentant mon niveau de joueur, je vais passer de 2 a 4 armes et de 7 a 15 puces avec un total avoisinant les 20 TP. Autrement dit, je dépasserai surement les 100M d'opérations :/

Je suis à l'écoute de conseils pour améliorer cette fonction ou bien carément en refaire une nouvelle. N'oubliez pas que je suis novice en récursivité

Merci d'avoir lu

[tbc92]

Un truc comme ça ?

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
Valeur est un tableau de 3 entiers
Valeur[1] = 4
Valeur[2] = 3
Valeur[3] = 2
maxValeur est un entier = 10
 
Pour i1 = 0 a MaxValeur / Valeur[1] 
  Deja_consomme = i1 * Valeur[1]
  Reste_Dispo = MAx_Valeur - Deja_consomme
  Pour i2 = 0 a Reste_Dispo / Valeur[2]
     Deja_consomme += i2 * Valeur[2]
     Reste_Dispo = MAx_Valeur - Deja_consomme
     Pour i3 = 0 a  Reste_Dispo / Valeur[3]   
         Print ( " Solution", i1, i2, i3)
     fin
   fin
Fin

Si le nombre d'objets différents est connu à l'avance (ici 3 armes différentes), ça marche. Si ce nombre n'est pas connu à l'avance, il faut passer à du plus lourd.

[Timothy142857]

Non justement, ici j'ai 7 puces + 2 armes. Mais progressivement, je vais gagner 1 arme et/ou 1 puce, donc le nombre d'itérations est variable

[tbc92]

La difficulté, c'est si tu peux avoir des puces et des armes, puis des sorts, des boucliers, des armures, des canons, des épées, etc : à chaque fois une nouvelle notion.

Ici, tu dis que tu dois gérer le nombre d'armes A, d'armes B et de puces C, et qu'il n'y a pas de puces D, et il n'y en aura jamais.
Du coup, l'algorithme proposé marche très bien.
Tu peux avoir 10 TP comme dans ton premier message, ou bien 1000 TP, l''algorithme continuera de donner toutes les combinaisons.

[Timothy142857]

J'ai eu un peu de mal a comprendre ton pseudo code, j'ai essaye de le traduire en phph et ca donne ca :

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
 
 
//Je défini mon tableau d'items
$tabElements=array(); 
 
$item = new Item();
    $item->setId(3);
    $item->setName('bandage');
    $item->setCost(2);
    array_push($tab, $item);
 
    $item1 = new Item();
    $item1->setId(8);
    $item1->setName('protein');
    $item1->setCost(3);
    array_push($tab, $item1);
 
 
    $item6 = new Item();
    $item6->setId(25);
    $item6->setName('steroid');
    $item6->setCost(5);
    array_push($tab, $item6);
 
 
function test($tabElements, $maxValeur) {
//Je crée le tableau comprenant tous les combos qui sera le return de ma fonction
    $arrayCombos = array();
 
    for ($index = 0; $index <= (floor($maxValeur / $tabElements[0]->getCost())); $index++) {// je boucle de 0 a (floor($maxValeur / $tabElements[0]->getCost())) = 10 /2
 
        $dejaConsomme = $index * $tabElements[0]->getCost();
        $resteDispo = $maxValeur - $dejaConsomme;
 
        for ($index1 = 0; $index1 <= (floor($resteDispo / $tabElements[1]->getCost())); $index1++) {
            $dejaConsomme+=$index1 * $tabElements[1]->getCost();
            $resteDispo = $maxValeur - $dejaConsomme;
 
            for ($index2 = 0; $index2 <= (floor($resteDispo / $tabElements[2]->getCost())); $index2++) {
                $dejaConsomme+=$index2 * $tabElements[2]->getCost();
                $resteDispo = $maxValeur - $dejaConsomme;
 
                 //Je créé mon combo 
                $arrayCombo = array();
 
 
                for ($index3 = 0; $index3 < $index; $index3++) {
                    array_push($arrayCombo, $tabElements[0]);
                }
                for ($index4 = 0; $index4 < $index1; $index4++) {
                    array_push($arrayCombo, $tabElements[1]);
                }
                for ($index5 = 0; $index5 < $index2; $index5++) {
                    array_push($arrayCombo, $tabElements[2]);
                }
 
                //Je push ce combo dans mon tableau de combos
                array_push($arrayCombos, $arrayCombo);
 
            }
        }
    }
    return $arrayCombos;
}

Tu penses que j'ai bien traduit ton algo? parce que ca ne fonctionne pas très bien :/

[tbc92]

En le relisant, je m'aperçois que je me suis planté, voici un correctif du pseudo-code :

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
 
Valeur est un tableau de 3 entiers
Valeur[1] = 4
Valeur[2] = 3
Valeur[3] = 2
maxValeur est un entier = 10
 
Pour i1 = 0 a MaxValeur / Valeur[1] 
  Deja_consomme = i1 * Valeur[1]
  Reste_Dispo = MAx_Valeur - Deja_consomme
  Pour i2 = 0 a Reste_Dispo / Valeur[2]
     Deja_consomme=  i1 * Valeur[1] + i2 * Valeur[2]
     Reste_Dispo = MAx_Valeur - Deja_consomme
     Pour i3 = 0 a  Reste_Dispo / Valeur[3]   
         Print ( " Solution", i1, i2, i3)
     fin
   fin
Fin

Seule la ligne 11 a changé.

[Timothy142857]

Ca ne semble toujours pas fonctionner, mais cest peut etre moi qui ai mal traduit. Néanmoins, je pense que ton algo ne s'adapte pas ) mon problème puisque il sous entend connaitre le nombre d'éléments du tableau de base, or ici il va changer régulièrement et nécessiterai de réécrire l'algo :/