Новый хабрапост в серии разборов недавно прошедшего чемпионата. Участникам квалификации, которые выбрали секцию фронтенда, нужно было решить несколько задач очень разной сложности: первая (по нашим ожиданиям) занимала 20 минут, последняя — около часа. Мы проверяли широкий спектр навыков разработчика интерфейсов, включая способность разобраться в необычной предметной области. A. Аннигилируй это
Авторы: Максим Сысоев, Константин ПетряевПервая задача — разминочная. Каждому участнику доставался один из четырёх вариантов задачи, похожих между собой. Мы предложили не только текстовое условие, но и «плохое» рекурсивное решение. Нужно было переделать код (написать жадный алгоритм, который выдавал самое быстрое решение), убрав рекурсию и разные глупости вроде лишних операций и вычислений.
Условие
Вы устроились работать в лабораторию по изучению антиматерии, где проводят различные опыты. Ваш отдел изучает процессы, которые происходят при объединении материи и антиматерии. Вам необходимо провести серию опытов над некоторым количеством молекул.
Соседний отдел разработал аппарат, который превращает материю в антиматерию на небольшое время. Он пригодится вам в проведении опытов, в которых используется следующий алгоритм:
— Находим 2 самых тяжёлых молекулы.
— Одну из них превращаем в антиматерию.
— Объединяем их. При этом, если вес одинаковый, они аннигилируются. Если же вес различается, то мы получаем новую молекулу, вес которой равен разнице весов предыдущих двух. Сама получившаяся молекула является материей.
— Если осталась одна молекула — нужно выяснить её вес. Если же молекул много — возвращаемся к пункту 1.
Вам необходимо узнать, молекула какого веса останется в конце опыта, это знание нужно учёным другого отдела.
Предыдущий разработчик набросал код, который занимался этими расчётами, однако код не может закончить расчёты в случае, когда опыт проводится на большом количестве молекул. Вам необходимо усовершенствовать код, чтобы он работал за приемлемое время.
Код, доставшийся вам в «наследство»
В качестве входных данных у вас будет массив с весами молекул. В качестве выходных данных необходимо вернуть число, которое обозначает вес последней молекулы. Если молекул не останется, то необходимо вернуть 0.
var findLatestWeight = function(weights, i = weights.length - 1) {
const cur = weights.length - 1 === i;
if (i === 0) return weights[0];
weights.sort((a, b) => a - b);
weights[i - 1] = (weights[i] === weights[i-1]) ? 0 : weights[i] - weights[i-1];
return findLatestWeight(weights, i - 1);
}Пример и примечания
Вход: [2,7,4,1,8,1]
Выход: 1
Берём молекулы с весом 7 и 8, превращаем 7 в антимолекулу и сталкиваем её с молекулой весом 8. Остаётся молекула весом 1. Веса оставшихся молекул стали [2,4,1,1,1]. Берём молекулы с весом 2 и 4, превращаем 2 в антимолекулу и сталкиваем её с молекулой весом 4. Остаётся молекула весом 2. Веса оставшихся молекул стали [2,1,1,1]. Берем молекулы с весом 2 и 1, превращаем 1 в антимолекулу и сталкиваем её с молекулой весом 2. Остаётся молекула весом 1. Веса оставшихся молекул стали [1,1,1]. Берем молекулы с весом 1 и 1, превращаем одну из них в антимолекулу и сталкиваем ее со второй. Они аннигилируются. Веса оставшихся молекул [1]. Осталась одна молекула. Результат — 1.
В качестве решения предоставьте файл, который экспортирует исправленный вариант функции findLatestWeight:
Решение будет запускаться в Node.js 12.
Пример
Вход: [2,7,4,1,8,1]
Выход: 1
Берём молекулы с весом 7 и 8, превращаем 7 в антимолекулу и сталкиваем её с молекулой весом 8. Остаётся молекула весом 1. Веса оставшихся молекул стали [2,4,1,1,1]. Берём молекулы с весом 2 и 4, превращаем 2 в антимолекулу и сталкиваем её с молекулой весом 4. Остаётся молекула весом 2. Веса оставшихся молекул стали [2,1,1,1]. Берем молекулы с весом 2 и 1, превращаем 1 в антимолекулу и сталкиваем её с молекулой весом 2. Остаётся молекула весом 1. Веса оставшихся молекул стали [1,1,1]. Берем молекулы с весом 1 и 1, превращаем одну из них в антимолекулу и сталкиваем ее со второй. Они аннигилируются. Веса оставшихся молекул [1]. Осталась одна молекула. Результат — 1.
Примечания
В качестве решения предоставьте файл, который экспортирует исправленный вариант функции findLatestWeight:
function findLatestWeight(weights) {
// ...
}
module.exports = findLatestWeight;Решение будет запускаться в Node.js 12.
Решение
В предоставленном «плохом» решении есть сразу несколько проблем. Первая — наличие рекурсии. Как заявлено в условии, мы будем обрабатывать большие массивы чисел, что сразу исключает рекурсивное решение.
var findLatestWeight = function(weights) {
let i = weights.length - 1;
do {
if (i === 0) return weights[0] || 0;
weights.sort((a, b) => a - b);
weights[i-1] = (weights[i]=== weights[i-1]) ? 0 : weights[i]-weights[i-1];
i--;
} while (true);
}Развернуть рекурсию здесь достаточно просто, однако возникает другая проблема — происходит постоянная пересортировка (от меньших к большим) и работа с концом массива. В результате мы получаем уменьшение предпоследнего элемента в массиве. Но после этого мы не обрезаем массив, и если в функцию был передан массив из миллиона элементов, то мы до самого конца будем заниматься его пересортировкой.
Вариант решения этой проблемы — попробовать постоянно обрезать массив.
var findLatestWeight = function(weights) {
let i = weights.length - 1;
do {
if (i === 0) return weights[0] || 0;
weights.sort((a, b) => a - b);
weights[i-1] = (weights[i]=== weights[i-1]) ? 0 : weights[i]-weights[i-1];
weights.length = i; // <--- вот так
i--;
} while (true);
}Неплохо, но нам необходимо также избавиться от сортировки, которая сама по себе является дорогой операцией. По большому счёту, нас в любой момент времени будут интересовать 2 самых больших члена массива. То есть это поиск двух максимумов, что делается в один проход достаточно просто. Для удобства вынесем такой поиск в отдельную функцию.
const maximumTwo = (arr) => {
let max1 = arr[0];
let max2 = arr[1];
let max1I = 0;
let max2I = 1;
for(let i = 2; i < arr.length; i++) {
if (arr[i] > max1) {
if (max1 > max2) {
max2 = arr[i];
max2I = i;
} else {
max1 = arr[i];
max1I = i;
}
} else if (arr[i] > max2) {
max2 = arr[i];
max2I = i;
}
}
if (max1 > max2) return [max2, max1, max2I, max1I];
return [max1, max2, max1I, max2I];
};А саму функцию поиска поменяем следующим образом:
const fn = function(weights) {
if (weights.length <= 1) {
return weights[0];
}
do {
const [x, y, xI, yI] = maximumTwo(weights);
if (x === 0) {
return y;
}
weights[xI] = 0;
weights[yI] = y - x;
} while(true);
};Таким образом, мы всегда будем обнулять меньший из двух элементов, а больший превращать в разницу между ними. Мы избавились от сортировки и получили вместо нее один линейный проход.
Из замеченных нами частых ошибок — участники брали максимальный элемент, умножали его на –1 и складывали со вторым по величине камнем. В результате получалось отрицательное число, которое потом использовалось в вычислениях «как есть». Кроме того, в задаче есть ментальная ловушка, связанная с тем, что можно попробовать оставить уникальные по весу камни и вычислить разницу из них. Однако этот подход не даёт верного результата.
B. БЭМ
Авторы: Евгений Мищенко, Владимир Гриненко tadatutaУсловие
Верстальщик Александр участвует в множестве проектов с использованием БЭМ-методологии. Он даже создал удобный плагин для любимой IDE, который позволяет ему писать имена классов в сокращённой записи и разворачивать их в полную. Но проблема в том, что для каждого проекта люди устанавливают разные разделители между блоком, элементом и модификатором (block__mod__val—elem, block–mod–val___elem), и ему приходится каждый раз править это в своём плагине вручную. Помогите Александру написать модуль, который будет на основании класса определять разделитель для сущностей. Правило для разделителей — произвольное количество символов (не буквы). Примеры возможных нотаций (модификаторы для блока во входящих данных могут быть без значения):
block_mod__elem // Считаем, что модификатор идёт первым
block_mod_mod__elem
block__elem_mod_mod
Уточнения:
— Классы в проектах пишут только маленькими буквами.
— На вход модуля подаётся строка с валидным CSS-классом.
Модуль должен вернуть ответ вида:
{
mod: "_", // разделитель для модификатора
elem: "__", // разделитель для элемента
}Оформить модуль необходимо как commonJS-модуль:
module.exports = function(str) {
}Решение
На вторую задачу отводилось примерно 20 минут. С её помощью мы хотели проверить у участников знание регулярных выражений.
Из условия мы узнаём, что на вход в функцию будет приходить строка, содержащая валидный CSS-класс с дополнительными ограничениями, в которой буквенные последовательности разделены произвольными последовательностями из небуквенных символов. Наша задача — найти разделители и понять их семантику.
Первой частью имени класса всегда будет название блока. Это последовательность из одной или более букв. Запишем соответствующее регулярное выражение: [a-z]+.
Аналогичные выражения потребуются нам для поиска остальных частей: имени модификатора и его значения либо имени элемента с соответствующими модификатором и значением.
Для поиска разделителей нам нужны небуквенные последовательности, подойдет выражение: [^a-z]+.
Соберём вместе и зададим группы, значения которых будем использовать:
let [, mod, elem ] = str.match(/[a-z]+(?:([^a-z]+)[a-z]+(?:\1)?[a-z]+)([^a-z]+)[a-z]+(?:\2)?[a-z]+/);Теперь нужно убедиться, что мы правильно определили семантику найденных групп. Можно воспользоваться тем, что встретиться дважды может только модификатор.
Напишем функцию, которая будет принимать исходную строку и найденный разделитель, чтобы посчитать количество вхождений:
const substringCount = (source, substr) => (source.match(new RegExp('[a-z]' + substr + '[a-z]', 'g')) || []).length;Если окажется, что разделитель elem встречается дважды, а mod — один раз, то на самом деле все наоборот. Итоговое решение:
module.exports = function(str) {
let [, mod, elem ] = str.match(/[a-z]+(?:([^a-z]+)[a-z]+(?:\1)?[a-z]+)([^a-z]+)[a-z]+(?:\2)?[a-z]+/);
const substringCount = (source, substr) => (source.match(new RegExp('[a-z]' + substr + '[a-z]', 'g')) || []).length;
if (substringCount(str, elem) === 2 && substringCount(str, mod) === 1) {
[mod, elem] = [elem, mod];
}
return { mod, elem };
}C. Фабрика клонов
Авторы: Дмитрий Андриянов dima117, Алексей ГусевУсловие
За окном 2319 год. Корпорации клонируют успешных сотрудников, чтобы они выполняли сложные задачи.
На производстве клонов решили маркировать новые «изделия» с помощью татуировки с баркодом на плече — чтобы отличать клонов между собой.
Помогите сотрудникам фабрики написать функцию, которая будет отрисовывать баркод с информацией о клоне.
Формат информации о клоне
Информация о клоне хранится в следующем виде:
type CloneInfo = {
/**
* Пол клона — строка ’male’ или ’female’
*/
sex: string;
/**
* Идентификатор клона — строка из маленьких и больших
* латинских букв и цифр, строго 10 символов
*/
id: string;
/**
* Имя клона — строка из маленьких и больших
* латинских букв и пробелов (от 0 до 26 символов)
*/
name: string;
}Алгоритм отрисовки баркода
Баркоды, которые используют на фабрике клонов, выглядят так:
Баркод имеет фиксированный размер — 148 на 156 пикселей. По периметру баркода находятся чёрная и белая рамки по 3 пикселя шириной каждая. Внутри рамок находится контент баркода, состоящий из 18 строк по 17 чёрных или белых квадратов в строке. Размер каждого квадрата — 8 на 8 пикселей.
Белые квадраты в контенте кодируют 0, чёрные — 1.
Алгоритм формирования контента баркода
На пересечении первой строки и первого столбца контента отрисовывается квадрат, кодирующий пол клона. Значение female кодируется нулём (белый цвет), male — единицей (чёрный цвет).
Далее из полей id и name формируется строка вида <id><name>. Поле name дополняется пробелами в конце до 26 символов.
Полученная строка конвертируется в байтовый массив — каждому символу строки ставится соответствующий ASCII-код (число от 0 до 255).
Затем каждый элемент полученного массива переводится в двоичную запись (восемь символов 0 или 1) и кодируется последовательностью из восьми квадратов (0 — белый квардрат, 1 — чёрный квадрат). Квадраты отрисовываются в контенте баркода последовательно и построчно.
В последней строке контента находится контрольная информация.
Алгоритм подсчёта контрольной информации
Каждый квадрат в строке контрольной информации определяет чётность суммы значений контента в соответствующем столбце. Если сумма нулей и единиц в столбце чётная, то в контрольной информации рисуется белый квадрат, в противном случае — чёрный.
Формат решения и примеры
Формат решения
Загружаемое вами решение должно содержать функцию renderBarcode:
Баркод:
Информация о клоне:
Баркод:
Загружаемое вами решение должно содержать функцию renderBarcode:
/**
* Отрисовать баркод для татуировки клона в element
* @param cloneInfo {CloneInfo} — информация о клоне
* @param element {HTMLDivElement} — div с фиксированным размером
* 148x156 пикселей, в который будет отрисовываться баркод
*/
function renderBarcode(cloneInfo, element) {
// ваш код
}</source lang="javascript">
Решение будет запускаться в браузере Google Chrome 77.
<h4>Пример 1</h4>
Информация о клоне:
<source lang="javascript">{
"sex": "male",
"id": "c5j818dyo5",
"name": "Oleg Vladimirovich"
}Баркод:
Пример 2
Информация о клоне:
{
"sex": "female",
"id": "0owrgqqwfw",
"name": "Dazdraperma Petrovna"
}Баркод:
Решение
Требовалось правильно сформировать бинарное представление данных, посчитать для него контрольную сумму и отрисовать эти данные в верстке. Давайте попробуем сделать это максимально просто и в лоб — без оптимизаций кода.
Начнём с бинарного представления. Для начала объявим вспомогательные функции:
// переводит символ в ASCII-код
function charToByte(char) {
return char.charCodeAt(0);
}
// переводит байт в строку из 0 и 1 (в двоичную систему счисления с незначащими нулями)
function byteToString(byte) {
return byte.toString(2).padStart(8, '0');
}Cформируем из исходных данных строку, состоящую из нулей и единиц:
let dataString =
(cloneInfo.sex === 'female' ? '0' : '1') +
cloneInfo.id.split('').map(charToByte).map(byteToString).join('') +
cloneInfo.name.padEnd(26, ' ').split('').map(charToByte).map(byteToString).join('');Затем напишем вёрстку и стили для нашего баркода:
// Идентификатор для блока, где будет находиться «контент» баркода.
// В принципе, вёрстку можно целиком строить через DOM API без использования innerHTML, и тогда идентификатор не потребуется.
// Если же реализовывать в лоб, случайный идентификатор защитит нас от того, что два баркода на странице «перемешаются».
// Это было очень частой ошибкой у участников чемпионата — многие не учитывали, что функция отрисовки баркода может вызываться несколько раз.
const contentElId = 'content-' + Math.random();
element.style.display = 'flex';
element.innerHTML = `
<style>
.barcode {
border: 3px solid black;
box-sizing: border-box;
}
.content {
margin-top: 3px;
margin-left: 3px;
width: 136px;
height: 144px;
display: flex;
flex-wrap: wrap;
}
.content__bit {
width: 8px;
height: 8px;
}
.content__bit_one {
background: black;
}
</style>
<div class="content" id="${contentElId}"></div>
`;
const contentDiv = document.getElementById(contentElId);
element.className += ' barcode';Отрендерим бинарные данные в вёрстке:
dataString
.split('')
.forEach((bit) => {
const bitDiv = document.createElement('div');
bitDiv.className = 'content__bit content__bit_' + (bit === '0' ? 'zero' : 'one');
contentDiv.appendChild(bitDiv);
});Осталось посчитать и отобразить контрольную сумму. Это можно сделать так:
for (let i = 0; i < 17; i++) {
// суммируем столбец
let sum = 0;
for (let j = i; j < 17 ** 2; j += 17) {
sum += parseInt(dataString[j], 2);
}
const check = 0;
const bitDiv = document.createElement('div');
// рисуем квадрат контрольной суммы для столбца
bitDiv.className = 'content__bit content__bit_' + (sum % 2 === 0 ? 'zero' : 'one');
contentDiv.appendChild(bitDiv);
}D. Автоматизируй это
Авторы: Владимир Русов, Дмитрий КанатниковВ каждом из вариантов квалификации была задача, где в качестве входных данных предлагалась HTML-страничка с таблицей или списком. У задач этой серии была разная легенда, но все они сводились к тому, что надо привести страницу к формату, похожему на Markdown. Разберём решение одной из задач.
Условие
На государственном портале предоставления услуг сделали возможность подавать заявление на получение документов полностью автоматически, для этого надо только заполнить таблицу с персональными данными.
Эти данные затем передаются на проверку в несколько инстанций, включая МВД. После начала тестирования выяснилось, что МВД принимает данные в формате Markdown, а Госуслуги пользуются HTML-форматом. Помогите написать скрипт миграции одного формата в другой, чтобы ребята поскорее запустились.
Вам нужно написать функцию, которая на вход принимает HTML-таблицу и преобразует ее в Markdown-подобную разметку.
В качестве решения этого задания отправьте файл .js, в котором объявлена функция solution:
function solution(input) {
// ...
}Формат входных/выходных данных и примечания
HTML-таблица приходит в виде строки:
В таблице могут содержаться теги colgroup, thead и tbody в фиксированном порядке. Все эти теги опциональны, но всегда будет присутствовать как минимум thead либо tbody.
— colgroup содержит теги col, у которых может быть опциональный атрибут align с одним из трёх значений (left|center|right)
— thead и tbody содержат 1 или более tr
— tr, в свою очередь, содержат как td, так и th
— В таблице всегда будет хотя бы одна строка. — В строке всегда будет хотя бы одна ячейка. — В ячейке всегда присутствует хотя бы один не-whitespace символ.
— Количество элементов th/td в строках всегда совпадает между всеми строками и с количеством элементов col в colgroup, при наличии colgroup.
— Пробелы и переносы строк в исходном HTML могут встречаться в любом месте, не нарушающем валидность HTML.
На выходе должна получиться строка с Markdown-разметкой:
— Первая встретившаяся строка в таблице должна всегда превращаться в строку-заголовок в Markdown-разметке.
— Все остальные строки идут в тело таблицы.
— Разделитель заголовка выводится всегда.
— Содержимое td вставляется как есть, содержимое th как **bold**.
— Между содержимым ячейки в markdown-разметке и разделителями ячеек (|) всегда один пробел.
— Пробелы по краям содержимого тегов td и th должны быть удалены.
— Переносы строк в содержимом ячеек должны быть удалены.
— Более одного пробела подряд в содержимом ячеек должны быть заменены одним пробелом.
— За выравнивание в ячейках столбцов Markdown-таблицы отвечает форматирование разделителя заголовка:
| :--- | значит выравнивание по левому краю
| :---: | значит выравнивание по центру
| ---: | значит выравнивание по правому краю
При отсутствии заданного в теге col атрибута align выравнивание должно быть задано влево.
— Для перевода строки нужно использовать символ \n.
— Решение будет проверяться в браузерном окружении (Chrome 78) с доступом к объектам document и window.
— Можно использовать синтаксис до es2018 включительно.
Формат входных данных
HTML-таблица приходит в виде строки:
<table>
<colgroup>
<col align="right" />
<col />
<col align="center" />
</colgroup>
<thead>
<tr>
<td>Command </td>
<td>Description </td>
<th>Is implemented </th>
</tr>
</thead>
<tbody>
<tr>
<th>git status</th>
<td>List all new or modified files</td>
<th>Yes</th>
</tr>
<tr>
<th>git diff</th>
<td>Show file differences that haven't been
staged</td>
<td>No</td>
</tr>
</tbody>
</table>В таблице могут содержаться теги colgroup, thead и tbody в фиксированном порядке. Все эти теги опциональны, но всегда будет присутствовать как минимум thead либо tbody.
— colgroup содержит теги col, у которых может быть опциональный атрибут align с одним из трёх значений (left|center|right)
— thead и tbody содержат 1 или более tr
— tr, в свою очередь, содержат как td, так и th
— В таблице всегда будет хотя бы одна строка. — В строке всегда будет хотя бы одна ячейка. — В ячейке всегда присутствует хотя бы один не-whitespace символ.
— Количество элементов th/td в строках всегда совпадает между всеми строками и с количеством элементов col в colgroup, при наличии colgroup.
— Пробелы и переносы строк в исходном HTML могут встречаться в любом месте, не нарушающем валидность HTML.
Формат выходных данных
На выходе должна получиться строка с Markdown-разметкой:
| Command | Description | **Is implemented** |
| ---: | :--- | :---: |
| **git status** | List all new or modified files | **Yes** |
| **git diff** | Show file differences that haven't been staged | No |— Первая встретившаяся строка в таблице должна всегда превращаться в строку-заголовок в Markdown-разметке.
— Все остальные строки идут в тело таблицы.
— Разделитель заголовка выводится всегда.
— Содержимое td вставляется как есть, содержимое th как **bold**.
— Между содержимым ячейки в markdown-разметке и разделителями ячеек (|) всегда один пробел.
— Пробелы по краям содержимого тегов td и th должны быть удалены.
— Переносы строк в содержимом ячеек должны быть удалены.
— Более одного пробела подряд в содержимом ячеек должны быть заменены одним пробелом.
— За выравнивание в ячейках столбцов Markdown-таблицы отвечает форматирование разделителя заголовка:
| :--- | значит выравнивание по левому краю
| :---: | значит выравнивание по центру
| ---: | значит выравнивание по правому краю
При отсутствии заданного в теге col атрибута align выравнивание должно быть задано влево.
Примечания
— Для перевода строки нужно использовать символ \n.
— Решение будет проверяться в браузерном окружении (Chrome 78) с доступом к объектам document и window.
— Можно использовать синтаксис до es2018 включительно.
Решение
Задача решается простым обходом DOM-дерева таблицы. Поддержка DOM-дерева реализована на уровне браузера, является его неотъемлемой частью, поэтому проблем не возникнет. Для решения задачи достаточно транслировать DOM-дерево из HTML в Markdown-разметку.
Рассмотрев примеры, можно заметить, что преобразование осуществляется достаточно просто. Ниже — код, который является телом функции solution(input).
Для начала нам понадобится преобразовать строку из HTML в DOM-дерево:
const div = document.createElement('div');
div.innerHTML = input;
const table = div.firstChild;Получив DOM-дерево, мы можем просто по нему пройти и обработать данные из разных DOM-узлов. Для этого достаточно рекурсивно обходить последовательноть children различных DOM-элементов:
const processors = {
'colgroup': processColgroup,
'thead': processThead,
'tbody': processTbody,
};
for (let child of table.children) {
processors[child.tagName.toLowerCase()](child);
}Из тегов colgroup и col нам интересно узнать выравнивание колонок таблицы:
const alignments = [];
const defaultAlign = 'left';
const processColgroup = (colgroup) => {
alignments.push(...Array(...colgroup.children).map(col => {
return col.align || defaultAlign;
}));
};В тегах thead, tbody и tr нас интересуют только дочерние элементы:
const rows = [];
const processThead = (thead) => {
rows.push(...Array(...thead.children).map(processTr));
};
const processTbody = (tbody) => {
rows.push(...Array(...tbody.children).map(processTr));
};
const processTr = (tr) => {
return Array(...tr.children).map(processCell);
};Важно не забыть, что по условию td и th форматируются по-разному:
const processCell = (cell) => {
const tag = cell.tagName.toLowerCase();
const content = clearString(cell.innerHTML);
return {
'td': content,
'th': `**${content}**`,
}[tag];
};Для работы с тестовым содержимым DOM необходимо выполнить требования, о которых сказано в условии:
const clearLineBreaks = (str) => str.replace(/\r?\n|\r/g, '');
const clearSpaces = (str) => str.replace(/\s+/g, ' ');
const clearString = (str) => clearSpaces(clearLineBreaks(str)).trim();После того, как мы обошли DOM-дерево, основная часть нашей таблицы оказалась записана в массив rows:
[
["Command","Description","**Is implemented**"],
["**git status**","List all new or modified files","**Yes**"],
["**git diff**","Show file differences that haven't been staged","No"]
]Информация о выравнивании колонок оказалась в массиве alignments:
["right","left","center"]Важно вспомнить, что информация о выравнивании колонок может отсутствовать во входных данных:
const updateAlignments = () => {
if (alignments.length > 0) return;
alignments.push(...rows[0].map(x => defaultAlign));
};
updateAlignments();Преобразуем alignments в конечный вид:
const alignmentsContents = alignments.map(align => {
return {
'left': ' :--- ',
'center': ' :---: ',
'right': ' ---: '
}[align];
});
const delimiter = `|${alignmentsContents.join('|')}|`;Пример значения delimiter:
"| ---: | :--- | :---: |"Завершающим этапом будет формирование Markdown-строки, содержащей все данные, прочитанные из HTML:
const lineEnd = '\n';
rows.forEach((row, i) => {
if (i > 0) markdown += lineEnd;
const mdRow = `| ${row.join(' | ')} |`;
markdown += mdRow;
if (i === 0) {
markdown += lineEnd;
markdown += delimiter;
}
});
return markdown;Конструкция return означает, что весь приведённый код был телом функции solution(input). В результате работы этой функции мы получим желаемый Markdown-код таблицы, показанный в примере выходных данных из условия задачи.
E. Пандемия вируса
Авторы: Андрей Мокроусов, Иван ПетуховВсемирная Организация Здравоохранения опубликовала доклад о признаках надвигающейся пандемии нового вируса, который угрожает фронтенд-разработчикам. Известно, что вирус никак не проявляет себя до тех пор, пока носитель не увидит JS-код, содержащий некоторое выражение. Как только заражённый увидел это выражение, он теряет способность писать код на JS и начинает непроизвольно писать код на Фортране.
В докладе упоминается, что вирус активируется от взгляда на использование первого аргумента функции, передаваемой аргументом в вызов функции Z.y.n, то есть заражённым нельзя показывать выражение, подобное Z.y.n(function(a, b, c){console.log(a)}).
Чтобы не потерять случайно всех своих фронтендеров, в компании AST & Co решили проверить, содержит ли их код упомянутое выражение. Помогите инженерам компании написать такую проверку.
Про код в компании AST & Co известно, что:
— он написан на ES3,
— обращение к свойствам объекта возможно как через точку, так и через скобки (a.b и a['b']),
— часть выражения может быть сохранена в переменной, но никогда не передаётся в функцию параметром (a(x) — запрещено),
— нет функций, которые возвращают часть искомого выражения,
— нет свойств объектов или элементов массивов, которые содержат часть выражения,
— при обращении к свойству объекта название свойства может быть взято из переменной (a[x], x — переменная),
— переменные получают свои значения при декларации и не переписываются, т. е. в коде не будет подобного var a = x; a = y; и var a = b = 1.
Формат решения и примечания
Проверка должна быть оформлена в виде CommonJS-модуля, который экспортирует функцию, принимающую на вход абстрактное синтаксическое дерево (ast) проверяемого кода.
Функция должна вернуть массив из ast-узлов, которые соответствуют местам использования первого параметра callback-функции, передаваемой аргументом в Z.y.n. Порядок элементов в массиве не важен, дубли не допускаются.
Следующий код можно взять за основу для обхода дерева.
Формат решения
Проверка должна быть оформлена в виде CommonJS-модуля, который экспортирует функцию, принимающую на вход абстрактное синтаксическое дерево (ast) проверяемого кода.
Функция должна вернуть массив из ast-узлов, которые соответствуют местам использования первого параметра callback-функции, передаваемой аргументом в Z.y.n. Порядок элементов в массиве не важен, дубли не допускаются.
module.exports = function (ast) {
...
return [...];
}Примечания
Следующий код можно взять за основу для обхода дерева.
/**
* Функция обхода дерева. Выполняет обход дерева в глубину,
* передавая в callback-функции onNodeEnter (до посещения потомков)
* и onNodeLeave (после посещения потомков) каждый узел дерева
* и текущую область видимости (смотри определение Scope ниже).
*
* @param {object} ast Исходное ast.
* @param {Function} [onNodeEnter=(node, scope)=>{}] Вызывается для каждого узла до посещения потомков.
* @param {Function} [onNodeLeave=(node, scope)=>{}] Вызывается для каждого узла после посещения потомков.
*/
function traverse(
ast,
onNodeEnter = (node, scope) => {},
onNodeLeave = (node, scope) => {}
) {
const rootScope = new Scope(ast);
_inner(ast, rootScope);
/**
* Определение области видимости узла.
* Может либо вернуть текущий scope, либо создать новый.
*
* @param {object} astNode ast-узел.
* @param {Scope} currentScope Текущая область видимости.
* @return {Scope} Область видимости для внутренних узлов astNode.
*/
function resolveScope(astNode, currentScope) {
let isFunctionExpression = ast.type === 'FunctionExpression',
isFunctionDeclaration = ast.type === 'FunctionDeclaration';
if (!isFunctionExpression &&
!isFunctionDeclaration) {
// Новые области видимости порождают только функции.
return currentScope;
}
// Каждая функция порождает новую область видимости.
const newScope = new Scope(ast, currentScope);
ast.params.forEach(param => {
// Параметры функции доступны внутри функции.
newScope.add(param.name);
});
if (isFunctionDeclaration) {
// Имя функции при декларации доступно снаружи функции.
currentScope.add(ast.id.name);
} else {
// Имя функции-выражения доступно только внутри неё.
newScope.add(ast.id.name);
}
return newScope;
}
/**
* Рекурсивная функция обхода ast.
*
* @param {object} astNode Текущий ast-узел.
* @param {Scope} scope Область видимости для текущего ast-узла.
*/
function _inner(astNode, scope) {
if (Array.isArray(astNode)) {
astNode.forEach(node => {
/* Рекурсивный обход элементов списков.
* Списками являются, например, параметры функций.
*/
_inner(node, scope);
});
} else if (astNode && typeof astNode === 'object') {
onNodeEnter(astNode, scope);
const innerScope = resolveScope(astNode, scope),
keys = Object.keys(astNode).filter(key => {
// loc - служебное свойство, а не ast-узел.
return key !== 'loc' &&
astNode[key] && typeof astNode[key] === 'object';
});
keys.forEach(key => {
// Обход всех потомков.
_inner(astNode[key], innerScope);
});
onNodeLeave(astNode, scope);
}
}
}
/**
* Представление области видимости.
*
* @class Scope (name)
* @param {object} astNode ast-узел, породивший эту область видимости.
* @param {object} parentScope Родительская область видимости.
*/
function Scope(astNode, parentScope) {
this._node = astNode;
this._parent = parentScope;
this._vars = new Set();
}
Scope.prototype = {
/**
* Добавление имени переменной в область видимости.
*
* @param {string} name Имя переменной.
*/
add(name) {
this._vars.add(name);
},
/**
* Была ли определена переменная с таким именем.
*
* @param {string} name Имя переменной.
* @return {boolean} Встречалась ли переменная с таким именем в доступных областях видимости.
*/
isDefined(name) {
return this._vars.has(name) || (this._parent && this._parent.isDefined(name));
}
};Решение
Сначала разберёмся с ограничениями.
— он написан на ES3Значит, при обходе дерева могут встретится только самые базовые конструкции языка. Например, для манипуляций с массивами доступны только циклы.
— обращение к свойствам объекта возможно как через точку, так и через скобки (a.b и a['b'])То есть нужно искать не только Z.y.n, но и Z['y'].n, Z.y['n'] и Z['y']['n'].
часть выражения может быть сохранена в переменной, но никогда не передаётся в функцию параметром (a(x) — запрещено)Этот пункт сразу делает задачу в несколько раз сложнее, потому что придётся отслеживать значения переменных и области видимостей. Например, нужно будет назодить такой код: var x = Z.y; x.n(...).
— нет функций, которые возвращают часть искомого выражения,Эти пункты (как и запрет на передачу выражения в функции) упрощают задачу, но учитывать значения переменных и области видимости всё-таки придётся.
— нет свойств объектов или элементов массивов, которые содержат часть выражения,
— переменные получают свои значения при декларации и не переписываются, т.е. в коде не будет подобного var a = x; a = y; и var a = b = 1.
— при обращении к свойству объекта, название свойства может быть взято из переменной (a[x], x — переменная)Этот пункт окрывает ещё один способ обращения к свойствам объекта, за которым нужно следить: var x = 'y'; Z[x].n(...).
Cтановится понятен примерный план решения:
1. Обойти всё дерево, собрав информацию о значениях переменных, которые они получают при декларации.
2. Найти искомую конструкцию, учитывая информацию из предыдущего пункта.
Код, который дан в примечании задачи, может сэкономить немного времени в самом скучном месте — обходе дерева и сборе информации о названиях и параметрах функций. Поэтому возьмём его и начнём с пункта 2.
Поиск выражения
Разобьём поиск на две части: сначала найдём Z.y.n(function(a, b, c){...}), затем — использование первого аргумента внутри функции.
Первая часть соответствует FunctionExpression — первому и единственному параметру в CallExpression, у которого callee — MemberExpression. Причём имя property — n, а object (ещё один MemberExpression с object и property под именем y) — Z.
Вторая часть соответствует любому обращению к первому аргументу, потому что единственное допустимое действие — перезапись — запрещено условием. Обращение к первому аргументу — это Identifier с тем же именем, который встретился где угодно кроме MemberExpression и ObjectLiteral в качестве свойства (x.a и var x = {a: ...} соответственно).
+++ b/traverse.js
@@ -120,3 +120,59 @@ Scope.prototype = {
return this._vars.has(name) || (this._parent && this._parent.isDefined(name));
}
};
+
+module.exports = function (ast) {
+ var result = [];
+
+ traverse(ast, (node, scope) => {
+ if (node.type !== 'CallExpression') {
+ return;
+ }
+ let args = node.arguments;
+ if (args.length !== 1 ||
+ args[0].type !== 'FunctionExpression') {
+ return;
+ }
+ let callee = node.callee;
+ if (callee.type !== 'MemberExpression') {
+ return;
+ }
+ let property = callee.property,
+ object = callee.object;
+ if (property.name !== 'n') {
+ return;
+ }
+ if (object.type !== 'MemberExpression') {
+ return;
+ }
+ property = object.property;
+ object = object.object;
+ if (property.name !== 'y') {
+ return;
+ }
+ if (object.type !== 'Identifier' ||
+ object.name !== 'Z') {
+ return;
+ }
+
+ checkFunction(args[0]);
+ });
+
+ function checkFunction(ast) {
+ let firstArg = ast.params[0];
+ if (!firstArg) {
+ return;
+ }
+
+ traverse(ast.body, (node, scope) => {
+ if (node.type !== 'Identifier') {
+ return;
+ }
+ if (node.name === firstArg.name) {
+ result.push(node);
+ }
+ });
+ }
+
+ return result;
+};По последнему вызову traverse видно, что при обходе требуется информация о родителях, чтобы корректно отфильтровать идентификаторы в MemberExpression и ObjectProperty. Добавляем:
Открыть код
--- a/traverse.js
+++ b/traverse.js
@@ -60,16 +60,16 @@ function traverse(
* @param {object} astNode Текущий ast-узел
* @param {Scope} scope Область видимости для текущего ast-узла
*/
- function _inner(astNode, scope) {
+ function _inner(astNode, scope, parent) {
if (Array.isArray(astNode)) {
astNode.forEach(node => {
/* Рекурсивный обход элементов списков.
* Списками являются, например, параметры функций
*/
- _inner(node, scope);
+ _inner(node, scope, parent);
});
} else if (astNode && typeof astNode === 'object') {
- onNodeEnter(astNode, scope);
+ onNodeEnter(astNode, scope, parent);
const innerScope = resolveScope(astNode, scope),
keys = Object.keys(astNode).filter(key => {
@@ -80,10 +80,10 @@ function traverse(
keys.forEach(key => {
// Обход всех потомков
- _inner(astNode[key], innerScope);
+ _inner(astNode[key], innerScope, astNode);
});
- onNodeLeave(astNode, scope);
+ onNodeLeave(astNode, scope, parent);
}
}
}
@@ -164,10 +164,22 @@ module.exports = function (ast) {
return;
}
- traverse(ast.body, (node, scope) => {
+ traverse(ast.body, (node, scope, parent) => {
if (node.type !== 'Identifier') {
return;
}
+ if (!parent) {
+ return;
+ }
+ if (parent.type === 'MemberExpression' &&
+ parent.computed === false &&
+ parent.property === node) {
+ return;
+ }
+ if (parent.type === 'ObjectProperty' &&
+ parent.key === node) {
+ return;
+ }
if (node.name === firstArg.name) {
result.push(node);
}Нужно учесть и обращение к свойствам объектов через скобки. Создадим функцию getPropName:
Открыть код
--- a/traverse.js
+++ b/traverse.js
@@ -121,6 +121,18 @@ Scope.prototype = {
}
};
+function getPropName(node) {
+ let prop = node.property;
+
+ if (!node.computed) {
+ return prop.name;
+ }
+
+ if (prop.type === 'StringLiteral') {
+ return prop.value;
+ }
+}
+
module.exports = function (ast) {
var result = [];
@@ -137,17 +149,17 @@ module.exports = function (ast) {
if (callee.type !== 'MemberExpression') {
return;
}
- let property = callee.property,
+ let property = getPropName(callee),
object = callee.object;
- if (property.name !== 'n') {
+ if (property !== 'n') {
return;
}
if (object.type !== 'MemberExpression') {
return;
}
- property = object.property;
+ property = getPropName(object);
object = object.object;
- if (property.name !== 'y') {
+ if (property !== 'y') {
return;
}
if (object.type !== 'Identifier' ||Этот код всё ещё содержит недостатки: он никак не использует области видимости и переменые. Однако он хотя бы проходит первые три теста. Теперь переходим к пункту 1.
Улучшение Scope
Нужно добавить в Scope сбор информации о переменных и их значениях. Кроме того, нужно сделать так, чтобы собранная информация не терялась между вызовами traverse:
Открыть код
--- a/traverse.js
+++ b/traverse.js
@@ -1,3 +1,12 @@
+const scopeStorage = new Map();
+
+function getScopeFor(ast, outerScope) {
+ if (!scopeStorage.has(ast)) {
+ scopeStorage.set(ast, new Scope(ast, outerScope));
+ }
+
+ return scopeStorage.get(ast);
+}
/**
* Функция обхода дерева. Выполняет обход дерева в глубину,
* передавая в callback-функции onNodeEnter (до посещения потомков).
@@ -13,7 +22,7 @@ function traverse(
onNodeEnter = (node, scope) => {},
onNodeLeave = (node, scope) => {}
) {
- const rootScope = new Scope(ast);
+ const rootScope = getScopeFor(ast);
_inner(ast, rootScope);
@@ -36,19 +45,19 @@ function traverse(
}
// Каждая функция порождает новую область видимости.
- const newScope = new Scope(ast, currentScope);
+ const newScope = getScopeFor(ast, currentScope);
ast.params.forEach(param => {
// Параметры функции доступны внутри функции.
- newScope.add(param.name);
+ newScope.add(param.name, param);
});
if (isFunctionDeclaration) {
// Имя функции при декларации доступно снаружи функции.
- currentScope.add(ast.id.name);
+ currentScope.add(ast.id.name, ast);
} else if (ast.id) {
// Имя функции-выражения доступно только внутри неё.
- newScope.add(ast.id.name);
+ newScope.add(ast.id.name, ast);
}
return newScope;
@@ -98,7 +107,7 @@ function traverse(
function Scope(astNode, parentScope) {
this._node = astNode;
this._parent = parentScope;
- this._vars = new Set();
+ this._vars = new Map();
}
Scope.prototype = {
@@ -107,8 +116,24 @@ Scope.prototype = {
*
* @param {string} name имя переменной
*/
- add(name) {
- this._vars.add(name);
+ add(name, value) {
+ this._vars.set(name, {
+ value: value,
+ scope: this
+ });
+ },
+ resolve(node) {
+ if (!node) {
+ return node;
+ }
+ if (node.type === 'Identifier') {
+ let value = this._vars.get(node.name);
+ if (value) {
+ return value;
+ }
+ value = (this._parent && this._parent.resolve(node));
+ return value;
+ }
},
/**
* Была ли определена переменная с таким именем.
@@ -136,6 +161,12 @@ function getPropName(node) {
module.exports = function (ast) {
var result = [];
+ traverse(ast, (node, scope) => {
+ if (node.type === 'VariableDeclarator') {
+ scope.add(node.id.name, node.init);
+ }
+ });
+
traverse(ast, (node, scope) => {
if (node.type !== 'CallExpression') {
return;Использование Scope
Теперь добавим использование знаний о переменных. Каждая часть выражения может быть помещена в переменную, поэтому будем обращаться к Scope после после каждой части. Заметьте, что сам Scope тоже может меняться, поскольку значения переменных привязаны к своей области видимости:
Открыть код
--- a/traverse.js
+++ b/traverse.js
@@ -146,13 +146,17 @@ Scope.prototype = {
}
};
-function getPropName(node) {
+function getPropName(node, scope) {
let prop = node.property;
if (!node.computed) {
return prop.name;
}
+ let resolved = scope.resolve(prop);
+ if (resolved) {
+ prop = resolved.value;
+ }
if (prop.type === 'StringLiteral') {
return prop.value;
}
@@ -177,22 +181,43 @@ module.exports = function (ast) {
return;
}
let callee = node.callee;
+
+ let resolved = scope.resolve(callee);
+ if (resolved) {
+ callee = resolved.value;
+ scope = resolved.scope;
+ }
+
if (callee.type !== 'MemberExpression') {
return;
}
- let property = getPropName(callee),
+ let property = getPropName(callee, scope),
object = callee.object;
if (property !== 'n') {
return;
}
+
+ resolved = scope.resolve(object);
+ if (resolved) {
+ object = resolved.value;
+ scope = resolved.scope;
+ }
+
if (object.type !== 'MemberExpression') {
return;
}
- property = getPropName(object);
+ property = getPropName(object, scope);
object = object.object;
if (property !== 'y') {
return;
}
+
+ resolved = scope.resolve(object);
+ if (resolved) {
+ object = resolved.value;
+ scope = resolved.scope;
+ }
+
if (object.type !== 'Identifier' ||
object.name !== 'Z') {
return;Последние улучшения
Самое время ещё раз посмотреть на весь код: решение проходит только пять тестов из девяти. Можно выделить три проблемы:
— Нет проверки, что Z — это необходимый нам глобальный объект, а не какая-то переменная.
— Нет проверки, что в функции нашлось использование именно аргумента нужной функции, а не вложенной переменной с тем же именем.
— Получение значения переменной происходит только один раз, хотя условием не запрещены цепочки вида var a = 'x', b = a.
Исправляем эти три пункта, и решение готово.
Открыть код
--- a/traverse.js
+++ b/traverse.js
@@ -128,10 +128,23 @@ Scope.prototype = {
}
if (node.type === 'Identifier') {
let value = this._vars.get(node.name);
- if (value) {
- return value;
+ if (!value) {
+ if (this._parent) {
+ value = this._parent.resolve(node);
+ } else {
+ // Это глобальный scope, поэтому node —
+ // необъявленная глобальная переменная.
+ this.add(node.name, node);
+ return this.resolve(node);
+ }
+ }
+ if (!value) {
+ return;
+ }
+ if (value.value.type === 'Identifier' &&
+ value.value !== node) {
+ return value.scope.resolve(value.value) || value;
}
- value = (this._parent && this._parent.resolve(node));
return value;
}
},
@@ -165,12 +178,15 @@ function getPropName(node, scope) {
module.exports = function (ast) {
var result = [];
+
traverse(ast, (node, scope) => {
if (node.type === 'VariableDeclarator') {
scope.add(node.id.name, node.init);
}
});
+ let rootScope = getScopeFor(ast);
+
traverse(ast, (node, scope) => {
if (node.type !== 'CallExpression') {
return;
@@ -213,9 +229,10 @@ module.exports = function (ast) {
}
resolved = scope.resolve(object);
+ let zScope;
if (resolved) {
object = resolved.value;
- scope = resolved.scope;
+ zScope = resolved.scope;
}
if (object.type !== 'Identifier' ||
@@ -223,6 +240,10 @@ module.exports = function (ast) {
return;
}
+ if (zScope && zScope !== rootScope) {
+ return;
+ }
+
checkFunction(args[0]);
});
@@ -232,7 +253,10 @@ module.exports = function (ast) {
return;
}
- traverse(ast.body, (node, scope, parent) => {
+ traverse(ast, (node, scope, parent) => {
+ if (parent === ast) {
+ return;
+ }
if (node.type !== 'Identifier') {
return;
}
@@ -248,7 +272,9 @@ module.exports = function (ast) {
parent.key === node) {
return;
}
- if (node.name === firstArg.name) {
+
+ let resolved = scope.resolve(node);
+ if (resolved && resolved.value === firstArg) {
result.push(node);
}
});Полный код решения:
Открыть код
const scopeStorage = new Map();
function getScopeFor(ast, outerScope) {
if (!scopeStorage.has(ast)) {
scopeStorage.set(ast, new Scope(ast, outerScope));
}
return scopeStorage.get(ast);
}
/**
* Функция обхода дерева. Выполняет обход дерева в глубину,
* передаваяв callback-функции onNodeEnter (до посещения потомков)
* и onNodeLeave (после посещения потомков) каждый узел дерева
* и текущую область видимости (смотри определение Scope ниже)
*
* @param {object} ast Исходное ast
* @param {Function} [onNodeEnter=(node, scope)=>{}] Вызывается для каждого узла до посещения потомков
* @param {Function} [onNodeLeave=(node, scope)=>{}] Вызывается для каждого узла после посещения потомков
*/
function traverse(
ast,
onNodeEnter = (node, scope) => {},
onNodeLeave = (node, scope) => {}
) {
const rootScope = getScopeFor(ast);
_inner(ast, rootScope);
/**
* Определение области видимости узла.
* Может либо вернуть текущий scope, либо создать новый
*
* @param {object} ast ast-узел
* @param {Scope} currentScope текущая область видимости
* @return {Scope} область видимости для внутренних узлов astNode
*/
function resolveScope(ast, currentScope) {
let isFunctionExpression = ast.type === 'FunctionExpression',
isFunctionDeclaration = ast.type === 'FunctionDeclaration';
if (!isFunctionExpression &&
!isFunctionDeclaration) {
// Новые области видимости порждают только функции
return currentScope;
}
// каждая функция порождает новую область видимости
const newScope = getScopeFor(ast, currentScope);
ast.params.forEach(param => {
// параметры функции доступны внутри функции
newScope.add(param.name, param);
});
if (isFunctionDeclaration) {
// имя функции при декларации доступно снаружи функции
currentScope.add(ast.id.name, ast);
} else if (ast.id) {
// имя функции-выражения доступно только внутри неё
newScope.add(ast.id.name, ast);
}
return newScope;
}
/**
* Рекурсивная функция обхода ast
*
* @param {object} astNode Текущий ast-узел
* @param {Scope} scope Область видимости для текущего ast-узла
*/
function _inner(astNode, scope, parent) {
if (Array.isArray(astNode)) {
astNode.forEach(node => {
/* Рекурсивный обход элементов списков.
* Списками являются, например, параметры функций
*/
_inner(node, scope, parent);
});
} else if (astNode && typeof astNode === 'object') {
onNodeEnter(astNode, scope, parent);
const innerScope = resolveScope(astNode, scope),
keys = Object.keys(astNode).filter(key => {
// loc - служебное свойство, а не ast-узел
return key !== 'loc' &&
astNode[key] && typeof astNode[key] === 'object';
});
keys.forEach(key => {
// Обход всех потомков
_inner(astNode[key], innerScope, astNode);
});
onNodeLeave(astNode, scope, parent);
}
}
}
/**
* Представление области видимости
*
* @class Scope (name)
* @param {object} astNode ast-узел, породивший эту область видимости
* @param {object} parentScope Родительская область видимости
*/
function Scope(astNode, parentScope) {
this._node = astNode;
this._parent = parentScope;
this._vars = new Map();
}
Scope.prototype = {
/**
* Добавление имени переменной в область видимости
*
* @param {string} name имя переменной
*/
add(name, value) {
this._vars.set(name, {
value: value,
scope: this
});
},
resolve(node) {
if (!node) {
return node;
}
if (node.type === 'Identifier') {
let value = this._vars.get(node.name);
if (!value) {
if (this._parent) {
value = this._parent.resolve(node);
} else {
// Это глобальный scope, поэтому node -
// необъявленная глобальная переменная
this.add(node.name, node);
return this.resolve(node);
}
}
if (!value) {
return;
}
if (value.value.type === 'Identifier' &&
value.value !== node) {
return value.scope.resolve(value.value) || value;
}
return value;
}
},
/**
* Была ли определена переменная с таким именем.
*
* @param {string} name имя переменной
* @return {boolean} Встречалась ли переменная с таким именем в доступных областях видимости
*/
isDefined(name) {
return this._vars.has(name) || (this._parent && this._parent.isDefined(name));
}
};
function getPropName(node, scope) {
let prop = node.property;
if (!node.computed) {
return prop.name;
}
let resolved = scope.resolve(prop);
if (resolved) {
prop = resolved.value;
}
if (prop.type === 'StringLiteral') {
return prop.value;
}
}
module.exports = function (ast) {
var result = [];
traverse(ast, (node, scope) => {
if (node.type === 'VariableDeclarator') {
scope.add(node.id.name, node.init);
}
});
let rootScope = getScopeFor(ast);
traverse(ast, (node, scope) => {
if (node.type !== 'CallExpression') {
return;
}
let args = node.arguments;
if (args.length !== 1 ||
args[0].type !== 'FunctionExpression') {
return;
}
let callee = node.callee;
let resolved = scope.resolve(callee);
if (resolved) {
callee = resolved.value;
scope = resolved.scope;
}
if (callee.type !== 'MemberExpression') {
return;
}
let property = getPropName(callee, scope),
object = callee.object;
if (property !== 'n') {
return;
}
resolved = scope.resolve(object);
if (resolved) {
object = resolved.value;
scope = resolved.scope;
}
if (object.type !== 'MemberExpression') {
return;
}
property = getPropName(object, scope);
object = object.object;
if (property !== 'y') {
return;
}
resolved = scope.resolve(object);
let zScope;
if (resolved) {
object = resolved.value;
zScope = resolved.scope;
}
if (object.type !== 'Identifier' ||
object.name !== 'Z') {
return;
}
if (zScope && zScope !== rootScope) {
return;
}
checkFunction(args[0]);
});
function checkFunction(ast) {
let firstArg = ast.params[0];
if (!firstArg) {
return;
}
traverse(ast, (node, scope, parent) => {
if (parent === ast) {
return;
}
if (node.type !== 'Identifier') {
return;
}
if (!parent) {
return;
}
if (parent.type === 'MemberExpression' &&
parent.computed === false &&
parent.property === node) {
return;
}
if (parent.type === 'ObjectProperty' &&
parent.key === node) {
return;
}
let resolved = scope.resolve(node);
if (resolved && resolved.value === firstArg) {
result.push(node);
}
});
}
return result;
};F. Задача Framework-часов
Авторы: Дмитрий Андриянов, Алексей Бережной collapsusУчастникам нужно было написать приложение для необычной предметной области при помощи готового фреймворка с не очень удобным API. Мы хотели дать участникам только базовую часть документации фреймворка — чтобы узнать подробности, требовалось прочитать его код. В качестве предметной области мы выбрали управление стрелочными часами.
Условие
Степан работает галактическим коллектором — собирает долги за ЖКХ по всей галактической Империи. Степану нравится его работа. Она дает возможность побывать в таких местах, куда в другой ситуации он никогда бы не попал. Море впечатлений и новых знакомств!
Степану приходится часто перелетать с одной планеты на другую. Планеты вращаются по разным орбитам, поэтому на каждой планете собственный счёт времени. Секунды везде текут одинаково, но на разных планетах разное количество секунд в минуте, минут в часе, часов в сутках (но сутки всегда равны двум оборотам часовой стрелки). Также считается, что в прошлом была Точка начала отсчёта времени, в которой время на всех планетах было равно 0 (0 часов, 0 минут, 0 секунд).
Пожалуйста, сделайте для Степана часы, которые могут переключаться между временем разных планет. Для этого вы можете использовать JavaScript и JS-фреймворк под названием Framework.
Часы должны иметь три стрелки: часовую, минутную и секундную. В аргументах конструктора приходят параметры времени для планет и текущее время (количество секунд, прошедших от точки отсчета). Часы должны иметь кнопку переключения (циклического) между временем планет. При переводе стрелок можно двигать их по часовой стрелке или против неё (по наикратчайшему пути).
При включении часов все стрелки указывают на значение 0. Необходимо кратчайшим путем перевести стрелки в положение, соответствующее указанному времени (параметр time) на первой планете из списка.
Пример кода прошивки часов
const ONE_SECOND_DEGREES = 6;
const ONE_SECOND_FACTOR = 1 / Framework.SPEED * ONE_SECOND_DEGREES;
class MyClock extends Framework.Clock {
constructor() {
super();
this.arrows.push(new Framework.Arrow("seconds", {
color: "red"
}));
this.arrows.push(new Framework.Arrow("minutes", {
weight: 3,
length: 80
}));
this.arrows.push(new Framework.Arrow("hours", {
weight: 3,
length: 60
}));
this.buttons.push(new Framework.Button("A", () => {
alert("A");
}));
this.tick = 0;
}
onBeforeTick() {
const [arrow] = this.arrows;
this.tick++;
arrow.rotateFactor = this.tick % 10 ? 0 : ONE_SECOND_FACTOR;
console.log("before: " + arrow.pos);
}
onAfterTick() {
const [arrow] = this.arrows;
console.log("after: " + arrow.pos);
}
}Что мы узнали о фреймворке:
— часы — это класс, унаследованный от базового,
— у часов есть стрелки и кнопки,
— есть валик, к которому прикреплены стрелки; через небольшие промежутки времени (100 мс) валик проворачивается по часовой стрелке на определенный угол; можно управлять стрелками, меняя коэффициент вращения стрелки относительно валика.
Решение
Итак, на разных планетах время считается по-разному, но есть «Точка начала отсчёта времени», в результате чего количество секунд одинаково. Будем оперировать этой величиной, актуализируя её каждый тик, а затем пересчитывать время конкретной планеты, вычислять положение стрелок и перемещать их из текущего состояния в целевое.
В исходной версии прошивки есть три стрелки: секундная, минутная и часовая. Секундная движется в соответствии с условиями задачи. Необходимо, чтобы минутная и часовая стрелки тоже двигалась, и нужно добавить кнопку переключения между временами планет с соответствующим поведением.
Посмотрим исходный код фреймворка и для удобства определим константу:
const TPS = 1000 / Framework.INTERVAL; // тиков в секундуРеализуем функцию пересчёта тиков в положение секундной/минутной/часовой стрелок в градусах для конкретной планеты.
function getTarget(ticks, planet) {
const { h, m, s } = planet; // временные параметры планеты
const ts = Math.floor(ticks / TPS); // всего секунд
const ss = ts % s * 360 / s;
const mm = Math.floor(ts / s) % m * 360 / m;
const hh = Math.floor(ts / (s * m)) % h * 360 / h;
return { hh, mm, ss };
}Фреймворк реализован так, что у нас есть единственный способ управления движением стрелок — это задавать коэффициент вращения rotateFactor. Для этого напишем вспомогательную функцию getRotateFactor, которая будет считать коэффициент вращения, получая текущее положение стрелки и то положение, к которому нужно прийти. У функции будет два режима:
1. нормальный ход времени,
2. перевод стрелок.
Во втором режиме стрелки могут двигаться в обратную сторону. Режим передадим дополнительным параметром.
function getRotateFactor(pos, target, forward = true) {
let angle = target - pos; // на какой угол надо изменить положение стрелки
if (forward) {
// в случае обычного хода стрелок
angle < 0 && (angle += 360); // при прохождении круга количество градусов меняется от 0 до 360 (а 360 превращается в 0), нужно это учитывать
} else {
// в случае перевода двигаем стрелки по кратчайшему пути
Math.abs(angle) > 180 && (angle -= Math.sign(angle) * 360)
}
return angle / Framework.SPEED;
}Из кода фреймворка мы узнаём, что есть ограничение MAX_SPEED на скорость перемещения стрелки. Нужно это учесть в функции getRotateFactor.
const MAX_FACTOR = Framework.MAX_SPEED / Framework.SPEED;
function getRotateFactor(pos, target, forward = true) {
let angle = target - pos;
if (forward) {
angle < 0 && (angle += 360);
} else {
Math.abs(angle) > 180 && (angle -= Math.sign(angle) * 360)
}
const factor = angle / Framework.SPEED;
// если желаемый коэффициент превышает максимально допустимый, берём максимально допустимый
return Math.abs(factor) > MAX_FACTOR ? Math.sign(factor) * MAX_FACTOR : factor;
}Задаём обработчик для кнопки переключения между планетами:
buttonAHandler() {
// циклически переключаемся между планетами
this.pos = (this.pos + 1) % this.planets.length;
// переходим в режим перевода стрелок
this.forward = false;
}Таким образом, при каждом тике происходит следующее:
onBeforeTick() {
const [sec, min, hour] = this.arrows;
const time = ++this.ticks;
const planet = this.planets[this.pos];
// высчитываем положение стрелок к которому хотим прийти
const target = getTarget(time, planet);
// задаём каждой стрелке коэффициент вращения
sec.rotateFactor = getRotateFactor(sec.pos, target.ss, this.forward);
min.rotateFactor = getRotateFactor(min.pos, target.mm, this.forward);
hour.rotateFactor = getRotateFactor(hour.pos, target.hh, this.forward);
// выходим из режима перевода стрелок только тогда, когда все стрелки достигли желаемой позиции
!sec.rotateFactor && !min.rotateFactor && !hour.rotateFactor && (this.forward = true);
}Полный код решения:
Открыть
const TPS = 1000 / Framework.INTERVAL;
const MAX_FACTOR = Framework.MAX_SPEED / Framework.SPEED;
function getTarget(ticks, planet) {
const { h, m, s } = planet;
const ts = Math.floor(ticks / TPS); // total seconds
const ss = ts % s * 360 / s;
const mm = Math.floor(ts / s) % m * 360 / m;
const hh = Math.floor(ts / (s * m)) % h * 360 / h;
return { hh, mm, ss };
}
function getRotateFactor(pos, target, forward = true) {
let angle = target - pos;
if (forward) {
angle < 0 && (angle += 360);
} else {
Math.abs(angle) > 180 && (angle -= Math.sign(angle) * 360)
}
const factor = angle / Framework.SPEED;
return Math.abs(factor) > MAX_FACTOR ? Math.sign(factor) * MAX_FACTOR : factor;
}
class MyClock extends Clock {
// planets - параметры планет
// [ { h: 4, m: 20, s: 10 }, ... ]
constructor({ planets, time }) {
super();
this.arrows.push(new Arrow('seconds', {
color: 'red'
}));
this.arrows.push(new Arrow('minutes', {
weight: 3,
length: 80
}));
this.arrows.push(new Arrow('hours', {
weight: 3,
length: 60
}));
this.buttons.push(new Button('Switch', this.buttonAHandler.bind(this)));
this.planets = planets;
this.ticks = time * TPS;
this.pos = 0;
this.forward = false;
}
onBeforeTick() {
const [sec, min, hour] = this.arrows;
const time = ++this.ticks;
const planet = this.planets[this.pos];
const target = getTarget(time, planet);
sec.rotateFactor = getRotateFactor(sec.pos, target.ss, this.forward);
min.rotateFactor = getRotateFactor(min.pos, target.mm, this.forward);
hour.rotateFactor = getRotateFactor(hour.pos, target.hh, this.forward);
!sec.rotateFactor && !min.rotateFactor && !hour.rotateFactor && (this.forward = true);
}
buttonAHandler() {
this.pos = (this.pos + 1) % this.planets.length;
this.forward = false;
}
}Тестирование
Задание проверялось автотестами. В них мы сделали заглушку для генератора тиков и передавали её в параметрах конструктора. Таким образом, вместо того, чтобы генерировать тики по таймеру, мы генерировали нужное количество тиков в коде теста и затем проверяли состояние стрелок.
Мы проверяли несколько ситуаций: стандартное движение стрелок, дискретность движения, перевод стрелок, превышение максимальной скорости, направление движения стрелок при переводе (условия, связанные с направлением, были разными в разных вариантах задачи).
Вывод
Задача получилась довольно сложной. Участникам нужно было разобраться в необычной предметной области и незнакомом фреймворке. Часть условий были скрыты — например, максимальная скорость и возможность обратного хода. Узнать о них можно было только из кода фреймворка.
По нашей оценке, задача должна была занять около часа. Полностью её решили всего четыре человека, а больше нуля баллов (пройдя не все тесты) набрали 18 участников.
Ссылки:
— Разбор ML-трека второго чемпионата
— Разбор фронтенд-трека первого чемпионата
— Разбор фронтенд-трека в соревновании прошлого года
