Cómo pasar el nivel final de JS QA Game de SEMrush

Hola, mi nombre es Timur y escribí un juego de control de calidad de SEMrush . Es posible que haya oído hablar de este juego si participó en Heisenbug en línea o vio los anuncios del juego en los chats de Telegram para probadores. En resumen, en QA Game necesitas completar niveles con dificultad creciente y detectar errores usando JavaScript.



En este artículo, analizaré el séptimo nivel (final y más difícil) y compartiré la decisión del ganador del juego *.







* Aclaración para jugadores. QA Game se lanzó en 2 transmisiones: en junio y en julio. Alexander anotó el número máximo de puntos para todo el tiempo desde la primera transmisión, por lo que en el artículo analizamos sus resultados. El resto de líderes se puede ver en el enlace .



Qué hay "dentro": la biblioteca Ace.js se usa para el editor de código en el juego , el resaltado de sintaxis y la finalización automática están disponibles en ella; webWorker se utiliza para ejecutar código en el lado del cliente (se inspiró en este artículo ). El backend está escrito en Python & Flask, implementado en Heroku . En total, tomó alrededor de 2 meses escribir el juego.



Cuando escribí QA Game, todavía no tenía experiencia con Ace.js y webWorkers, y fue interesante probarlos. Si quieres hacer un juego similar, te aconsejo que pienses en:

• ejecutando el código del reproductor en el lado del servidor, no en el lado del cliente, como hice yo;
• utilizando un marco de backend asincrónico. Si el backend está en Python, recomiendo Quart o FastAPI ).

Leyenda del juego de control de calidad

En el juego, debes controlar al personaje ZERO2, que puede probar, buscar y corregir errores. El control se realiza mediante código JavaScript, ZERO2 tiene su propio SDK, lo que simplifica enormemente la programación.



Por ejemplo, para probar todas las funciones disponibles en el nivel, debe ejecutar el siguiente código:

let result = scan();
for (f of result.features) {
    smoke_test(f);
}

Y luego, para corregir todos los errores encontrados durante las pruebas, esto es:

result = scan();
for (b of result.bugs) {
    fix_bug(b);
}

Cada nuevo nivel del juego contiene funciones adicionales y requiere el uso de algoritmos más complejos; El análisis detallado de cada uno de ellos se publica en GitHub . En este artículo analizaré en detalle el nivel 7, ya que fue en él donde se determinó cuál de los jugadores recibiría la máxima cantidad de puntos.

¿Cómo conseguir el máximo de puntos? Versión del creador del juego.

En el nivel 7, los jugadores deben corregir y verificar la cantidad máxima posible de errores en 120 segundos, mientras que:

1. El botón RUN solo se puede presionar 60 veces;
2. Después de 120 segundos, el algoritmo finaliza automáticamente, ya no se otorgan puntos (la validación se realizó tanto en el front-end como en el back-end);
3. Por cada error corregido, se otorgan 100 puntos, por un error corregido y verificado: 150 puntos;
4. Cada vez que inicias RUN, todos los puntos se restablecen y se generan nuevos errores de forma aleatoria.

Para obtener el número máximo de puntos, debe analizar los factores que afectan el resultado:

• Simplificación del código . Es necesario eliminar todas las construcciones innecesarias y escribir código claro, comprobando la posibilidad de bucles. Muchos participantes perdieron puntos debido a errores en el código, dando lugar a bucles vacíos sin fin;
• Reducir el tiempo de respuesta a una solicitud . Cada método SDK realiza una solicitud al servidor y, en promedio, una solicitud tarda entre 200 y 400 ms. Para reducir esta cifra, debe encontrar un servidor adecuado y ejecutar consultas desde él;
• Optimización de algoritmos . La mayoría de las veces se tarda en encontrar los pasos para reproducir el error (función research_bug). Por lo tanto, debe pensar en cómo optimizar el algoritmo para encontrar una solución en el número mínimo de intentos;
• "Paralelización" del algoritmo . El lanzamiento estándar ocurre en un hilo (un webWorker) y todos los métodos API son sincrónicos. Puede intentar "paralelizar" el algoritmo. Y también puede ver si es posible hacer que algunos de los métodos sean asincrónicos (alerta de spoiler: algunos pueden).

Optimización de algoritmos

La función research_bug (bug_id, steps) devuelve 0 si los pasos de reproducción especificados no son correctos, 1 si los pasos de reproducción especificados son el comienzo de una combinación correcta de pasos y 100 si los pasos especificados son una combinación completa de pasos para reproducir el error.



El algoritmo para seleccionar los pasos de reproducción puede tener este aspecto:

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);
        }
    }
};

Esta función se puede acelerar si, para una determinada secuencia, al recibir un "0", no se vuelve a verificar la misma secuencia, reemplazando el último carácter. En su lugar, debe agregar inmediatamente otro carácter a la cadena y verificar el resultado para una nueva línea.



Qué significa eso? Es posible "guardar" el número de llamadas a research_bug usando este algoritmo (aunque no funcionará más rápido en todos los casos):

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 += ">";
        }
    }

Comparemos los resultados:

Es importante tener en cuenta que el segundo algoritmo no siempre es más rápido, pero en la mayoría de los casos le permite encontrar una solución en menos pasos. Además, en algunos casos, importa cuál de los caracteres> o <se sustituirá en primer lugar. Sin embargo, dada la aleatoriedad de las combinaciones seleccionadas, podemos concluir que esto no dará un aumento notable.



¿Quizás puedas encontrar un algoritmo mejor?

"Paralelizar" la ejecución del trabajo sobre errores

Esto se puede hacer de 2 formas:

1. Cree nuevos webWorkers y páselos código JavaScript en la línea:
   
   
   
   

   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);

   
   
   Con este enfoque, solo queda resolver el problema de sincronizar diferentes flujos entre sí, y aquí puede usar la propiedad de la función fix_bug (bug_id); si la función devuelve "0", entonces el error aún no se ha solucionado.
2. Vea todos los métodos API que son llamados por métodos SDK desde JS y cree su propio script en su lenguaje de programación favorito. Este enfoque es bueno porque tiene total libertad de acción, la capacidad de ejecutar fácilmente la solución en varios subprocesos, la capacidad de ejecutar su propio script desde el servidor, que tendrá una latencia mínima para las solicitudes de red.

Funciones asincrónicas

Después de analizar todas las funciones del SDK, puede ver que las funciones fix_bug y verify_fix pueden hacerse asincrónicas simplemente reescribiendo las funciones estándar que se utilizan en el juego:

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());
}

¿Cómo conseguir el máximo de puntos? Versión ganadora.

Alexander se convirtió en el ganador con 28.050 puntos. Contó cómo logró lograrlo, luego la narración en primera persona.



Cuando me uní al juego, todavía había pocos participantes (menos de 10). Después de varios intentos, mi programa superó los 11.000 puntos y ocupó el primer lugar por un amplio margen.



Pero como la solución en sí era bastante trivial, me di cuenta de que no me quedaría en primer lugar por mucho tiempo, así que comencé a pensar en cómo mejorar el programa.



Primero, miré qué afecta más la velocidad de trabajo, resultó que el 99% del tiempo estaba ocupado por solicitudes al servidor. Cada solicitud tomó aproximadamente 110-120 ms. En consecuencia, había 3 opciones principales para acelerar el programa:

• Mejorar el algoritmo y reducir el número de solicitudes al servidor;
• Usar solicitudes asincrónicas al servidor;
• Reducir el tiempo de una solicitud.

Rechacé la segunda opción, ya que iría más allá de las condiciones del problema y de la API síncrona original.



Había varias formas de reducir la cantidad de solicitudes al servidor, pero todas dieron solo un pequeño aumento (unas pocas decenas de por ciento en total).



Por lo tanto, comencé a pensar en cómo reducir el tiempo de una solicitud. Miré dónde se implementó el servidor del juego, resultó que estaba en AWS en Dublín (ping a Dublín desde mi ciudad> 100 ms). Al principio, quería alquilar un servidor en este centro de datos y ejecutar el programa directamente desde el siguiente bastidor. Pero como tenía un servidor gratuito en Alemania, primero decidí ejecutar el programa desde allí.



Instalé DE, VNC, Firefox, lancé el programa y un ping más bajo aumentó inmediatamente la cantidad de puntos ganados en 2 veces. Y como la diferencia con el resto era muy grande, decidí no mejorar más el resultado.



He aquí una historia.

Errores comunes de los participantes

Como epílogo, compartiré algunos errores típicos que impidieron a los participantes obtener más puntos:

• Bucles interminables sobre la misma lista de errores ya corregidos. Si el algoritmo no recuerda los errores ya corregidos y los corrige varias veces, se pierde tiempo;
• Errores en bucles con selección de pasos de reproducción para errores. Como resultado, los ciclos se volvieron interminables. Muchos participantes utilizaron el límite de 100 caracteres al buscar pasos de repetición, aunque la longitud máxima de línea para reproducir errores fue de 10 caracteres;
• No todos los participantes intentaron ejecutar sus algoritmos varias veces, y si ejecuta el mismo algoritmo 2-3 veces, podría obtener un poco más de puntos debido a una distribución diferente de errores y otras secuencias para reproducir errores.

Estaré encantado de responder preguntas sobre el juego y ver tus opciones para resolver el séptimo nivel.