Cara lulus level akhir Game JS QA dari SEMrush

Hai nama saya Timur dan saya menulis Game QA dari SEMrush . Anda mungkin pernah mendengar tentang game ini jika Anda berpartisipasi dalam Heisenbug online atau melihat pengumuman game di obrolan Telegram untuk penguji. Singkatnya, dalam QA Game Anda harus menyelesaikan level dengan kesulitan yang meningkat dan menangkap bug menggunakan JavaScript.



Pada artikel ini, saya akan menganalisis level ketujuh (terakhir dan paling sulit) dan membagikan keputusan pemenang permainan *.







* Klarifikasi untuk pemain. QA Game diluncurkan dalam 2 aliran: pada bulan Juni dan Juli. Jumlah poin maksimum untuk sepanjang waktu dicetak oleh Alexander dari aliran pertama, jadi dalam artikel kami menganalisis hasilnya. Pemimpin lainnya dapat dilihat di tautan .



Apa yang "di dalam": pustaka Ace.js digunakan untuk editor kode dalam game ; penyorotan sintaks dan pelengkapan otomatis tersedia di dalamnya; webWorker digunakan untuk mengeksekusi kode di sisi klien (terinspirasi oleh artikel ini ). Backend ditulis dengan Python & Flask, diterapkan di Heroku . Totalnya, butuh waktu sekitar 2 bulan untuk menulis game tersebut.



Saat saya menulis QA Game, saya belum memiliki pengalaman dengan Ace.js & webWorkers, dan sangat menarik untuk mencobanya. Jika Anda ingin membuat game serupa, maka saya menyarankan Anda untuk memikirkan:

• dengan menjalankan kode pemain di sisi server, bukan di sisi klien, seperti yang saya lakukan;
• menggunakan kerangka kerja backend asinkron. Jika backend menggunakan Python, saya merekomendasikan Quart atau FastAPI ).

Legenda Game QA

Dalam permainan, Anda perlu mengontrol karakter ZERO2, yang mampu menguji, mencari dan memperbaiki bug. Kontrol dilakukan dengan menggunakan kode JavaScript, ZERO2 memiliki SDK sendiri, yang sangat menyederhanakan pemrograman.



Misalnya, untuk menguji semua fitur yang tersedia di level, Anda perlu menjalankan kode berikut:

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

Dan kemudian untuk memperbaiki semua bug yang ditemukan selama pengujian, ini adalah:

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

Setiap level baru dalam game berisi fungsi tambahan dan membutuhkan penggunaan algoritme yang lebih kompleks; analisis rinci masing-masing dipublikasikan di GitHub . Pada artikel ini, saya akan menganalisis secara rinci level ke-7, karena di atasnya ditentukan pemain mana yang akan menerima jumlah poin maksimum.

Bagaimana cara mendapatkan poin maksimal? Versi pembuat game.

Di level 7, pemain perlu memperbaiki dan memverifikasi jumlah bug maksimum yang mungkin dalam 120 detik, sementara:

1. Tombol RUN hanya dapat ditekan 60 kali;
2. Setelah 120 detik, algoritme berakhir secara otomatis, poin tidak lagi diberikan (validasi dilakukan di front-end dan back-end);
3. Untuk setiap bug tetap, 100 poin diberikan, untuk bug yang dikoreksi dan diverifikasi - 150 poin;
4. Setiap kali Anda memulai RUN, semua poin disetel ulang, dan bug baru dibuat secara acak.

Untuk mendapatkan jumlah poin maksimum, Anda perlu menganalisis faktor-faktor yang memengaruhi hasil:

• Penyederhanaan kode . Anda perlu menghapus semua konstruksi yang tidak perlu dan menulis kode yang jelas, memeriksanya untuk kemungkinan perulangan. Banyak peserta kehilangan poin karena kesalahan dalam kode, yang menyebabkan loop kosong tanpa akhir;
• Mengurangi waktu respons untuk permintaan . Setiap metode SDK membuat permintaan ke server, dan rata-rata, satu permintaan membutuhkan 200-400 md. Untuk mengurangi angka ini, Anda perlu mencari server yang sesuai dan menjalankan kueri darinya;
• Pengoptimalan algoritme . Sebagian besar waktu yang diperlukan untuk menemukan langkah-langkah untuk mereproduksi bug (function investig_bug). Oleh karena itu, Anda perlu memikirkan tentang cara mengoptimalkan algoritme untuk menemukan solusi dalam jumlah upaya minimum;
• "Paralelisasi" dari algoritme . Peluncuran standar terjadi di satu thread (satu webWorker), dan semua metode API sinkron. Anda dapat mencoba "memparalelkan" algoritme. Dan Anda juga dapat melihat apakah mungkin untuk membuat beberapa metode asynchronous (spoiler alert: beberapa bisa).

Pengoptimalan algoritme

Fungsi investig_bug (bug_id, steps) mengembalikan 0 jika langkah-langkah pemutaran yang ditentukan tidak benar, 1 jika langkah-langkah pemutaran yang ditentukan adalah awal dari kombinasi langkah-langkah yang benar, dan 100 jika langkah-langkah yang ditentukan adalah kombinasi lengkap dari langkah-langkah untuk mereproduksi bug.



Algoritme untuk memilih langkah pemutaran mungkin terlihat seperti ini:

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

Fungsi ini dapat dipercepat jika, untuk urutan tertentu, saat menerima "0", tidak memeriksa ulang urutan yang sama, mengganti karakter terakhir. Sebagai gantinya, Anda perlu segera menambahkan karakter lain ke string dan memeriksa hasilnya untuk baris baru.



Apa artinya? Anda dapat "menyimpan" jumlah panggilan investig_bug dengan menggunakan algoritme ini (meskipun tidak akan bekerja lebih cepat di semua kasus):

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

Mari bandingkan hasilnya:

Penting untuk diperhatikan bahwa algoritme kedua tidak selalu lebih cepat, tetapi dalam banyak kasus, algoritme ini memungkinkan Anda menemukan solusi dalam beberapa langkah. Juga, untuk beberapa kasus, penting karakter mana> atau <yang akan diganti di tempat pertama. Namun, mengingat kombinasi yang dipilih acak, kita dapat menyimpulkan bahwa ini tidak akan memberikan peningkatan yang nyata.



Mungkin Anda dapat menemukan algoritme yang lebih baik?

"Memparalelkan" pelaksanaan pekerjaan pada bug

Ini dapat dilakukan dengan 2 cara:

1. Buat webWorkers baru, dan berikan kode JavaScript kepada mereka sejalan:
   
   
   
   

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

   
   
   Dengan pendekatan ini, yang tersisa hanyalah menyelesaikan masalah sinkronisasi aliran yang berbeda satu sama lain, dan di sini Anda dapat menggunakan properti fungsi fix_bug (bug_id) - jika fungsi mengembalikan "0", maka bug belum diperbaiki.
2. Lihat semua metode API yang dipanggil oleh metode SDK dari JS dan buat skrip Anda sendiri dalam bahasa pemrograman favorit Anda. Pendekatan ini bagus karena Anda memiliki kebebasan penuh untuk bertindak, kemampuan untuk dengan mudah menjalankan solusi di beberapa utas, kemampuan untuk menjalankan skrip Anda sendiri dari server, yang akan memiliki latensi minimum untuk permintaan jaringan.

Fungsi asinkron

Setelah menganalisis semua fungsi SDK, Anda dapat melihat bahwa fungsi fix_bug dan verifikasi_fix dapat dibuat asinkron hanya dengan menulis ulang fungsi standar yang digunakan dalam 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());
}

Bagaimana cara mendapatkan poin maksimal? Versi pemenang.

Alexander menjadi pemenang dengan 28.050 poin. Dia menceritakan bagaimana dia berhasil mencapai ini, lalu narasinya sebagai orang pertama.



Saat saya ikut permainan, pesertanya masih sedikit (kurang dari 10). Setelah beberapa kali mencoba, program saya mendapatkan lebih dari 11.000 poin dan menempati posisi pertama dengan selisih yang besar.



Tetapi karena solusinya sendiri cukup sepele, saya menyadari bahwa saya tidak akan bertahan lama di tempat pertama, jadi saya mulai berpikir tentang bagaimana meningkatkan program.



Pertama, saya melihat apa yang paling memengaruhi kecepatan kerja, ternyata 99% waktunya ditempati oleh permintaan ke server. Setiap permintaan membutuhkan waktu sekitar 110-120ms. Oleh karena itu, ada 3 opsi utama untuk mempercepat program:

• Meningkatkan algoritma dan mengurangi jumlah permintaan ke server;
• Menggunakan permintaan asynchronous ke server;
• Mengurangi waktu satu permintaan.

Saya menolak opsi kedua, karena itu akan melampaui kondisi masalah dan API sinkron asli.



Ada beberapa cara untuk mengurangi jumlah permintaan ke server, tetapi semuanya hanya memberikan sedikit peningkatan (total beberapa puluh persen).



Oleh karena itu, saya mulai memikirkan cara mengurangi waktu untuk satu permintaan. Saya melihat di mana server game diterapkan, ternyata di AWS di Dublin (ping ke Dublin dari kota saya> 100ms). Awalnya saya ingin menyewa server di pusat data ini dan menjalankan program langsung dari rak berikutnya. Tetapi karena saya memiliki server gratis di Jerman, saya pertama kali memutuskan untuk menjalankan program dari sana.



Saya menginstal DE, VNC, Firefox, meluncurkan program - dan ping yang lebih rendah segera meningkatkan jumlah poin yang diperoleh sebanyak 2 kali lipat. Dan karena jarak dari yang lain sangat besar, maka saya memutuskan untuk tidak meningkatkan hasil lebih jauh.



Inilah sebuah cerita.

Kesalahan umum peserta

Sebagai penutup, saya akan membagikan beberapa kesalahan umum yang membuat peserta tidak mendapatkan lebih banyak poin:

• Perulangan tak berujung pada daftar yang sama dari bug yang sudah diperbaiki. Jika algoritme tidak mengingat bug yang telah diperbaiki dan memperbaikinya beberapa kali, waktu akan terbuang percuma;
• Kesalahan dalam loop dengan pemilihan langkah pemutaran untuk bug. Akibatnya, siklus menjadi tak berujung. Banyak kontributor menggunakan batas 100 karakter saat mencari langkah pemutaran ulang, meskipun panjang baris maksimum untuk bug yang diputar ulang adalah 10 karakter;
• Tidak semua peserta mencoba menjalankan algoritme mereka beberapa kali, dan jika Anda menjalankan algoritme yang sama 2-3 kali, Anda bisa mendapatkan lebih banyak poin karena distribusi bug yang berbeda dan urutan lain untuk mereproduksi bug.

Saya akan dengan senang hati menjawab pertanyaan tentang game dan melihat opsi Anda untuk menyelesaikan level ketujuh.