Dans cet article, je vais analyser le septième niveau (final et le plus difficile) et partager la décision du vainqueur du jeu *.
* Clarification pour les joueurs. QA Game a été lancé en 2 flux: en juin et en juillet. Le nombre maximum de points pour tout le temps a été marqué par Alexander dès le premier flux, donc dans l'article, nous analyserons ses résultats. Le reste des dirigeants peut être vu sur le lien .
Ce qui est "à l'intérieur": la bibliothèque Ace.js est utilisée pour l'éditeur de code du jeu , la coloration syntaxique et l'auto-complétion y sont disponibles; webWorker est utilisé pour exécuter du code côté client (inspiré de cet article ). Le backend est écrit en Python & Flask, déployé sur Heroku . Au total, il a fallu environ 2 mois pour écrire le jeu.
Quand j'ai écrit QA Game, je n'avais pas encore d'expérience avec Ace.js et webWorkers, et c'était intéressant de les essayer. Si vous souhaitez faire un jeu similaire, alors je vous conseille de penser à:
- en exécutant le code du joueur côté serveur, pas côté client, comme je l'ai fait;
- en utilisant un framework backend asynchrone. Si le backend est en Python, je recommande Quart ou FastAPI ).
Légende du jeu QA
Dans le jeu, vous devez contrôler le personnage ZERO2, qui est capable de tester, rechercher et corriger les bogues. Le contrôle s'effectue à l'aide de code JavaScript, ZERO2 possède son propre SDK, ce qui simplifie grandement la programmation.
Par exemple, pour tester toutes les fonctionnalités disponibles au niveau, vous devez exécuter le code suivant:
let result = scan();
for (f of result.features) {
smoke_test(f);
}Et puis pour corriger tous les bugs trouvés lors des tests, comme ceci:
result = scan();
for (b of result.bugs) {
fix_bug(b);
}Chaque nouveau niveau du jeu contient des fonctions supplémentaires et nécessite l'utilisation d'algorithmes plus complexes; une analyse détaillée de chacun d'eux est publiée sur GitHub . Dans cet article, j'analyserai en détail le 7ème niveau, car c'est sur lui qu'il a été déterminé lequel des joueurs recevrait le maximum de points.
Comment obtenir un maximum de points? Version du créateur du jeu.
Au niveau 7, les joueurs doivent corriger et vérifier le nombre maximum de bogues possible en 120 secondes, tandis que:
- Le bouton RUN ne peut être enfoncé que 60 fois;
- Au bout de 120 secondes, l'algorithme se termine automatiquement, les points ne sont plus attribués (la validation était à la fois sur le front-end et sur le back-end);
- Pour chaque bug corrigé, 100 points sont attribués, pour un bug corrigé et vérifié - 150 points;
- Chaque fois que RUN démarre, tous les points sont réinitialisés et de nouveaux bogues sont générés aléatoirement.
Pour obtenir le nombre maximum de points, vous devez analyser les facteurs affectant le résultat:
- Simplification du code . Il est nécessaire de supprimer toutes les constructions inutiles et d'écrire du code clair, en le vérifiant pour la possibilité de bouclage. De nombreux participants ont perdu des points en raison d'erreurs dans le code, conduisant à des boucles vides sans fin;
- Réduire le temps de réponse à une demande . Chaque méthode SDK envoie une requête au serveur et, en moyenne, une requête prend entre 200 et 400 ms. Pour réduire ce chiffre, vous devez trouver un serveur approprié et exécuter des requêtes à partir de celui-ci;
- Optimisation des algorithmes . La plupart du temps, il faut trouver les étapes pour reproduire le bogue (fonction investiguer_bug). Par conséquent, vous devez réfléchir à la façon d'optimiser l'algorithme afin de trouver une solution dans le nombre minimum de tentatives;
- "Parallélisation" de l'algorithme . Le lancement standard se produit dans un thread (un webWorker), et toutes les méthodes API sont synchrones. Vous pouvez essayer de "paralléliser" l'algorithme. Et vous pouvez également voir s'il est possible de rendre certaines méthodes asynchrones (alerte spoiler: certaines le peuvent).
Optimisation des algorithmes
La fonction investig_bug (bug_id, steps) renvoie 0 si les étapes de lecture spécifiées ne sont pas correctes, 1 si les étapes de lecture spécifiées sont le début d'une combinaison correcte d'étapes et 100 si les étapes spécifiées sont la combinaison complète d'étapes pour reproduire le bogue.
L'algorithme de sélection des étapes de lecture peut ressembler à ceci:
function find_steps(bug_id) {
let path = '';
let result = 0;
while (result != 100) {
path += '>';
result = investigate_bug(bug_id, path);
if (result === 0) {
path = path.slice(0, -1);
path += '<';
result = investigate_bug(bug_id, path);
}
}
};Cette fonction peut être accélérée si, pour une certaine séquence, lors de la réception d'un "0", ne revérifiez pas la même séquence en remplaçant le dernier caractère. Au lieu de cela, vous devez immédiatement ajouter un autre caractère à la chaîne et vérifier le résultat pour une nouvelle ligne.
Qu'est-ce que ça veut dire? Il est possible de «sauvegarder» le nombre d'appels à investiguer_bug en utilisant cet algorithme (bien qu'il ne fonctionnera pas plus vite dans tous les cas):
function find_steps2(bug_id) {
let path = "";
result = 0;
prev_result = 0; // ,
// 0,
//
while (result != 100) {
result = investigate_bug(bug_id, path + ">");
if (result === 0) {
if (prev_result === 0) {
result = investigate_bug(bug_id, path + "<");
if (result > 0) {
prev_result = 1;
path += "<";
} else {
// 0,
// path
// 100 1
result = investigate_bug(bug_id, path);
}
} else {
prev_result = 0;
path += "<";
}
} else {
prev_result = 1;
path += ">";
}
}Comparons les résultats:
| Corriger les étapes de lecture | Nombre d'appels à investiguer_bug dans la fonction find_steps | Nombre d'appels investig_bug dans la fonction find_steps2 |
|---|---|---|
| >> | 2 | 2 |
| << | 4 | 6 |
| <<< | 6 | cinq |
| >> << >> | 8 | 7 |
| <<<<<< | 12 | 12 |
Peut-être pouvez-vous trouver un meilleur algorithme?
"Paralléliser" l'exécution du travail sur les bogues
Cela peut être fait de 2 manières:
- Créez de nouveaux webWorkers et transmettez-leur le code JavaScript en ligne:
let my_code = "console.log('Any JS code which you want to run');"; let bb = new Blob([hidden_js + my_code], { type: 'text/javascript' }); // convert the blob into a pseudo URL let bbURL = URL.createObjectURL(bb); // Prepare the worker to run the code let worker = new Worker(bbURL);
Avec cette approche, il ne reste plus qu'à résoudre le problème de la synchronisation des différents flux entre eux, et ici vous pouvez utiliser la propriété de la fonction fix_bug (bug_id) - si la fonction retourne "0", le bogue n'a pas encore été corrigé. - Affichez toutes les méthodes API appelées par les méthodes SDK de JS et créez votre propre script dans votre langage de programmation préféré. Cette approche est bonne car vous avez une totale liberté d'action, la possibilité d'exécuter facilement la solution dans plusieurs threads, la possibilité d'exécuter votre propre script depuis le serveur, ce qui aura une latence minimale pour les requêtes réseau.
Fonctions asynchrones
Après avoir analysé toutes les fonctions du SDK, vous pouvez voir que les fonctions fix_bug et verify_fix peuvent être rendues asynchrones en réécrivant simplement les fonctions standard utilisées dans le jeu:
function verify_fix(bug, path) {
let xhr = new XMLHttpRequest();
// - true - ,
xhr.open('POST', "https://qa.semrush-games.com/api/verify_fix", true);
xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
xhr.send("bug=" + bug + "&path=" + path);
}
function fix_bug(bug, path) {
var xhr = new XMLHttpRequest();
xhr.open('POST', "https://qa.semrush-games.com/api/fix_bug", true);
xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
xhr.onreadystatechange = function () {
if (this.readyState === XMLHttpRequest.DONE && this.status === 200) {
if (this.response.toString().length > 3) {
// , :
verify_fix(bug, path);
}
}
};
xhr.send("bug=" + bug.toString());
}
Comment obtenir le maximum de points? Version gagnante.
Alexander est devenu le gagnant avec 28 050 points. Il a raconté comment il a réussi à y parvenir, puis la narration à la première personne.
Quand j'ai rejoint le jeu, il y avait encore peu de participants (moins de 10). Après plusieurs tentatives, mon programme a obtenu plus de 11 000 points et a pris la première place de loin.
Mais comme la solution elle-même était assez triviale, j'ai réalisé que je ne resterais pas longtemps en premier lieu, alors j'ai commencé à réfléchir à la façon d'améliorer le programme.
Tout d'abord, j'ai regardé ce qui affectait le plus la vitesse de travail, il s'est avéré que 99% du temps était occupé par des requêtes au serveur. Chaque demande a pris environ 110 à 120 ms. En conséquence, il y avait 3 options principales pour accélérer le programme:
- Améliorer l'algorithme et réduire le nombre de requêtes au serveur;
- Utilisation de requêtes asynchrones vers le serveur;
- Réduire le temps d'une demande.
J'ai refusé la deuxième option, car elle irait au-delà des conditions du problème et de l'API synchrone d'origine.
Il y avait plusieurs façons de réduire le nombre de requêtes au serveur, mais toutes ne donnaient qu'une petite augmentation (quelques dizaines de pour cent au total).
Par conséquent, j'ai commencé à réfléchir à la façon de réduire le temps d'une demande. J'ai regardé où le serveur de jeu était déployé, il s'est avéré que c'était dans AWS à Dublin (ping à Dublin depuis ma ville> 100ms). Au début, je voulais louer un serveur dans ce centre de données et exécuter le programme directement à partir du rack suivant. Mais comme j'avais un serveur gratuit en Allemagne, j'ai d'abord décidé d'exécuter le programme à partir de là.
J'ai installé DE, VNC, Firefox, lancé le programme - et un ping inférieur a immédiatement augmenté le nombre de points gagnés de 2 fois. Et comme l'écart par rapport au reste était très important, j'ai décidé de ne pas améliorer davantage le résultat.
Voici une histoire.
Erreurs courantes des participants
En guise de postface, je vais partager quelques erreurs typiques qui ont empêché les participants d'obtenir plus de points:
- Des boucles sans fin sur la même liste de bogues déjà corrigés. Si l'algorithme ne se souvient pas des bogues déjà corrigés et les corrige plusieurs fois, le temps est perdu;
- Erreurs dans les boucles avec sélection des étapes de lecture pour les bogues. En conséquence, les cycles sont devenus interminables. De nombreux participants ont utilisé la limite de 100 caractères lors de la recherche des étapes de relecture, bien que la longueur de ligne maximale pour relire les bogues était de 10 caractères;
- Tous les participants n'ont pas essayé d'exécuter leurs algorithmes plusieurs fois, et si vous exécutez le même algorithme 2-3 fois, vous pourriez obtenir un peu plus de points en raison d'une distribution différente des bogues et d'autres séquences pour reproduire les bogues.
Je serai heureux de répondre aux questions sur le jeu et de voir vos options pour résoudre le septième niveau.