Geekly articles weekly

Frontend, algoritme, dan possum Frederick. Kami menganalisis tugas-tugas dari kontes Yandex

Dengan posting ini, kami menyelesaikan serangkaian publikasi tentang kontes Yandex.Blitz pada tahun 2018. Kami berharap Anda memiliki kesempatan untuk berpartisipasi atau setidaknya melihat jenis tugas apa yang kami usulkan dekat dengan produksi. Kontes terakhir dikhususkan untuk penggunaan algoritma di frontend. Hari ini kami menerbitkan analisis terperinci dari 12 masalah: 6 masalah pertama diusulkan dalam babak kualifikasi, dan masalah 7-12 di final. Kami mencoba menjelaskan bagaimana kondisi terbentuk, keterampilan apa yang kami perhatikan. Terima kasih kepada semua peserta atas minat mereka!



Tugas 1


Tugas pertama adalah melakukan pemanasan, selama 20 menit, dan kami memutuskan untuk membuat kondisinya sehingga mudah diselesaikan dengan bantuan ekspresi reguler.

Semua opsi untuk tugas dikonstruksi dengan cara yang sama - ada pengelompokan ke poin, yang masing-masing dapat diwakili oleh grup dalam ekspresi reguler akhir.

Pertimbangkan salah satu opsi: Kantor Pos.

Ketentuan


Di planet Jopan-14-53, penduduk setempat ingin mengirim surat satu sama lain, tetapi robot merpati yang seharusnya mengirimkannya bingung di alamat. Anda harus mengajari mereka untuk mengurai surat dan memeriksa validitasnya.

Struktur bagian dasar dari alamat terdiri dari wilayah, kotamadya, nama dan nama keluarga penerima. Kotamadya dapat dibagi menjadi kabupaten dan kantor pos. Semua bagian dipisahkan oleh koma.

Nama-nama daerah, kota dan kabupaten adalah kata-kata, huruf pertama di setiap kata besar, sisanya kecil. Nama dua kata dimungkinkan, dipisahkan oleh spasi atau tanda minus. Dalam setiap kata dari tiga hingga delapan huruf AZ.

Penduduk memiliki 6 jari di tangan mereka, dalam kehidupan sehari-hari sistem duodecimal. Angka 0–9 digunakan sebagaimana adanya, dan 10 dan 11 ditunjukkan oleh tanda ~ dan ≈ .

Nomor kantor pos dalam komposisi memiliki 3 digit berturut-turut, atau 4 dibagi menjadi 2 kelompok dengan 2 digit dengan tanda minus. Contoh: 300 , 44-99 .

Kadang-kadang penduduk mengirim surat ke kota atas permintaan. Dalam hal ini, tidak ada alamat: hanya kotamadya dan nama penerima.

Itu lucu, tetapi orang-orang di planet ini hanya disebut enam nama dan sembilan nama keluarga. Nama: Shob, Ryob, Mob, Xiang, Ryan, Mans. Nama keluarga: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Penghuni planet ini sama sekali bukan pemimpi.

Parsing


Struktur bagian dasar dari alamat terdiri dari wilayah, kotamadya, nama dan nama keluarga penerima. Kotamadya dapat dibagi menjadi kabupaten dan kantor pos. Semua bagian dipisahkan oleh koma.

Dari paragraf pertama kita belajar bagaimana menunjukkan wilayah, kotamadya, distrik, kantor pos, nama dan nama keluarga, dan dalam urutan apa mereka harus mengikuti garis yang diuji.

Nama-nama daerah, kota dan kabupaten adalah kata-kata, huruf pertama di setiap kata besar, sisanya kecil. Nama dua kata dimungkinkan, dipisahkan oleh spasi atau tanda minus. Dalam setiap kata dari tiga hingga delapan huruf AZ.

Dari paragraf ini jelas bahwa kelompok tersebut sesuai dengan kata-kata ([-][-]{2,7}) . Dan namanya, masing-masing, ([-][-]{2,7}(?:[- ][-][-]{2,7})) .

Penduduk memiliki 6 jari di tangan mereka, dalam kehidupan sehari-hari sistem duodecimal. Angka 0–9 digunakan sebagaimana adanya, dan 10 dan 11 ditunjukkan oleh tanda ~ dan ≈ .

Di sini kita belajar bahwa tidak cukup menggunakan \d untuk angka - Anda perlu menggunakan [0-9~≈] .

Nomor kantor pos dalam komposisi memiliki 3 digit berturut-turut, atau 4 dibagi menjadi 2 kelompok dengan 2 digit dengan tanda minus. Contoh: 300 , 44-99 .

Dengan demikian, grup tersebut sesuai dengan nomor kantor pos ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .

Kadang-kadang penduduk mengirim surat ke kota atas permintaan. Dalam hal ini, tidak ada alamat: hanya kotamadya dan nama penerima.

Kami memahami, mengingat, dan mempertimbangkan dalam pertemuan fungsi akhir sehingga kabupaten dan kantor pos mungkin tidak hadir secara bersamaan.

Itu lucu, tetapi orang-orang di planet ini hanya disebut enam nama dan sembilan nama keluarga. Nama: Shob, Ryob, Mob, Xiang, Ryan, Mans. Nama keluarga: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Penghuni planet ini sama sekali bukan pemimpi.

Ini adalah bagian terakhir dari kondisi. Di sini kami membutuhkan grup sederhana lain (||||||||) (|||||) atau rekan yang lebih pendek ([][]|[]) ([C]|[]||) .

Untuk mempermudah, kami menyimpan grup ke dalam variabel dan menggunakannya dalam ekspresi reguler yang dihasilkan.

 const w = '[-][-]{2,7}'; // word const d = '[0-9~≈]'; // digit const name = `(?:${w}(?:[- ]${w})?)`; const number = `(?:${d}{3}|${d}{2}-${d}{2})`; const person = '(?:[][]|[]) (?:|||||)'; // , , (,  , )?  const re = new RegExp(`^(${name}),\\s*(${name}),\\s*(?:(${name}),\\s*(${number}),\\s*)?(${person})$`); module.exports = function(str) { //      if (typeof str !== 'string') return null; const res = str.match(re); //   -   if (!res) return null; //    //    ,     return res.slice(1); };

Tugas 2. Kode di mana ada kesalahan


Ketentuan


Pada siang hari, tim pengembangan membuat beberapa fitur baru. Tetapi dalam mempersiapkan rilis, menggabungkan konflik terjadi, dan setelah mereka diselesaikan, tata letak berpisah. Sangat mendesak untuk menghilangkan kesalahan karena jumlah minimum koreksi dalam kode sehingga rilis punya waktu untuk mulai berproduksi.

Anda diberikan halaman HTML dengan gaya rusak dan format PNG (dengan hasil yang diharapkan). Anda perlu memperbaiki kesalahan sehingga hasilnya saat melihat di Chrome menjadi sama dengan tangkapan layar asli. Kirim halaman yang diperbaiki sebagai solusi untuk masalah tersebut.

Halaman HTML dengan gaya rusak. Tata letak:



Parsing


Dalam tugas ini, kami mencoba meniru situasi yang sering dihadapi pengembang Yandex: di basis kode besar, temukan beberapa baris kode sederhana, koreksi yang mengarah ke hasil yang diinginkan. Artinya, kesulitannya bukan dalam menulis kode, tetapi dalam memahami di mana tepatnya untuk menulisnya (atau menghapusnya).

Kami mengambil kode mesin pencari yang sebenarnya dan membuat beberapa koreksi yang merusak tata letak. Para peserta kompetisi memiliki kurang dari satu jam untuk menangani sekitar 250 kilobyte tata letak dan membawa kode ke keadaan yang sesuai dengan tata letak.

Jelas bahwa batas waktu untuk kompetisi tidak memungkinkan membaca seluruh kode, sehingga para peserta harus menggunakan alat untuk pengembang di browser.

Untuk memperbaiki salah satu dari empat opsi tugas, perubahan berikut cukup:

  diff --git a / blitz.html b / blitz.html 
  indeks 36b9af8..1e30545 100644 
  --- a / blitz.html 
  +++ b / blitz.html 
  @@ -531.10 +531.6 @@ 
  iframe [src $ = 'ext-analytics.html'] { 
  tinggi: otomatis; 
  } 
  -.search2__button .suggest2-form__button: nth-child (1) { 
  - latar belakang: # ff0! important; 
  -} 
  - 
  / * ../../blocks-desktop/input/__control/input__control.styl end * / 
  / * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css dimulai * / 
  / * Diposisikan relatif terhadap input__box. 
  @@ -744.10 +740.6 @@ 
  iframe [src $ = 'ext-analytics.html'] { 
  background-clip: kotak-padding; 
  } 
  .input_theme_websearch .input__clear { 
  background-image: url ("/ static / web4 / node_modules / islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"); 
  ukuran latar: 16px; 
  @@ -857.6 +849.7 @@ 
  iframe [src $ = 'ext-analytics.html'] { 
  warna latar: # f2cf46; 
  } 
  .websearch-button__text: before { 
  + posisi: absolut; 
  atas: -6px; 
  kanan: -9px; 
  lebar: 0; 
  @@ -866.8 +859.6 @@ 
  iframe [src $ = 'ext-analytics.html'] { 
  gaya perbatasan: solid; 
  border-color: rgba (255.219,76,0); 
  border-left-color: inherit; 
  - posisi: relatif; 
  - z-index: -1000; 
  } 
  / * ../../blocks-deskpad/websearch-button/websearch-button.styl end * / 
  @@ -1349.6 +1340.7 @@ 
  iframe [src $ = 'ext-analytics.html'] { 
  ukuran font: 14px; 
  garis-tinggi: 40px; 
  posisi: relatif; 
  + display: inline-block; 
  tinggi: otomatis; 
  bantalan: 0; 
  vertical-align: tengah;


Tugas 3. Gambar dengan variabilitas yang diberikan


Ketentuan




Perancang mendesain logo. Ini perlu digunakan dalam berbagai kondisi. Untuk membuatnya senyaman mungkin, buat dengan satu elemen HTML di CSS murni.

Anda tidak dapat menggunakan gambar (bahkan melalui data: uri).

Parsing


Karena tugasnya adalah menggunakan hanya satu div, yang kita miliki hanyalah div itu sendiri dan elemen pseudo :: before dan :: after.

Gambar pada tata letak, untungnya, hanya terdiri dari tiga area dengan warna berbeda. Kami membuat latar belakang kami sendiri untuk setiap elemen yang dapat diakses, dengan benar posisi dan sudut bulat. Ada bayangan di area abu-abu tata letak - kami membuatnya dengan gradien.

 div { background: #0C0C0C; border-radius: 10px; position: relative; } div:before { border-radius: 9px 9px 0 0; position: absolute; width: 100%; height: 50%; background: #F8E34B; content: ''; } div:after { content: ''; background: linear-gradient(178deg, #C8C8C8 0px , transparent 7px), #EEEDEF; position: absolute; width: 50%; height: 50%; bottom: 0; border-radius: 0 0 0 9px; }

Tugas 4


Ketentuan


Petya bekerja sebagai penata huruf senior di koran Moscow Frontender. Untuk tata letak surat kabar Petya menggunakan tumpukan teknologi web. Tugas paling sulit yang dihadapi Petya adalah tata letak pos dalam artikel surat kabar: kolom surat kabar di setiap edisi memiliki lebar yang berbeda, dan pos tersebut memiliki font dan jumlah karakter yang berbeda.

Petya perlu memilih ukuran font sendiri untuk setiap heading sehingga ukuran font maksimum, tetapi pada saat yang sama semua teks heading cocok dengan ruang yang disediakan untuknya.

Bantu Petya: terapkan fungsi calcFontSize, yang memungkinkan Anda memasukkan teks yang ditransfer ke dalam wadah sehingga pas ke seluruh wadah dan memiliki ukuran maksimum yang memungkinkan. Jika ini gagal, maka solusinya akan mengembalikan nol. Panjang jalur input maksimum adalah 100 karakter. String input tidak boleh kosong. Solusi Anda harus berisi seluruh kode fungsi dan tidak boleh menggunakan dependensi eksternal sehingga Petya dapat menyalinnya ke dalam proyeknya dan menyebutnya dalam kodenya.

Kami akan memeriksa seberapa optimal solusi Anda bekerja dan memperhalusnya jika menghasilkan terlalu banyak manipulasi DOM.

Parsing


Hal pertama yang harus dilakukan adalah mempelajari bagaimana menentukan apakah teks tersebut cocok dengan wadah, mengingat bahwa teks dalam wadah dapat mengambil beberapa baris. Cara termudah untuk melakukan ini adalah dengan menggunakan elemen.getBoundingClientRect () fungsi, yang memungkinkan Anda untuk mendapatkan dimensi elemen.

Anda dapat menggambar teks dengan elemen bentang terpisah di dalam wadah dan memeriksa apakah lebar atau tinggi elemen ini melebihi ukuran wadah. Jika ya, maka teks tidak sesuai dengan wadah.

Selanjutnya, periksa kondisi batas. Jika teks tidak masuk ke dalam wadah bahkan dengan ukuran font minimum, maka tidak dapat dimasukkan. Jika teks pecah dengan ukuran maksimum yang diizinkan, maks akan menjadi jawaban yang benar. Dalam kasus lain, ukuran font yang diinginkan adalah di suatu tempat dalam interval [min, maks].

Untuk menemukan solusi, Anda perlu memilah-milah seluruh celah ini dan menemukan nilai ukuran font di mana teks ditempatkan dalam wadah, tetapi jika Anda meningkatkannya dengan 1 –– itu akan berhenti cocok.

Anda dapat melakukan ini dengan loop sederhana untuk rentang [min, maks], tetapi solusinya akan melakukan banyak pemeriksaan dan menggambar ulang halaman - setidaknya satu untuk setiap nilai yang akan diperiksa dalam rentang. Kompleksitas algoritmik dari solusi semacam itu akan linear.

Untuk meminimalkan jumlah pemeriksaan dan mendapatkan solusi yang berfungsi untuk O (log n), Anda perlu menggunakan algoritma pencarian biner. Gagasan algoritma adalah bahwa pada setiap iterasi pencarian, rentang nilai dibagi menjadi dua bagian, dan pencarian berlanjut secara rekursif di setengah di mana solusi berada. Pencarian akan berakhir ketika rentang runtuh ke nilai tunggal. Baca lebih lanjut tentang algoritma pencarian biner di artikel Wikipedia .

Kami memeriksa kompleksitas algoritmik dari solusi menggunakan MutationObserver : kami menempatkannya di halaman dan menghitung berapa banyak mutasi DOM membuat keputusan dalam proses menemukan jawaban. Untuk beberapa pengujian, jumlah mutasi sangat terbatas dari atas sehingga hanya solusi yang didasarkan pada pencarian biner yang dapat melewati batasan ini.

Untuk mendapatkan skor penuh untuk tugas tersebut, perlu juga hati-hati memeriksa kondisi batas yang berbeda (pencocokan min dan maks, baris teks kosong pada input) dan menyediakan beberapa kondisi lingkungan di mana kode dijalankan (misalnya, diperbaiki dengan! Ukuran font penting di halaman CSS )

Tugas 5. Kesulitan dalam komunikasi


Di setiap opsi kualifikasi, ada tugas di mana halaman HTML dengan beberapa antarmuka ditawarkan sebagai input. Tugas-tugas memiliki legenda yang berbeda, tetapi mereka semua bermuara pada kenyataan bahwa perlu untuk mengekstrak beberapa data dari halaman dan, menggunakan data ini, entah bagaimana berinteraksi dengan antarmuka.

Mari kita menganalisis solusi untuk salah satu tugas dari seri ini, yang disebut "Kesulitan dalam komunikasi."

Ketentuan


Kuda Adolf suka berbicara dengan teman-teman di telepon. Sayangnya, ini jarang terjadi. Setiap kali Adolf ingin menelepon, butuh lebih dari satu jam untuk memanggil nomor teman. Ini karena sangat sulit baginya untuk menekan tombol yang tepat dengan kuku tebalnya.

Untungnya, ponsel Adolf mendukung JavaScript. Tolong tulis sebuah program yang memanggil teman-teman Adolf dengan mengklik pada keyboard. Semua nomor yang diperlukan dicatat dalam buku catatan. Kuda yang malang akan sangat berterima kasih padamu!

Parsing


Berikut adalah halaman yang ditawarkan sebagai input:



Bagian pertama dari solusi ini adalah mengambil data
Setiap digit nomor telepon diatur oleh gambar melalui gambar-latar belakang. Pada saat yang sama, selama verifikasi, angkanya diganti secara dinamis. Jika Anda membuka debugger di browser dan melihat pohon DOM halaman, Anda akan melihat bahwa setiap elemen DOM menggunakan kelas yang jelas:

 <div class="game"> <div class="target"> <div class="line"> <div class="symbol nine"></div> <div class="symbol eight"></div> <div class="symbol five"></div> <div class="symbol separator"></div> <div class="symbol four"></div> <div class="symbol one"></div> <div class="symbol two"></div> <div class="symbol separator"></div> </div> <!-- ... --> </div> <!-- ... --> </div>

Dalam hal ini, cukup membuat kamus, mengekstrak kelas CSS dan mengubahnya menjadi string dengan angka sesuai kamus, tidak termasuk pemisah (pemisah kelas CSS). Misalnya, seperti ini:

 const digits = document.querySelectorAll('.game .target .symbol:not(.separator)'); const dict = { 'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'eight': 8, 'nine': 9, 'zero': 0, }; const phoneNumber = Array.from(digits).reduce((res, elem) => { for (const className of elem.classList) { if (className in dict) { res.push(dict[className]); break; } } return res; }, []);

Hasilnya, kita mendapatkan array berikut: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].

Bagian kedua dari solusinya adalah berinteraksi dengan antarmuka
Pada tahap ini, kita sudah memiliki array dengan semua digit angka, dan kita perlu memahami tombol mana pada keyboard yang sesuai dengan digit mana. Jika kita melihat kode HTML, kita akan melihat bahwa tidak ada kelas petunjuk khusus yang menunjukkan angka pada keyboard:

 <div class="keys"> <div class="key"></div> <div class="key"></div> <!-- … --> </div>

Seseorang bisa secara manual membuat kamus lain dengan indeks, tetapi ada cara yang lebih sederhana. Jika Anda memperhatikan gaya pada inspektur web, Anda akan melihat bahwa angka pada tombol diatur melalui konten properti CSS untuk: before pseudo-element. Misalnya, untuk kunci "3", gaya terlihat seperti ini:

 .key:nth-child(3):before { content: '3'; }

Untuk mendapatkan nilai properti ini, kami menggunakan metode window.getComputedStyle:

 const keys = Array.from(document.querySelectorAll('.game .key')).reduce((res, elem) => { const key = window //  CSSStyleDeclaration  - .getComputedStyle(elem, ':before') //    .getPropertyValue('content') //     ,      .replace(/"/g, ''); res[key] = elem; return res; }, {});

Akibatnya, kita mendapatkan objek di mana teks kunci akan menjadi teks pada tombol (angka atau "panggilan"), dan nilainya akan menjadi simpul DOM.

Tetap hanya untuk mengambil nilai-nilai dari array pertama (phoneNumber), pergi melalui mereka dan klik pada tombol yang sesuai menggunakan kamus kunci kami:

 phoneNumber.push('call'); const call = () => { const event = new Event('click'); const next = phoneNumber.shift(); keys[next].dispatchEvent(event); if (phoneNumber.length) { setTimeout(call, 100); } } call();

Harap dicatat: sebelum melakukan panggilan, kami menambahkan nilai panggilan ke akhir array. Ini diperlukan oleh kondisi tugas, karena jika Anda menekan nomor dan tidak menekan "panggilan", solusi tidak akan lulus tes.

Fitur lainnya adalah penekanan tombol keyboard yang tidak sinkron. Jika interval waktu antara penekanan tombol saat panggilan kurang dari 50 ms, maka solusi ini juga tidak akan lulus tes. Fitur ini tidak dijelaskan secara eksplisit dalam kondisi masalah, dan kami mengharapkan peserta untuk mengetahuinya dengan membaca kode sumber halaman. Ngomong-ngomong, sedikit kejutan menunggu peserta dalam kode sumber. ;)

Tugas 6


Ketentuan


Fedor Rakushkin mengelola sistem manajemen tugas di perusahaannya. Server tempat sistem berada gagal (dan Fedor tidak melakukan backup).

Di memori server, masih ada cache struktur yang menggambarkan tugas, pelaksana, dan pengamat, serta hubungan antara struktur ini. Selain itu, tautan cache ke struktur terakhir yang diubah dipertahankan.

Bantu Fedor menulis fungsi yang dapat memulihkan semua koneksi yang mungkin antara tugas dan pengguna dan menyimpannya ke dalam dokumen dalam format Penurunan harga, dari mana Fedor kemudian akan mengembalikan database ke server baru.

Dokumen penurunan harga harus memiliki format berikut:

 ##  - %  1%,  %username1%, : %username2% - %  2%,  %username1%, : %username2%, %username3% - %  3%,  %username1% //     - %  4%, : %username1%, %username2% //     - %  5% //       - %  6%, : %username1% - %  1%,  %username1% //  - %  2% - %  3%, : %username1% ##  - %username1% * %  1% // ,    * %  2% * %  3% * %  1% - %username2% * %  3%

Daftar tugas, daftar pelaksana dalam tugas, daftar pengamat dalam tugas, daftar pengguna dan daftar tugas yang dilakukan pengguna harus diurutkan secara leksikografis.

Deskripsi struktur dalam cache


Pengguna disimpan dalam cache sebagai struktur tipe `Pengguna`:

 type User = { login: string; tasks: Task[]; spectating: Task[]; };

Tugas disimpan dalam cache sebagai struktur tipe `Tugas`:

 type Task = { title: string; assignee: User; spectators: User[]; subtasks: Task[]; parent: Task | null; };

Template Solusi


Solusi Anda harus mengandung modul CommonJS yang mengekspor fungsi yang sesuai dengan tanda tangan berikut:

 /** * @param {User|Task} data -     , *        (User  Task) * @return {string} */ module.exports = function (data) { //   return '…'; }

Contohnya


 //    const User1 = { type: 'user', login: 'fedor', tasks: [], spectating: [] }; const User2 = { type: 'user', login: 'arkady', tasks: [], spectating: [] }; //    const Task1 = { type: 'task', title: 'Do something', assignee: null, spectators: [], subtasks: [], parent: null }; const Task2 = { type: 'task', title: 'Something else', assignee: null, spectators: [], subtasks: [], parent: null }; const Task3 = { type: 'task', title: 'Sub task', assignee: null, spectators: [], subtasks: [], parent: null }; //    : //      Task1.assignee = User1; User1.tasks.push(Task1); // ...    —  Task1.spectators.push(User2); User2.spectating.push(Task1); //      , //       Task2.spectators.push(User1); User1.spectating.push(Task2); //      Task3.parent = Task2; Task2.subtasks.push(Task3); // ,     —  3 const lastEdited = Task3;

Jika Anda menampilkan tautan ke `lastEdited`, Anda mendapatkan struktur berikut:

 { type: 'task', title: 'Sub task', assignee: null, spectators: [], subtasks: [], parent: { type: 'task', title: 'Something else', assignee: null, spectators: [ { type: 'user', login: 'fedor', tasks: [ { type: 'task', title: 'Do something', assignee: [Circular], spectators: [ { type: 'user', login: 'arkady', tasks: [], spectating: [ [Circular] ] } ], subtasks: [], parent: null } ], spectating: [ [Circular] ] } ], subtasks: [ [Circular] ], parent: null } }

Markdown , :

 ##  - Do something,  fedor, : arkady - Something else, : fedor - Sub task ##  - arkady - fedor * Do something


, .

, , . , :

 /** *  ,     * @param {{ref: object, visited: ?boolean}} ctx * @param {object} handlers —     */ function traverse(ctx, handlers) { //    ,  ctx.ref , — ,     task.parent if (!ctx.ref) { return; } //   ,    ,       const visited = ctx.visited || new Set(); if (visited.has(ctx.ref)) { return; } visited.add(ctx.ref); //       handlers[ctx.ref.type](ctx.ref, goDeeper); //  ,       function goDeeper(subrefs) { //       for (const subref of [].concat(subrefs)) { traverse({ visited, ref: subref }, handlers); } } } //      const users = []; const tasks = []; // ref   —     traverse({ ref }, { user(user, deeper) { users.push(user); deeper(user.tasks); // to task.assignee deeper(user.spectating); // to task.spectators }, task(task, deeper) { tasks.push(task); deeper(task.assignee); // to user.tasks deeper(task.spectators); // to user.spectating deeper(task.parent); // to task.subtasks deeper(task.subtasks); // to task.parent } );

. , , …

 users.sort((u1, u2) => u1.login < u2.login ? -1 : (u1.login > u2.login ? 1 : 0)); tasks.sort((t1, t2) => t1.title < t2.title ? -1 : (t1.title > t2.title ? 1 : 0));

… — :

 //    const taskLine = t => `${ t.title }${ t.assignee ? `,  ${t.assignee.login}` : '' }${ t.spectators.length ? `, : ${t.spectators.map(u => u.login).join(', ')}` : '' }`; function renderTasks (parent = null, indent = 0) { return tasks .filter(t => t.parent === parent) .map(t => [ '\n', ' '.repeat(indent), //  '- ', taskLine(t), //    t.subtasks.length ? printTasks(t, indent + 2) : '' //   ].join('')) .join(''); } function renderUsers () { return ${users.map(u => `\n- ${u.login}${ u.tasks.map(t => `\n * ${t.title}`).join('') }`).join('')} } const result = ` ##  ${renderTasks()} ##  ${renderUsers()} `.trim();

7.



, .. :



, . , «».



.



, . , . . . HTML CSS. JavaScript .

, , - . , .


HTML/CSS, , , - .

CSS, , — float, . float , , .

— , . ( jsfiddle.net .)

— padding-top, margin-top ( ). DOM- (). ( .)

8.



HTML-. , . , . .

(pixel perfect). .

. .

, , . , . , : - , , .

, . , , .


, — . — CSS- border ( ), background ( ) box-shadow ( ).

- « » ( ) . , , .

— , 70 70 . : , . CSS- , CSS- , .



— 210 210 , 70 70 .



9.



— , -. JavaScript, . , .

: . , , . .

, — . — . , JavaScript API . , -, , . 10 , HTTP- .

— . , , , .

-.

:
— API npm- @yandex-blitz/phone.
— API .
— -, : task.js .
— - runkit- .

-, .


— GET- return connect.

: - . , , . .

, : , . :

 const writeQueue = []; const processQueue = () => { if (writeQueue.length) { const fn = writeQueue.shift(); fn().then(() => { processQueue(); }); } }

, « ».

 const writeQueue = []; let isWriteInProgress = false; const processQueue = () => { if (isWriteInProgress) { return; } if (writeQueue.length) { isWriteInProgress = true; const fn = writeQueue.shift(); fn().then(() => { isWriteInProgress = false; processQueue(); }); } }

, POST- . , , .

 app.post("/speeddial/:digit/:phonenumber", (req, res) => { writeQueue.push(makeWriteJob(phone, req, res)); processQueue(); });

:

 const express = require('express'); const { BEEP_CODES } = require('@yandex-blitz/phone'); const writeQueue = []; let isWriteInProgress = false; const processQueue = () => { if (isWriteInProgress) { return; } if (writeQueue.length) { isWriteInProgress = true; const fn = writeQueue.shift(); fn().then(() => { isWriteInProgress = false; processQueue(); }); } } const makeWriteJob = (phone, req, res) => { return () => { return phone.getData() .then(value => { const speeddialDict = JSON.parse(value); speeddialDict[req.params.digit] = Number(req.params.phonenumber); return phone .setData(JSON.stringify(speeddialDict)) .then(() => phone.beep(BEEP_CODES.SUCCESS)) .then(() => { res.sendStatus(200); }) }) .catch(e => { phone.beep(BEEP_CODES.ERROR).then(() => { res.sendStatus(500); }) }) } }; const createApp = ({ phone }) => { const app = express(); //   ,   « »   digit app.get("/speeddial/:digit", (req, res) => { phone.getData().then(value => { const speeddialDict = JSON.parse(value); return phone.connect() .then(async () => { await phone.dial(speeddialDict[req.params.digit]); res.sendStatus(200); }, async() => { await phone.beep(BEEP_CODES.FATAL); res.sendStatus(500); }); }).catch(async (e) => { await phone.beep(BEEP_CODES.ERROR); res.sendStatus(500); }); }); //   « »   digit  phonenumber app.post("/speeddial/:digit/:phonenumber", (req, res) => { writeQueue.push(makeWriteJob(phone, req, res)); processQueue(); }); return app; }; exports.createApp = createApp;

10.



. , «».

:
— , .
— , , .
— , , .
— , : ← ↓ ↑ →.
— — , .

, , , , .

.

.

HTML- ( ).

, window.onMazeReady(). . 2 , .

CSS- map.

click CSS-:
— — control_direction_left,
— — control_direction_down,
— — control_direction_up,
— — control_direction_right.

CSS- :

 background: radial-gradient(circle at 5px 5px, #eee, #000);

25 , 500 . Sebagai contoh:









window.map String. :
# —
. —
o —
x —

, , , — . .

,

 window.map = ` ##### #o#x# #.#.# #...# ##### `;

:



:

 <!DOCTYPE html> <html lang=ru/> <head> <style> body { padding: 100px 0 0 100px; } .game-box { perspective: 500px; perspective-origin: center; } .map { transform-style: preserve-3d; } .map__tilt_left { transform: rotateY(-25deg); } .map__tilt_down { transform: rotateX(-25deg); } .map__tilt_up { transform: rotateX(25deg); } .map__tilt_right { transform: rotateY(25deg); } </style> <title></title> </head> <body> <div class="game-box"> <div class="map"> <!--  --> </div> </div> <script> // JavaScript </script> </body> </html>


(HTML, CSS, JS). , «» .

. ( ), , .

, , .

, :

 <table class="map map__tilt_none"> <!-- ... --> <tr> <td class="map__cell map__cell_content_wall"></td> <td class="map__cell map__cell_content_empty"></td> <td class="map__cell map__cell_content_ball"></td> <td class="map__cell map__cell_content_exit"></td> <td class="map__cell map__cell_content_wall"></td> </tr> <!-- ... --> </table>

:

 .map { border: 0; border-spacing: 0; border-collapse: separate; background-color: #ccc; transform-style: preserve-3d; } .map__cell { box-sizing: border-box; border: 1px solid; border-color: #9b9b9b #575757 #575757 #9b9b9b; width: 30px; height: 30px; text-align: center; vertical-align: middle; font-size: 0; line-height: 0; background-color: #707070; } .map__cell_content_ball:after { content: ''; display: inline-block; width: 20px; height: 20px; border-radius: 50%; background: radial-gradient(circle at 5px 5px, #eee, #000); } .map__cell_content_wall { border-width: 4px; } .map__cell_content_exit { background-color: #000; border: 5px solid; border-color: #222 #555 #555 #222; }

— — .

, .

«» , . , . , :

 window.map = ` ####### ##.#### #..o..# ##x.#.# ###...# ####### `;

:

 function convertMap(mapInput) { return mapInput .trim() .split(/\n\s*/) .map(row => row.split('')); }

, HTML :

 const CELL_CONTENT = { '#': 'wall', 'o': 'ball', '.': 'empty', 'x': 'exit' }; function buildGameBoxHtml(map) { return ` <div class="game-box"> <table class="map map__tilt_none"> ${map.map(row => ` <tr> ${row.map(cell => ` <td class="map__cell map__cell_content_${CELL_CONTENT[cell]}"></td> `).join('')} </tr> `).join('')} </table> <!--      --> <div class="controls"> <button class="control control_direction_left">←</button> <button class="control control_direction_down">↓</button> <button class="control control_direction_up">↑</button> <button class="control control_direction_right">→</button> </div> </div> `; }

, :

 let gameBox = document.querySelector('.game-box'); let map = gameBox.querySelector('.map'); //           gameBox.addEventListener('click', ({ target }) => { //      if (!target.classList.contains('control')) { return; }; //      - const direction = target.className.match(/\bcontrol_direction_(\w+)/)[1]; //  ,   - map.className = map.className.replace(/\bmap__tilt_\w+/, `map__tilt_${direction}`); //  ,     let ball = map.querySelector('.map__cell_content_ball'); //       let nextBall = getNextCell(map, ball, direction); //      ball.classList.remove('map__cell_content_ball'); ball.classList.add('map__cell_content_empty'); //     ,            while ( !nextBall.classList.contains('map__cell_content_wall') && !ball.classList.contains('map__cell_content_exit') ) { ball = nextBall; nextBall = getNextCell(map, ball, direction); } //      ball.classList.remove('map__cell_content_empty'); ball.classList.add('map__cell_content_ball'); }); const DIRECTIONS = { 'left': [-1, 0], 'up': [0, -1], 'down': [0, 1], 'right': [1, 0] }; //  DOM API ,        function getNextCell(map, cell, direction) { const directionDiff = DIRECTIONS[direction]; return map.rows[cell.parentNode.rowIndex + directionDiff[1]].cells[cell.cellIndex + directionDiff[0]]; }

— callback : window.onMazeReady(). .

, . , , . HTML, CSS JS — , .

, :
— ,
— , ,
— , ,
— , ,
— , ,
— , .

, :
— ,
— ,
— DOM API ,
— .

11.



, , . , . , .

, . , . . .js, :

 module.exports = function solveCaptcha(captcha) { // ... }

. .
:

 captcha = ' TRABWARH THSCAHAW WWBSCWAA CACACHCR '

:
— S — (sign)
— T — (tree)
— R — (road)
—…

:

 [ 'TRABWARH THSCAHAW' , 'WWBSCWAA CACACHCR' ]

:
— 1 10.
— .
— , .
— ( ).
— , , .
— , .

Cut the cake codewars.com.


, 10. , . , . :
— ;
— , .

, . : «… , ». . .



. . , . .

. «», .

 module.exports = function solveCaptcha(captcha) { const n = //     const sizes = getAllSizes(); //      // board —    //   —   ,   //  ,    const board = []; //    function placeNext(remains) { //    ... if (remains === 0) { // ... ,   ,   return board; } else { // ... //         // ,     const pos = getEmptyPos(); //        for (let i = 0; i < sizes.length; i++) { //  ,    const size = sizes[i]; //          //     (      //     !== 1),  null const layer = getLayer(pos, size); //     if (layer) { //     board.push(layer); //     const res = placeNext(remains - 1); //  ,  if (res) return res; //      //    board.pop(); } } } } //   return placeNext(n); }

12. -



X . VCS , .

, -. — , .

, . , , . .

, . ( ) .

.



. — 1000, - — 20.

:

 type PullRequest = { /** *     ( ) *   N: 1 <= N <= 1000 */ files: string[], /** *     VCS */ id: string, /** * Unix-timestamp  - */ created: number, }

(created) (id) – .



CommonJS- :

 /** * @param {PullRequest[]} pullRequests  PR,     * @returns {string[]}      */ module.exports = function (pullRequests) { //   }



NodeJS v9.11.2. .



 function mergeAllPRs(prs) { /* solution */ } console.assert( mergeAllPRs([ { id: '#1', created: 1536077100, files: ['.gitignore', 'README.md'] }, { id: '#2', created: 1536077700, files: ['index.js', 'package-lock.json', 'package.json'] }, { id: '#3', created: 1536077800, files: ['.pnp.js', 'yarn.lock'] } ]) .join(',') === [ "#1", "#2", "#3" ].join(',') ); console.assert( mergeAllPRs([ { id: '#1', created: 1536074100, files: ['README.md'] }, { id: '#2', created: 1536078700, files: ['README.md'] }, { id: '#3', created: 1536097800, files: ['README.md'] } ]).join(',') === [ "#1" ].join(',') ); console.assert( mergeAllPRs([ { id: '#1', created: 1536077100, files: ['.gitignore', 'README.md'] }, { id: '#2', created: 1536077700, files: ['index.js', 'package-lock.json', 'package.json'] }, { id: '#3', created: 1536077800, files: ['.pnp.js', 'package-lock.json', 'yarn.lock'] }, { id: '#4', created: 1536077900, files: ['index.spec.js', 'index.spec.ts', 'index.ts'] } ]) .join(',') === [ "#1", "#2", "#4" ].join(',') );


— , .

, « » (, ).

, , , . ( some includes). — O(n 2 ).

, , ( . ). — O(n).

:

 function conflicts(a, b) {  let i = 0;  let j = 0;  while (i < a.length && j < b.length) {      if (a[i] === b[j]) {          return true;      } else if (a[i] > b[j]) {          j++;      } else {          i++;      }  }  return false; } function mergeAllPrs (input) {  let i = 0;  const mergedFiles = [];  const mergedPrs = [];  while (i < input.length) {      const pr = input[i];      if (!conflicts(mergedFiles, pr.files)) {          mergedPrs.push(pr);          mergedFiles.push(...pr.files);      }      i++;  }  return mergedPrs.map(x => x.id); };

, , . , :

 console.assert(  mergeAllPrs([      {          "id": "1",          "created": 1538179200,          "files": [ "a", "b", "c", "d" ]      },      {          "id": "2",          "created": 1538189200,          "files": [ "a", "x" ]      },      {          "id": "3",          "created": 1538199200,          "files": [ "b", "g" ]      },      {          "id": "4",          "created": 1538209200,          "files": [ "c",  "f" ]      },      {          "id": "5",          "created": 1538219200,          "files": [ "d", "w" ]      }  ])  .join(',') === ['2', '3', '4', '5'].join(',') );

, ( , ).

: «» -, «» — ( ). ( ).

:

 [  {      "id": "#1",      "created": 1536077100,      "files": [ ".gitignore", "README.md" ]  },  {      "id": "#2",      "created": 1536077700,      "files": [ "index.js", "package-lock.json", "package.json" ]  },  {      "id": "#3",      "created": 1536077800,      "files": [ "index.js" ]  } ]

#2 #3 , ["#1", "#2"]. .



, .

, — O(n 2 ), . .

, , . , , .

conflicts , . :

 const conflictMatrix = new Uint8Array(prs.length ** 2); const prToIndex = new WeakMap(); for (let i = 0; i < prs.length; i++) {  const pr1 = prs[i];  prToIndex.set(pr1, i);  conflictMatrix[i * prs.length + i] = 0;  for (let j = i + 1; j < prs.length; j++) {      const pr2 = prs[j];      conflictMatrix[i * prs.length + j] = conflictMatrix[j * prs.length + i] = conflicts(pr1.files, pr2.files);  } } /** *     PR (    ) */ function doPRsConflict(pr1, pr2) {  const i = prToIndex.get(pr1);  const j = prToIndex.get(pr2);  return conflictMatrix[i * prs.length + j] === 1; }

«» , . ( ) , . , , - .

, , .

 /** *     prsSet,           */ function getNonConflictingPRs (prsSet, mergedPrs) {  const result = [];  const prsToTest = [...prsSet, ...mergedPrs];  prsSet.forEach((pr) => {      if (!conflictsWithSomePR(pr, prsToTest)) {          result.push(pr);      }  });  return result; }

.

 const fullSearch = (prsSet, mergedPrs = [], mergedFilesCount = 0) => {  hits++;  //  ,            //   ,      const safeToMergePRs = getNonConflictingPRs(prsSet, mergedPrs);  mergedPrs = mergedPrs.concat(safeToMergePRs);  safeToMergePRs.forEach((pr) => {      prsSet.delete(pr);      mergedFilesCount += pr.files.length;  });  const pr = prsSet.values().next().value; // ...

.

Source: https://habr.com/ru/post/id430560/

More articles:


All Articles