En recréant mon site perso pro, j’ai dû refaire le tour des projets que j’ai réalisés pour les ajouter à moins portfolio. Je suis retombé sur un mini défi, qui faisait parti d’un jeu réservé aux étudiants en école d’ingénieur. Le principe était simple, on présentait 4 nombres, il fallait trouver les bons opérateurs (+ – x %) pour obtenir 150.
Les concepteurs du site avait proposé une équation (fausse car ils avaient oublié les règles de priorisation des opérateurs 😅). Cependant, pour éviter que des étudiants crées un compte pour tester, puis un autre pour jouer et valider l’étape en une fois, en un temps record, j’ai proposé d’ajouter de l’aléatoire. L’objectif était toujours de placer les bons opérateur, avec les nombre proposés, pour atteindre 150 (nombre important pour la campagne).
J’ai donc créé un script qui recherchait toutes les équations possibles, avec pour résultat 150, contenant 3 opérateurs, avec des nombres entre 2 et 38. Après quelques suppressions (je n’ai plus la liste des équations excluent, mais il y avait les simplistes, du type 6 x 25 + a – a, 30 x 5 – a + a, 15 x 10 etc…. j’arrivais à un peu plus de 14.000 équations possible, une d’entre elle étant tirée au sort, au hasard, à l’arrivé du joueur sur la page du défis.
Dans ce poste, je vais recréer un script faisant cette même fouille. Rien de subtil, on va y aller en testant toutes les possibilités, de façon séquentielle.
1/ Les constantes et variables
Commençons par définir ce qui sera fixé au début du script. Je vais créer ce script en PHP, pour des raisons de simplicité… et d’habitude ! 🧐
| $nmin | La valeur minimale des nombres dans les équations |
| $nmax | La valeur maximale des nombres utilisés |
| $total | Le total visé |
| $nbmb | Le nombre de membres numériques ( = nombre d’opérateurs +1) |
| $operateurs | Un tableau des opérateurs disponibles, typiquement [‘+‘, ‘–‘, ‘*‘, ‘/‘] |
| $compteur | Un tableau dans lequel on comptera les équations testées et validées. Il sera définit ainsi: [‘test’=>0, ‘valid’=> 0] |
| $membres | Tableau présentant les valeurs actuelles des opérateurs et membres numérique, qui seront incrémenté au fur et à mesure du déroulement du script. Il sera définit ainsi: [‘num’=>[], ‘opr’=> []] |
| $continuer_num | Booléen permettant de contrôler si on continue de boucler ou si on a fait les tour des nombres autorisés |
| $continuer_opr | Booléen permettant de contrôler si on continue de boucler parmi les opérateurs. |
2/ Fonctionnement
a/ Incrémentation des membres numérique
Nous allons d’abord créer un fonction, qui va incrémenter les $nbmembres nombres, chacun leur tour, de façon séquentielle, par exemple, avec 3 membres entre 1 et 3, on aura successivement:
111, 112, 113, 121, 122, 123, 131, 132, 133,
211, 212, 213, 221, 222, 223, 231, 232, 233,
311, 312, 313, 321, 322, 323, 331, 332, 333
On sait que le nombre de combinaisons de nombre possibles est
La fonction va contrôler les membre numérique en partant de la fin, 3 cas:
- le membre est inférieur à la valeur max autorisée, on l’incrémente et la fonction renvoie TRUE
- le membre a la valeur max autorisée, on place la valeur minimale et on laisse tourner la fonction sur le membre précédent
- le membre a la valeur max autorisée et il s’agit du premier membre, on revoie FALSE, arrivé à ce point, logiquement, toutes les combinaisons ont été testées.
function incrementer()
{
global $membres, $nmin, $nmax;
for($i=sizeof($membres['num'])-1; $i>=0; $i--)
{
if($membres['num'][$i]<$nmax)
{
$membres['num'][$i]++;
return true;
}
else if($i>0)
{$membres['num'][$i] = $nmin;}
else
{return false;}
}
}On commence par peupler $membres (en fonction du nombre de membres et de la valeur numérique minimale)
On lance ensuite une boucle while, qui tourne tant que $continuer_num == true, cette variable prenant la valeur retournée par la fonction incrementer().
//On initialise la liste des membres
for($i=0; $i<$nbmb; $i++)
{$membres['num'][] = $nmin;}
//On lance la boucle
while($continuer_num)
{
//une combinaison de plus testée
$compteur['test']++;
//on garde la combinaison en mémoire pour affichage en fin de script
$sauvegarde[] = implode(",", $membres['num']);
//on incrémente le membres, la sortie définit si on continue de boucler sur le while
$continuer_num = incrementer();
}Je test avec les valeurs 1<=X<=10, avec 4 membres numérique. Le script complet est disponible sur github. Le script m’affiche la durée d’exécution, le nombre de combinaisons trouvées, ainsi que la liste complète – attention, selon les valeurs, la mémoire peut rapidement saturer ou le script atteindre le timeout de PHP. J’obtiens en sortie :
10000 combinaisons testées
en 0.0025031566619873 sLa première phase d’exploration des combinaisons est ok, on a bien (10 – 1 + 1)4 = 104 = 10000 combinaisons trouvées.
On peut maintenant boucler sur les opérateurs.
b/ Incrémentation des opérateurs
On va travailler sur la même fonction, qui va boucler également sur les opérateurs. Pour une même combinaison numérique, on testera tous les opérateurs avant d’incrémenter les membres numérique:
Avec la combinaison 111 , les tests opérateurs donnent :
1+1+1 ; 1+1-1 ; 1+1*1 ; 1+1/1
1-1+1 ; 1-1-1 ; 1-1*1 ; 1-1/1
1*1+1 ; 1*1-1 ; 1*1*1 ; 1*1/1
1/1+1 ; 1/1-1 ; 1/1*1 ; 1/1/1
Puis on incrémente sur les membres numériques, on obtient 112, et on test :
1+1+2 ; 1+1-2 ; 1+1*2 ; 1+1/2
1-1+2 ; 1-1-2 ; 1-1*2 ; 1-1/2
1*1+2 ; 1*1-2 ; 1*1*2 ; 1*1/2
1/1+2 ; 1/1-2 ; 1/1*2 ; 1/1/2
et ainsi de suite...Dans le cas présent, le nombre de formules possible est:
($nmax – $nmin + 1)$nbmb x sizeof($operateurs)($nbmb-1)
On va modifier la fonction incrementer() pour qu’elle s’occupe aussi des combinaisons d’opérateurs. On fera passer un chaîne en paramètre, qui définira le type de membre à incrémenter, puis un booléen qui indique si doit boucler ce membre. En effet, comme définit dans la liste précédente, on incrémentera les membres numérique seulement une fois que tous les opérateurs ont été testé sur la combinaison. Au moment d’incrémenter les nombre, on devra donc avoir réinitialisé la combinaison d’opérateurs.
En début de fonction, on définira les valeurs max et min selon le type à incrémenter. Dans le cas des nombres, on garde $nmin et $nmax, mais pour les opérateur, on aura 0 et sizeof($operateurs)-1.
function incrementer($typ='num', $boucler=false)
{
global $membres, $nmin, $nmax, $operateurs;
//Définition des valeur minimale et maximale selon le type d'opérateur à incrémenter
$min = ($typ=='opr') ? 0 : $nmin;
$max = ($typ=='opr') ? sizeof($operateurs)-1 : $nmax;
for($i=sizeof($membres[$typ])-1; $i>=0; $i--)
{
if($membres[$typ][$i]<$max)
{
$membres[$typ][$i]++;
return true;
}
else if($i>0)
{
$membres[$typ][$i] = $min;
}
else
{
if($boucler)
{
//si c'est un membre sur lequel on doit reboucler, on réinitialise
foreach($membres[$typ] as $k=>$v)
{$membres[$typ][$k] = $min;}
}
return false;
}
}
}Il faut ensuite revoir la boucle while, dans laquelle on ajoutera une seconde boucle while, qui contrôle la valeur $continuer_opr. C’est dans cette seconde boucle, que l’on incrémente le nombre de formule testées, avec d’incrémenter les opérateurs pour savoir si on poursuit. Si les opérateurs ont tous été testés pour cette combinaison numérique, incrementer() renvoie FALSE, après avoir réinitialisé le tableau opérateurs. On remonte à la boucle while des nombres qui va à son tour lancer incrementer(), si cette fonction renvoie TRUE, on boucle en repassant $continuer_opr à TRUE. Sinon, la boucle prend fin et on affiche les résultats.
while($continuer_num)
{
//on redéfinit la boucle opérateur sur TRUE
$continuer_opr = true;
while($continuer_opr)
{
//une combinaison de plus testée
$compteur['test']++;
//on garde la combinaison en mémoire pour affichage en fin de script
$sauvegarde[] = implode(",", $membres['num']).'/'.implode(",", $membres['opr']);
//on incrémente les opérateurs
$continuer_opr = incrementer('opr', true);
}
//on incrémente les membres numérique
$continuer_num = incrementer();
}On n’oubliera pas de définir les opérateurs disponibles, puis les initialiser, je ne précise pas cela ici, il suffit de regarder le script sur github pour cela.
J’ai fait un petit test, avec des nombres entre 1 et 10, 4 membres et les opérateurs +,-,x et /.
640000 combinaisons testées
en 0.27113199234009 sOn va maintenant passer à la phase finale du script, le test de la formule, pour obtenir le résultat et savoir si elle satisfait les conditions recherchées.
c/ Calcul du résultat
On commence par ajouter la valeur de résultat rechercher en ajoutant la variable $total.
Je vais tester les formule avec eval(). Evidement, si je souhaitais faire tourner cela en ligne, j’ajouterait des contrôles des valeurs (intval()… ) et des limites aux nombres d’opérateurs ou de delta entre min et max, mais on est dans un script destiné à tourner localement, donc pas de soucis de sécurité.
Je vais donc créer une fonction qui créera la formule sous forme de chaîne, puis une fonction qui la test.
function ecrireFormule($dt)
{
global $operateurs;
//on débute la chaîne par le 1er membre numérique
$str = $dt['num'][0];
//on boucle sur les membres opérateurs, on ajoute l'opérateur[X] et le nombre[X+1]
foreach($dt['opr'] as $k=>$v)
{
$str.= $operateurs[$dt['opr'][$k]] . $dt['num'][$k+1];
}
return $str;
}
function calculerResultat($str)
{
return eval("return ".$str.";");
}
Dans la seconde boucle while, on contrôlera si la formule renvoie la valeur recherchée, auquel cas, on la sauvegardera.
while($continuer_num)
{
//on redéfinit la boucle opérateur sur TRUE
$continuer_opr = true;
while($continuer_opr)
{
//une combinaison de plus testée
$compteur['test']++;
//on écrit la formule puis on la test
$str = ecrireFormule($membres);
if(calculerResultat($str)==$total)
{
//la formule donne le bon résultat, une formuale de plus est valide
$compteur['valid']++;
//on sauvegarde cette valeur
$sauvegarde[] = $str;
}
//on incrémente les opérateurs
$continuer_opr = incrementer('opr', true);
}
//on incrémente les membres numérique
$continuer_num = incrementer();
}Là encore le script est dispo sur mon github. Voici ce que donne le script avec des nombres entre 1 et 10, 4 membres, les opérateurs +, -, x, / et un résultat recherché de 42
640000 formules testées
1684 sont valides
en 1.4404809474945 sEt voilà !
Les scripts permettent d’afficher les formules valides, mais on voit de suite qu’avec seulement 4 opérateurs, 4 valeurs entre 1 et 10, on a 1684 formules disponibles pour obtenir 42 👽.
Je pense que je reviendrais plus tard sur ces scripts, j’ai quelques idées:
- ajouter des contrôles (interdire de diviser par 0; min<max; reculer le timeout…)
- une sortie en JSON ou d’insertion dans une base MySQL, pour utilisation dans d’autres scripts
- un portage en JS
- ignorer certains cas (x1 ; /1 ; +1-1 …) peu intéressants
Vous pouvez retrouver les scripts sur mon github.
A titre de démo, vous trouverez ici les 23213 formules donnant 42, avec 4 nombres entre 1 et 25 (10240000 combinaisons testée en 24 secondes… Merci l’informatique ! 👍).
