Frontend, Algorithmen und Opossum Frederick. Wir analysieren die Aufgaben des Yandex-Wettbewerbs

Mit diesem Beitrag schließen wir eine Reihe von Veröffentlichungen über Yandex.Blitz-Wettbewerbe im Jahr 2018 ab. Wir hoffen, dass Sie die Gelegenheit hatten, teilzunehmen oder zumindest zu sehen, welche Art von Aufgaben wir in der Nähe der Produktion vorschlagen. Der letzte Wettbewerb war der Verwendung von Algorithmen im Frontend gewidmet. Heute veröffentlichen wir detaillierte Analysen von 12 Problemen: Die ersten 6 wurden in der Qualifikationsrunde und die Probleme 7–12 im Finale vorgeschlagen. Wir haben versucht zu erklären, wie sich Bedingungen gebildet haben, auf welche Fähigkeiten wir geachtet haben. Vielen Dank an alle Teilnehmer für ihr Interesse!

Aufgabe 1

Die erste Aufgabe bestand darin, sich 20 Minuten lang aufzuwärmen, und wir beschlossen, den Zustand so zu gestalten, dass er mit regulären Ausdrücken leicht gelöst werden konnte.

Alle Optionen für die Aufgabe sind auf ähnliche Weise aufgebaut - es gibt eine Aufteilung in Punkte, von denen jeder durch die Gruppe im endgültigen regulären Ausdruck dargestellt werden kann.

Betrachten Sie eine der Optionen: Post.

Zustand

Auf dem Planeten Jopan-14-53 wollen sich die Einheimischen gegenseitig Briefe schicken, aber die Taubenroboter, die sie ausliefern sollen, sind in den Adressen verwirrt. Sie müssen ihnen beibringen, Buchstaben zu analysieren und ihre Gültigkeit zu überprüfen.

Die Struktur des grundlegenden Teils der Adresse besteht aus der Region, der Gemeinde, dem Vor- und Nachnamen des Empfängers. Die Gemeinde kann in Landkreise und Postämter unterteilt werden. Alle Teile sind durch ein Komma getrennt.

Die Namen von Regionen, Gemeinden und Bezirken sind Wörter, der erste Buchstabe in jedem Wort ist groß, der Rest ist klein. Es sind Namen mit zwei Wörtern möglich, die durch ein Leerzeichen oder ein Minuszeichen getrennt sind. In jedem Wort drei bis acht Buchstaben AZ.

Die Bewohner haben 6 Finger in der Hand, im Alltag das Duodezimalsystem. Die Zahlen 0–9 werden unverändert verwendet, und 10 und 11 werden durch die Zeichen ~ und ≈ angezeigt.

Die Postnummer in der Komposition besteht entweder aus 3 Ziffern in einer Reihe oder aus 4 Ziffern, die in 2 Gruppen zu je 2 Ziffern mit einem Minuszeichen unterteilt sind. Beispiele: 300 , 44-99 .

Manchmal schicken die Bewohner auf Anfrage Briefe an die Gemeinde. In diesem Fall gibt es keine Adresse: nur die Gemeinde und den Namen des Empfängers.

Es ist lustig, aber die Menschen auf dem Planeten heißen nur sechs Namen und neun Nachnamen. Namen: Shob, Ryob, Mob, Xiang, Ryan, Mans. Nachnamen: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Die Bewohner dieses Planeten sind überhaupt keine Träumer.

Parsen

Die Struktur des grundlegenden Teils der Adresse besteht aus der Region, der Gemeinde, dem Vor- und Nachnamen des Empfängers. Die Gemeinde kann in Landkreise und Postämter unterteilt werden. Alle Teile sind durch ein Komma getrennt.

In den ersten Absätzen erfahren wir, wie Region, Gemeinde, Bezirk, Post, Name und Nachname angegeben werden und in welcher Reihenfolge sie in der getesteten Zeile folgen sollen.

Die Namen von Regionen, Gemeinden und Bezirken sind Wörter, der erste Buchstabe in jedem Wort ist groß, der Rest ist klein. Es sind Namen mit zwei Wörtern möglich, die durch ein Leerzeichen oder ein Minuszeichen getrennt sind. In jedem Wort drei bis acht Buchstaben AZ.

Aus diesem Absatz geht hervor, dass die Gruppe den Wörtern entspricht ([-][-]{2,7}) . Und die Namen ([-][-]{2,7}(?:[- ][-][-]{2,7})) .

Die Bewohner haben 6 Finger in der Hand, im Alltag das Duodezimalsystem. Die Zahlen 0–9 werden unverändert verwendet, und 10 und 11 werden durch die Zeichen ~ und ≈ angezeigt.

Hier erfahren wir, dass es nicht ausreicht, \d für Zahlen zu verwenden - Sie müssen [0-9~≈] .

Die Postnummer in der Komposition besteht entweder aus 3 Ziffern in einer Reihe oder aus 4 Ziffern, die in 2 Gruppen zu je 2 Ziffern mit einem Minuszeichen unterteilt sind. Beispiele: 300 , 44-99 .

Somit entspricht die Gruppe den Postnummern ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .

Manchmal schicken die Bewohner auf Anfrage Briefe an die Gemeinde. In diesem Fall gibt es keine Adresse: nur die Gemeinde und den Namen des Empfängers.

Wir verstehen, erinnern uns und berücksichtigen bei der Versammlung der endgültigen Funktion, dass der Bezirk und das Postamt gleichzeitig abwesend sein können.

Es ist lustig, aber die Menschen auf dem Planeten heißen nur sechs Namen und neun Nachnamen. Namen: Shob, Ryob, Mob, Xiang, Ryan, Mans. Nachnamen: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Die Bewohner dieses Planeten sind überhaupt keine Träumer.

Dies ist der letzte Teil der Bedingung. Hier brauchten wir eine andere einfache Gruppe (||||||||) (|||||) oder ihr kürzeres Gegenstück ([][]|[]) ([C]|[]||) .

Der Einfachheit halber speichern wir die Gruppen in Variablen und verwenden sie im resultierenden regulären Ausdruck.

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

Aufgabe 2. Code, in dem ein Fehler vorliegt

Zustand

Tagsüber hat das Entwicklungsteam mehrere neue Funktionen entwickelt. Bei der Vorbereitung des Releases traten jedoch Zusammenführungskonflikte auf, und nachdem sie gelöst wurden, wurde das Layout getrennt. Es ist dringend erforderlich, Fehler aufgrund der minimalen Anzahl von Korrekturen im Code zu beseitigen, damit die Version Zeit hat, in Produktion zu gehen.

Sie erhalten eine HTML-Seite mit fehlerhaften Stilen und einem PNG-Format (mit dem erwarteten Ergebnis). Sie müssen die Fehler beheben, damit das Ergebnis beim Anzeigen in Chrome dem ursprünglichen Screenshot entspricht. Senden Sie die korrigierte Seite als Lösung für das Problem.

HTML-Seite mit defekten Stilen. Layout:

Parsen

In dieser Aufgabe haben wir versucht, die Situation nachzuahmen, auf die Yandex-Entwickler regelmäßig stoßen: Finden Sie in der riesigen Codebasis die wenigen einfachen Codezeilen, deren Korrektur zum gewünschten Ergebnis führt. Das heißt, die Schwierigkeit bestand nicht darin, den Code zu schreiben, sondern zu verstehen, wo genau er geschrieben (oder gelöscht) werden soll.

Wir haben den echten Suchmaschinencode genommen und nur ein paar Korrekturen vorgenommen, die das Layout beschädigt haben. Die Teilnehmer des Wettbewerbs hatten weniger als eine Stunde Zeit, um mit ungefähr 250 Kilobyte Layout fertig zu werden und den Code in einen Zustand zu bringen, der dem Layout entspricht.

Es ist klar, dass das Zeitlimit für den Wettbewerb nicht das Lesen des gesamten Codes erlaubte, daher sollten die Teilnehmer die Tools für Entwickler im Browser verwenden.

Um eine der vier Aufgabenoptionen zu korrigieren, waren die folgenden Änderungen ausreichend:

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

  Index 36b9af8..1e30545 100644 

  --- a / blitz.html 

  +++ b / blitz.html 

  @@ -531.10 +531.6 @@ 

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

  Höhe: Auto; 

  }} 

  -.search2__button .suggest2-form__button: n-tes Kind (1) { 

  - Hintergrund: # ff0! wichtig; 

  -} 

  - - 

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

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

  / * Positioniert relativ zu input__box. 

  -744.10 +740.6 @@ 

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

  Hintergrundclip: Polsterbox; 

  }} 

  .input_theme_websearch .input__clear { 

  Hintergrundbild: URL ("/ static / web4 / node_modules / Islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"); 

  Hintergrundgröße: 16px; 

  @@ -857.6 +849.7 @@ 

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

  Hintergrundfarbe: # f2cf46; 

  }} 

  .websearch-button__text: vor { 

  + Position: absolut; 

  oben: -6px; 

  rechts: -9px; 

  Breite: 0; 

  @@ -866.8 +859.6 @@ 

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

  Randstil: fest; 

  Randfarbe: rgba (255,219,76,0); 

  Rand-links-Farbe: erben; 

  - Position: relativ; 

  - Z-Index: -1000; 

  }} 

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

  @@ -1349.6 +1340.7 @@ 

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

  Schriftgröße: 14px; 

  Zeilenhöhe: 40px; 

  Position: relativ; 

  + Anzeige: Inline-Block; 

  Höhe: Auto; 

  Polsterung: 0; 

  vertikal ausrichten: Mitte; 

Aufgabe 3. Ein Bild mit einer bestimmten Variabilität

Zustand

Der Designer hat das Logo entworfen. Es muss unter verschiedenen Bedingungen verwendet werden. Um es so bequem wie möglich zu gestalten, erstellen Sie ein HTML-Element in reinem CSS.

Sie können keine Bilder verwenden (auch nicht durch Daten: uri).

Parsen

Da die Aufgabe darin bestand, nur ein Div zu verwenden, haben wir nur das Div selbst und die Pseudoelemente :: vorher und :: nachher.

Das Bild auf dem Layout besteht glücklicherweise nur aus drei Bereichen unterschiedlicher Farbe. Wir erstellen unseren eigenen Hintergrund für jedes zugängliche Element, die richtige Position und die runden Ecken. Es gibt einen Schatten auf dem grauen Bereich des Layouts - wir machen es mit einem Farbverlauf.

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

Aufgabe 4

Zustand

Petja arbeitet als leitender Schriftsetzer in der Zeitung Moscow Frontender. Für das Layout der Zeitung verwendet Petya einen Stapel von Webtechnologien. Die schwierigste Aufgabe für Petya war die Anordnung der Überschriften in Zeitungsartikeln: Die Zeitungsspalten in jeder Ausgabe haben unterschiedliche Breiten, und die Überschriften haben eine andere Schriftart und eine unterschiedliche Anzahl von Zeichen.

Petya muss für jede Überschrift seine eigene Schriftgröße auswählen, damit die Schriftgröße maximal ist. Gleichzeitig passt der gesamte Überschriftentext in den ihm zugewiesenen Bereich.

Hilfe Petya: Implementieren Sie die Funktion calcFontSize, mit der Sie den übertragenen Text so in den Container eingeben können, dass er in den gesamten Container passt und die maximal mögliche Größe hat. Wenn dies fehlschlägt, sollte die Lösung null zurückgeben. Die maximale Länge der Eingabezeile beträgt 100 Zeichen. Die Eingabezeichenfolge darf nicht leer sein. Ihre Lösung sollte den gesamten Funktionscode enthalten und keine externen Abhängigkeiten verwenden, damit Petja ihn in sein Projekt kopieren und in seinem Code aufrufen kann.

Wir werden prüfen, wie optimal Ihre Lösung funktioniert, und sie optimieren, wenn sie zu viele DOM-Manipulationen hervorruft.

Parsen

Als Erstes müssen Sie lernen, wie Sie feststellen, ob der Text in den Container passt, da der Text im Container mehrere Zeilen umfassen kann. Der einfachste Weg, dies zu tun, ist die Verwendung der Funktion element.getBoundingClientRect () , mit der Sie die Abmessungen des Elements abrufen können.

Sie können Text mit einem separaten Span-Element im Container zeichnen und prüfen, ob die Breite oder Höhe dieses Elements die Größe des Containers überschreitet. Wenn ja, passt der Text nicht in den Container.

Überprüfen Sie als nächstes die Randbedingungen. Wenn der Text trotz einer Mindestschriftgröße nicht in den Container passt, kann er nicht eingegeben werden. Wenn der Text mit der maximal zulässigen Größe unterbrochen wird, ist max die richtige Antwort. In anderen Fällen liegt die gewünschte Schriftgröße irgendwo im Intervall [min, max].

Um eine Lösung zu finden, müssen Sie diese gesamte Lücke sortieren und einen Wert für die Schriftgröße finden, bei dem der Text in den Container eingefügt wird. Wenn Sie ihn jedoch um 1 –– erhöhen, passt er nicht mehr.

Sie können dies mit einer einfachen for-Schleife über den Bereich [min, max] tun, aber die Lösung führt viele Überprüfungen und Neuzeichnungen der Seite durch - mindestens eine für jeden Wert, der im Bereich überprüft werden soll. Die algorithmische Komplexität einer solchen Lösung ist linear.

Um die Anzahl der Überprüfungen zu minimieren und eine Lösung zu erhalten, die für O (log n) funktioniert, müssen Sie den binären Suchalgorithmus verwenden. Die Idee des Algorithmus ist, dass bei jeder Iteration der Suche der Wertebereich in zwei Hälften geteilt wird und die Suche in der Hälfte, in der sich die Lösung befindet, rekursiv fortgesetzt wird. Die Suche wird beendet, wenn der Bereich auf einen einzelnen Wert reduziert wird. Weitere Informationen zum binären Suchalgorithmus finden Sie im Wikipedia-Artikel .

Wir haben die algorithmische Komplexität der Lösung mit MutationObserver überprüft: Wir haben sie auf der Seite platziert und berechnet, wie viele Mutationen das DOM bei der Suche nach der Antwort trifft. Bei einigen Tests war die Anzahl der Mutationen von oben streng begrenzt, so dass nur eine auf binärer Suche basierende Lösung diese Einschränkung bestehen konnte.

Um die volle Punktzahl für die Aufgabe zu erhalten, mussten auch die verschiedenen Randbedingungen (Übereinstimmung von min und max, eine leere Textzeile an der Eingabe) sorgfältig überprüft und verschiedene Umgebungsbedingungen angegeben werden, unter denen der Code ausgeführt wird (z. B. behoben mit! Wichtige Schriftgröße auf der CSS-Seite )

Aufgabe 5. Kommunikationsschwierigkeiten

In jeder der Qualifizierungsoptionen gab es eine Aufgabe, bei der eine HTML-Seite mit einer Schnittstelle als Eingabe angeboten wurde. Die Aufgaben hatten eine andere Legende, aber sie alle liefen darauf hinaus, dass es notwendig war, einige Daten von der Seite zu extrahieren und mithilfe dieser Daten irgendwie mit der Benutzeroberfläche zu interagieren.

Lassen Sie uns die Lösung für eine der Aufgaben dieser Reihe analysieren, die als "Kommunikationsschwierigkeiten" bezeichnet wurde.

Zustand

Pferd Adolf liebt es, mit Freunden am Telefon zu sprechen. Dies ist leider selten. Jedes Mal, wenn Adolf anrufen möchte, benötigt er mehr als eine Stunde, um die Nummer eines Freundes zu wählen. Dies liegt daran, dass es für ihn sehr schwierig ist, mit seinen dicken Hufen die richtigen Tasten zu treffen.

Glücklicherweise unterstützt Adolfs Handy JavaScript. Bitte schreiben Sie ein Programm, das Adolfs Freunde wählt, indem Sie auf die Tastatur klicken. Alle notwendigen Nummern werden in einem Notizbuch festgehalten. Das unglückliche Pferd wird Ihnen sehr dankbar sein!

Parsen

Hier ist die Seite, die als Eingabe angeboten wurde:



Der erste Teil der Lösung ist das Abrufen von Daten
Jede der Ziffern der Telefonnummer wird durch ein Bild über das Hintergrundbild gesetzt. Gleichzeitig werden die Zahlen während der Überprüfung dynamisch ersetzt. Wenn Sie den Debugger in einem Browser öffnen und den DOM-Baum der Seite anzeigen, werden Sie feststellen, dass jedes DOM-Element eindeutige Klassen verwendet:

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

In diesem Fall reichte es aus, nur ein Wörterbuch zu erstellen, CSS-Klassen zu extrahieren und sie in eine Zeichenfolge mit einer dem Wörterbuch entsprechenden Zahl ohne Trennzeichen (CSS-Klassentrennzeichen) zu konvertieren. Zum Beispiel so:

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

Als Ergebnis erhalten wir das folgende Array: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].

Der zweite Teil der Lösung besteht in der Interaktion mit der Schnittstelle
Zu diesem Zeitpunkt haben wir bereits ein Array mit allen Ziffern der Nummer, und wir müssen verstehen, welche Tasten auf der Tastatur welcher Ziffer entsprechen. Wenn wir uns den HTML-Code ansehen, werden wir feststellen, dass es keine speziellen Hinweisklassen gibt, die eine Zahl auf der Tastatur angeben:

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

Man könnte einfach manuell ein anderes Wörterbuch nach Index erstellen, aber es gibt einen einfacheren Weg. Wenn Sie sich die Stile im Webinspektor genau ansehen, werden Sie feststellen, dass die Nummer auf der Schaltfläche über den Inhalt der CSS-Eigenschaft für das Pseudoelement: before festgelegt wird. Für die Taste „3“ sehen die Stile beispielsweise folgendermaßen aus:

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

Um den Wert dieser Eigenschaft abzurufen, verwenden wir die window.getComputedStyle-Methode:

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

Als Ergebnis erhalten wir ein Objekt, bei dem die Schlüsseltexte die Texte auf den Schaltflächen (Nummer oder "Anruf") sind und die Werte DOM-Knoten sind.

Es bleibt nur, die Werte aus dem ersten Array (phoneNumber) zu übernehmen, sie durchzugehen und mit unserem Schlüsselwörterbuch auf die entsprechenden Schaltflächen zu klicken:

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

Bitte beachten Sie: Vor dem Wählen fügen wir am Ende des Arrays einen Aufrufwert hinzu. Dies ist für die Bedingungen der Aufgabe erforderlich, da die Lösung den Test nicht besteht, wenn Sie die Nummer wählen und nicht auf "Anrufen" klicken.

Ein weiteres Merkmal ist das asynchrone Drücken der Tastaturtasten. Wenn das Zeitintervall zwischen den Tastenanschlägen beim Wählen weniger als 50 ms beträgt, besteht diese Lösung den Test ebenfalls nicht. Diese Funktion wurde in den Bedingungen des Problems nicht explizit beschrieben, und wir erwarteten, dass der Teilnehmer dies durch Lesen des Quellcodes der Seite herausfindet. Übrigens erwartete die Teilnehmer des Quellcodes eine kleine Überraschung. ;)

Aufgabe 6

Zustand

Fedor Rakushkin verwaltet das Task-Management-System in seinem Unternehmen. Der Server, auf dem sich das System befindet, ist ausgefallen (und Fedor hat keine Sicherungen durchgeführt).

Im Speicher des Servers befand sich noch ein Cache mit Strukturen, die Aufgaben, Ausführende und Beobachter sowie die Beziehungen zwischen diesen Strukturen beschreiben. Außerdem wurde die Cache-Verknüpfung zur zuletzt geänderten Struktur beibehalten.

Helfen Sie Fedor, eine Funktion zu schreiben, mit der alle möglichen Verbindungen zwischen Aufgaben und Benutzern wiederhergestellt und in einem Dokument im Markdown-Format gespeichert werden können, von dem aus Fedor die Datenbank auf einem neuen Server wiederherstellt.

Das Abschriften-Dokument sollte das folgende Format haben:

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

Die Liste der Aufgaben, die Liste der Ausführenden in der Aufgabe, die Liste der Beobachter in der Aufgabe, die Liste der Benutzer und die Liste der Aufgaben, die der Benutzer ausführt, sollten lexikografisch sortiert werden.

Beschreibung der Strukturen im Cache

Benutzer werden im Cache als Struktur vom Typ "Benutzer" gespeichert:

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

Aufgaben werden im Cache als Struktur vom Typ "Aufgabe" gespeichert:

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

Lösungsvorlage

Ihre Lösung sollte ein CommonJS-Modul enthalten, das eine Funktion exportiert, die der folgenden Signatur entspricht:

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

Beispiele

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

Wenn Sie einen Link zu "lastEdited" anzeigen, erhalten Sie die folgende Struktur:

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

— . , , , .

-.

Anmerkungen:
— 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 . Zum Beispiel:









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) { //   } 

Anmerkungen

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

.