Фронтенд, алгоритмы и опоссум Фридрих. Разбираем задачи конкурса Яндекса

Этим постом мы завершаем серию публикаций о конкурсах Яндекс.Блиц в 2018 году. Надеемся, что вам довелось поучаствовать или хотя бы посмотреть, какие приближенные к продакшену задачи мы предлагаем. Последний контест был посвящен применению алгоритмов во фронтенде. Сегодня мы публикуем подробные разборы 12 задач: первые 6 из них предлагались в квалификационном раунде, а задачи 7–12 — в финале. Мы постарались объяснить, как формировались условия, на какие навыки мы обращали внимание. Спасибо всем участникам за проявленный интерес!

Задача 1

Первая задача должна была быть разминочной, на 20 минут, и мы решили сделать ее условие таким, чтобы она легко решалась с помощью регулярных выражений.

Все варианты задания построены похожим образом — есть разбивка на пункты, каждый из которых может быть представлен группой в итоговом регулярном выражении.

Рассмотрим один из вариантов: Почтамт.

Условие

На планете Джопан-14-53 местные жители хотят отправлять друг другу письма, но роботы-почтовые голуби, которые должны их доставлять, путаются в адресах. Вам предстоит научить их разбирать письма и проверять их на валидность.

Структура базовой части адреса состоит из региона, муниципалитета, имени и фамилии адресата. Муниципалитет может делиться на округа и почтовые отделения. Все части разделены знаком запятой ,.

Названия регионов, муниципалитетов и округов — слова, первая буква в каждом слове — большая, остальные — маленькие. Возможны названия из двух слов, разделенных пробелом или знаком минуса. В каждом слове от трех до восьми букв А-Я.

У жителей на руках по 6 пальцев, в быту двенадцатеричная система. Цифры 0–9 используются как есть, а 10 и 11 обозначаются знаками ~ и ≈.

Номер почтового отделения в составе имеет либо 3 цифры подряд, либо 4, разделенные на 2 группы по 2 цифры знаком минуса. Примеры: 300, 44-99.

Иногда жители отправляют письма в муниципалитет до востребования. В этом случае адреса нет: только муниципалитет и имя адресата.

Смешно, но людей на планете зовут всего шестью именами и девятью фамилиями. Имена: Сёб, Рёб, Моб, Сян, Рян, Ман. Фамилии: Сё, Рё, Мо, Ся, Ря, Ма, Сю, Рю, Му. Жители на этой планете совсем не фантазёры.

Разбор

Структура базовой части адреса состоит из региона, муниципалитета, имени и фамилии адресата. Муниципалитет может делиться на округа и почтовые отделения. Все части разделены знаком запятой ,.

Из первых абзацев узнаём, как указываются регион, муниципалитет, округ, почтовое отделение, имя и фамилия, и в каком порядке они должны следовать в тестируемой строке.

Названия регионов, муниципалитетов и округов — слова, первая буква в каждом слове — большая, остальные — маленькие. Возможны названия из двух слов, разделенных пробелом или знаком минуса. В каждом слове от трех до восьми букв А-Я.

Из этого абзаца понятно, что словам соответствует группа ([А-ЯЁ][а-яё]{2,7}). А названиям, соответственно, ([А-ЯЁ][а-яё]{2,7}(?:[- ][А-ЯЁ][а-яё]{2,7})).

У жителей на руках по 6 пальцев, в быту двенадцатеричная система. Цифры 0–9 используются как есть, а 10 и 11 обозначаются знаками ~ и ≈.

Здесь мы узнаём, что для цифр недостаточно использовать d — нужно использовать [0-9~≈].

Номер почтового отделения в составе имеет либо 3 цифры подряд, либо 4, разделенные на 2 группы по 2 цифры знаком минуса. Примеры: 300, 44-99.

Таким образом, номерам почтовых отделений сответствует группа ([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}).

Иногда жители отправляют письма в муниципалитет до востребования. В этом случае адреса нет: только муниципалитет и имя адресата.

Понимаем, запоминаем и учитываем в сборке итоговой функции, что округ и почтовое отделение могут одновременно отсутствовать.

Смешно, но людей на планете зовут всего шестью именами и девятью фамилиями. Имена: Сёб, Рёб, Моб, Сян, Рян, Ман. Фамилии: Сё, Рё, Мо, Ся, Ря, Ма, Сю, Рю, Му. Жители на этой планете совсем не фантазёры.

Это последняя часть условия. Здесь нужна была еще одна простая группа (Сё|Рё|Мо|Ся|Ря|Ма|Сю|Рю|Му) (Сёб|Рёб|Моб|Сян|Рян|Ман) или её более короткий аналог ([СР][ёяю]|М[оау]) ([CР]ёб|[СР]ян|Моб|Ман).

Для простоты сохраняем группы в переменные и используем их в итоговом регулярном выражении.

const w = '[А-ЯЁ][а-яё]{2,7}'; // word
const d = '[0-9~≈]';           // digit

const name = `(?:${w}(?:[- ]${w})?)`;
const number = `(?:${d}{3}|${d}{2}-${d}{2})`;
const person = '(?:[СР][ёяю]|М[оау]) (?:Сёб|Рёб|Моб|Сян|Рян|Ман)';

// регион, муниципалитет, (округ, почтовое отделение, )?имя фамилия
const re = new RegExp(`^(${name}),\s*(${name}),\s*(?:(${name}),\s*(${number}),\s*)?(${person})$`);

module.exports = function(str) {
    // Если пришло совсем не то
    if (typeof str !== 'string') return null;

    const res = str.match(re);

    // Если пришло что-то не то
    if (!res) return null;

    // Иначе все хорошо
    // Только отрезаем первый элемент, в котором полное совпадение
    return res.slice(1);
};

Задача 2. Код, в котором есть ошибка

Условие

За день команда разработки сделала несколько новых фич. Но при подготовке релиза произошли мерж-конфликты, и после их разрешения верстка разъехалась. Необходимо срочно избавиться от ошибок за счет минимального количеста исправлений в коде, чтобы релиз успел попасть в продакшен.

Вам предоставляется HTML-страница с поломанными стилями и макет в формате PNG (с ожидаемым результатом). Необходимо исправить ошибки, чтобы результат при просмотре в Chrome стал совпадать с оригинальным скриншотом. Исправленную страницу отправьте как решение задачи.

HTML-страница с поломанными стилями. Макет:

Разбор

В этом задании мы постарались сымитировать ситуацию, с которой регулярно сталкиваются разработчики Яндекса: в огромной кодовой базе найти те самые несколько простых строк кода, исправление которых приводит к нужному результату. То есть сложность состояла не в том, чтобы написать код, а в том, чтобы понять, где именно его написать (или удалить).

Мы взяли реальный код поисковой выдачи и внесли буквально несколько правок, которые развалили верстку. У участников соревнования было меньше часа, чтобы разобраться примерно с 250 килобайтами верстки и привести код к состоянию, соответствующему макету.

Понятно, что ограничение времени на соревнование не позволяло прочитать весь код, поэтому участникам следовало воспользоваться инструментами для разработчиков в браузере.

Для исправления одного из четырех вариантов задания было достаточно следующих изменений:

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

 /* Позиционируется относительно 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;

Задача 3. Картинка с заданной вариативностью

Условие

Дизайнер разработал логотип. Его потребуется использовать в самых разных условиях. Чтобы это было максимально удобно, сверстайте его с помощью одного HTML-элемента на чистом CSS.

Использовать картинки (даже через data:uri) нельзя.

Разбор

Так как задание состояло в том, чтобы пользоваться только одним div, то всё, чем мы распологаем, — это сам div и псевдоэлементы ::before и ::after.

Картинка на макете, к счастью, состоит как раз из трех областей разного цвета. Делаем для каждого доступного элемента свой фон, правильно позиционируем и скругляем уголки. На серой области макета есть тень — делаем ее с помощью градиента.

div {
    background: #0C0C0C;
    border-radius: 10px;
    position: relative;
}	

div:before {
    border-radius: 9px 9px 0 0;
    position: absolute;
    width: 100%;
    height: 50%;
    background: #F8E34B;
    content: '';
}

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

Задача 4

Условие

Петя работает старшим верстальщиком в газете «Московский фронтендер». Для верстки газеты Петя использует стек веб-технологий. Самая сложная задача, с которой столкнулся Петя, — это верстка заголовков в газетных статьях: колонки газеты в каждом выпуске имеют разную ширину, а заголовки — разный шрифт и разное количество символов.

Пете нужно подбирать свой размер шрифта для каждого заголовка так, чтобы размер шрифта был максимальным, но при этом весь текст заголовка влез в отведенное ему место.

Помогите Пете: реализуйте функцию calcFontSize, которая позволит вписать переданный текст в контейнер таким образом, чтобы он влезал в контейнер целиком и имел максимально возможный размер. Если же это не удается сделать, то решение должно возвращать null. Максимальная длина строки на вход — 100 символов. Входная строка не может быть пустой. Ваше решение должно содержать код функции целиком и не должно использовать внешние зависимости, чтобы Петя мог скопировать ее в свой проект и вызывать у себя в коде.

Мы будем проверять, насколько оптимально работает ваше решение, и штрафовать его, если оно производит слишком большое количество манипуляций с DOM.

Разбор

Первое, что нужно сделать, — это научиться определять, вписывается ли текст в контейнер с учетом того, что текст в контейнере может занимать несколько строк. Самый простой способ сделать это — воспользоваться функцией element.getBoundingClientRect(), которая позволяет получить размеры элемента.

Можно отрисовать текст отдельным span-элементом внутри контейнера, и проверить, превышает ли ширина или высота этого элемента размеры контейнера. Если да, значит, текст не помещается в контейнер.

Далее следует проверить граничные условия. Если текст не влезает в контейнер даже с минимальным размером шрифта — значит, его нельзя вписать. Если текст влезает с максимально разрешенным размером — правильным ответом будет max. В иных случаях искомый размер шрифта находится где-то в промежутке [min, max].

Для поиска решения нужно перебрать весь этот промежуток и найти такое значение font-size, при котором текст помещается в контейнер, но если увеличить его на 1 –—перестанет помещаться.

Можно сделать это простым циклом for по диапазону [min, max], но при этом решение будет делать очень много проверок и перерисовок страницы — как минимум по одной для каждого проверяемого значения в диапазоне. Алгоритмическая сложность такого решения будет линейной.

Чтобы минимизировать число проверок и получить решение, работающее за O(log n), нужно воспользоваться алгоритмом бинарного поиска. Идея алгоритма состоит в том, что на каждой итерации поиска диапазон значений делится на две половины, и поиск рекурсивно продолжается в той половине, в которой находится решение. Поиск закончится, когда диапазон схлопнется до одного значения. Подробнее о алгоритме бинарного поиска можно прочитать в статье в Википедии.

Алгоритмическую сложность решения мы проверяли с помощью MutationObserver: мы помещали его на страницу и подсчитывали, сколько мутаций DOM делает решение в процессе поиска ответа. Для части тестов число мутаций было жестко ограничено сверху таким образом, чтобы пройти это ограничение могло только решение, основанное на бинарном поиске.

Чтобы получить полный балл за задачу, также нужно было аккуратно проверить разные граничные условия (совпадающие min и max, пустая строка текста на входе) и предусмотреть несколько условий окружения, в котором запускается код (например, фиксированный с !important font-size в CSS страницы).

Задача 5. Трудности общения

В каждом из вариантов квалификации была задача, где в качестве входных данных предлагалась HTML-страничка с каким-то интерфейсом. У заданий была разная легенда, но все они сводились к тому, что надо было извлечь какие-то данные со страницы и, используя эти данные, как-то повзаимодействовать с интерфейсом.

Разберем решение одной из задач этой серии, которая называлась «Трудности общения».

Условие

Конь Адольф любит говорить с друзьями по телефону. К сожалению, это происходит редко. Каждый раз, когда Адольф хочет позвонить, у него уходит больше часа, чтобы набрать номер друга. Всё потому, что ему очень трудно попасть своими толстыми копытами по нужным клавишам.

К счастью, телефон Адольфа поддерживает JavaScript. Пожалуйста, напишите программу, которая набирает телефоны друзей Адольфа, кликая по клавиатуре. Все нужные номера записаны в блокноте. Несчастный конь будет вам очень благодарен!

Разбор

Вот как выглядит страничка, которая предлагалась в качестве входных данных:

Первая часть решения — извлекаем данные
Каждая из цифр номера телефона задается картинкой через background-image. При этом во время проверки цифры подставляются динамически. Если открыть отладчик в браузере и посмотреть на DOM-дерево страницы, то вы заметите, что на каждом DOM-элементе используются понятные классы:

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

В данном случае достаточно было просто создать словарь, извлечь CSS-классы и преобразовать их в строку с номером по словарю, исключив разделители (CSS-класс separator). Например, так:

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

В результате получим такой массив: [9, 8, 5, 4, 1, 2, 8, 0, 9, 0].

Вторая часть решения — повзаимодействовать с интерфейсом
На этом этапе у нас уже есть массив со всеми цифрами номера, и надо понять, какие кнопки на клавиатуре какой цифре соответствуют. Если мы посмотрим на HTML-код, то увидим, что никаких специальных классов-подсказок, обозначающих цифру, на клавиатуре нет:

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

Можно было бы просто вручную создать еще один словарь по индексу, но есть способ проще. Если посмотреть внимательно на стили в веб-инспекторе, то можно заметить, что цифра на кнопке задается через CSS-свойство content для псевдоэлемента :before. Например, для клавиши «3» стили выглядят так:

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

Чтобы получить значение этого свойства, воспользуемся методом window.getComputedStyle:

const keys = Array.from(document.querySelectorAll('.game .key')).reduce((res, elem) => {
    const key = window
	// Получаем CSSStyleDeclaration для псевдо-элемента
	.getComputedStyle(elem, ':before')
	// Получаем значение свойства
	.getPropertyValue('content')
	// Значение будет вместе с кавычками, поэтому не забываем убрать их
	.replace(/"/g, '');
    res[key] = elem;
    return res;
}, {});

В результате мы получим объект, где в качестве ключей будут выступать тексты на кнопках (цифра или «call»), а в качестве значений — DOM-узлы.

Остается только взять значения из первого массива (phoneNumber), пройтись по ним и прокликать соответствующие кнопки, используя наш словарь keys:

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

Обратите внимание: прежде чем сделать набор номера, мы добавляем в конец массива значение call. Этого требуют условия задачи, так как если набрать номер и не нажать «вызов», то решение не пройдет проверки.

Другая особенность — асинхронное нажатие на кнопки клавиатуры. Если временной интервал между нажатиями на клавиши при наборе номера меньше 50 мс, то такое решение тоже не пройдет проверки. Эта особенность не была описана в условиях к задаче явно, и мы ожидали, что участник выяснит это, прочитав исходный код страницы. Кстати, в исходном коде участников ждал небольшой сюрприз. ;)

Задача 6

Условие

Фёдор Ракушкин администрирует систему управления задач в своей компании. Сервер, на котором размещается система, вышел из строя (а бекапов Фёдор не делал).

В памяти сервера остался кэш структур, описывающих задачи, исполнителей и наблюдателей, а также взаимосвязи между этими структурами. Кроме того, сохранилась ссылка в кэше на последнюю структуру, которая была изменена.

Помогите Фёдору написать функцию, которая сможет восстановить все возможные связи задач и пользователей и сохранить их в документ в формате Markdown, из которого Фёдор затем восстановит базу данных на новом сервере.

Markdown-документ должен иметь следующий формат:

## Задачи
	
- %Название задачи 1%, делает %username1%, наблюдают: %username2%
- %Название задачи 2%, делает %username1%, наблюдают: %username2%, %username3%
- %Название задачи 3%, делает %username1% // у задачи нет наблюдателей
- %Название задачи 4%, наблюдают: %username1%, %username2%  // у задачи нет исполнителя
- %Название задачи 5% // у задачи нет исполнителя и наблюдателей
- %Название задачи 6%, наблюдают: %username1%
  - %Название подзадачи 1%, делает %username1% // подзадача
  - %Название подзадачи 2%
    - %Название подзадачи 3%, наблюдают: %username1%

## Пользователи
- %username1%
  * %Название задачи 1% // задачи, которые делает пользователь
  * %Название задачи 2%
  * %Название задачи 3%
  * %Название подзадачи 1%
- %username2%
  * %Название задачи 3%

Список задач, список исполнителей в задаче, список наблюдателей в задаче, список пользователей и список задач, которые делает пользователь, должны быть отсортированы лексикографически.

Описание структур в кэше

Пользователи хранятся в кэше в виде структуры типа `User`:

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

Задачи хранятся в кэше в виде структуры типа `Task`:

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

Шаблон решения

Ваше решение должно содержать CommonJS-модуль, экспортирующий функцию, соответствующую следующей сигнатуре:

/**
 * @param {User|Task} data - последний отредактированный объект в кэше,
 * из которого нужно восстановить все возможные данные (User или Task)
 * @return {string}
 */
module.exports = function (data) {
    // ваш код
    return '…';
}

Примеры

// Пользователи в памяти
const User1 = { type: 'user', login: 'fedor', tasks: [], spectating: [] };
const User2 = { type: 'user', login: 'arkady', tasks: [], spectating: [] };
									
// Задачи в памяти
const Task1 = { type: 'task', title: 'Do something', assignee: null, spectators: [], subtasks: [], parent: null };
const Task2 = { type: 'task', title: 'Something else', assignee: null, spectators: [], subtasks: [], parent: null };
const Task3 = { type: 'task', title: 'Sub task', assignee: null, spectators: [], subtasks: [], parent: null };

// И связи между ними:
// Первую задачу делает первый пользователь
Task1.assignee = User1;
User1.tasks.push(Task1);
// ...а наблюдает за ней — второй
Task1.spectators.push(User2);
User2.spectating.push(Task1);

// Вторую задачу пока никто не делает,
// но первый пользователь за ней наблюдает
Task2.spectators.push(User1);
User1.spectating.push(Task2);

// Третья задача является подзадачей второй
Task3.parent = Task2;
Task2.subtasks.push(Task3);

// Известно, что последняя измененная структура — задача 3
const lastEdited = Task3;

Если вывести ссылку на `lastEdited` — получается такая структура:

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

На выходе должен получиться текст в формате Markdown со всеми найденными задачами и пользователями, отсортированными в алфавитном порядке:

## Задачи

- Do something, делает fedor, наблюдают: arkady
- Something else, наблюдают: fedor
  - Sub task

## Пользователи

- arkady
- fedor
  * Do something

Разбор

Решение задачи состояло в том, чтобы восстановить данные графа по ссылке и затем сериализовать его в требуемом формате.

Это можно сделать, например, через обход графа в ширину и в глубину. Напишем код для обхода и соберем все данные, которые нужно будет вывести:

/**
 * Абстрактный обходчик, подходящий для всех вариантов
 * @param {{ref: object, visited: ?boolean}} ctx
 * @param {object} handlers — обработчики для каждого типа
 */
function traverse(ctx, handlers) {
    // Не падаем в случае, если ctx.ref пустой, — например, в случае вызова с task.parent
    if (!ctx.ref) {
        return;
    }		

    // Предотвращаем обход узлов, сохраняя все посещенные узлы, используя контекст и набор уже посещенных
    const visited = ctx.visited || new Set();
    if (visited.has(ctx.ref)) {
        return;
    }
    visited.add(ctx.ref);

    // Вызываем обработчик для исходного типа узла
    handlers[ctx.ref.type](ctx.ref, goDeeper);

    // Промежуточная функция, позволяющая рекурсивно пойти глубже в обработчиках
    function goDeeper(subrefs) {
        // Запускаем для каждого подузла нужный обработчик
        for (const subref of [].concat(subrefs)) {
            traverse({ visited, ref: subref }, handlers);
        }
    }
}

// Коллекции для пользователей и задач
const users = [];
const tasks = [];

// ref в начале — ссылка на переданный узел
traverse({ ref }, {
    user(user, deeper) {
        users.push(user);
        deeper(user.tasks); // to task.assignee
        deeper(user.spectating); // to task.spectators
    },
    task(task, deeper) {
        tasks.push(task);
        deeper(task.assignee); // to user.tasks
        deeper(task.spectators); // to user.spectating
        deeper(task.parent); // to task.subtasks
        deeper(task.subtasks); // to task.parent
    }
);

В итоге получилась коллекция пользователей и задач. Далее, согласно условию задачи, нужно было отсортировать коллекции…

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

… после чего — вывести их в нужном формате:

// форматирует строку задачи
const taskLine = t => `${
    t.title
}${	
    t.assignee ? `, делает ${t.assignee.login}` : ''
}${
    t.spectators.length ? `, наблюдают: ${t.spectators.map(u => u.login).join(', ')}` : ''
}`;

function renderTasks (parent = null, indent = 0) {
    return tasks
        .filter(t => t.parent === parent) 
        .map(t => [
            'n',
            ' '.repeat(indent), // отбивка
            '- ', taskLine(t), // вывод названия задачи
            t.subtasks.length ? printTasks(t, indent + 2) : '' // подзадачи рекурсивно
        ].join(''))
        .join('');
}

function renderUsers () {
    return ${users.map(u => `n- ${u.login}${
        u.tasks.map(t => `n  * ${t.title}`).join('')
    }`).join('')}
}

const result =  `
## Задачи
${renderTasks()}
## Пользователи
${renderUsers()}
`.trim();

Задача 7. Здесь могла быть ваша реклама

Условие

Представьте, что вы работаете в Яндексе и верстаете баннеры для Яндекс.Директа. Вы получили задание доработать шаблон баннера:

Недавно разработчики бэкенда изменили формат данных, которые приходят с сервера. Максимальный размер заголовка увеличился на несколько символов, и теперь длинные заголовки не помещаются в отведенное для них место между левой границей баннера и кнопкой «Перейти».

Дизайнер решил перенести кнопку в правый нижний угол баннера.

Исправьте шаблон баннера, чтобы он соответствовал новому макету. Нужно, чтобы текст обтекал кнопку слева и сверху. Текст баннера подставляется в шаблон динамически и может быть любым. Баннер всегда имеет одинаковый размер. В шаблоне можно использовать только HTML и CSS. Использовать JavaScript и картинки нельзя.

Примечательно, что это одна из реальных задач, которая когда-то возникла при верстке рекламных баннеров. Если изучить сайты РСЯ, можно встретить похожий баннер и подсмотреть там решение.

Разбор

Для решения задачи нужно написать всего несколько строчек HTML/CSS, но придумать, что написать, не так-то просто.

Единственное средство CSS, влияющее на обтекание блоков текстом, — это float, но его недостаточно для решения задачи. Свойство float влияет на элементы, которые идут после текущего, а в задании нужно сделать обтекание текстом сверху.

Первый вариант решения — добавить над кнопкой распорку нулевой ширины, которая сдвинет кнопку вниз. (Пример на jsfiddle.net.)

Еще один вариант — сдвинуть весь контент родителя вниз при помощи свойства padding-top, а после этого вложенный блок с текстом сдвинуть на такое же расстояние вверх при помощи свойства margin-top (задать отрицательное значение). В этом случае не понадобится дополнительный DOM-элемент (распорка). (Пример.)

Задача 8. Сверстать макет

Условие

Ефросинья работает HTML-верстальщиком. Дизайнер прислал ей очередной макет, который нужно сверстать. Ефросинья еще не закончила предыдущую задачу, а верстка нового макета нужна очень срочно. Помогите Ефросинье сделать работу вовремя.

Верстка должна в точности соответствовать макету по этой ссылке (pixel perfect). В верстке нельзя использовать изображения.

Мы хотели вызвать у людей яркие эмоции. Поэтому сформулировали условие как рутинную задачу верстальщика и предложили необычный макет.

На макете не элементы интерфейса, как могло показаться из условия, а рисунок из линий. Линий довольно много, и их пересечения трудно одновременно удержать в голове. Мы старались, чтобы макет выглядел абсурдно: на нем изображена какая-то неведомая абракадабра, но проставлены размеры, как это делают дизайнеры.

Кажется, нам удалось достичь цели. У всех, кому мы показывали задачу, макет вызывал удивление.

Разбор

Так как по условию задачи в верстке нельзя было использовать картинки, единственный способ ее решить — сверстать фигуру блочными элементами. Средства для рисования — CSS-свойства border (цвет и толщина), background (фоновый цвет или градиенты с резкими границами) и box-shadow (тени с резкими границами и отступами).

Из-за большого количества линий на макете вариант решения «в лоб» (сверстать каждую линию блочным элементом с фоном и абсолютным позиционированием) занял бы много времени. Мы рассчитывали, что участники выделят и сверстают повторяющиеся фрагменты макета, а потом скомбинируют их для получения финального изображения.

Пример решения — считать, что макет состоит из квадратных фрагментов 70 на 70 пикселей. Фрагменты могут быть трех видов: угловой, боковой и пустой. Написав CSS-классы для каждого из этих фрагментов, а также CSS-классы для их поворота, можно легко составить из них нужное изображение.

Еще один вариант решения — собрать изображение из больших квадратов 210 на 210 пикселей, перекрывая места их пересечения маленькими полосатыми квадратами 70 на 70 пикселей.

Задача 9. Злоключения Адольфа

Условие

Конь Адольф — владелец телефона с пользовательским интерфейсом, сделанным на веб-технологиях. Адольф научился набирать номера на телефоне с помощью программы на JavaScript, которая нажимает кнопки интерфейса в нужном порядке. Для набора номера ему больше не нужно мучиться, пытаясь попасть в кнопки копытами.

Но случилась беда: от частых разговоров телефон перегрелся и сгорел.

Адольф купил новый аппарат, но оказалось, что у него другая клавиатура. Программа набора с ней не работает.

Постоянно переписывать программу набора Адольфу не хотелось, ограничивать себя в беседах — тоже. Помочь бедному Адольфу вызвался его друг — опоссум Фридрих. Он рассказал Адольфу, что производитель телефонов поддерживает JavaScript API и обещает сохранение обратной совместимости. Чтобы упростить набор номеров, Фридрих написал веб-сервер, управляющий телефоном, и добавил функцию быстрого набора.
Быстрый набор позволяет хранить в телефоне до 10 номеров и звонить, отправляя на телефон HTTP-запрос с цифрой нужного номера.

Адольф поблагодарил Фридриха и с радостью начал пользоваться новой функцией — он снова мог звонить друзьям. Но вскоре конь заметил, что иногда записанные номера исчезают из телефона, а сам аппарат часто зависает, и его приходится перезагружать.

Помогите коню Адольфу убрать ошибки из кода веб-сервера.

Примечания:
— API поставляется npm-пакетом @yandex-blitz/phone.
— Документация к API.
— Код веб-сервера, написанный Фридрихом: task.js.
— Исправлять и тестировать код веб-сервера удобно в runkit-блокноте.

В качестве решения предоставьте файл с кодом веб-сервера, в котором исправлены ошибки.

Разбор

Первые два красных теста исправляются довольно тривиально — возвращаем потерянный в обработчике GET-запросов return и пишем обработку ошибок для вызова connect.


С последним тестом чуть сложнее: ошибка происходит из-за асинхронности. Если два запроса на запись приходят одновременно, в обработчиках каждого из них считается текущее состояние хранилища, а потом хранилище будет дважды перезаписано. В итоге в нем останется информация только о последнем записанном номере.


Чтобы этого избежать, можно упорядочить обработку запросов: не исполнять их сразу, а отправлять в очередь и исполнять по одному. Заведем очередь и функцию ее обработки:

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

        fn().then(() => {
            processQueue();
        });
    }
}

Чтобы ограничить количество исполняемых одновременно записей, заведем флаг «происходит ли сейчас обработка элемента».

const writeQueue = [];
let isWriteInProgress = false;
	
const processQueue = () => {
    if (isWriteInProgress) {
        return;
    }

    if (writeQueue.length) {
        isWriteInProgress = true;

        const fn = writeQueue.shift();

        fn().then(() => {
            isWriteInProgress = false;
            processQueue();
        });
    }
}

Наконец, в обработчике POST-запросов на запись номеров в хранилище будем добавлять элементы в очередь. На случай, если очередь была пустой, будем запускать обработку очереди.

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

Полный код решения:

const express = require('express');
const { BEEP_CODES } = require('@yandex-blitz/phone');
				
const writeQueue = [];
let isWriteInProgress = false;

const processQueue = () => {
    if (isWriteInProgress) {
        return;
    }

    if (writeQueue.length) {
        isWriteInProgress = true;

        const fn = writeQueue.shift();

        fn().then(() => {
            isWriteInProgress = false;
            processQueue();
        });
    }
}

const makeWriteJob = (phone, req, res) => {
    return () => {
        return phone.getData()
            .then(value => {
                const speeddialDict = JSON.parse(value);

                speeddialDict[req.params.digit] = Number(req.params.phonenumber);

                return phone
                    .setData(JSON.stringify(speeddialDict))
                    .then(() => phone.beep(BEEP_CODES.SUCCESS))
                    .then(() => {
                        res.sendStatus(200);
                    })
            })
            .catch(e => {
                phone.beep(BEEP_CODES.ERROR).then(() => {
                    res.sendStatus(500);
                })
            })
    }
};

const createApp = ({ phone }) => {
    const app = express();

    // звонит по номеру, записанному в «быстром наборе» под цифрой digit
    app.get("/speeddial/:digit", (req, res) => {
        phone.getData().then(value => {
            const speeddialDict = JSON.parse(value);

            return phone.connect()
                .then(async () => {
                    await phone.dial(speeddialDict[req.params.digit]);

                    res.sendStatus(200);
                }, async() => {
                    await phone.beep(BEEP_CODES.FATAL);

                    res.sendStatus(500);
                });
        }).catch(async (e) => {
            await phone.beep(BEEP_CODES.ERROR);

            res.sendStatus(500);
        });
    });

    // записывает в «быстрый набор» под цифру digit номер phonenumber
    app.post("/speeddial/:digit/:phonenumber", (req, res) => {
        writeQueue.push(makeWriteJob(phone, req, res));
        processQueue();
    });

    return app;
};

exports.createApp = createApp;

Задача 10. Лабиринт

Условие

Системный администратор Евгений очень любит свою работу. Но еще больше он любит старые восьмибитные игры, поэтому в свободное время решил сделать игру «Лабиринт».

Правила игры простые:
— Лабиринт состоит из стенок, пустых полей и выхода.
— В лабиринте есть шарик, который может кататься по пустым полям, пока не упрется в стенку.
— Перемещением шарика можно управлять при помощи наклона поля в одну из четырех сторон, при этом шарик будет катиться, пока может.
— Чтобы наклонить поле, надо использовать кнопки управления: ← ↓ ↑ →.
— Когда шарик попадает на клетку выхода — игра закончена, с этого момента он не должен реагировать на кнопки управления.

Евгений с удовольствием бы доделал игру сам, но прямо сейчас в сеть компании, где он работает, попал страшный вирус, и борьба с ним заняла всё его время.

Помогите Евгению дописать игру.

Все карты в наших тестах имеют прямоугольную форму и ограничены по периметру стенками.

Решение должно представлять из себя один HTML-файл (все нужные скрипты и стили должны содержаться внутри).

После того как игра будет проинциализирована, надо вызывать глобальную функцию window.onMazeReady(). Только после этого будет запущено автоматическое тестирование вашего решения. Если вызов функции не произойдет в течение 2 минут, задание считается невыполненным.

Контейнер с игровым полем должен иметь CSS-класс map.

Кнопки управления должны реагировать на событие click и иметь следующие CSS-классы:
— влево — control_direction_left,
— вниз — control_direction_down,
— вверх — control_direction_up,
— вправо — control_direction_right.

CSS-стили для градиента на шарике:

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

Поле наклоняется в каждую из сторон на 25 градусов с центральной перспективой, удаленной на 500 пикселей. Например:

Карта лабиринта доступна в поле window.map типа String. Следующие символы являются специальными:
# — стенка
. — пустое место
o — шарик
x — выход

Каждая строка, содержащая хотя бы один специальный символ, является линией лабиринта, а каждый символ — полем лабиринта. Любые другие символы не имеют значения и должны быть проигнорированы при построении лабиринта.

Например, код вида

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

должен дать такой результат:

Предлагается следующий шаблон решения:

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

Разбор

Это задание было рассчитано на проверку всех навыков (HTML, CSS, JS). В реальной работе одному и тому же человеку часто приходится и верстать, и «оживлять» интерфейс.

Первым шагом надо было правильно измерить размеры и цвета в макете из условия. Мы сознательно не стали давать готовые размеры и стили (за исключением стилей для трансформаций поля), чтобы проверить, насколько хорошо участники смогут добыть эти данные самостоятельно.

Придумывая задание, мы старались выбрать максимально простые геометрические формы, которые бы исключали вариации и позволяли правильно сверстать макет разными способами.

Например, можно было реализовать игровое поле при помощи таблицы:

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

Стили:

.map {
    border: 0;
    border-spacing: 0;
    border-collapse: separate;
    background-color: #ccc;
    transform-style: preserve-3d;
}			

.map__cell {
    box-sizing: border-box;
    border: 1px solid;
    border-color: #9b9b9b #575757 #575757 #9b9b9b;
    width: 30px;
    height: 30px;
    text-align: center;
    vertical-align: middle;
    font-size: 0;
    line-height: 0;
    background-color: #707070;
}

.map__cell_content_ball:after {
    content: '';
    display: inline-block;
    width: 20px;
    height: 20px;
    border-radius: 50%;
    background: radial-gradient(circle at 5px 5px, #eee, #000);
}

.map__cell_content_wall {
    border-width: 4px;
}

.map__cell_content_exit {
    background-color: #000;
    border: 5px solid;
    border-color: #222 #555 #555 #222;
}

Самые сложные стили — для наклонов поля и градиента шарика — можно было взять из описания к задаче.

На следующем шаге надо было сгенерировать игровое поле, используя эту верстку и строку с описанием карты.

Одной из «ловушек» было то, что карта могла содержать незначащие пробельные символы. В задании было явно сказано, что такие символы нужно игнорировать. Например, такие символы могли появиться при использовании строкового литерала:

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

С помощью такой несложной функции можно было преобразовать строку с картой в удобный двумерный массив:

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

Имея такой массив, несложно построить HTML для всего игрового поля:

const CELL_CONTENT = {
    '#': 'wall',
    'o': 'ball',
    '.': 'empty',
    'x': 'exit'
};

function buildGameBoxHtml(map) {
    return `
        <div class="game-box">
            <table class="map map__tilt_none">
                ${map.map(row => `
                    <tr>
                        ${row.map(cell => `
                            <td class="map__cell map__cell_content_${CELL_CONTENT[cell]}"></td>
                        `).join('')}
                    </tr>
                `).join('')}
            </table>
            
            <!-- Кнопки для управления наклоном поля -->
            <div class="controls">
                <button class="control control_direction_left">←</button>
                <button class="control control_direction_down">↓</button>
                <button class="control control_direction_up">↑</button>
                <button class="control control_direction_right">→</button>
            </div>
        </div>
    `;
}

Когда игровое поле готово, остается добавить обработчики нажатия для кнопок управления наклоном поля:

let gameBox = document.querySelector('.game-box');
let map = gameBox.querySelector('.map');

// Используем делегирование событий и добавляем один обработчик только на контейнер
gameBox.addEventListener('click', ({ target }) => {
    // Обрабатываем только клики по контролам
    if (!target.classList.contains('control')) {
        return;
    };
    
    // Получаем направление наклона прямо из класса-модификатора
    const direction = target.className.match(/bcontrol_direction_(w+)/)[1];

    // Наклоняем карту, заменяя соответствующий класс-модификатор
    map.className = map.className.replace(/bmap__tilt_w+/, `map__tilt_${direction}`);
    
    // Получаем клетку, в которой находится шарик
    let ball = map.querySelector('.map__cell_content_ball');
    
    // Вычисляем предположительную следующую клетку для шарика
    let nextBall = getNextCell(map, ball, direction);
    
    // Убираем шарик из предыдущей клетки
    ball.classList.remove('map__cell_content_ball');
    ball.classList.add('map__cell_content_empty');

    // Уточняем следующую клетку для шарика, пока не упремся в стенку или не выкатимся в клетку выхода
    while (
        !nextBall.classList.contains('map__cell_content_wall') &&
        !ball.classList.contains('map__cell_content_exit')
    ) {
        ball = nextBall;
        nextBall = getNextCell(map, ball, direction);
    }

    // Ставим шарик в вычисленную клетку
    ball.classList.remove('map__cell_content_empty');
    ball.classList.add('map__cell_content_ball');
});

const DIRECTIONS = {
    'left': [-1, 0],
    'up': [0, -1],
    'down': [0, 1],
    'right': [1, 0]
};

// Используя DOM API таблиц, находим следующую клетку для определенного направления наклона
function getNextCell(map, cell, direction) {
    const directionDiff = DIRECTIONS[direction];
    return map.rows[cell.parentNode.rowIndex + directionDiff[1]].cells[cell.cellIndex + directionDiff[0]];
}

И самое последнее — надо было не забыть вызвать callback при готовности лабиринта: window.onMazeReady(). Только после этого вызова начинался запуск автотестов для проверки правильности решения.

Мы тестировали каждое решение при помощи скриншотов, сравнивая эталонное изображение с решением. При этом мы допускали, что идеальное попиксельное совпадение почти невозможно, поэтому сравнение было нестрогим. Таким образом мы ушли от проверки конкретной реализации HTML, CSS и JS к проверке конечного результата — в том виде, в котором его видит пользователь в браузере.

Мы проверяли, что:
— игровое поле отрисовалось правильно,
— шарик никуда не катится, если сразу упирается в стенку,
— шарик катится на несколько клеток, если они свободны,
— если шарик докатился до стенки, то при повторном наклоне в ту же сторону он не покатится дальше,
— после того как шарик прокатился и уперся в стенку, он катится в других доступных направлениях,
— если шарик закатился в клетку выхода, он не выкатывается из нее.

Таким образом, в одном задании нам удалось проверить следующие навыки:
— работу с макетом от дизайнеров,
— верстку,
— применения DOM API и работу с событиями,
— придумывание и реализацию алгоритмов.

Задача 11. Капча

Условие

Представьте, что вы китайский студент, который зарабатывает на жизнь прохождением капчи за деньги. На одном из сайтов вам периодически встречается капча, решение которой занимает много времени. Вы хотите написать робота, чтобы автоматизировать решение задачи.

Капча представляет собой фотографию, которую нужно разделить на прямоугольные фрагменты. У всех фрагментов должна быть одинаковая площадь, но могут быть разные размеры сторон. Каждый фрагмент должен содержать ровно один дорожный знак. В качестве решения этого задания отправьте файл .js, который экспортирует функцию:

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

Ваши коллеги уже предобработали фотографию. Они разбили ее по сетке на маленькие квадратные части и для каждой из них определили основной объект.
Фотография попадает к вам в виде строки:

captcha = ‘  
  TRABWARH  
  THSCAHAW  
  WWBSCWAA  
  CACACHCR  
‘

Обозначение объектов:
— S — дорожный знак (sign)
— T — дерево (tree)
— R — дорога (road)
—…

На выходе должен получиться массив строк:

[  
  ‘TRABWARH  
   THSCAHAW‘  
   ,  
  ‘WWBSCWAA  
   CACACHCR‘  
]

Есть несколько условий:
— Количество дорожных знаков на фотографии всегда больше 1 и меньше 10.
— Каждый фрагмент должен быть прямоугольником.
— Площадь каждого из получившихся фрагментов должна быть одинаковой, но размеры могут отличаться.
— В выходном массиве фрагменты должны идти сверху вниз и слева направо (относительно левого верхнего угла).
— Если существует несколько способов решения, то при сравнении способов приоритет отдается тому, у которого ширина первого отличающегося фрагмента будет наибольшей.
— Если решения не существует, надо вернуть пустой массив.

При подготовке задания мы вдохновлялись задачей Cut the cake с сайта codewars.com.

Разбор

По условиям задачи, количество знаков не может быть больше 10. Это небольшое количество, и можно решить задачу перебором вариантов. Задача осложняется тем, что нужно перебирать размещение двумерных фигур в двумерном пространстве. Поэтому сначала установим правила размещения фигур:
— будем считать ключевой точкой фрагмента его левый верхний угол;
— во время перебора будем пробовать ставить ключевую точку каждого фрагмента в самую левую свободную клетку поля в самой верхней строке, где есть свободные клетки.

Поскольку мы знаем размеры поля и общее количество дорожных знаков, мы можем заранее определить площадь и сгенерировать все варианты прямоугольников такой площади. У нас есть правило: «… приоритет отдается тому, у которого ширина первого отличающегося фрагмента будет наибольшей». Поэтому при переборе будем сначала пробовать более широкие прямоугольники. Для этого отсортируем варианты по убыванию ширины.

Будем перебирать расположение фрагментов рекурсивно. На каждом шаге рекурсии попробуем поставить на поле очередной фрагмент. Если это удалось, перейдем к следующему шагу. В конце убираем фрагмент с поля и пробуем поставить на его место следующий.

Информацию о размещении фрагмента на поле удобно хранить в виде двумерного массива. Если для каждого фрагмента иметь отдельный «слой», то будет удобно ставить их на поле и убирать оттуда.

module.exports = function solveCaptcha(captcha) {  
    const n = // посчитать количество дорожных знаков
    const sizes = getAllSizes(); // получить все прямоугольники заданной площади
	
    // board — это массив слоев
    // каждый слой — это двумерный массив, в котором 
    // отмечены клетки, занятые определенным фрагментом
    const board = []; 
    
    // поиск решения перебором
    function placeNext(remains) {

        // если не осталось фрагментов... 
        if (remains === 0) {
        
            // ...то считаем, что решение найдено, и выходим
            return board;
        } else {
            // иначе...
        
            // находим самую левую свободную ячейку в самой верхней 
            // строке, которая не полностью заполнена
            const pos = getEmptyPos();

            // по очереди пробуем поставить фрагменты всех размеров
            for (let i = 0; i < sizes.length; i++) {
                // размер прямоугольника, который пробуем поставить
                const size = sizes[i];

                // получаем слой с фрагментом нужного размера на нужном месте
                // если фрагмент поставить нельзя (он не подходит на свободное место 
                // или количество дорожных знаков !== 1), получаем null
                const layer = getLayer(pos, size);

                // если удалось поставить фрагмент
                if (layer) {
                    // добавляем слой на поле
                    board.push(layer);
                    
                    // пробуем поставить следующие фрагменты
                    const res = placeNext(remains - 1);

                    // если получилось, выходим
                    if (res) return res;

                    // иначе убираем фрагмент с поля
                    // и пробуем следующий
                    board.pop();
                }
            }
        }
    }
    
    // запускаем перебор
    return placeNext(n);
}

Задача 12. Робот для пулл-реквестов

Условие

В компании X есть своя система контроля версий. Эта VCS не умеет анализировать изменения в файлах и может смёржить два реквеста автоматически, если они не содержат изменений в одних и тех же файлах.

В определённый момент запускается робот, который автоматически мёржит в мастер пулл-реквесты. Задача робота — смёржить наибольшее количество изменений, после чего дежурный разработчик собирает текущий мастер в релиз и отдаёт его в тестирование.

Робот принимает на вход список реквестов, отсортированных по времени создания. В данных о каждом реквесте содержится список файлов, которые в нём изменились, и время создания реквеста. В каждом реквесте может быть изменён хотя бы один файл.

Робот должен вернуть массив с идентификаторами реквестов в том порядке, в котором их нужно смёржить. При этом робот должен влить максимум изменений (количество изменённых файлов) без конфликтов в порядке времени создания реквестов.

Напишите код этого робота.

Формат ввода

На вход подаётся массив реквестов. Длина массива — не более 1000, количество конфликутющих между собой пулл-реквестов — не более 20.

У каждого реквеста такая структура:

type PullRequest = {  
    /**  
     * Массив имён изменённых файлов (отсортирован лексикографически)  
     * Длина массива N: 1 <= N <= 1000  
     */  
    files: string[],  
    /**  
     * Уникальный идентификатор реквеста в VCS  
     */  
    id: string,  
    /**  
     * Unix-timestamp создания пулл-реквеста  
     */  
    created: number,  
}

Время создания (created) и идентификатор (id) каждого реквеста – уникальны.

Формат вывода

Код робота должен экспортироваться в виде CommonJS-модуля вида:

/**  
 * @param {PullRequest[]} pullRequests массив PR, отсортированных по времени создания  
 * @returns {string[]} идентификаторы реквестов в порядке мёржа  
 */  
module.exports = function (pullRequests) {  
    // ваш код  
}

Примечания

Ваше решение будет тестироваться в NodeJS версии v9.11.2. Оно не должно использовать внешних зависимостей.

Примеры входных и выходных данных

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

Разбор

Решить задачу можно несколькими способами — например, жадным алгоритмом.

Идея жадного алгоритма в том, чтобы на каждом шаге вливать «самый лучший» реквест (тот, в котором больше всего файлов и который не конфликтует с уже влитыми).

Для проверки того, конфликтуют ли два реквеста, нужно сравнить список файлов, которые они меняют. Это можно сделать через два вложенных цикла (или через методы some и includes). Алгоритмическая сложность этой операции — O(n²).

Так как файлы в реквесте отсортированы по алфавиту, можно воспользоваться алгоритмом поиска пересечений, который осуществляется с помощью прохода по массивам двумя индексами (подробнее см. в этой статье). Такой способ работает существенно быстрее — за O(n).

Код для жадного решения:

function conflicts(a, b) {
   let i = 0;
   let j = 0;

   while (i < a.length && j < b.length) {
       if (a[i] === b[j]) {
           return true;
       } else if (a[i] > b[j]) {
           j++;
       } else {
           i++;
       }
   }

   return false;
}

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

К сожалению, жадный алгоритм не будет работать в случае, если имеет смысл не вливать реквест сразу. Например, на таких данных он выдаст неправильный ответ:

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

Чтобы обойти эту ошибку, нужно реализовать полный перебор всех возможных решений (о том, вливать или не вливать каждый реквест).

Перебор всех вариантов можно схематично представить в виде дерева: «узлом» дерева будет пулл-реквест, а «листом» — список всех реквестов в ветке дерева (то есть вариант решения). Из каждого узла будут выходить одна или две ветки (вливать реквест или нет).

Разберем пример:

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

Реквесты #2 и #3 здесь конфликтуют, верным ответом здесь будет ["#1", "#2"]. Изобразим дерево решений для этого примера.

Решение задачи сводится к поиску той ветки дерева, в которой вливается максимальное количество файлов.

Проблема в том, что алгоритмическая сложность такого решения становится очень большой — O(n²), и оно перестает соответствовать ограничению на время работы. Код нужно ускорять.

Первым шагом будем предварительно генерировать матрицу конфликтов, в которой собрана информация о том, конфликтуют ли два реквеста между собой. Это позволит быстро проверять реквесты на конфликтность, не выполняя честную проверку каждый раз, а используя предпосчитанное значение из матрицы.

Функцию conflicts используем такую же, как и раньше. Генерация матрицы выглядит следующим образом:

const conflictMatrix = new Uint8Array(prs.length ** 2);
const prToIndex = new WeakMap();

for (let i = 0; i < prs.length; i++) {
   const pr1 = prs[i];
   prToIndex.set(pr1, i);
   conflictMatrix[i * prs.length + i] = 0;
   for (let j = i + 1; j < prs.length; j++) {
       const pr2 = prs[j];
       conflictMatrix[i * prs.length + j] = conflictMatrix[j * prs.length + i] = conflicts(pr1.files, pr2.files);
   }	
}

/**
*  Конфликутуют ли два PR (используем посчитанное значение из матрицы)
*/
function doPRsConflict(pr1, pr2) {
   const i = prToIndex.get(pr1);
   const j = prToIndex.get(pr2);
   return conflictMatrix[i * prs.length + j] === 1;
}

Далее необходимо «срезать» в дереве решений те ветки, которые можно не обходить. На каждом шаге решения (в узле дерева) могут быть такие реквесты, которые не конфликтуют с другими. Если их влить, то картина конфликтов не изменится, а количество узлов-решений в дереве сократится.

Чтобы получить список реквестов, которые не конфликтуют на текущем шаге, нужно обойти коллекцию и проверить каждый.

/**
* получить все реквесты из prsSet, которые не конфликтуют со смерженными и с оставшимися не смерженными
*/
function getNonConflictingPRs (prsSet, mergedPrs) {
   const result = [];
   const prsToTest = [...prsSet, ...mergedPrs];
   prsSet.forEach((pr) => {
       if (!conflictsWithSomePR(pr, prsToTest)) {
           result.push(pr);
       }
   });
   return result;
}

Делать это нужно на каждом входе в рекурсивную функцию поиска.

const fullSearch = (prsSet, mergedPrs = [], mergedFilesCount = 0) => {
   hits++;	

   // выбираем реквесты, которые не конфликтуют ни с одним из смерженных и оставшихся
   // их можно смержить, и конфликтов не будет
   const safeToMergePRs = getNonConflictingPRs(prsSet, mergedPrs);
   mergedPrs = mergedPrs.concat(safeToMergePRs);
   safeToMergePRs.forEach((pr) => {
       prsSet.delete(pr);
       mergedFilesCount += pr.files.length;
   });

   const pr = prsSet.values().next().value;
// ...дальше продолжается код обхода дерева решений

Остальной код останется прежним.

Автор: Leono

Источник