フロントエンド、アルゴリズム、ポッサムフレデリック。 Yandexコンテストのタスクを分析します

この投稿では、2018年にYandex.Blitzコンテストに関する一連の出版物を完成させています。 参加していただくか、少なくとも制作の近くでどのようなタスクを提案するかをご覧ください。 最後のコンテストは、フロントエンドでのアルゴリズムの使用に捧げられました。 本日、12の問題の詳細な分析を公開します。最初の6つは予選で提案され、問題7〜12は決勝で提案されました。 条件がどのように形成され、どのスキルに注意を払ったかを説明しようとしました。 すべての参加者の関心に感謝します！

タスク1

最初のタスクは20分間のウォームアップでしたが、正規表現を使用して簡単に解決できるように、その状態を作ることにしました。

割り当てのすべてのオプションは同様の方法で構築されます-ポイントに分類され、各ポイントは最終的な正規表現のグループで表すことができます。

オプションの1つ、郵便局を検討してください。

状態

惑星ジョパン-14-53では、地元の人々はお互いに手紙を送りたいと思っていますが、それらを届ける鳩ロボットは住所が混同しています。 あなたは彼らに手紙を解析し、有効性をチェックするように教えなければなりません。

住所の基本部分の構造は、受取人の地域、市区町村、名前、姓で構成されます。 自治体は郡と郵便局に分けることができます。 すべての部分はコンマで区切られます。

地域、市町村、地区の名前は単語で、各単語の最初の文字は大きく、残りは小さいです。 スペースまたはマイナス記号で区切られた2語の名前が可能です。 3〜8文字の各単語A〜Z。

住民は6本の指を手に持っています。日常生活では十二指腸系です。 番号0〜9はそのまま使用され、10と11は記号~と≈示されます。

構図内の郵便局番号には、3桁の行または4桁のマイナス記号付き2桁の2つのグループに分かれています。 例： 44-99 。

時々、住民は要求に応じて自治体に手紙を送る。 この場合、住所はありません。自治体と宛先の名前のみです。

それは面白いですが、地球上の人々は6名と9名の姓のみと呼ばれています。 名前：Shob、Ryob、Mob、Xiang、Ryan、Mans。 姓：翔、,、,、夏、ia、馬、Ma、龍、,。 この惑星の住民は夢想家ではありません。

解析

住所の基本部分の構造は、受取人の地域、市区町村、名前、姓で構成されます。 自治体は郡と郵便局に分けることができます。 すべての部分はコンマで区切られます。

最初の段落から、地域、市町村、地区、郵便局、名前と姓を示す方法、およびテストされた行で従うべき順序を学びます。

地域、市町村、地区の名前は単語で、各単語の最初の文字は大きく、残りは小さいです。 スペースまたはマイナス記号で区切られた2語の名前が可能です。 3〜8文字の各単語A〜Z。

この段落から、グループが単語([-][-]{2,7})対応していることが明らかです。 そして、それぞれの名前([-][-]{2,7}(?:[- ][-][-]{2,7})) 。

住民は6本の指を手に持っています。日常生活では十二指腸系です。 番号0〜9はそのまま使用され、10と11は記号~と≈示されます。

ここで、数字に\dを使用するだけでは不十分であることがわかります- [0-9~≈]を使用する必要があります。

構図内の郵便局番号には、3桁の行または4桁のマイナス記号付き2桁の2つのグループに分かれています。 例： 44-99 。

したがって、グループは郵便局番号([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2})ます。

時々、住民は要求に応じて自治体に手紙を送る。 この場合、住所はありません。自治体と宛先の名前のみです。

私たちは、地区と郵便局が同時に欠席する可能性があることを最終機能の集会で理解し、覚えており、考慮します。

それは面白いですが、地球上の人々は6名と9名の姓のみと呼ばれています。 名前：Shob、Ryob、Mob、Xiang、Ryan、Mans。 姓：翔、,、,、夏、ia、馬、Ma、龍、,。 この惑星の住民は夢想家ではありません。

これは条件の最後の部分です。 ここでは、もう1つの単純なグループ(||||||||) (|||||)または短い([][]|[]) ([C]|[]||) 。

簡単にするために、グループを変数に保存し、結果の正規表現で使用します。

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

タスク2.エラーがあるコード

状態

日中、開発チームはいくつかの新しい機能を作成しました。 しかし、リリースの準備中にマージの競合が発生し、それらが解決された後、レイアウトが分割されました。 リリースが実稼働に入るまでの時間を確保するために、コードの修正が最小限に抑えられているため、エラーを取り除くことが急務です。

壊れたスタイルとPNG形式のHTMLページが提供されます（予想される結果）。 Chromeで表示したときの結果が元のスクリーンショットと同じになるように、エラーを修正する必要があります。 修正されたページを問題の解決策として送信します。

壊れたスタイルのHTMLページ 。 レイアウト：

解析

このタスクでは、Yandex開発者が頻繁に遭遇する状況を模倣しようとしました。巨大なコードベースで、ごく少数の単純なコード行を見つけ、その修正により目的の結果が得られます。 つまり、コードを書くのが難しかったのではなく、正確にどこを書く（または削除する）かを理解するのが難しかったのです。

検索結果の実際のコードを取得し、レイアウトを壊したわずかな修正を加えました。 コンテストの参加者は、約250キロバイトのレイアウトを処理し、コードをレイアウトに対応する状態にするのに1時間もかかりませんでした。

競争の時間制限がコード全体を読むことを許可しなかったことは明らかであるため、参加者はブラウザで開発者向けのツールを使用する必要があります。

4つのタスクオプションのいずれかを修正するには、次の変更で十分でした。

  diff --git a / blitz.html b / blitz.html 

 インデックス36b9af8..1e30545 100644 

  --- a / blitz.html 

  +++ b / blitz.html 

  @@ -531.10 +531.6 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

 高さ：自動; 

  } 

  -.search2__button .suggest2-form__button：nth-​​child（1）{ 

  -背景：＃ff0！重要; 

  -} 

  - 

  / * ../../blocks-desktop/input/__control/input__control.styl end * / 

  / * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css begin * / 

  / * input__boxに対して相対的に配置されます。 

  @@ -744.10 +740.6 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

  background-clip：パディングボックス。 

  } 

  .input_theme_websearch .input__clear { 

 背景画像：url（ "/ static / web4 / node_modules / islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"）; 

 背景サイズ：16px; 

  @@ -857.6 +849.7 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

 背景色：＃f2cf46; 

  } 

  .websearch-button__text：before { 

  +位置：絶対値; 

 上：-6px; 

 右：-9px; 

 幅：0; 

  @@ -866.8 +859.6 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

 ボーダースタイル：ソリッド; 

 ボーダーカラー：rgba（255,219,76,0）; 

  border-left-color：継承; 

  -位置：相対; 

  -z-index：-1000; 

  } 

  / * ../../blocks-deskpad/websearch-button/websearch-button.styl end * / 

  @@ -1349.6 +1340.7 @@ 

  iframe [src $ = 'ext-analytics.html'] { 

 フォントサイズ：14px; 

 行の高さ：40px; 

 位置：相対; 

  +表示：インラインブロック。 

 高さ：自動; 

 パディング：0; 

 垂直整列：中央; 

タスク3.指定された変動性のある画像

状態

デザイナーがロゴをデザインしました。 さまざまな条件で使用する必要があります。 できるだけ便利にするために、純粋なCSSの1つのHTML要素で構成します。

写真を使用することはできません（データ：uriを使用しても）。

解析

タスクはdivを1つだけ使用することであったため、div自体と疑似要素:: beforeおよび:: afterのみがあります。

幸いなことに、レイアウト上の画像は、異なる色の3つの領域のみで構成されています。 アクセシブルな要素ごとに独自の背景を作成し、コーナーを正しく配置して丸くします。 レイアウトの灰色の領域に影があります-グラデーションを使用してください。

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

タスク4

状態

Petyaは、モスクワのFrontender新聞でシニアタイプセッターとして働いています。 新聞のレイアウトに、PetyaはWebテクノロジーのスタックを使用しています。 Petyaが直面した最も困難なタスクは、新聞記事の見出しのレイアウトでした。各号の新聞コラムの幅は異なり、見出しのフォントと文字数は異なります。

Petyaは、フォントサイズが最大になるように各見出しに独自のフォントサイズを選択する必要がありますが、同時に、見出しのテキスト全体がそれに割り当てられたスペースに収まります。

Petyaのヘルプ：calcFontSize関数を実装します。これにより、転送されたテキストをコンテナーに入力できるようになり、コンテナー全体に収まり、可能な最大サイズになります。 これが失敗した場合、ソリューションはnullを返します。 入力行の最大長は100文字です。 入力文字列を空にすることはできません。 ソリューションには関数コード全体が含まれている必要があり、Petyaがそれを自分のプロジェクトにコピーして自分のコードで呼び出すことができるように、外部依存関係を使用しないでください。

ソリューションがどの程度最適に機能するかを確認し、DOMで操作が多すぎる場合は解決します。

解析

最初に行うことは、コンテナ内のテキストが数行かかる場合、テキストがコンテナに収まるかどうかを判断することを学ぶことです。 これを行う最も簡単な方法は、 element.getBoundingClientRect（）関数を使用することです。これにより、要素の寸法を取得できます。

コンテナ内に個別のspan要素を使用してテキストを描画し、この要素の幅または高さがコンテナのサイズを超えているかどうかを確認できます。 その場合、テキストはコンテナに収まりません。

次に、境界条件を確認します。 テキストが最小フォントサイズでもコンテナに収まらない場合、入力できません。 テキストが最大許容サイズで途切れる場合、maxは正解になります。 その他の場合、目的のフォントサイズは[min、max]の間隔のどこかにあります。

解決策を見つけるには、このギャップ全体をソートして、テキストがコンテナに配置されるフォントサイズの値を見つける必要がありますが、1ずつ増やすと収まりません。

範囲[min、max]の単純なforループでこれを行うことができますが、ソリューションはページの多くのチェックと再描画を行います-範囲内でチェックされる値ごとに少なくとも1つ。 このようなソリューションのアルゴリズムの複雑さは線形になります。

チェックの数を最小限に抑え、O（log n）で機能するソリューションを得るには、バイナリ検索アルゴリズムを使用する必要があります。 アルゴリズムの考え方は、検索の各反復で、値の範囲が2つの半分に分割され、検索が解が位置する半分で再帰的に継続するというものです。 範囲が単一の値に縮小されると、検索は終了します。 Wikipediaの記事でバイナリ検索アルゴリズムの詳細を読んでください 。

MutationObserverを使用してソリューションのアルゴリズムの複雑さをチェックしました。ページに配置し、DOMが答えを見つけるプロセスで決定する突然変異の数を計算しました。 一部のテストでは、バイナリ検索に基づくソリューションのみがこの制限に合格できるように、突然変異の数が上記から厳密に制限されていました。

タスクの完全なスコアを取得するには、異なる境界条件（入力と最小、最大、テキストの空行に一致）を慎重に確認し、コードが実行されるいくつかの環境条件を提供する必要がありました（たとえば、CSSページの重要なフォントサイズ）

タスク5.コミュニケーションの難しさ

それぞれの認定オプションには、何らかのインターフェイスを持つHTMLページが入力として提案されるタスクがありました。 タスクには別の凡例がありましたが、ページからいくつかのデータを抽出し、このデータを使用して何らかの方法でインターフェイスとやり取りする必要があるという事実にすべてが要約されました。

このシリーズのタスクの1つである「コミュニケーションの難しさ」と呼ばれる解決策を分析しましょう。

状態

ホース・アドルフは電話で友人と話すのが大好きです。 残念ながら、これはまれです。 アドルフが電話をかけるたびに、友人の番号をダイヤルするのに1時間以上かかります。 これは、彼が太いひづめで正しいキーを打つことが非常に難しいためです。

幸いなことに、Adolfの電話はJavaScriptをサポートしています。 キーボードをクリックしてAdolfの友人にダイヤルするプログラムを書いてください。 必要な番号はすべてノートに記録されます。 不幸な馬はあなたにとても感謝しています！

解析

入力として提供されたページは次のとおりです。



ソリューションの最初の部分はデータの取得です
電話番号の各桁は、background-imageを介した画像によって設定されます。 同時に、検証中に、数値が動的に置き換えられます。 ブラウザーでデバッガーを開き、ページのDOMツリーを見ると、各DOM要素がクリアクラスを使用していることがわかります。

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

この場合、ディクショナリを作成し、CSSクラスを抽出し、それらをディクショナリに応じた数字の文字列に変換するだけで十分でした。 たとえば、次のように：

 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; }, []); 

その結果、次の配列を取得します：[9、8、5、4、1、2、8、0、9、0]。

ソリューションの2番目の部分は、インターフェイスと対話することです
この段階では、すでに数字のすべての数字を含む配列があり、キーボードのどのボタンがどの数字に対応するかを理解する必要があります。 HTMLコードを見ると、キーボード上の数字を示す特別なヒントクラスがないことがわかります。

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

インデックスによって別の辞書を簡単に手動で作成できますが、もっと簡単な方法があります。 Webインスペクターでスタイルをよく見ると、ボタンの番号が、疑似要素の前のCSSプロパティコンテンツによって設定されていることがわかります。 たとえば、「3」キーの場合、スタイルは次のようになります。

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

このプロパティの値を取得するには、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; }, {}); 

その結果、キーテキストがボタン上のテキスト（数値または「呼び出し」）になり、値がDOMノードになるオブジェクトを取得します。

最初の配列（phoneNumber）から値を取得し、それらを通過して、辞書キーを使用して対応するボタンをクリックするだけです。

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

注：ダイヤルする前に、値呼び出しを配列の最後に追加します。 これはタスクの条件に必要です。番号をダイヤルして「呼び出し」を押さないと、ソリューションはテストに合格しないためです。

もう1つの機能は、キーボードボタンの非同期押下です。 ダイヤル時のキーストローク間の時間間隔が50ミリ秒未満の場合、このソリューションもテストに合格しません。 この機能はタスクの条件に明示的に記述されていなかったため、参加者がページのソースコードを読んで見つけることを期待していました。 ところで、ソースコードの参加者にはちょっとした驚きが待っていました。 ;）

タスク6

状態

Fedor Rakushkinは、会社でタスク管理システムを管理しています。 システムが配置されているサーバーが故障しています（Fedorはバックアップを実行しませんでした）。

サーバーのメモリには、タスク、エグゼキューター、オブザーバー、およびこれらの構造間の関係を記述する構造のキャッシュが残っていました。 さらに、最後に変更された構造へのキャッシュ内のリンクが保持されました。

Fedorがタスクとユーザー間のすべての可能な接続を復元し、それらをMarkdown形式のドキュメントに保存できる関数を作成し、Fedorがデータベースを新しいサーバーに復元するのを支援します。

マークダウンドキュメントの形式は次のとおりです。

 ##  - %  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% 

タスクのリスト、タスクのエグゼキューターのリスト、タスクのオブザーバーのリスト、ユーザーのリスト、およびユーザーが実行するタスクのリストは、辞書式にソートする必要があります。

キャッシュ内の構造の説明

ユーザーは `User`型の構造としてキャッシュに保存されます：

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

タスクはタイプ `Task`の構造としてキャッシュに保存されます：

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

ソリューションテンプレート

ソリューションには、次の署名に対応する関数をエクスポートするCommonJSモジュールが含まれている必要があります。

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

例

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

`lastEdited`へのリンクを表示すると、次の構造が得られます。

 { 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 . 例：









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 ² ).

, , ( . ). — 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 ² ), . .

, , . , , .

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; // ...      

.