Avec cet article, nous terminons une série de publications sur les concours Yandex.Blitz en 2018. Nous espérons que vous avez eu l'occasion de participer ou du moins de voir quel type de tâches nous proposons à proximité de la production. Le dernier concours était consacré à l'utilisation d'algorithmes en frontend. Aujourd'hui, nous publions des analyses détaillées de 12 problèmes: les 6 premiers d'entre eux ont été proposés dans le tour de qualification, et les problèmes 7 à 12 dans la finale. Nous avons essayé d'expliquer comment les conditions se sont formées, à quelles compétences nous avons prêté attention. Merci à tous les participants pour leur intérêt!
Tâche 1
La première tâche consistait à s'échauffer, pendant 20 minutes, et nous avons décidé de faire son état afin qu'il soit facilement résolu en utilisant des expressions régulières.
Toutes les options pour la tâche sont construites de manière similaire - il y a une ventilation en points, chacun pouvant être représenté par le groupe dans l'expression régulière finale.
Considérez l'une des options: Bureau de poste.
Condition
Sur la planète Jopan-14-53, les habitants veulent s'envoyer des lettres, mais les robots colombophiles qui devraient les livrer sont confus dans les adresses. Vous devez leur apprendre à analyser les lettres et à vérifier leur validité.
La structure de la partie de base de l'adresse se compose de la région, de la commune, du nom et du prénom du destinataire. La municipalité peut être divisée en comtés et bureaux de poste. Toutes les parties sont séparées par une virgule.
Les noms des régions, municipalités et districts sont des mots, la première lettre de chaque mot est grande, les autres sont petites. Les noms à deux mots sont possibles, séparés par un espace ou un signe moins. Dans chaque mot de trois à huit lettres AZ.
Les habitants ont 6 doigts dans leurs mains, dans la vie quotidienne le système duodécimal. Les chiffres 0–9 sont utilisés tels quels, et 10 et 11 sont indiqués par les signes
~ et
≈ .
Le numéro du bureau de poste dans la composition a soit 3 chiffres d'affilée, soit 4 divisés en 2 groupes de 2 chiffres avec un signe moins. Exemples:
300 ,
44-99 .
Parfois, les résidents envoient des lettres à la municipalité sur demande. Dans ce cas, il n'y a pas d'adresse: uniquement la commune et le nom du destinataire.
C'est drôle, mais les gens de la planète ne sont appelés que six noms et neuf noms de famille. Noms: Shob, Ryob, Mob, Xiang, Ryan, Mans. Noms de famille: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Les habitants de cette planète ne sont pas du tout des rêveurs.
Analyse
La structure de la partie de base de l'adresse se compose de la région, de la commune, du nom et du prénom du destinataire. La municipalité peut être divisée en comtés et bureaux de poste. Toutes les parties sont séparées par une virgule.
À partir des premiers paragraphes, nous apprenons comment indiquer la région, la municipalité, le district, le bureau de poste, le nom et le prénom, et dans quel ordre ils doivent suivre dans la ligne testée.
Les noms des régions, municipalités et districts sont des mots, la première lettre de chaque mot est grande, les autres sont petites. Les noms à deux mots sont possibles, séparés par un espace ou un signe moins. Dans chaque mot de trois à huit lettres AZ.
A partir de ce paragraphe, il est clair que le groupe correspond aux mots
([-][-]{2,7}) . Et les noms, respectivement,
([-][-]{2,7}(?:[- ][-][-]{2,7})) .
Les habitants ont 6 doigts dans leurs mains, dans la vie quotidienne le système duodécimal. Les chiffres 0–9 sont utilisés tels quels, et 10 et 11 sont indiqués par les signes ~ et ≈ .
Ici, nous apprenons qu'il ne suffit pas d'utiliser
\d pour les nombres - vous devez utiliser
[0-9~≈] .
Le numéro du bureau de poste dans la composition a soit 3 chiffres d'affilée, soit 4 divisés en 2 groupes de 2 chiffres avec un signe moins. Exemples: 300 , 44-99 .
Ainsi, le groupe correspond aux numéros de bureau de poste
([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .
Parfois, les résidents envoient des lettres à la municipalité sur demande. Dans ce cas, il n'y a pas d'adresse: uniquement la commune et le nom du destinataire.
Nous comprenons, nous nous souvenons et prenons en compte dans l'assemblage de la fonction finale que le district et le bureau de poste peuvent être simultanément absents.
C'est drôle, mais les gens de la planète ne sont appelés que six noms et neuf noms de famille. Noms: Shob, Ryob, Mob, Xiang, Ryan, Mans. Noms de famille: Sho, Ryo, Mo, Xia, Rya, Ma, Syu, Ryu, Mu. Les habitants de cette planète ne sont pas du tout des rêveurs.
Ceci est la dernière partie de la condition. Ici, un autre groupe simple était nécessaire
(||||||||) (|||||) ou son homologue plus court
([][]|[]) ([C]|[]||) .
Par souci de simplicité, nous enregistrons les groupes dans des variables et les utilisons dans l'expression régulière résultante.
const w = '[-][-]{2,7}';
Tâche 2. Code dans lequel il y a une erreur
Condition
Au cours de la journée, l'équipe de développement a réalisé plusieurs nouvelles fonctionnalités. Mais lors de la préparation de la publication, des conflits de fusion se sont produits et, une fois résolus, la disposition s'est séparée. Il est urgent de se débarrasser des erreurs dues au nombre minimum de corrections dans le code pour que la version ait le temps de se mettre en production.
Vous disposez d'une page HTML avec des styles cassés et un format PNG (avec le résultat attendu). Vous devez corriger les erreurs afin que le résultat lors de l'affichage dans Chrome devienne le même que la capture d'écran d'origine. Envoyez la page corrigée comme solution au problème.
Page HTML avec des styles cassés. Disposition:
Analyse
Dans cette tâche, nous avons essayé d'imiter la situation que les développeurs Yandex rencontrent régulièrement: dans l'énorme base de code, trouvez les quelques lignes de code simples, dont la correction conduit au résultat souhaité. Autrement dit, la difficulté n'était pas d'écrire le code, mais de comprendre où exactement l'écrire (ou le supprimer).
Nous avons pris le vrai code du moteur de recherche et apporté quelques corrections qui ont cassé la mise en page. Les participants au concours avaient moins d'une heure pour traiter environ 250 kilo-octets de mise en page et amener le code dans un état correspondant à la mise en page.
Il est clair que la limite de temps pour le concours n'a pas permis de lire l'intégralité du code, donc les participants devraient utiliser les outils pour les développeurs dans le navigateur.
Pour corriger l'une des quatre options de tâche, les modifications suivantes étaient suffisantes:
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-analytics.html'] { hauteur: auto;
}
-.search2__button .suggest2-form__button: nth-child (1) { - arrière-plan: # ff0! important;
-}
-
/ * ../../blocks-desktop/input/__control/input__control.styl end * /
/ * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css begin * /
/ * Positionné par rapport à input__box.
@@ -744.10 +740.6 @@
iframe [src $ = 'ext-analytics.html'] { fond-clip: padding-box;
}
.input_theme_websearch .input__clear { background-image: url ("/ static / web4 / node_modules / islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg"); taille de l'arrière-plan: 16px;
@@ -857.6 +849.7 @@
iframe [src $ = 'ext-analytics.html'] { couleur de fond: # f2cf46;
}
.websearch-button__text: avant { + position: absolue;
en haut: -6px;
à droite: -9px;
largeur: 0;
@@ -866.8 +859.6 @@
iframe [src $ = 'ext-analytics.html'] { style bordure: solide;
couleur de la bordure: rgba (255,219,76,0);
border-left-color: hériter;
- position: relative;
- indice z: -1000;
}
/ * ../../blocks-deskpad/websearch-button/websearch-button.styl end * /
@@ -1349.6 +1340.7 @@
iframe [src $ = 'ext-analytics.html'] { taille de police: 14px;
hauteur de ligne: 40 px;
position: relative;
+ affichage: bloc en ligne;
hauteur: auto;
rembourrage: 0;
alignement vertical: milieu;
Tâche 3. Une image avec une variabilité donnée
Condition
Le designer a conçu le logo. Il devra être utilisé dans diverses conditions. Pour le rendre aussi pratique que possible, composez-le avec un élément HTML en CSS pur.
Vous ne pouvez pas utiliser d'images (même à travers des données: uri).
Analyse
Puisque la tâche consistait à n'utiliser qu'un seul div, nous n'avons que le div lui-même et les pseudo-éléments :: before et :: after.
L'image sur la mise en page, heureusement, se compose de seulement trois zones de couleurs différentes. Nous créons notre propre arrière-plan pour chaque élément accessible, positionner correctement et arrondir les coins. Il y a une ombre sur la zone grise de la mise en page - nous la faisons avec un dégradé.
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; }
Tâche 4
Condition
Petya travaille comme compositeur principal dans le journal Moscow Frontender. Pour la mise en page du journal, Petya utilise une pile de technologies Web. La tâche la plus difficile à laquelle Petya a été confrontée a été la mise en page des titres dans les articles de journaux: les colonnes des journaux dans chaque numéro ont des largeurs différentes, et les titres ont des polices et des nombres de caractères différents.
Petya doit choisir sa propre taille de police pour chaque titre afin que la taille de police soit maximale, mais en même temps tout le texte du titre tient dans l'espace qui lui est alloué.
Aidez Petya: implémentez la fonction calcFontSize, qui vous permettra d'entrer le texte transféré dans le conteneur afin qu'il tienne dans tout le conteneur et ait la taille maximale possible. Si cela échoue, la solution doit retourner null. La longueur de ligne d'entrée maximale est de 100 caractères. La chaîne d'entrée ne peut pas être vide. Votre solution doit contenir l'intégralité du code de fonction et ne doit pas utiliser de dépendances externes pour que Petya puisse le copier dans son projet et l'appeler dans son code.
Nous vérifierons le fonctionnement optimal de votre solution et l'améliorerons si elle produit trop de manipulations DOM.
Analyse
La première chose à faire est d'apprendre à déterminer si le texte tient dans le conteneur, étant donné que le texte dans le conteneur peut prendre plusieurs lignes. La façon la plus simple de le faire est d'utiliser la fonction
element.getBoundingClientRect () , qui vous permet d'obtenir les dimensions de l'élément.
Vous pouvez dessiner du texte avec un élément span séparé à l'intérieur du conteneur et vérifier si la largeur ou la hauteur de cet élément dépasse la taille du conteneur. Si oui, le texte ne rentre pas dans le conteneur.
Ensuite, vérifiez les conditions aux limites. Si le texte ne tient pas dans le conteneur même avec une taille de police minimale, il ne peut pas être saisi. Si le texte rompt avec la taille maximale autorisée, max sera la bonne réponse. Dans d'autres cas, la taille de police souhaitée se situe quelque part dans l'intervalle [min, max].
Pour trouver une solution, vous devez trier l'intégralité de cet écart et trouver une valeur de taille de police à laquelle le texte est placé dans le conteneur, mais si vous l'augmentez de 1 –– il cessera de s'adapter.
Vous pouvez le faire avec une simple boucle for sur la plage [min, max], mais la solution effectuera de nombreux contrôles et redessins de la page - au moins une pour chaque valeur à vérifier dans la plage. La complexité algorithmique d'une telle solution sera linéaire.
Pour minimiser le nombre de vérifications et obtenir une solution qui fonctionne pour O (log n), vous devez utiliser l'algorithme de recherche binaire. L'idée de l'algorithme est qu'à chaque itération de la recherche, la plage de valeurs est divisée en deux moitiés, et la recherche se poursuit récursivement dans la moitié dans laquelle se trouve la solution. La recherche se terminera lorsque la plage se réduira à une seule valeur. En savoir plus sur l'algorithme de recherche binaire
dans l'article Wikipedia .
Nous avons vérifié la complexité algorithmique de la solution à l'aide de
MutationObserver : nous l'avons placée sur la page et calculé combien de mutations le DOM prend la décision dans le processus de recherche de la réponse. Pour certains tests, le nombre de mutations était strictement limité par le haut de sorte que seule une solution basée sur la recherche binaire pouvait passer cette restriction.
Pour obtenir le score complet de la tâche, il était également nécessaire de vérifier soigneusement les différentes conditions aux limites (correspondance min et max, une ligne de texte vide à l'entrée) et de fournir plusieurs conditions environnementales dans lesquelles le code est exécuté (par exemple, corrigé avec! Taille de police importante dans la page CSS )
Tâche 5. Difficultés de communication
Dans chacune des options de qualification, il y avait une tâche où une page HTML avec une certaine interface était offerte en entrée. Les tâches avaient une légende différente, mais elles se résumaient toutes au fait qu'il était nécessaire d'extraire certaines données de la page et, en utilisant ces données, d'interagir d'une manière ou d'une autre avec l'interface.
Analysons la solution à l'une des tâches de cette série, qui s'appelait "Difficultés de communication".
Condition
Horse Adolf aime parler avec des amis au téléphone. Malheureusement, c'est rare. Chaque fois qu'Adolf veut appeler, il lui faut plus d'une heure pour composer le numéro d'un ami. En effet, il lui est très difficile de frapper les bonnes touches avec ses sabots épais.
Heureusement, le téléphone d'Adolf prend en charge JavaScript. Veuillez écrire un programme qui appelle les amis d'Adolf en cliquant sur le clavier. Tous les numéros nécessaires sont enregistrés dans un cahier. Le malheureux cheval vous en sera très reconnaissant!
Analyse
Voici la page qui a été proposée en entrée:
La première partie de la solution est la récupération des donnéesChacun des chiffres du numéro de téléphone est défini par une image via l'image d'arrière-plan. Dans le même temps, lors de la vérification, les numéros sont substitués dynamiquement. Si vous ouvrez le débogueur dans un navigateur et regardez l'arborescence DOM de la page, vous remarquerez que chaque élément DOM utilise des classes claires:
<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>
Dans ce cas, il suffisait juste de créer un dictionnaire, d'extraire des classes CSS et de les convertir en une chaîne avec un numéro selon le dictionnaire, à l'exclusion des séparateurs (séparateur de classe CSS). Par exemple, comme ceci:
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; }, []);
En conséquence, nous obtenons le tableau suivant: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].
La deuxième partie de la solution est d'interagir avec l'interfaceÀ ce stade, nous avons déjà un tableau avec tous les chiffres du numéro, et nous devons comprendre quels boutons du clavier correspondent à quel chiffre. Si nous regardons le code HTML, nous verrons qu'il n'y a pas de classes d'indices spéciales indiquant un nombre sur le clavier:
<div class="keys"> <div class="key"></div> <div class="key"></div> </div>
On pourrait simplement créer manuellement un autre dictionnaire par index, mais il existe un moyen plus simple. Si vous examinez attentivement les styles dans l'inspecteur Web, vous remarquerez que le nombre sur le bouton est défini via le contenu de la propriété CSS pour le pseudo-élément: avant. Par exemple, pour la touche «3», les styles ressemblent à ceci:
.key:nth-child(3):before { content: '3'; }
Pour obtenir la valeur de cette propriété, nous utilisons la méthode window.getComputedStyle:
const keys = Array.from(document.querySelectorAll('.game .key')).reduce((res, elem) => { const key = window
En conséquence, nous obtenons un objet où les textes clés seront les textes sur les boutons (numéro ou «appel»), et les valeurs seront des nœuds DOM.
Il ne reste plus qu'à prendre les valeurs du premier tableau (phoneNumber), les parcourir et cliquer sur les boutons correspondants à l'aide de notre dictionnaire de clés:
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();
Veuillez noter: avant de composer, nous ajoutons une valeur d'appel à la fin du tableau. Ceci est requis par les conditions de la tâche, car si vous composez le numéro et n'appuyez pas sur «appeler», la solution ne passera pas le test.
Une autre caractéristique est la pression asynchrone des boutons du clavier. Si l'intervalle de temps entre les frappes lors de la numérotation est inférieur à 50 ms, cette solution ne réussira pas non plus le test. Cette fonctionnalité n'était pas explicitement décrite dans les conditions du problème, et nous nous attendions à ce que le participant le découvre en lisant le code source de la page. Au fait, une petite surprise attendait les participants au code source. ;)
Tâche 6
Condition
Fedor Rakushkin administre le système de gestion des tâches dans son entreprise. Le serveur sur lequel se trouve le système a échoué (et Fedor n'a pas effectué de sauvegardes).
Dans la mémoire du serveur, il restait un cache de structures décrivant les tâches, les exécuteurs et les observateurs, ainsi que les relations entre ces structures. De plus, le lien du cache vers la dernière structure modifiée a été conservé.
Aidez Fedor à écrire une fonction qui peut restaurer toutes les connexions possibles entre les tâches et les utilisateurs et enregistrez-les dans un document au format Markdown, à partir duquel Fedor restaurera ensuite la base de données sur un nouveau serveur.
Le document de démarque doit avoir le format suivant:
## - % 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%
La liste des tâches, la liste des exécuteurs dans la tâche, la liste des observateurs dans la tâche, la liste des utilisateurs et la liste des tâches que l'utilisateur effectue doivent être triées lexicographiquement.
Description des structures dans le cache
Les utilisateurs sont stockés dans le cache en tant que structure de type "Utilisateur":
type User = { login: string; tasks: Task[]; spectating: Task[]; };
Les tâches sont stockées dans le cache en tant que structure de type `Task`:
type Task = { title: string; assignee: User; spectators: User[]; subtasks: Task[]; parent: Task | null; };
Modèle de solution
Votre solution doit contenir un module CommonJS exportant une fonction correspondant à la signature suivante:
module.exports = function (data) {
Des exemples
Si vous affichez un lien vers `lastEdited`, vous obtenez la structure suivante:
{ 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
, .
, , . , :
function traverse(ctx, handlers) {
. , , …
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));
… — :
7.
Condition
, .. :
, . , «».
.
, . , . . . HTML CSS. JavaScript .
, , - . , .
HTML/CSS, , , - .
CSS, , — float, . float , , .
— , . (
jsfiddle.net .)
— padding-top, margin-top ( ). DOM- (). (
.)
8.
Condition
HTML-. , . , . .
(pixel perfect). .
. .
, , . , . , : - , , .
, . , , .
, — . — CSS- border ( ), background ( ) box-shadow ( ).
- « » ( ) . , , .
— , 70 70 . : , . CSS- , CSS- , .
— 210 210 , 70 70 .
9.
Condition
— , -. JavaScript, . , .
: . , , . .
, — . — . , JavaScript API . , -, , . 10 , HTTP- .
— . , , , .
-.
Remarques:
— 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();
10.
Condition
. , «».
:
— , .
— , , .
— , , .
— , : ← ↓ ↑ →.
— — , .
, , , , .
.
.
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 . Par exemple:
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> </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');
— callback : window.onMazeReady(). .
, . , , . HTML, CSS JS — , .
, :
— ,
— , ,
— , ,
— , ,
— , ,
— , .
, :
— ,
— ,
— DOM API ,
— .
11.
Condition
, , . , . , .
, . , . . .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 =
12. -
Condition
X . VCS , .
, -. — , .
, . , , . .
, . ( ) .
.
. — 1000, - — 20.
:
type PullRequest = { files: string[], id: string, created: number, }
(created) (id) – .
CommonJS- :
module.exports = function (pullRequests) {
RemarquesNodeJS v9.11.2. .
function mergeAllPRs(prs) { } 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); } } function doPRsConflict(pr1, pr2) { const i = prToIndex.get(pr1); const j = prToIndex.get(pr2); return conflictMatrix[i * prs.length + j] === 1; }
«» , . ( ) , . , , - .
, , .
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++;
.