Clever Geek Handbook

How to pass the final level of JS QA Game from SEMrush

Hi my name is Timur and I wrote a QA Game from SEMrush . You may have heard about this game if you participated in Heisenbug online or saw the announcements of the game in Telegram chats for testers. In short, in QA Game you need to complete levels with increasing difficulty and catch bugs using JavaScript.



In this article, I will analyze the seventh (final and most difficult) level and share the decision of the winner of the game *.



image



* Clarification for players. QA Game was launched in 2 streams: in June and in July. The maximum number of points for all the time was scored by Alexander from the first stream, so in the article we will analyze his results. The rest of the leaders can be seen at the link .



What's "inside": the Ace.js library is used for the code editor in the game ; syntax highlighting and auto-completion are available in it; webWorker is used to execute code on the client side (was inspired by this article ). The backend is written in Python & Flask, deployed on Heroku . In total, it took about 2 months to write the game.



When I wrote QA Game, I had no experience with Ace.js & webWorkers yet, and it was interesting to try them out. If you want to make a similar game, then I advise you to think about:



  • by executing player code on the server side, not on the client side, as I did;
  • using an asynchronous backend framework. If the backend is in Python, I recommend Quart or FastAPI ).


QA Game Legend



In the game, you need to control the character ZERO2, who is able to test, search and fix bugs. The control takes place using JavaScript code, ZERO2 has its own SDK, which greatly simplifies programming.



For example, to test all the features available at the level, you need to run the following code: 



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


And then to fix all the bugs found during testing, like this: 



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


Each new level in the game contains additional functions and requires the use of more complex algorithms; detailed analysis of each of them is published on GitHub . In this article, I will analyze in detail the 7th level, since it was on it that it was determined which of the players would receive the maximum number of points.



How to get maximum points? Game creator version.



At level 7, players need to fix and verify the maximum possible number of bugs in 120 seconds, while:



  1. The RUN button can only be pressed 60 times;
  2. After 120 seconds, the algorithm ends automatically, points are no longer awarded (validation was on both the front-end and the back-end);
  3. For each fixed bug, 100 points are awarded, for a corrected and verified bug - 150 points;
  4. Every time you start RUN, all points are reset, and new bugs are randomly generated.


To get the maximum number of points, you need to analyze the factors affecting the result:



  • Simplification of the code . It is necessary to remove all unnecessary constructions and write clear code, checking it for the possibility of looping. Many participants lost points due to errors in the code, leading to endless empty loops;
  • Reducing the response time to a request . Each SDK method makes a request to the server, and on average, one request takes 200-400 ms. To reduce this figure, you need to find a suitable server and execute queries from it;
  • Algorithm optimization . Most of the time it takes to find the steps to reproduce the bug (function investigate_bug). Therefore, you need to think about how to optimize the algorithm in order to find a solution in the minimum number of attempts;
  • "Parallelization" of the algorithm . Standard launch happens in one thread (one webWorker), and all API methods are synchronous. You can try to "parallelize" the algorithm. And you can also see if it is possible to make some of the methods asynchronous (spoiler alert: some can).


Algorithm optimization



The investigate_bug (bug_id, steps) function returns 0 if the specified playback steps are not correct, 1 if the specified playback steps are the beginning of a correct combination of steps, and 100 if the specified steps are the full combination of steps to reproduce the bug.



The algorithm for selecting playback steps may look like this: 



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


This function can be accelerated by not rechecking the same sequence, replacing the last character, for a certain sequence when receiving a "0". Instead, you need to immediately add another character to the string and check the result for a newline.



What does it mean? It is possible to “save” the number of calls to investigate_bug by using this algorithm (although it will not work faster in all cases): 



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


Let's compare the results:

Correct playback steps Number of investigate_bug calls in find_steps function The number of investigate_bug calls in the find_steps2 function
>> 2 2
<< 4 6
<<< 6 five
>> << >> 8 7
<<<<<< 12 12
It is important to note that the second algorithm is not always faster, but in most cases it allows you to find a solution in fewer steps. Also, for some cases, it matters which of the characters> or <will be substituted in the first place. However, given the randomness of the selected combinations, we can conclude that this will not give a noticeable increase.



Perhaps you can find a better algorithm?



"Parallelizing" the execution of work on bugs



This could be done in 2 ways:



  1. Create new webWorkers, and pass JavaScript code to them in line: 



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


    With this approach, it remains only to solve the issue of synchronizing different streams with each other, and here you can use the fix_bug (bug_id) function property - if the function returns "0", then the bug has not been fixed yet.
  2. View all API methods that are called by SDK methods from JS and make your own script in your favorite programming language. This approach is good because you have complete freedom of action, the ability to easily run the solution in several threads, the ability to run your own script from the server, which will have a minimum latency for network requests.


Asynchronous functions



After analyzing all SDK functions, you can see that the fix_bug and verify_fix functions can be made asynchronous by simply rewriting the standard functions that are used in the game: 



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


How to get maximum points? Winner version.



Alexander became the winner with 28,050 points. He told how he managed to achieve this, then the narration in the first person.



When I joined the game, there were still few participants (less than 10). After several attempts, my program got over 11,000 points and took first place by a wide margin.



But since the solution itself was quite trivial, I realized that I would not stay in the first place for long, so I began to think about how to improve the program.



First, I looked at what affects the speed of work the most, it turned out that 99% of the time was occupied by requests to the server. Each request took approximately 110-120ms. Accordingly, there were 3 main options for accelerating the program:



  • Improving the algorithm and reducing the number of requests to the server;
  • Using asynchronous requests to the server;
  • Reducing the time of one request.


I refused the second option, since it would go beyond the conditions of the problem and the original synchronous API.



There were several ways to reduce the number of requests to the server, but all of them gave only a small increase (a few tens of percent in total).



Therefore, I began to think about how to reduce the time of one request. I looked where the game server was deployed, it turned out that it was in AWS in Dublin (ping to Dublin from my city> 100ms). At first I wanted to rent a server in this data center and run the program directly from the next rack. But since I had a free server in Germany, I first decided to run the program from there.



I installed DE, VNC, Firefox, launched the program - and a lower ping immediately increased the number of points earned by 2 times. And since the gap from the others was very large, I decided not to improve the result further.



Here's a story.



Common mistakes of participants



As an afterword, I will share a few typical mistakes that prevented participants from getting more points:



  • Endless loops over the same list of already fixed bugs. If the algorithm does not remember already fixed bugs and fixes them several times, time is wasted;
  • Errors in loops with selection of playback steps for bugs. As a result, the cycles became endless. Many contributors used the 100 character limit when looking for replay steps, although the maximum line length for replaying bugs was 10 characters;
  • Not all participants tried to run their algorithms several times, and if you run the same algorithm 2-3 times, you could get a little more points due to a different distribution of bugs and other sequences to reproduce bugs.


I will be happy to answer questions about the game and see your options for solving the seventh level.


More articles:


All Articles