Frontend, algorithms and possum. Parse the tasks of the Yandex contest

With this post, we are completing a series of publications about competitions Yandex. Blitz in 2018. We hope that you had the opportunity to participate, or at least see, what tasks we are proposing that are close to production. The last contest was devoted to the application of algorithms in the frontend. Today, we publish detailed reviews of 12 tasks: the first 6 of them were proposed in the qualifying round, and tasks 7–12 in the final. We tried to explain how the conditions were formed, what skills we paid attention to. Thanks to all participants for their interest!

Task 1

The first task was to be warming up, for 20 minutes, and we decided to make her condition such that it was easily solved using regular expressions.

All variants of the task are constructed in a similar way - there is a breakdown into points, each of which can be represented by a group in the final regular expression.
')
Consider one of the options: Post Office.

Condition

On the planet Jopan-14-53, the locals want to send letters to each other, but mailing pigeons who have to deliver them are confused in the addresses. You have to teach them to disassemble the letters and check them for validity.

The structure of the base part of the address consists of the region, municipality, the name and surname of the addressee. The municipality can be divided into districts and post offices. All parts are separated by a comma,.

The names of regions, municipalities and districts are words, the first letter in each word is big, the rest are small. The names of two words are possible, separated by a space or a minus sign. Each word has from three to eight letters AZ.

The inhabitants on the hands of 6 fingers, in everyday life duodenalized system. Figures 0–9 are used as is, and 10 and 11 are denoted by ~ and ≈ .

The post office number in the composition has either 3 digits in a row, or 4, divided into 2 groups of 2 digits with a minus sign. Examples: 300 , 44-99 .

Sometimes residents send letters to the municipality of demand. In this case, there is no address: only the municipality and the name of the addressee.

It's funny, but people on the planet are called only six names and nine surnames. Names: Shob, Reb, Mob, Xiang, Ryan, Man. Surnames: Shyo, Ryo, Mo, Xia, Rya, Ma, Xiu, Ryu, Mu. Residents on this planet are not dreamers.

Parsing

The structure of the base part of the address consists of the region, municipality, the name and surname of the addressee. The municipality can be divided into districts and post offices. All parts are separated by a comma,.

From the first paragraphs we find out how the region, municipality, district, post office, first and last name are indicated, and in what order they should follow in the line under test.

The names of regions, municipalities and districts are words, the first letter in each word is big, the rest are small. The names of two words are possible, separated by a space or a minus sign. Each word has from three to eight letters AZ.

From this paragraph it is clear that the words correspond to the group ([-][-]{2,7}) . And the names, respectively, ([-][-]{2,7}(?:[- ][-][-]{2,7})) .

The inhabitants on the hands of 6 fingers, in everyday life duodenalized system. Figures 0–9 are used as is, and 10 and 11 are denoted by ~ and ≈ .

Here we learn that it’s not enough to use \d for numbers — you need to use [0-9~≈] .

The post office number in the composition has either 3 digits in a row, or 4, divided into 2 groups of 2 digits with a minus sign. Examples: 300 , 44-99 .

Thus, the numbers of post offices correspond to the group ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) .

Sometimes residents send letters to the municipality of demand. In this case, there is no address: only the municipality and the name of the addressee.

We understand, remember and take into account in the assembly of the final function that the district and the post office may be absent at the same time.

It's funny, but people on the planet are called only six names and nine surnames. Names: Shob, Reb, Mob, Xiang, Ryan, Man. Surnames: Shyo, Ryo, Mo, Xia, Rya, Ma, Xiu, Ryu, Mu. Residents on this planet are not dreamers.

This is the last part of the condition. Here, another simple group was needed (||||||||) (|||||) or its shorter analogue ([][]|[]) ([C]|[]||) .

For simplicity, we save groups to variables and use them in the final regular expression.

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

Task 2. Code in which there is an error

Condition

During the day, the development team made several new features. But during the preparation of the release, merge conflicts occurred, and after their resolution, the layout was dispersed. It is urgent to get rid of errors due to the minimum number of fixes in the code so that the release has time to get into production.

You are provided with an HTML page with broken styles and a PNG layout (with the expected result). It is necessary to correct the errors so that the result when viewing in Chrome begins to coincide with the original screenshot. Send the corrected page as a solution to the problem.

HTML page with broken styles. Layout:

Parsing

In this task, we tried to imitate the situation that Yandex developers regularly encounter: in a huge code base to find the very few simple lines of code that, if corrected, lead to the desired result. That is, the difficulty was not to write the code, but to understand exactly where to write it (or delete it).

We took the real code of search results and made literally a few edits that destroyed the layout. The competitors had less than an hour to sort out approximately 250 kilobytes of typesetting and bring the code to the state corresponding to the layout.

It is clear that the time limit for the competition did not allow to read the entire code, so participants should use the developer tools in the browser.

To correct one of the four options for the assignment, the following changes were sufficient:

  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'] { 

  height: auto; 

  } 

  -.search2__button .suggest2-form__button: nth-child (1) { 

  - background: # ff0! important; 

  -} 

  - 

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

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

  / * Positioned relative to input__box. 

  @@ -744.10 +740.6 @@ 

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

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

  background-size: 16px; 

  @@ -857.6 +849.7 @@ 

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

  background-color: # f2cf46; 

  } 

  .websearch-button__text: before { 

  + position: absolute; 

  top: -6px; 

  right: -9px; 

  width: 0; 

  @@ -866.8 +859.6 @@ 

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

  border-style: solid; 

  border-color: rgba (255,219,76,0); 

  border-left-color: inherit; 

  - position: relative; 

  - z-index: -1000; 

  } 

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

  @@ -1349.6 +1340.7 @@ 

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

  font-size: 14px; 

  line-height: 40px; 

  position: relative; 

  + display: inline-block; 

  height: auto; 

  padding: 0; 

  vertical-align: middle; 

Task 3. A picture with a given variation

Condition

Designer designed the logo. It will need to be used in a variety of conditions. To make this as convenient as possible, roll it using a single HTML element on pure CSS.

Use pictures (even through data: uri) is impossible.

Parsing

Since the task was to use only one div, all that we have is a div itself and the pseudo-elements :: before and :: after.

The picture on the layout, fortunately, consists of just three areas of different colors. We make our own background for each available element, correctly position and round the corners. There is a shadow on the gray area of ​​the layout - we make it using a gradient.

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

Task 4

Condition

Petya works as a senior coder in the newspaper Moscow Fronder. For the layout of the newspaper, Peter uses a stack of web technologies. The most difficult task that Petya faced is the layout of headlines in newspaper articles: the columns of the newspaper in each issue have different widths, and the headings are different font and different number of characters.

Petya needs to choose his own font size for each title so that the font size is maximum, but the entire text of the title fits into the space allotted to it.

Help Petya: implement the calcFontSize function, which will allow you to enter the transferred text into a container so that it fits into the entire container and has the maximum possible size. If this fails, then the solution should return null. The maximum length of an input line is 100 characters. Input string cannot be empty. Your solution should contain the entire function code and should not use external dependencies so that Petya could copy it into his project and call it in his code.

We will check how optimally your solution works and penalize it if it performs too many DOM manipulations.

Parsing

The first thing to do is to learn how to determine whether the text fits into the container, given that the text in the container can take several lines. The easiest way to do this is to use the element.getBoundingClientRect () function, which allows you to get the dimensions of the element.

You can draw text with a separate span-element inside the container, and check whether the width or height of this element is larger than the container's dimensions. If yes, then the text does not fit in the container.

Next you should check the boundary conditions. If the text does not fit into the container even with the minimum font size - it means that it can not be entered. If the text fits with the maximum allowed size - the correct answer is max. In other cases, the desired font size is somewhere in the range [min, max].

To find a solution, you need to go through the entire gap and find a font-size value in which the text is placed in the container, but if you increase it by 1 –– it will no longer fit.

You can do this with a simple for loop over the [min, max] range, but the solution will do a lot of checks and page redraws — at least one for each value you check in the range. The algorithmic complexity of such a solution will be linear.

To minimize the number of checks and get the solution working for O (log n), you need to use a binary search algorithm. The idea of ​​the algorithm is that at each iteration of the search, the range of values ​​is divided into two halves, and the search continues recursively in the half in which the solution is located. The search will end when the range collapses to one value. More information about the binary search algorithm can be found in an article on Wikipedia .

We checked the algorithmic complexity of the solution with the help of MutationObserver : we put it on the page and calculated how many mutations the DOM makes a decision in the search for an answer. For some tests, the number of mutations was strictly limited from above so that only a solution based on a binary search could pass this restriction.

To get the full score for the task, you also had to carefully check different boundary conditions (matching min and max, an empty line of text at the entrance) and provide several conditions for the environment in which the code runs (for example, fixed with an important font-size in the CSS page ).

Task 5. Communication difficulties

In each of the qualification options there was a task where an HTML page with some kind of interface was offered as input. The tasks had a different legend, but they all boiled down to the fact that it was necessary to extract some data from the page and, using this data, to somehow interact with the interface.

Let us analyze the solution to one of the tasks in this series, which was called “Communication Difficulties”.

Condition

Horse Adolf loves to talk with friends on the phone. Unfortunately, this rarely happens. Every time Adolf wants to call, it takes him more than an hour to dial a friend’s number. This is because it is very difficult for him to hit his thick hooves on the right keys.

Fortunately, Adolf’s phone supports javascript. Please write a program that dials Adolf's friends' phone numbers by clicking on the keyboard. All the necessary numbers are written in a notebook. Unhappy horse will be very grateful to you!

Parsing

Here is the page that was offered as input:



The first part of the solution is retrieving the data.
Each of the digits of the phone number is set by the image through background-image. At the same time, during the test, the numbers are dynamically substituted. If you open the debugger in the browser and look at the DOM-tree of the page, you will notice that on each DOM element there are clear classes:

 <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 this case, it was enough just to create a dictionary, extract CSS classes and convert them into a string with a number according to the dictionary, excluding separators (CSS class separator). For example:

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

As a result, we obtain the following array: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].

The second part of the solution is to interact with the interface.
At this stage, we already have an array with all the digits of the number, and we need to understand which buttons on the keyboard correspond to which digit. If we look at the HTML code, we will see that there are no special classes-hints denoting the number on the keyboard:

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

One could simply manually create another dictionary by index, but there is an easier way. If you look closely at the styles in the web inspector, you can see that the number on the button is set via the CSS content property for the: before pseudo-element. For example, for the “3” key, the styles look like this:

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

To get the value of this property, we use the window.getComputedStyle method:

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

As a result, we will get an object, where the keys on the buttons will be the keys (digit or “call”), and the values ​​will be DOM nodes.

It only remains to take values ​​from the first array (phoneNumber), walk through them and click the corresponding buttons using our keys dictionary:

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

Please note: before dialing, we add the call value to the end of the array. This is required by the conditions of the problem, because if you dial the number and do not press the "call", the solution will not pass the test.

Another feature is asynchronous clicking on the keyboard buttons. If the time interval between key presses when dialing a number is less than 50 ms, then this solution will also not pass the test. This feature was not explicitly described in the conditions of the problem, and we expected the participant to find out by reading the source code of the page. By the way, in the source code of the participants was waiting for a small surprise. ;)

Task 6

Condition

Fedor Rakushkin administers the task management system in his company. The server hosting the system has failed (and Fedor did not backups).

The memory of the server has a cache of structures describing tasks, executors and observers, as well as the relationship between these structures. In addition, the cached link to the last structure that was changed has been saved.

Help Fedor write a function that can restore all possible connections of tasks and users and save them into a document in Markdown format, from which Fedor will then restore the database on the new server.

Markdown document should have the following format:

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

The list of tasks, the list of executors in the task, the list of observers in the task, the list of users and the list of tasks that the user does should be sorted lexicographically.

Description of the structures in the cache

Users are stored in the cache in the form of a structure like `User`:

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

Tasks are stored in a cache in the form of a structure like `Task`:

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

Solution template

Your solution must contain a CommonJS module that exports a function corresponding to the following signature:

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

Examples

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

If you display a link to `lastEdited`, you get the following structure:

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

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

— . , , , .

-.

:
— 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.

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 . For example:









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.

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

Condition

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

Notes

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

.