Как пройти финальный уровень JS QA Game от SEMrush

Привет, меня зовут Тимур, и я написал QA Game от SEMrush. Вы могли слышать об этой игре, если участвовали в Heisenbug online или видели анонсы игры в Telegram-чатах для тестировщиков. Если коротко, то в QA Game нужно проходить уровни с нарастающей сложностью и отлавливать баги, используя JavaScript.

В этой статье я разберу седьмой (финальный и самый сложный) уровень и поделюсь решением победителя игры*.



* Пояснение для игроков. QA Game была запущена в 2 потока: в июне и в июле. Максимальное количество баллов за все время набрал Александр из первого потока, поэтому в статье разбираем именно его результаты. Остальных лидеров можно увидеть по ссылке.

Что «внутри»: для редактора кода в игре используется библиотека Ace.js в ней доступны подсветка синтаксиса и автодополнение; для исполнения кода на стороне клиента используется webWorker (был вдохновлен этой статьей). Backend написан на Python & Flask, задеплоен на Heroku. В сумме на написание игры было потрачено около 2 месяцев.

Когда я писал QA Game, у меня еще не было опыта с Ace.js & webWorkers, и было интересно их попробовать. Если вы хотите сделать подобную игру, то советую подумать над:

• исполнением кода игроков на стороне сервера, а не на стороне клиента, как сделал я;
• использованием асинхронного фреймворка для бэкенда. Если бекенд на Python, советую Quart или FastAPI).

Легенда QA Game

В игре необходимо управлять персонажем ZERO2, который умеет тестировать, искать и исправлять баги. Управление происходит с помощью JavaScript кода, у ZERO2 есть собственный SDK, который заметно упрощает программирование.

Например, чтобы протестировать все имеющиеся на уровне фичи, нужно выполнить такой код:

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

А чтобы после этого исправить все найденные при тестировании баги, такой:

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

Каждый новый уровень в игре содержит в себе дополнительные функции и требует применения более сложных алгоритмов; подробный разбор каждого из них опубликован на GitHub. В этой статье я детально разберу 7 уровень, поскольку именно на нем определялось, кто из игроков получит максимальное количество баллов.

Как набрать максимум баллов? Версия создателя игры.

На 7 уровне игрокам нужно исправить и верифицировать максимально возможное количество багов за 120 секунд, при этом:

1. Нажать кнопку RUN можно только 60 раз;
2. Через 120 секунд алгоритм автоматически завершается, баллы больше не начисляются (валидация была и на фронтенде, и на бекенде);
3. За каждый исправленный баг начисляется 100 очков, за исправленный и верифицированный —150 очков;
4. Каждый раз запуск RUN сбрасывает все очки, и новые баги генерируются случайным образом.

Чтобы набрать максимальное количество баллов, нужно проанализировать факторы, влияющие на результат:

• Упрощение кода. Нужно убрать все лишние конструкции и писать понятный код, проверяя его на возможность зацикливания. Многие участники теряли баллы из-за ошибок в коде, приводящих к бесконечным пустым циклам;
• Снижение времени ответа на запрос. Каждый метод SDK делает запрос к серверу, и в среднем на один запрос тратится 200-400 мс. Чтобы снизить этот показатель, нужно найти подходящий сервер и выполнять запросы с него;
• Оптимизация алгоритма. Больше всего времени требуется на поиск шагов воспроизведения бага (функция investigate_bug). Поэтому нужно подумать, как оптимизировать алгоритм, чтобы находить решение за минимальное количество попыток;
• «Распараллеливание» алгоритма. Стандартный запуск происходит в один поток (один webWorker), и все API-методы синхронные. Можно попробовать «распараллелить» алгоритм. А еще можно просмотреть, возможно ли часть методов сделать асинхронными (спойлер: некоторые можно).

Оптимизация алгоритма

Функция investigate_bug(bug_id, steps) возвращает 0, если указанные шаги воспроизведения не верны, 1, если указанные шаги воспроизведения являются началом верной комбинации шагов и 100, если указанные шаги — это полная комбинация шагов для воспроизведения бага.

Алгоритм подбора шагов воспроизведения может выглядеть так:

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

Эту функцию можно ускорить, если для определенной последовательности при получении «0» не перепроверять ту же последовательность, заменяя последний символ. Вместо этого нужно сразу добавить еще один символ к строке и проверять результат для новой строки.

Что это значит? Можно “сэкономить” количество вызовов investigate_bug, применяя такой алгоритм (хотя он будет быстрее работать не для всех случаев):

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

Сравним результаты:
Важно отметить, что второй алгоритм не всегда работает быстрее, но для большинства случаев он позволяет найти решение за меньшее количество шагов. Также для некоторых случаев имеет значение какой из символов > или < будет подставляться в первую очередь. Правда, учитывая случайность выбранных комбинаций, можно сделать заключение, что это не даст заметного прироста.

Возможно, вы найдете более оптимальный алгоритм?

«Распараллеливаем» выполнение работы над багами

Это можно было сделать 2 способами:

1. Создавать новые webWorkers, и передавать им JavaScript код в строке:
   
   

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

   
   При таком подходе остается только решить вопрос синхронизации разных потоков между собой, и тут можно пользоваться свойством функции fix_bug(bug_id) — если функция возвращает «0», значит, баг еще не был исправлен.
2. Посмотреть все API методы, которые вызываются SDK методами из JS и сделать свой собственный скрипт на любимом языке программирования. Такой подход хорош тем, что у вас появляется полная свобода действий, возможность легкого запуска решения в несколько потоков, возможность запуска собственного скрипта с сервера, у которого будет минимальная задержка для сетевых запросов.

Асинхронные функции

Проанализировав все SDK функции, можно было заметить, что функцию fix_bug и verify_fix можно сделать асинхронными, просто переписав стандартные функции, которые используются в игре:

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

Как набрать максимум баллов? Версия победителя.

Победителем стал Александр, набравший 28 050 баллов. Он рассказал, как удалось этого достичь, далее повествование от первого лица.

Когда я подключился к игре, то в ней еще было мало участников (меньше 10). После нескольких попыток моя программа получила больше 11000 очков и заняла первое место с большим отрывом.

Но так как само решение было достаточно тривиальным, то я понимал, что на первом месте я останусь не надолго, поэтому стал думать как улучшить программу.

Сначала я посмотрел, что больше всего влияет на скорость работы, оказалось, что 99% времени занимали запросы к серверу. Каждый запрос занимал примерно 110-120 мс. Соответственно было 3 основных варианта ускорения программы:

• Улучшение алгоритма и уменьшение количества запросов к серверу;
• Использование асинхронных запросов к серверу;
• Уменьшение времени одного запроса.

От второго варианта я отказался, так как это выходило бы за рамки условий задачи и исходного синхронного API.

Уменьшить количество запросов к серверу можно было несколькими способами, но все они давали лишь небольшой прирост (в сумме несколько десятков процентов).

Поэтому я стал думать, как уменьшить время одного запроса. Посмотрел где развернут сервер игры, оказалось что в AWS в Дублине (пинг до Дублина из моего города >100мс). Сначала я хотел арендовать сервер в этом датацентре и запустить программу прямо с соседней стойки. Но так как у меня был свободный сервер в Германии, то для начала решил запустить программу оттуда.

Установил DE, VNC, Firefox, запустил программу — и меньший пинг сразу увеличил количество заработанных очков в 2 раза. И так как отрыв от остальных был очень большой, то дальше результат я решил не улучшать.

Вот такая история.

Типичные ошибки участников

В качестве послесловия поделюсь несколькими типичными ошибками, которые не давали участникам получить больше баллов:

• Бесконечные циклы по одному и тому же списку уже исправленных багов. Если алгоритм не запоминает уже исправленные баги и исправляет их по несколько раз, время тратится впустую;
• Ошибки в циклах с подбором шагов воспроизведения для багов. В результате этого циклы становились бесконечными. Многие участники использовали ограничение в 100 символов при поиске шагов воспроизведения, хотя максимальная длина строки для воспроизведения багов была 10 символов;
• Не все участники пробовали запустить свои алгоритмы по несколько раз, и при запуске одного и того же алгоритма 2-3 раза можно было бы получить чуть больше баллов за счет другого распределения багов и других последовательностей для воспроизведения багов.

Буду рад ответить на вопросы об игре и увидеть ваши варианты решения седьмого уровня.