Utilisation d'un Web Worker pour la résolution d'un tirage du jeu télévisé Le Compte Est Bon
<html><head> <title>Le Compte Est Bon</title></head><body> <h1>Le Compte Est Bon : Résolution par JavaScript</h1> <h2>Les plaques disponibles pour le tirage</h2> Les plaques grises sont celles tirées pour le jeu <div id="jeu"></div> <h2>Le tirage du jeu</h2> <div id="plaques"></div> <h2>Solution</h2> <div id="buttons"> <div id="btn1" class="btn" onclick="getSolutionMultiThreads(1)">Chercher la solution</div> <div id="btn2" class="btn" onclick="getSolutionMultiThreads(2)">Avec 2 processus</div> <div id="btn2" class="btn" onclick="getSolutionMultiThreads(3)">Avec 3 processus</div> <div id="btn2" class="btn" onclick="getSolutionMultiThreads(4)">Avec 4 processus</div> </div> <div id="resultats"></div> <script type="text/javascript"> /* Mélange aléatoire d'un tableau */ function shuffle(tab) { tab.sort(function(a,b) { return Math.random()-Math.random(); }); } /* Tirage de dés entre 1 et n */ function getTirageDe(n) { return Math.floor(n * Math.random() + 1); } /* Retourne le numéro des nb plaques tirées au sort */ function getTiragePlaques(plaques, nb) { /* Crée le tableau des numéros d'indice de l'ensemble des plaques */ var indices=[] for (var i=0; i<plaques.length; i++) { indices.push(i); } /* Mélange du tableau d'indice */ shuffle(indices); return indices.slice(0, nb); } /* Tableau des plaques disponile dans le jeu */ var plaques=[1, 2, 3, 4, 5, 6, 7, 8, 9 ,10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 25, 50, 75, 100]; /* Tableau des 6 numéros de plaques tirées */ var indices=getTiragePlaques(plaques, 6); /* Retourne le nombre cible entre 100 et 999 à atteindre */ var but=99+getTirageDe(900); /* var tirages=[4,3,8,7,2,75]; var but=496; var tirages=[1,6,2,7,7,9]; var but=945; var tirages=[9,75,7,2,3,6]; var but=751; [23, 3, 22, 20, 5, 17], 122 [13, 17, 20, 10, 22, 12] 892 [20, 19, 12, 1, 11, 9] 248 */ // var but=721; // var indices=[16, 22, 12, 2, 7, 5]; var indices=[23, 20, 18, 17, 19, 1], but=600; var jeu={}; /* Tableau de la valeur des plaques tirées */ var tirages=[]; for (var i=0; i<indices.length; i++) { tirages[i]=plaques[indices[i]]; } relaunch(); printJeu(jeu); var myWorkers=[]; /* Tableau des workers */ /* Affiche les plaques de départ et le jeu avec les 6 plaques tirées et le but */ function printJeu(jeu) { var html=""; for (var i=0; i<jeu.plaques.length; i++) { var classe=""; if (jeu.indices.indexOf(i)>=0) { // Il s'agit d'une plaque tirée dans le jeu classe="off" } html+="<div class=\"plaque "+classe+"\">"+plaques[i]+"</div>"; } document.getElementById("jeu").innerHTML=html; var html=""; for (var i=0; i<jeu.tirages.length; i++) { html+="<div class=\"plaque\" id=\"plaque"+i+"\" data-indice=\""+i+"\" data-num-plaque=\""+jeu.indices[i]+"\">"+jeu.tirages[i]+"</div>"; } html+="<div class=\"but\">"; for (var i=0; i<jeu.but.toString().length; i++) { html+="<div class=\"chiffre\">"+jeu.but.toString()[i]+"</div>"; } html+="</div>"; document.getElementById("plaques").innerHTML=html; } /* Fonctions d'interfaces */ function hideButtons() { document.getElementById("buttons").style.display="none"; document.getElementById("resultats").innerHTML="<p>Recherche en cours</p><img src=\"media/calculate.png\" class=\"spinner\">"; document.getElementById("resultats").style.display="block"; } function relaunch() { /* Construction de l'objet du jeu */ jeu = { plaques: plaques, indices: indices, tirages: tirages, but: but, tours:[], solutions:[], uniques:[], proches:[], operateurs: ["+","-","x","/"], nbTours: 0, threadOperateurs: ["+","-","x","/"], numThread: 0, nbThread: 0, start: 0, end:0 }; document.getElementById("buttons").style.display="block"; document.getElementById("resultats").innerHTML=""; document.getElementById("resultats").style.display="none"; } /* Solution avec un seul worker */ function getSolution() { /* Lancement du worker dédié */ if (window.Worker) { hideButtons(); myWorkers[0]=new Worker("worker-lecompteestbon.js"); /* Envoyer un message avec la consigne de calcul de la solution */ myWorkers[0].postMessage(jeu); /* Réception du message avec le résultat */ myWorkers[0].onmessage=function(evenement) { printSolution(evenement.data); } } else { alert("Navigateur trop ancien"); } } /* Solution avec plusieurs threads (nb de 1, 2, 3 ou 4) */ function getSolutionMultiThreads(nb) { /* Lancement du worker dédié */ if (window.Worker) { var dt=new Date(); jeu.start=dt.getTime(); if ((nb!=1)&&(nb!=2)&&(nb!=3)&&(nb!=4)) { nb=1; } jeu.nbThread=nb; hideButtons(); console.log("Nb threads="+nb); for (var i=0; i<nb; i++) { myWorkers[i]={worker: {}, completed: false}; myWorkers[i].worker=new Worker("worker-lecompteestbon-multi.js"); /* Définition des opérations à traiter par thread */ var s=Math.floor(jeu.operateurs.length/nb); var fin=(i+1)*s; if ((i==nb-1)) { fin=jeu.operateurs.length; } jeu.threadOperateurs = jeu.operateurs.slice(i*s, fin); jeu.numThread=i; console.log("Thread #"+i+" avec opérateur(s) : "+jeu.threadOperateurs.toString()); /* Envoyer un message avec la consigne de calcul de la solution */ myWorkers[i].worker.postMessage(jeu); /* Réception du message avec le résultat */ myWorkers[i].worker.onmessage=function(evenement) { traiterOneSolution(evenement.data); } } } else { alert("Navigateur trop ancien"); } } // fonction de traitement d'une partie des solutions en mode multi threads function traiterOneSolution(solution) { jeu.uniques=jeu.uniques.concat(solution.uniques); myWorkers[solution.numThread].completed=true; // Vérifier si tous les Workers sont traités var completed=true; for (var i=0; i<myWorkers.length; i++) { if (!myWorkers[i].completed) { completed=false; } } if (completed) { /* Filtrer les solutions */ filtrerSolutions(); /* Mettre à jour le timer */ var dt=new Date(); jeu.end=dt.getTime(); /* Afficher les solutions */ printSolution(jeu); } } // Retourne le nombre de plaques du tirage utilisées par une solution function compterPlaqueSolution(solution) { // Suppression des indices -1 (plaques de calcul) var tmp=solution[solution.length-1].indices.filter( val => val==-1?false:true); return jeu.tirages.length-tmp.length; } /* Filtrer les solutions retournées par tous les Workers */ function filtrerSolutions() { // Parcourir toutes les solutions pour trouver la plus courte var nbBest=6, nbPlaque=0; for (var i=0; i<jeu.uniques.length; i++) { var sol=jeu.uniques[i]; nbBest=Math.min(nbBest, compterPlaqueSolution(sol)); } // Parcourir toutes les solutions pour ne garder que les plus courtes for (var i=0; i<jeu.uniques.length; i++) { var sol=jeu.uniques[i]; if (compterPlaqueSolution(sol)>nbBest) { jeu.uniques.splice(i, 1); i=-1; } } } // Afficher les solutions sur la page function printSolution(jeu) { var n=jeu.uniques.length; var res=document.getElementById("resultats"); if (n==0) { res="Le Compte n'y est pas !"; } else { var s=((n>0)?"s":""); var temps=(jeu.end-jeu.start)/1000; var txt=n+" solution"+s+" trouvée"+s+" en "+temps.toFixed(2)+ " secondes avec "+jeu.nbThread+" processus"; console.log(txt); res.innerHTML ="<p><strong>Le Compte Est Bon</strong> avec "+txt+"</p>"; res.innerHTML+="<div class=\"btn\" onclick=\"relaunch()\">Recommencer</div>"; for (var i=0; i<jeu.uniques.length; i++) { res.innerHTML+=getPrintTours(jeu.uniques[i]); } } } // Retourne le code HTML des tours d'une solution function getPrintTours(tours) { var html="<div class=\"calcul\">"; for (var i=0; i<tours.length; i++) { var t=tours[i]; var classe1="", classe2=""; if (i>0) { if (tours[i-1].indices[t.p1]<0) {classe1="result";} if (tours[i-1].indices[t.p2]<0) {classe2="result";} } // Remettre les plaques dans l'ordre si ope=negation ou division if ((t.ope=="-")||(t.ope=="/")) { if (t.v1<t.v2) { var d=t.v1; t.v1=t.v2; t.v2=d; c1=d; c1=c2; c2=d; } } html+="<div class=\"ligne\"><div class=\"plaque "+classe1+"\">"+t.v1+"</div><div class=\"operation\">"+t.ope+"</div><div class=\"plaque "+classe2+"\">"+t.v2+"</div>"+"<div class=\"operation\">=</div><div class=\"plaque result\">"+t.rst+"</div></div>"; } html+="</div>"; return html; } </script> <div class="source">Source des règles du jeu : <a target="_blank" href="https://www.apmep.fr/Le-compte-est-souvent-bon">https://www.apmep.fr/Le-compte-est-souvent-bon</a></div> <style type="text/css"> body { font-family: arial; } div#resultats { display:none; } div#buttons { display:block; } div.btn { display:inline-block; font-weight: bold; cursor: pointer; background: #066f09; border:2px solid #066f09; color:#fff; border-radius: 6px; padding:6px; margin:6px; } div.btn:hover { background: #fff; color:#066f09;; } div.plaque, div.chiffre, div.operation { color:#fff; font-size:24px; text-align:center; font-weight: bold; width:40px; background: #000; padding:1px; border:1px solid #000; display:inline-block; } div.plaque { border-radius: 3px; } div.plaque.off { background: #ccc; color:#666; } div.plaque.result { background: #fff; color:#333; } div.chiffre { width:20px; } div.operation { color:#000; background: transparent; border:0px; width:35px; font-size:35px; } div.calcul { padding:5px; margin:5px; padding-left:10px; border-left:3px solid #999; } div.calcul:hover { background: #ccc; } div.ligne { padding:3px; } div#plaques, div#chiffres, div.tour { padding:0px; } div#jeu { max-width:490px; } div#plaques .plaque, div#jeu .plaque { margin:2px; } div.jeu, div.but { padding:10px; display:inline-block; } div.source { font-size:12px; font-weight: bold; text-align: right; margin-top:30px; margin-right:5px; } h2 { margin-bottom:3px; } @keyframes rotate { from { transform: rotate(0deg); } to { transform: rotate(360deg); } } img.spinner { width:128px; height:128px; margin:50px; animation: rotate 2s ease-in-out alternate infinite; } </style></body></html>
/* Fichier JS du script lecompteestbon */// Execute l'operation ope sur les plaques numero p1 et p2 de jeu et met a jour le nouveau jeu function tour(jeu, p1, p2, ope) { if (jeu.tours.length==0) { // On prend les plaques du départ var plaques=jeu.tirages; var indices=jeu.indices; } else { // On récupère les plaques du tour précédent var plaques=jeu.tours[jeu.tours.length-1].plaques; var indices=jeu.tours[jeu.tours.length-1].indices; } var restes=[], resteIndices=[]; var v1, v2; for (var i=0; i<plaques.length; i++) { if ((i==p1)||(i==p2)) { if (i==p1) { v1=plaques[p1]; } if (i==p2) { v2=plaques[p2]; } } else { restes.push(plaques[i]); resteIndices.push(indices[i]); } } switch (ope) { case "+": var rst=v1+v2; restes.push(rst); resteIndices.push(-1); break; case "-": var rst=Math.abs(v1-v2); restes.push(rst); resteIndices.push(-1); break; case "x": var rst=v1*v2; restes.push(rst); resteIndices.push(-1); break; case "/": if (v1%v2==0) { var rst=v1/v2; resteIndices.push(-1); restes.push(rst); } else if (v2%v1==0) { var rst=v2/v1; resteIndices.push(-1); restes.push(rst); } break; } jeu.nbTours++; var tour={ p1: p1, p2: p2, v1: v1, v2: v2, ope:ope, rst:rst, plaques: restes, indices: resteIndices }; /* Un tour est composé des numéros de plaques p1 et p2 de la valeur des plaques v1 et v2 et d'indice i1 et i2 dans le tirage de l'opération ope et de son resultat rst et enfin du tableau plaques qui reste à utiliser */ jeu.tours.push(tour); // Si le tour arrive au but, enregistrer la solution qui utilise le moins d'opérations if (rst===jeu.but) { // Ajout de la nouvelle solution jeu.solutions.push(jeu.tours); // Filtrer les solutions avec moins d'opérations que la solution minimale ou la solution courante jeu.solutions=jeu.solutions.filter(t => t.length <= Math.min(jeu.tours.length, jeu.solutions[0].length)); } else { // Enregistrer les solutions les plus proches } return rst;}/* Fonction récursive pour parcourir les possibilites de réduction du tableau de tirage */function chercherSolution(jeu, operations="") { if (jeu.tours.length==0) { var plaques=jeu.tirages; } else { var plaques=jeu.tours[jeu.tours.length-1].plaques; } if (plaques.length<=2) { // Il ne reste plus assez de plaques : fin de la recherche return true; } // Tableaux des tours de la solution var tours=[]; // Boucle sur la première plaque du calcul for (var p1=0; p1<jeu.tirages.length; p1++) { // Boucle sur la seconde plaque (indice p2 de p1+1 a n) for (var p2=p1+1; p2<plaques.length; p2++) { // Boucle sur les 4 operations if (operations=="") { operations=jeu.operateurs; } operations.forEach(function(ope, index) { tours[p1+"-"+p2+"-"+index]=JSON.parse(JSON.stringify(jeu.tours)); // Réduction du tableau des plaques if (tour(jeu, p1, p2, ope)!=jeu.but) { /* Fonction de calcul d'une opération */ // Application de l'opération du tour chercherSolution(jeu); // Appel récursif } jeu.tours=tours[p1+"-"+p2+"-"+index]; }); } }}// Vérifier si les tours t1 et t2 sont equivalentsfunction isTourEquival(t1, t2) { if (t1.ope==t2.ope) { // Meme operation if ((t1.v1==t2.v1)&&(t1.v2==t2.v2)) {return true;} // Meme valeur de v1 et v2 if ((t1.v1==t2.v2)&&(t1.v2==t2.v1)) {return true;} // Meme valeur de v1 et v2 inversée } return false;} // Verifier que les solutions s1 et s2 sont bien uniquesfunction isSolutionEquivalente(s1, s2) { // Pas meme nombre de tours if (s1.length!=s2.length) { return false; } // Vérifier si le tour final est semblable entre les deux solutions var n=s1.length; if (isTourEquival(s1[n-1], s2[n-1])) { return true; } // Parcourir tous les tours de s1 for (var i=0; i<s1.length; i++) { var isTrouve=false; // Chercher un tour equivalent dans la solution s2 for (var j=0; j<s2.length; j++) { if (isTourEquival(s1[i], s2[j])) { isTrouve=true; break; } } if (isTrouve) { return true; } } return false;} /* Filtrer les solutions pupprimer les doublons */function filtrerSolution(jeu) { var uniques=[]; /* Ajouter la 1ere solution d'office*/ if (jeu.solutions.length==0) { } else { uniques.push(JSON.parse(JSON.stringify(jeu.solutions[0]))); // Comparer le reste des solutions for (var i=1; i<jeu.solutions.length; i++) { // Verifier si la solution est bien nouvelle var isNew=true; for (var j=0; j<uniques.length; j++) { // Si les deux solutions sont équivalentes, on ne l'ajoute pas à uniques if (isSolutionEquivalente(jeu.solutions[i], uniques[j])) { isNew=false; break; } } if (isNew) { uniques.push(JSON.parse(JSON.stringify(jeu.solutions[i]))); } } } jeu.uniques=uniques;}var jeu={};onmessage=function(evenement) { jeu=evenement.data; console.time("Traitements worker thread #"+jeu.numThread); var dt=new Date(); jeu.start=dt.getTime(); chercherSolution(jeu, jeu.threadOperateurs); filtrerSolution(jeu); console.timeEnd("Traitements worker thread #"+jeu.numThread); var dt=new Date(); jeu.end=dt.getTime(); postMessage(jeu);}