Задачи
Подбор размеров шрифта
Парсинг HTML
Условие
Петя работает старшим верстальщиком в газете «Московский фронтендер». Для верстки газеты Петя использует стек веб-технологий. Самая сложная задача, с которой столкнулся Петя, — это верстка заголовков в газетных статьях: колонки газеты в каждом выпуске имеют разную ширину, а заголовки — разный шрифт и разное количество символов.
Пете нужно подбирать свой размер шрифта для каждого заголовка так, чтобы размер шрифта был максимальным, но при этом весь текст заголовка влез в отведенное ему место.
Помогите Пете: реализуйте функцию 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 мс, то такое решение тоже не пройдет проверки. Эта особенность не была описана в условиях к задаче явно, и мы ожидали, что участник выяснит это, прочитав исходный код страницы. Кстати, в исходном коде участников ждал небольшой сюрприз. ;)