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

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

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

Задача 1

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

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

Условие

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

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

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

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

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

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

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

Разбор

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

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

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

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

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

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

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

Таким образом, номерам почтовых отделений сответствует группа ([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. Код, в котором есть ошибка

Условие

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

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

Макет: 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

Условие

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

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

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

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

Разбор

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

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

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

Условие

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

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

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

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

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

Разбор

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

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

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

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

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

Условие

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

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

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

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

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

Разбор

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

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

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

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

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

Условие

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

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

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

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

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

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

Примечания:
— 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 пикселей. Например:

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

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

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

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

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

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

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

Разбор

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

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

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

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

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

Стили:

.map { border: 0; border-spacing: 0; border-collapse: separate; background-color: #ccc; transform-style: preserve-3d;
} .map__cell { box-sizing: border-box; border: 1px solid; border-color: #9b9b9b #575757 #575757 #9b9b9b; width: 30px; height: 30px; text-align: center; vertical-align: middle; font-size: 0; line-height: 0; background-color: #707070;
} .map__cell_content_ball:after { content: ''; display: inline-block; width: 20px; height: 20px; border-radius: 50%; background: radial-gradient(circle at 5px 5px, #eee, #000);
} .map__cell_content_wall { border-width: 4px;
} .map__cell_content_exit { background-color: #000; border: 5px solid; border-color: #222 #555 #555 #222;
}

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

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

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

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

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

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

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

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

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

let gameBox = document.querySelector('.game-box');
let map = gameBox.querySelector('.map'); // Используем делегирование событий и добавляем один обработчик только на контейнер
gameBox.addEventListener('click', ({ target }) => { // Обрабатываем только клики по контролам if (!target.classList.contains('control')) { return; }; // Получаем направление наклона прямо из класса-модификатора const direction = target.className.match(/\bcontrol_direction_(\w+)/)[1]; // Наклоняем карту, заменяя соответствующий класс-модификатор map.className = map.className.replace(/\bmap__tilt_\w+/, `map__tilt_${direction}`); // Получаем клетку, в которой находится шарик let ball = map.querySelector('.map__cell_content_ball'); // Вычисляем предположительную следующую клетку для шарика let nextBall = getNextCell(map, ball, direction); // Убираем шарик из предыдущей клетки ball.classList.remove('map__cell_content_ball'); ball.classList.add('map__cell_content_empty'); // Уточняем следующую клетку для шарика, пока не упремся в стенку или не выкатимся в клетку выхода while ( !nextBall.classList.contains('map__cell_content_wall') && !ball.classList.contains('map__cell_content_exit') ) { ball = nextBall; nextBall = getNextCell(map, ball, direction); } // Ставим шарик в вычисленную клетку ball.classList.remove('map__cell_content_empty'); ball.classList.add('map__cell_content_ball');
}); const DIRECTIONS = { 'left': [-1, 0], 'up': [0, -1], 'down': [0, 1], 'right': [1, 0] }; // Используя DOM API таблиц, находим следующую клетку для определенного направления наклона
function getNextCell(map, cell, direction) { const directionDiff = DIRECTIONS[direction]; return map.rows[cell.parentNode.rowIndex + directionDiff[1]].cells[cell.cellIndex + directionDiff[0]];
}

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

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

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

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

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

Условие

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

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

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

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

captcha = ‘ TRABWARH THSCAHAW WWBSCWAA CACACHCR ‘

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

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

[ ‘TRABWARH THSCAHAW‘ , ‘WWBSCWAA CACACHCR‘ ]

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

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

Разбор

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

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

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

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

module.exports = function solveCaptcha(captcha) { const n = // посчитать количество дорожных знаков const sizes = getAllSizes(); // получить все прямоугольники заданной площади // board — это массив слоев // каждый слой — это двумерный массив, в котором // отмечены клетки, занятые определенным фрагментом const board = []; // поиск решения перебором function placeNext(remains) { // если не осталось фрагментов... if (remains === 0) { // ...то считаем, что решение найдено, и выходим return board; } else { // иначе... // находим самую левую свободную ячейку в самой верхней // строке, которая не полностью заполнена const pos = getEmptyPos(); // по очереди пробуем поставить фрагменты всех размеров for (let i = 0; i < sizes.length; i++) { // размер прямоугольника, который пробуем поставить const size = sizes[i]; // получаем слой с фрагментом нужного размера на нужном месте // если фрагмент поставить нельзя (он не подходит на свободное место // или количество дорожных знаков !== 1), получаем null const layer = getLayer(pos, size); // если удалось поставить фрагмент if (layer) { // добавляем слой на поле board.push(layer); // пробуем поставить следующие фрагменты const res = placeNext(remains - 1); // если получилось, выходим if (res) return res; // иначе убираем фрагмент с поля // и пробуем следующий board.pop(); } } } } // запускаем перебор return placeNext(n);
}

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

Условие

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

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

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

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

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

Формат ввода

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

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

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

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

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

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

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

Примечания

11. Ваше решение будет тестироваться в NodeJS версии v9. Оно не должно использовать внешних зависимостей. 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(n2).

в этой статье). Так как файлы в реквесте отсортированы по алфавиту, можно воспользоваться алгоритмом поиска пересечений, который осуществляется с помощью прохода по массивам двумя индексами (подробнее см. Такой способ работает существенно быстрее — за 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(n2), и оно перестает соответствовать ограничению на время работы.

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

Генерация матрицы выглядит следующим образом: Функцию 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;
// ...дальше продолжается код обхода дерева решений

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Интервью с Дэвидом Гобелем

Дэвид любезно согласился дать LEAF очень интересное интервью. Дэвид Гобель – изобретатель, филантроп, футурист и ярый сторонник технологий омоложения; вместе с Обри де Греем он известен как один из основателей Methuselah Foundation и как автор концепции Longevity Escape Velocity (LEV), ...

10 долларов на хостинг: 20 лет назад и сегодня

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