Yandex Algorithm Save
Задачи Яндекс.Контеста 2019 по направлению Frontend и мои решения на них
Задачи Яндекс.Контест
Мне нравятся интересные задачи и я люблю участвовать в конкурсах, поэтому в данном репозитории собрана моя коллекция задач которые я решила и которые решу в будущем. Направление: frontend (javascript) Постаралась сохранить исходное форматирование, чтобы ничего не упустить и разделила по разным статусам:
-
– задача решена, все тесты Яндекс.Контеста пройдены
-
– пройдена только часть тестов Яндекс.Контеста
-
– задача решена и успешно работает с примерами из условия задачи, но тесты Яндекс.Контеста недоступны для прогона
-
– задача не решена совсем
Статус можно увидеть рядом с названием задачи. Каждой решенной задаче соответствует файл, который указан после статуса в содержании или под заголовком "Решение" после условия задачи.
Содержание
Весна 2019 Квалификация
A. Исследователи
Дан список, в которой хранятся исследователи и топонимы (имена мест) где они бывали. Список имеет следующий формат:
[
[<explorer1>, <toponym1>, <toponym2>, ...],
[<explorer2>, <toponym2>, <toponym3>, ...],
[<explorer3>, <toponym4>, <toponym1>, ...],
...
]
Надо развернуть этот список, таким образом, чтобы на первом месте оказался топоним, а на остальных исследователи.
Формат ввода
[
["Mallory", "Everest", "Mont Blanc", "Pillar Rock"],
["Mawson", "South Pole", "New Hebrides"],
["Hillary", "Everest", "South Pole"]
]
Формат вывода
[
["Everest", "Hillary", "Mallory"],
["South Pole", "Hillary", "Mawson"],
["Mont Blanc", "Mallory"],
["Pillar Rock", "Mallory"],
["New Hebrides", "Mawson"]
]
Примечания
Решение необходимо предоставить в виде CommonJS-модуль:
module.exports = function (explorers) {
// Your code here.
};
Вердикт RE также означает, что отправленное решение неверно.
Решение
Файл: A_reserachers.js
Комментарии:
Уверена, что эта задача должна решаться с помощью хэш списков, но, пока я не изучила алгоритмы и структуры данных, будет решение через массивы:
const searchers = [
["Mallory", "Everest", "Mont Blanc", "Pillar Rock"],
["Mawson", "South Pole", "New Hebrides"],
["Hillary", "Everest", "South Pole"]
];
function getToponim(arr) {
const allPoints = arr.reduce((acc, item) => {
acc = [...acc, ...item.slice(1)];
acc = Array.of(...new Set(acc))
return acc;
}, []);
const res = allPoints.map((point) => {
const searchersOnPoint = [];
searchers.forEach((searcher) => {
if (searcher.includes(point)) searchersOnPoint.push(searcher[0])
})
return [point, ...searchersOnPoint]
})
return res;
}
console.log(getToponim(searchers));
B. Раскраска карты
Вы попросили коллег раскрасить страны на нескольких географических картах. Но оказалось, что ваши коллеги иногда ошибаются и забывают покрасить какую-нибудь страну. Необходимо написать функцию, которая найдет все неокрашенные страны. Функция принимает на вход: - название начальной страны и ее цвет (например, code: ’RU’, color: ’red’); - функцию получения соседей (принимает на вход название страны и возвращает массив соседей с их цветами).
Функция должна вернуть промис, который разрешится массивом неокрашенных стран (typeof country.color === ’undefined’).
Нельзя вызывать функцию получения соседей параллельно. Нельзя использовать async/await и генераторы.
Интерфейс функции поиска соседей:
interface Country {
code: string;
color: string | undefined;
}
// Принимает название страны, возвращает список ее соседей.
function getNeightbors(countryCode: string): Promise<Country[]> {
// ...
}
Решение необходимо предоставить в виде CommonJS-модуль:
/**
* @param {Country} startCountry
* @param {Function} getNeightbors
*/
module.exports = function (startCountry, getNeightbors) {
// Your code here.
};
Вердикт RE также означает, что отправленное решение неверно.
Формат ввода
Начальная точка A (code: ’A’, color: ’red’).
getNeighbors(’A’) вернет:
[
{code: ’B’, color: ’red’},
{code: ’F’, color: ’red’},
{code: ’E’, color: ’green’},
]
getNeighbors(’E’) вернет:
[
{code: ’A’, color: ’red’},
{code: ’F’, color: ’red’},
{code: ’D’, color: undefined},
]
и т.д. Решение должно вернуть массив с непокрашенными странами (порядок элементов в массиве не важен) [’D’]
C. Секретное сообщение
На старой заброшенной базе геодезистов вы нашли код, который возвращает секретные послания, зашифрованные среди географических данных. Скрипт содержит несколько синтаксических ошибок и кажется работает очень медленно. Ваша задача - привести его в порядок.
Формат ввода
const data1 = [
{
"geometry": [20, 40],
"part1": "Three",
"part2": "3"
},
{
"geometry": [5, 40],
"part1": "One",
"part2": "1"
},
{
"geometry": [30, 40],
"part1": "Four",
"part2": "4"
}
];
const data2 = [
{
"geometry": [10, 20],
"part1": "Two",
"part2": "2"
},
{
"geometry": [40, 20],
"part1": "Five",
"part2": "5"
}
];
const maxLength = 3;
Формат вывода
[
"One Three Four",
"Two Five",
"Message is too long"
]
Примечания
В модуле task.js описан метод, который принимает на вход три аргумента - data1, data2 и maxLength. В переменной data1 и data2 передаются массивы объектов вида:
{
geometry: [number, number];
part_1: string;
part_2: string;
}
В переменной maxLength передается максимально разрешенная длина итогового сообщения. Чтобы получить секретное сообщение из набора геоданных, нужно отсортировать данные в массиве по первой координате из поля geometry, а затем сложить в строку слова, хранящиеся в одном из полей.
Вам нужно получить три сообщения. Первые два сообщения должны получиться из массивов data1 и data2 путем сложения строк из поля part1. Третье сообщение должно получиться из объединненых массивов data1 и data2 путем сложения строк из поля part2.
К сожалению, ленивые переводчики отказываются работать со слишком длинными сообщениями, поэтому если какое-то из сообщений содержит больше maxLength слов, вместо сообщения нужно вывести строку "Message is too long".
Решение необходимо предоставить в виде исправленого модуля task.js. Вердикт RE также означает, что отправленное решение неверно.
D. Логотип Конструктора карт
Дизайнер обновил логотип Конструктора карт (масштаб x5):
Его потребуется использовать в самых разных условиях. Чтобы это было максимально удобно, сверстайте его с помощью одного HTML-элемента на чистом CSS. Использовать картинки (даже через data:uri) нельзя.
Примечания
Цвет фона: #fc0
Цвета центрального круга: #f00
Цвет внешнего круга: #fff
Цвет "ножки": #fa0000
Решение нужно предоставить в виде CSS-файла.
Ваш файл будет подключен как solution.css к HTML-странице вида:
<!DOCTYPE html>
<html>
<head>
<style>
body {
margin: 0;
}
</style>
<link rel="stylesheet" href="solution.css">
</head>
<body>
<div></div>
</body>
</html>
Важно: логотип должен находиться в верхнем левом углу страницы, вплотную прижатый к нему.
Ваше решение будет тестироваться в браузере Google Chrome 69. Рекомендуем использовать плагины для pixel-perfect верстки, например, PerfectPixel.
E. Виджет организации
| Название | Значение |
|---|---|
| Ограничение времени | 10 секунд |
| Ограничение памяти | 256Mb |
| Ввод | input.html |
| Вывод | стандартный вывод или output.png |
Разработчик Виктор сверстал виджет для показа информации об организации. Все было хорошо. Но потом дизайнер прислал правки: было необходимо скруглить углы виджета и сделать вариант уменьшенного виджета. Также виджет выглядел странно при добавлении более длинного текста. Нужно помочь Виктору починить макет.
Желаемый результат:
Примечания
Необходимо привести внешний вид в соответствии с требованиями с наименьшим количеством изменений в текущем CSS-файле.
Текущие CSS-стили: solution.css.
После исправлений, нужно предоставить обновленный CSS-файл. Данный файл будет подключен как solution.css к HTML-странице.
Ваше решение будет тестироваться в браузере Google Chrome 69. Семейство и другие параметры шрифтов изменять не надо. При этом локально у вас может не совпадать шрифт с ожидаемым состоянием, т.к. скриншоты сделаны в Ubuntu.
Рекомендуем использовать плагины для pixel-perfect верстки, например, PerfectPixel.
F. Путь через снега
| Название | Значение |
|---|---|
| Ограничение времени | 10 секунд |
| Ограничение памяти | 256Mb |
В городе X очень суровая зима. Для того, чтобы люди могли как-то перемещаться по городу в морозы и бураны в нём работает сеть специальных заведений, где каждый прохожий может оттаять, согреться. Чтобы помочь пользователям наших картографических сервисов, мы решили добавить возможность построения "теплых"пеших маршрутов, которые учитывали бы такие заведения. Напишите алгоритм, который прокладывал бы путь через сеть улиц, не позволяя пользователю проходить больше двух точек подряд не погревшись. Считается в стартовой и конечной точках маршрута пользователю есть где укрыться от мороза. Дан неориентированный граф, часть вершин которого отмечены (места, где можно погреться). Нужно найти кратчайший путь между первой и последней вершинами, такой, что хотя бы одна из каждых трех идущих подряд вершин была бы отмечена, или сказать, что такого пути нет.
Граф представлен списком смежности: массивом, где каждый индекс - это номер вершины, а значение доступное по индексу - это массив с номерами вершин с которыми данная вершина соединена. Т.к. граф неориентирован, матрица связей всегда симметрична. Т.е. если ‘graph[N].contains(M)‘ то и ‘graph[M].contains(N)‘. Вершины в списке связей / списке отмеченных точек не обязательно упорядочены. Например такой вот цикличный граф, состоящий из четырех вершин:
0 --- 1
| |
3 --- 2
в виде списка смежности выглядит так:
[
[1,3],
[0,2],
[1,3],
[0,2]
]
Интересующий нас путь начинается от вершины с индексом 0 и заканчивается в вершине с максимальным номером. Первая и последняя вершины всегда отмечены. Отмеченные вершины передаются в виде массива с их номерами. Например, [2,4,7]. Максимальное количество вершин в графе не превышает 10e4. Максимальное количество связей не превышает 10e6. Любое количество вершин в графе может быть отмечено (от 2ух до всех). Желательно, чтобы алгоритм быстро работал даже на больших графах.
Формат ввода
0!
| \
1 2
| \
3 4
| \
5! 6
| \
7---8---9!
const graph = [
[1,2],
[0,3],
[0,4],
[1,5],
[2,6],
[3,7],
[4,9],
[5,8],
[7,9],
[6,8]
];
const markedVertices = [0,5,9];
Формат вывода
6
Искомый путь: 0,1,3,5,7,8,9.
Примечания
Решение необходимо предоставить в виде CommonJS-модуль (функция вернет количество шагов в пути, если путь есть, или null, если пути не существует):
module.exports = function findShortestMarkedPathLength(graph, markedVertices) {
// Your code here.
};
Весна 2019 Финал
Осень 2019 Квалификация
A. Время - деньги (15 баллов)
Коля изобрёл машину времени у себя в гараже и решил на этом заработать. Но так как он знает, что Организация Контроля Времени может забрать у него машину, он решил вести себя осторожнее и использовать рынок ценных бумаг в качестве источника дохода.
Он отправился в будущее, посмотрел там историю котировок по акциям компании FAIS. Компания примечательна тем, что один человек может держать только одну акцию. Но когда Коля увидел историю, он понял, что сам не сможет вычислить, когда нужно покупать акцию, а когда продавать. Тогда он обратился за помощью к вам, пообещав отдать половину заработанных денег.
Вам прекрасно известно, что за подобные махинации могут оштрафовать или даже посадить в тюрьму, и вы решили посчитать, стоит ли участвовать в этом. Вы уже решали подобную алгоритмическую задачу пару лет назад и смогли найти свой старый код. К сожалению, его производительности не хватает, чтобы посчитать результат за адекватное время.
Вам нужно оптимизировать представленную программу, которая вычисляет максимально возможный доход из всех возможных, опираясь на данные котировок. При этом не нужно учитывать деньги, которые тратятся на покупку акций, так как Коля собирается взять их со своего счёта.
Ваш старый код
Входные данные — массив чисел, каждое из которых отражает цену акции в конкретный день. Выходные данные — одно число, обозначающее максимально возможную прибыль.
var maxProfit = function (prices) {
return calculate(prices, 0);
}
function calculate(prices, index) {
if (index >= prices.length) {
return 0;
}
var maxProfix = 0;
for (var start = index; start < prices.length; start++) {
var localMaxProfit = 0;
for (var i = start + 1; i < prices.length; i++) {
if (prices[start] < prices[i]) {
var profit = calculate(prices, i + 1) + prices[i] - prices[start];
if (profit > localMaxProfit) {
localMaxProfit = profit;
}
}
}
if (localMaxProfit > maxProfix)
maxProfix = localMaxProfit;
}
return maxProfix;
}
Примеры работы
Пример 1
Вход: [71, 11, 51, 31, 61, 41]
Выход: 70
Покупаем во второй день по цене 11 и продаём на третий день за 51, прибыль — 40. После этого покупаем за 31 в четвёртый день и продаем на пятый за 61, прибыль — 30. В итоге получаем прибыль 70.
Пример 2
Вход: [13, 24, 35, 46, 57]
Выход: 44
Покупаем в первый день, продаём в последний.
Пример 3
Вход: [700, 612, 445, 343, 10]
Выход: 0
Здесь вообще невозможно заработать, поэтому максимальная прибыль — 0.
Примечания
В качестве решения предоставьте файл, который экспортирует исправленный вариант функции maxProfit:
function maxProfit(prices) {
// ...
}
module.exports = maxProfit;
Решение будет запускаться в Nodejs 12.
Решение
Файл: A_moneytime.js
Комментарии:
Здесь обратила внимание на то, что нужно чтобы код просто быстро работал, а этому мешает рекурсия:
function maxProfit(prices) {
let localMaxProfit = 0;
for (let i = 0, l = prices.length; i < l; i++) {
if (i + 1 !== l && prices[i] < prices[i+1]) {
localMaxProfit += prices[i+1] - prices[i];
}
}
return localMaxProfit;
}
const entry = [71,11,51,31,61,41]; // 70
const entry2 = [13,24,35,46,57]; // 44
const entry3 = [700,612,445,343,10]; // 0
console.log(maxProfit(entry), maxProfit(entry2), maxProfit(entry3));
B. Парсер событий (15 баллов)
Менеджер Евгений решил сделать бота для популярного мессенджера, чтобы автоматически добавлять события в свой календарь. Раз в определенное время бот должен распознавать специально размеченный текст и отправлять его в сервис, который ожидает данные в специальном формате. В силу низкой квалификации в программировании Евгению нужна помощь с модулем, который принимает массив строк и формирует из них строку для сервиса календаря.
Формат ввода
В каждой строке название мероприятия содержится в кавычках, а дата — в одном из форматов:
DD.MM.YYYY, DD.MM.YY, DD/MM/YYYY, DD/MM/YY
Пример входных данных:
[
"В это воскресенье (22.09.2019) будет великолепное время, чтобы \"Пробежать марафон\".",
"А вот \"Садить деревья\" стоит на следующий день (23/09/19), ведь будет стоять жара."
]
Могут быть и строки, в которых нет нужных данных. Такие строки следует игнорировать.
Формат вывода
Для примера выше должна вернуться строка:
"Пробежать марафон": 22.09.2019
"Садить деревья": 23.09.19
Решение должно быть оформлено в виде commonJS-модуля:
module.exports = function(input) {
}
Решение
Файл: B_eventparser.js
Комментарии:
Решила задачу с использованием indexOf, код не прошел второй тест и только тогда до меня дошло, что данная задача должна решаться с помощью регулярок (которые я не знаю). Переписала на регулярки как смогла, в итоге даже первый тест был не пройден :D. Оставила тот код, который хотя бы частично работал:
function taskParser(strings) {
const res = [];
for (let i = 0, l = strings.length; i < l; i++) {
// для поиска события
const beginEvent = strings[i].indexOf('\"');
const endEvent = strings[i].indexOf('\"', beginEvent+1);
const event = (beginEvent !== -1 && endEvent !== -1) ? strings[i].slice(beginEvent+1, endEvent) : null;
// для поиска даты
const beginDate = strings[i].indexOf('(');
const endDate = strings[i].indexOf(')');
const dateOfString = (beginDate !== -1 && endDate !== -1) ? strings[i].slice(beginDate+1, endDate) : null;
const date = dateOfString && getDate(dateOfString);
if (date !== null && event !== null) {
const dateMatch = strings[i].match(/\d{2}[\/?\.]\d{2}[\/?\.]\d{2,4}/)[0].split('/').join('.');
const eventFromString = `\"${event}\": ${dateMatch}`
res.push(eventFromString);
}
}
function getDate(dateOfString) {
let stringArr;
if (dateOfString.indexOf('.') !== -1) {
stringArr = dateOfString.split('.');
} else if (dateOfString.indexOf('/') !== -1) {
stringArr = dateOfString.split('/');
}
const everyIsNumber = stringArr.length === 3 && stringArr.every((item) => isNumber(item) && item.length <= 4);
const isDate = stringArr[0] <= 31 && stringArr[1] <= 12;
if (everyIsNumber && isDate) {
return stringArr.join('.');
}
return null;
}
function isNumber(n) { return !isNaN(parseFloat(n)) && !isNaN(n - 0) }
return res.join('\n');
}
function tasker2(strings) {
const res = [];
for (let i = 0, l = strings.length; i < l; i++) {
const dateMatch = strings[i].match(/\d{2}[\/?\.]\d{2}[\/?\.]\d{2,4}/);
const eventMatch = strings[i].match(/("|')([^"']+)/);
if (dateMatch && eventMatch) {
res.push(eventMatch[0] + ": " + dateMatch[0])
}
}
return res.join('\n');
}
const entry = [
"В это воскресенье (22.09.2019) будет великолепное время, чтобы \"Пробежать марафон\".",
"А вот \"Садить деревья\" стоит на следующий день (23/09/19), ведь будет стоять жара."
];
// '"Пробежать марафон": 22.09.2019\n"Садить деревья": 23.09.19';
// "Садить деревья": 23.09.19
console.log(tasker(entry));
C. Идентификация котиков (40 баллов)
Сильный и независимый программист Вася держит дома 12 котов. Коты ходят гулять на улицу, и Вася хочет следить за тем, как каждый из них уходит и возвращается. Для этого Вася установил над дверцей для котов веб-камеру, которая делает фото, когда кот входит и выходит. Чтобы автоматически различать котов между собой, Вася придумал напечатать на их ошейниках баркоды, для отрисовки которых он придумал собственный алгоритм.
Помогите Васе написать функцию, которая отрисовывает баркод для ошейников его котов.
Формат информации о коте
Вася хранит информацию о котах в виде объектов:
type CatInfo = {
/**
* Кличка кота - строка из маленьких и больших
* латинских букв и цифр, и пробелов (от 0 до 11 символов)
*/
name: string;
/**
* Идентификатор кота - целое число от 0 до 255
*/
id: number;
/**
* Дата родждения кота в формате UNIX timestamp
*/
birthday: number;
}
Алгоритм отрисовки баркода
Баркоды, которые придумал Вася, выглядят так:
В баркоде две основные секции: контент и контрольная сумма, ограниченные прямоугольниками шириной 7 пикселей с толщиной границы 3 пикселя.
Контент представляет собой 8 строк по 16 черных или белых квадратов в каждой строке (размер одного квадрата 8 на 8 пикселей), строки заполняются последовательно сверху вниз. Контрольная сумма — это столбец из 8 квадратов.
Белые квадраты в контенте кодируют 0, чёрные — 1.
Алгоритм формирования контента баркода
Поле name дополняется пробелами в конце до 11 символов и конвертируется в байтовый массив — каждому символу строки ставится соответствующий ASCII-код (число от 0 до 255).
Каждый элемент полученного массива переводится в двоичную запись (восемь сивмолов 0 или 1) и кодируется последовательностью из восьми квадратов (0 — белый квардрат, 1 — чёрный квадрат). Квадраты отрисовываются в контенте баркода последовательно и построчно.
Далее поле id конвертируется в 8-битное двоичное число, которое кодируется последовательностью из восьми квадратов и дописывается в контент баркода.
Затем поле birthday переводится в 32-битное двоичное число, которое по такому же принципу кодируется квадратами и дописывается в конец баркода.
Алгоритм формирования контрольной суммы
Контрольная сумма вычисляется по строкам контента. Для отрисовки квадрата контрольной суммы определяется чётность суммы значений контента в соответствующей строке. Если значение чётное — в строке рисуется белый квадрат, в противном случае — чёрный.
Формат решения
Загружаемое вами решение должно содержать функцию renderBarcode:
/**
* Отрисовать баркод для кота
* @param catInfo {CatInfo} - информация о коте
* @param element {HTMLDivElement} - div с фиксированным размером 157x64 пикселей,
* в который будет отрисовываться баркод
*/
function renderBarcode(catInfo, element) {
// ваш код
}
Решение будет запускаться в браузере Google Chrome 77.
Примеры работы
Информация о коте:
{
"id": 185,
"name": "Murzick",
"birthday": 1164210686
}
Баркод:
{
"id": 96,
"name": "Ferdinand",
"birthday": 1429648740
}
Баркод:
Решение
Файлы: C_catsindent.js, C_catsindent.html
Комментарии:
Мне всегда было интересно как генерируется QR код. Казалось что это мега сложно, поэтому к этой задаче приступала неохотно тк была уверена, что не успею решить за оставшееся время. Каково же было мое удивление, когда код прошел все тесты с первого раза. И теперь я научилась кодировать информацию. Эта задача мне понравилась больше всего, тут и котики и программирование, и в голове давно уже сидит pet project, в котором такая функция точно пригодится:
const entry1 = {
"id": 185,
"name": "Murzick",
"birthday": 1164210686
}
const entry2 = {
"id": 96,
"name": "Ferdinand",
"birthday": 1429648740
}
const div = document.getElementById('barcode');
function renderBarcode(catInfo, element) {
const separator = '<div style="width: 1px; border: 3px solid black"></div>';
const squereBlack = '<div style="width: 8px; height: 8px; background-color: black"></div>';
const squereWhite = '<div style="width: 8px; height: 8px; background-color: white"></div>';
const content = [];
const summContent = [];
for (let nameLength = catInfo.name.length; nameLength < 11; nameLength ++) {
catInfo.name += ' ';
}
const asciName = catInfo.name.split('').map((symb) => symb.charCodeAt(0).toString(2));
const codeName = toEightSymb(asciName, 8);
const codeId = toEightSymb([catInfo.id.toString(2)], 8);
const codeBirthD = toEightSymb([catInfo.birthday.toString(2)], 32);
const code = codeName.join('') + codeId.join() + codeBirthD;
for (let i = 0, l = code.length; i < l; i++) {
if (+code[i] === 0) {
content.push(squereWhite);
} else if (+code[i] === 1) {
content.push(squereBlack);
}
}
for (let i = 0, l = code.length, sum = 0; i <= l; i++) {
if (i%16 === 0 && i !== 0) {
if (sum%2 === 0) {
summContent.push(squereWhite);
} else {
summContent.push(squereBlack);
}
sum = +code[i];
} else {
sum += +code[i];
}
}
function toEightSymb(string, base) {
return string.map((item) => {
for (let itemLength = item.length; itemLength < base; itemLength++) {
item = '0' + item;
}
return item;
});
}
element.innerHTML = '<div style="display: flex; width: 100%; height: 100%; align-items: stretch">' + separator + '<div style="display: flex; flex-wrap: wrap; width: 128px; height: 100%">' + content.join('') + '</div>' + separator + '<div style="display: flex; flex-direction: column">' + summContent.join('') + '</div>' + separator + '</div>';
}
renderBarcode(entry1, div);
D. Живая сталь (40 баллов)
На планете Ксетаксис живёт два племени огромных боевых человекоподобных роботов, которые уже давно воюют друг с другом.
Представители более развитой расы «космических жокеев» с другой планеты, которые сканируют Вселенную в поисках разумной жизни, установили, что в стародавние времена по планете прошёл компьютерный вирус, который изменил таблицы во внутренней документации некоторых роботов — с markdown-подобного внутреннего формата на HTML. Из-за этого общение между роботами было нарушено и разразилась война.
Помогите написать скрипт, который сконвертирует таблицы обратно во внутренний формат, понятный каждому роботу, и восстановит мир на планете. Роботы не должны страдать!
Вам нужно написать функцию, которая на вход принимает HTML таблицы и преобразует его в wiki-подобную разметку.
В качестве решения этого задания отправьте файл .js, в котором объявлена функция solution:
function solution(input) {
// ...
}
Формат ввода
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</th>
<th>Yes </th>
</tr>
<tr>
<th>git diff</td>
<td>Show file differences that have not 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.
Формат вывода
На выходе должна получиться строка с wiki-подобной разметкой:
^ Command ^ Description ^ Is implemented ^
^ git status | List all new or modified files ^ Yes |
^ git diff | Show file differences that have not been staged | No |
Разделитель перед ячейкой таблицы выводится в зависимости от того, th это или td. Карет для th — ^, и вертикальная черта для td — |.
Все ячейки строк из thead должны быть разделены через карет вне зависимости от того, tdэто или th. Все строки, получившиеся из thead, должны завершаться каретом, а из tbody — вертикальной чертой. Пробелы по краям содержимого тегов td и th должны быть удалены.
Переносы строк в содержимом ячеек должны быть удалены.
Более одного пробела подряд в содержимом ячеек должны быть заменены одним пробелом.
За выравнивание в ячейках столбцов результирующей wiki-подобной таблицы отвечают пробелы вокруг содержимого ячейки:
- | xxx | два пробела справа и один слева значит выравнивание влево
- | xxx | два пробела по обоим сторонам значат выравнивание по центру
- | xxx | два слева и один справа — по правому краю
При отсутствии заданного в теге col атрибута align выравнивание должно быть задано влево.
Примечания
- Для перевода строки нужно использовать символ \n.
- Решение будет проверяться в браузерном окружении (Chrome 78) с доступом к объектам document и window.
- Можно использовать синтаксис до es2018 включительно.
E. Пандемия вируса (50 баллов)
Всемирная Организация Здравоохранения опубликовала доклад о признаках надвигающейся пандемии нового вируса, который угрожает фронтенд-разработчикам. Известно, что вирус никак не проявляет себя до тех пор, пока носитель не увидит js-код, содержащий некоторое выражение. Как только заражённый увидел это выражение, он теряет способность писать код на js и начинает непроизвольно писать код на фортране.
В докладе упоминается, что вирус активируется от взгляда на использование первого аргумента функции, передаваемой аргументом в вызов функции ‘Z.y.n‘, то есть заражённым нельзя показывать выражение, подобное ‘Z.y.n(function(a, b, c){console.log(a)})‘.
Чтобы не потерять случайно всех своих фронтендеров, в компании AST & Co решили проверить, содержит ли их код упомянутое выражение. Помогите инженерам компании написать такую проверку.
Про код в компании AST & Co известно, что:
- он написан на es3,
- переменные получают свои значения при декларации и не переписываются, т.е. в коде не будет подобного ‘var a = x; a = y;‘ и ‘var a = b = 1;‘,
- обращение к свойствам объекта возможно как через точку, так и через скобки (‘a.b‘ и ‘a[’b’]‘),
- часть выражения может быть сохранена в переменной, но никогда не передаётся в функцию параметром (‘a(x)‘ — запрещено),
- нет функций, которые возвращают часть искомого выражения,
- нет свойств объектов или элементов массивов, которые содержат часть выражения,
- при обращении к свойству объекта, название свойства может быть взято из переменной (‘a[x]‘, x — переменная).
Проверка должна быть оформлена в виде CommonJS-модуля, который экспортирует функцию, принимающую на вход абстрактное синтаксическое дерево (ast) проверяемого кода.
Функция должна вернуть массив из ast-узлов, которые соответствуют местам использования первого параметра callback-функции, передаваемой аргументом в ‘Z.y.n‘. Порядок элементов в массиве не важен, дубли не допускаются.
module.exports = function (ast) {
...
return [...];
}
Ast получается из js-кода с помощью модуля @babel/parser версии 7.6.0.
const parser = require(’@babel/parser’),
ast = parser.parse(code);
Пример
Ввод
{
"type": "File",
"start": 0,
"end": 97,
"program": {
"type": "Program",
"start": 0,
"end": 97,
"sourceType": "script",
"interpreter": null,
"body": [
{
"type": "ExpressionStatement",
"start": 0,
"end": 48,
"expression": {
"type": "CallExpression",
"start": 0,
"end": 47,
"callee": {
"type": "MemberExpression",
"start": 0,
"end": 5,
"object": {
"type": "MemberExpression",
"start": 0,
"end": 3,
"object": {
"type": "Identifier",
"start": 0,
"end": 1,
"name": "Z"
},
"property": {
"type": "Identifier",
"start": 2,
"end": 3,
"name": "y"
},
"computed": false
},
"property": {
"type": "Identifier",
"start": 4,
"end": 5,
"name": "n"
},
"computed": false
},
"arguments": [
{
"type": "FunctionExpression",
"start": 6,
"end": 46,
"id": null,
"generator": false,
"async": false,
"params": [
{
"type": "Identifier",
"start": 16,
"end": 17,
"name": "a"
}
],
"body": {
"type": "BlockStatement",
"start": 19,
"end": 46,
"body": [
{
"type": "ReturnStatement",
"start": 25,
"end": 44,
"argument": {
"type": "Identifier",
"start": 42,
"end": 43,
"name": "a"
}
}
],
"directives": []
}
}
]
}
},
{
"type": "ExpressionStatement",
"start": 50,
"end": 96,
"expression": {
"type": "CallExpression",
"start": 50,
"end": 95,
"callee": {
"type": "MemberExpression",
"start": 50,
"end": 55,
"object": {
"type": "MemberExpression",
"start": 50,
"end": 53,
"object": {
"type": "Identifier",
"start": 50,
"end": 51,
"name": "Z"
},
"property": {
"type": "Identifier",
"start": 52,
"end": 53,
"name": "y"
},
"computed": false
},
"property": {
"type": "Identifier",
"start": 54,
"end": 55,
"name": "n"
},
"computed": false
},
"arguments": [
{
"type": "FunctionExpression",
"start": 56,
"end": 94,
"id": null,
"generator": false,
"async": false,
"params": [
{
"type": "Identifier",
"start": 66,
"end": 67,
"name": "x"
}
],
"body": {
"type": "BlockStatement",
"start": 69,
"end": 94,
"body": [
{
"type": "ExpressionStatement",
"start": 75,
"end": 92,
"expression": {
"type": "CallExpression",
"start": 75,
"end": 91,
"callee": {
"type": "MemberExpression",
"start": 75,
"end": 86,
"object": {
"type": "Identifier",
"start": 75,
"end": 82,
"name": "console"
},
"property": {
"type": "Identifier",
"start": 83,
"end": 86,
"name": "log"
},
"computed": false
},
"arguments": [
{
"type": "StringLiteral",
"start": 87,
"end": 90,
"extra": {
"rawValue": "x",
"raw": "'x'"
},
"value": "x"
}
]
}
}
],
"directives": []
}
}
]
}
}
],
"directives": []
}
}
Вывод
[
{
"type": "Identifier",
"start": 42,
"end": 43,
"name": "a"
}
]
Примечания
Следующий код можно взять за основу для обхода дерева.
/**
* Функция обхода дерева. Выполняет обход дерева в глубину,
* передаваяв 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));
}
};
F. Галактический коллектор (60 баллов)
Степан работает галактическим коллектором — собирает долги за ЖКХ по всей галактической Империи. Степану нравится его работа. Она дает возможность побывать в таких местах, куда в другой ситуации он никогда бы не попал. Море впечатлений и новых знакомств!
Степану приходится часто перелетать с одной планеты на другую. Планеты вращаются по разным орбитам, поэтому на каждой планете собственный счёт времени. Секунды везде текут одинаково, но на разных планетах разное количество секунд в минуте, минут в часе, часов в сутках (но сутки всегда равны двум оборотам часовой стрелки). Также считается, что в прошлом была Точка начала отсчёта времени, в которой время на всех планетах было равно 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);
}
}
Формат параметров конструктора
// текущее время (количество секунд от точки отсчета времени)
const time = 1267457;
// параметры планет
// h — количество часов в одном обороте стрелки
// m — количество минут в часе
// s — количество секунд в минуте
const planets = [
{ h: 4, m: 20, s: 10 },
{ h: 12, m: 60, s: 60 }
];
const app = new MyClock({ planets, time });
Пример
Ввод
{
"comments": "положение стрелок",
"steps": [
{ "ticks": 10 },
{ "button": 0, "ticks": 10 },
{ "button": 0, "ticks": 10 }
],
"params": {
"time": 615,
"planets": [
{ "h": 6, "m": 30, "s": 30 },
{ "h": 12, "m": 60, "s": 60 }
]
}
}
Вывод
[
{
"seconds": 192,
"minutes": 240,
"hours": 0
},
{
"seconds": 102,
"minutes": 60,
"hours": 0
},
{
"seconds": 216,
"minutes": 240,
"hours": 0
}
]
Примечания
Откройте HTML-файл тестовой страницы по ссылке «Скачать условие задачи» в конце описания. Вам нужно написать на JavaScript класс с названием MyClock, который реализует поведение, описанное в условии.
class MyClock extends Framework.Clock {
// ваш код
}
При проверке, файл с вашим решением будет подключен на тестовую страницу в место, обозначенное комментарием:
<!-- в качестве решения предоставьте файл solution.js -->
<script src="solution.js"></script>
Идентификаторы стрелок (первый параметр их конструктора) должны быть такими же, как в примере: "seconds", "minutes", "hours". Ваше решение будет тестироваться в браузере Google Chrome 77.
Осень 2019 Финал
A. Асинхронный API из параллельной вселенной (15 баллов)
Ваш коллега-разработчик из параллельной вселенной прислал вам свою новую библиотеку для управления космическим кораблем. Т.к. космический корабль штука сложная, то и API у библиотеки довольно «развесистый», точное число методов неизвестно, документации, разумеется, нет. Зато известно, что в параллельной вселенной люди ходят по потолку, спят днём, работают ночью, а ещё используют только асинхронные функции и всегда передают callback первым аргументом. Странные ребята! У нас на Земле уже давно все на промисах пишут. Однако библиотеку нужно интегрировать в проект. Поэтому вам поступила задача написать обёртку, которая будет предоставлять тот же API, но на промисах.
Формат ввода
Пример исходного API:
const api = {
a: {
b: {
c: callback => setTimeout(() => callback(null, ’hello’), 100)
}
},
aa: {
bb: (callback, x, y) => setTimeout(() => callback(null, x + y), 200)
}
};
Формат вывода
Отправьте решение в виде:
/**
* @param {Object} api - исходное API
* @returns {Object}
*/
module.exports = function promisify(api) {
// ...
return promisedApi;
};
Пример использования:
const promisedApi = promisify(api);
promisedApi.a.b.c()
.then(res => console.log(res)); // => ’hello’
Примечания
- обёртка должна возвращать rejected promise в случае ошибки при вызове исходного API, callback всегда принимает ошибку первым аргументом:
callback(error, data) - в исходном API могут встречаться константы (числа, строки и булевые), их нужно возвращать как есть:
api.foo.myConst = 1; promisedApi.foo.myConst === 1; - инициализация обёртки должна быть «ленивой»: в исходном API может быть большое количество неймспейсов, и обращаться к ним нужно по мере использования.
B. Будни стажера (15 баллов)
В команде Яндекса работает стажёр Степан. Сроки уже поджимают, а он не успевает с вёрсткой страниц. Помогите Степану сверстать одну из них по макету из этой задачи.
При вёрстке не должно быть отступов от левого и верхнего края страницы. Также нельзя использовать изображения. Вот макет:
Как видите, макет состоит из плиток двух размеров: стандартного и двойного. Стандартная плитка занимает 1/3 ширины экрана, двойная — 2/3. Высота плитки фиксированная - 200px. Расстояние между плитками 20 пикселей.
Цвет бекграунда стандартной плитки #8a2be2, цвет двойной #000
В результате у вас должна получиться HTML-страница с вёрсткой для макета. Размер страницы не должен превышать 10 КБ.
Примечания
Обратите внимание:
- в шаблонах можно писать только вёрстку и стили — JavaScript и изображения использовать нельзя;
Решение
Файл: B_weekdaysintern.html
Комментарии:
Долго не могла пройти тесты изза собственной невнимательности. Много времени потратила на то, чтобы просто подобрать высоту, оказалось, она была в описании...
<html>
<head>
<meta charset="utf-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge"/>
<style>
body {
margin: 0;
padding: 0;
}
.banner {
height: 200px;
overflow: hidden;
min-width: calc(100vw / 3 - 20px);
margin-right: 20px;
margin-bottom: 20px;
}
.title {
line-height: 36px;
font-size: 36px;
}
.button {
float: right;
background-color: #FEDA5A;
color: black;
padding: 8px 20px;
line-height: 20px;
text-decoration: none;
}
.button:hover {
background-color: #fccd33;
}
.content {
line-height: 24px;
font-size: 24px;
}
.wrapper {
height: 200px;
width: calc(100vw + 20px);
display: flex;
justify-content: space-between;
flex-wrap: wrap;
}
.s {
background-color: #8a2be2;
flex-grow: 1;
flex-basis: calc(100vw / 3 - 20px);
}
.l {
background-color: #000;
flex-grow: 2;
flex-basis: calc(100vw / 3 * 2 - 20px);
}
</style>
</head>
<body>
<div class="wrapper">
<div class="banner s">
</div>
<div class="banner s">
</div>
<div class="banner s">
</div>
<div class="banner s">
</div>
<div class="banner l">
</div>
<div class="banner l">
</div>
<div class="banner s">
</div>
</div>
</body>
</html>
C. Идеальные прямоугольники (40 баллов)
Боб — художник-экспрессионист. Все его работы представляют собой цветные строго вертикальные прямоугольники на белом фоне.
Недавно его работы опубликовали на сайте известного журнала Top Art. Боб решил разглядеть свои полотна поближе, увеличил масштаб страницы и пришел в ужас от расплывшихся углов и нечётких краёв его идеальных прямоугольников.
Будучи человеком обстоятельным, он изучил проблему и решил свои шедевры сконвертировать в HTML, чтобы под любым углом и в любом масштабе линии оставались идеальными. Для выполнения задуманного он выбрал вас.
Напишите для него сервис, который сможет генерировать html из картинок.
Формат ввода
На вход подаётся строка, которая содержит картинку в base64
Формат вывода
Верните функцию traceImage, которая на вход принимает ссылку на картинку, а возвращает промис, который резолвится со строкой. В строке должна быть вёрстка, которая повторяет эту картинку.
Отправьте решение в виде:
/**
*
* @param {String} imageSrc - base64 картинки, например ’data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAA...’
* @returns {Promise}
*/
function traceImage(imageSrc) {
// Ваше решение
}
Примечания
- Картинка может быть любого размера
- Картинка не прозрачная
- Цвет пустых пикселей — белый (r, g, b): (255, 255, 255)
- На картинке изображён 1 цветной непрозрачный прямоугольник
- Все линии горизонтальные или вертикальные
- Код выполняется в браузере
Пример
Дана картинка строкой в base64 (в том виде, в котором она будет передаваться в функцию): https://gist.github.com/senaev/50460323558db543256cb7f196e7d81d
Для такой картинки можно сгенерировать строку:
<div>
<div style="
position: absolute;
width: 11px;
height: 15px;
top: 135px;
left: 109px;
background-color: rgb(255, 255, 0);
"></div>
</div>
D. Ход конём (40 баллов)
Геннадий - интеллектуал. Он любит знакомиться с интересными людьми. Но будучи человеком осмотрительным и недоверчивым, делает он это только в интернете. Недавно Геннадий обнаружил, что сопоставимых по IQ собеседников можно отыскать на шахматном форуме, но вот беда - в шахматы играть Геннадий не умеет, а все обучаторы основаны на javascript-е, который Геннадий осмотрительно отключает, чтобы избежать вероятности подцепить вирус.
Чтобы помочь Геннадию - предлагаем сделать обучатор для игры в шахматы без javascript, который будет показывать, как ходит конь. Обучатор должен выглядеть как шахматная доска. Кликаешь по клетке - тебе показывают, куда с этой клетки может пойти конь.
Формат ввода
html-документ, при загрузке которого рисуется шахматная доска
Формат вывода
Задание будет протестировано в реальном браузере (Chrome 77).
В браузере будет загружен ваш html-документ. Робот кликает в различные ячейки шахматного поля и снимает скриншоты после кликов.
Скриншоты должны соответствовать эталонным
Пример
Примечания
- Реализация на CSS и HTML. Javascript использовать нельзя.
- Вся верстка должна быть квадратной, без теней, градиентов, скруглений и т.п.
- Ширина и высота ячейки - 30 пикселей
- Шахматное поле находится на странице слева сверху, без отступов
- Цвет выделенной ячейки #ff0000
- Цвет ячейки, на которую может ходить фигура #0000ff
- Цвет светлой ячейки #f4cd8d
- Цвет темной ячейки #745853
- Левая верхняя ячейка светлая
- Изначально ни одна ячейка не выделена
- Выделение происходит по клику в конкретную ячейку и сохраняется до следующего клика
Решение
Файл: D_chess.html
Комментарии:
Когда прочитала в условии что js не нужен, решила, что задачка изи и я быстро решу ее. Ага, конечно... Как только я не пыталась ее сделать: и через ссылки с :target (но можно только одну ячейку сделать синей), и через родственные селекторы (но окрашивались только те ячейки, что идут после активной). В итоге вспомнила разбор задачи с конем на Хабре и поняла, что ячейки становятся активными в тестах не по клику на них, а с помощью создания события new Event(), и не обязательно чтобы на них можно было кликать физически. Сделала кнопку как обертку, по клику на которую показывается ее содержимое, и добавила overflow: hidden. Синие ячейки появляются как надо, но на них нельзя кликнуть тк они поверх кнопок. Вот такой получился костыль :). Очень жду разбора задач от Яндекс. Код очень длинный, поэтому можно посмотреть только в файле.
E. Рельеф планеты Х (60 баллов)
В 2050 году учёные из МКС начали получать особенные сигналы из космоса с массивами чисел. Учёные предполагают, что некая инопланетная цивилизация передаёт в массивах рельеф части своей планеты. Вам предложили присоединиться к исследованию зашифрованного сигнала, чтобы помочь воссоздать эту предположительную местность.
Описание прилагается:
Значения h описывают высоты (h > 0), низины (h < 0) и уровень моря (h = 0) в пикселях (px) кратные 10. (далее в h, пиксели будут опускаться).
Площади (S) объектов определяются суммой абсолютных значений элементов. ([–10,–30,–10], S=50)
Ширина одной клетки = 10px
- Солнце расположено в промежутке 100 < h < 150. Если его нет, то тема сменяется на ночную. Цвет: #ffff00
- Звёзды расположены на высоте h ≥ 150. Видны только ночью. Цвет: #ffffff
- Горы — положительно определённые палиндромы нечётной длины > 1 с вершиной 30 ≤ h ≤ 100 ([0,10,30,10,0]). Нужно найти и нарисовать самую большую гору по площади (остальные возвышенности не рисуем). Цвет на день / ночь: #bb3300 / #5b3500
- Озёра — отрицательно определённые палиндромы нечётной длины > 1 с глубиной −30 ≥ h ≥ −100. ([0,–10,–30,–10,0]). Нужно найти и нарисовать самое большое озеро по площади (остальные низменности не рисуем). Цвет на день / ночь: #0f5ed6 / #036bb5
- Алмазы расположены на глубине h < −100, должны граничить с землёй h ≥ 0). [0,–110,10]. Клетка перевёрнута на 45∘. Цвет: #ffffff
- Цвет дневного неба: #5baef7
- Цвет звёздного неба: #120078
- Цвет земли: #793b0f
Учёные хотят, чтобы вы графически представили такой массив в виде прямоугольников одинаковой ширины.
Примеры:
День:
[0,–10,–20,–30,–20,–10,0,10,–160,0,40,0,140,150,0,–120,0,–20,0,20,10,20,30,40,30,20,10,0]
Ночь:
[0,–10,–20,–30,–20,–10,160,10,–110,0,40,0,90,0,0,150,–130,0,–20,0,20,170,10,20,30,40,30,20,10,0]
Решение представляет собой функцию, возвращющую объект со строками {script,style}, которые будут добавляться в HTML-документ с единственным элементом в теле <div class="world»</div>.
Задача решается при помощи разметки, без использования canvas.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<style type="text/css">‘${style}‘</style>
</head>
<body>
<div class="world"></div>
<script type="text/javascript">‘${script}‘</script>
</body>
</html>
Пришлите решение в таком виде:
module.exports = function(arr) {
let script,style;
...
return {
script: script,
style: style
};
}
Примечания
Обратите внимание:
-
‘script’и‘style’добавляются в чистом виде без тегов, ширина блока (класса) ‘world’ должна быть равна произведению количества элементов на ширину одной клетки (10 px). Например, для массива [0,10,150,10,–150] ширина равняется 5×10px = 50px, - высота блока (класса)
‘world’должна быть равна сумме абсолютных значений максимального и минимального элементов. Например, для массива [0,10,150,10,–150] высота равняется |150| + |–150| = 300 px, - горы и озёра не обязательно должны граничить с уровнем моря (h=0),
- горы и озёра монотонно убывают и возрастают от центра,
- для алмаза [–150], h = −150 определяет нижнюю грань (т.е. нужно верстать с –140 по –150),
- тесты на скриншоты будут прогоняться относительно класса ‘world’.
F. Космические Рейнджеры (60 баллов)
В параллельной вселенной человечество научилось путешествовать к соседним звёздам.
Для этого построили «Звёздные ускорители» (ЗУ), которые могут перебрасывать корабль на несколько световых лет в одну из четырёх сторон (вперед/назад/вправо/влево). Да, параллельная вселенная двухмерная, не спрашивайте.
ЗУ отличаются мощностью от 1 до 9 — и могут использовать как всю, так и только часть своей мощности для перемещения корабля.
Услуга эта дорогая, но, что удивительно, цена фиксирована и не зависит от затраченной мощности. Таким образом, выгодно строить маршрут так, чтобы количество межпространственных прыжков было минимальным.
Вы попали в эту вселенную и только что купили себе новенький космический корабль с последней версией местных звёздных карт.
Интерфейс заботливо показывает вам фрагмент галактики с проложенным по нему оптимальным маршрутом.
From: 0:2
To: 8:7
0:2 -> 0:3 -> 4:3 -> 4:7 -> 8:7
===============================================================================
1 1 4 2 5 5 4 2 2
1 5 5 2 1 4
[1] 3 1 5 5 2 5 3
|
[5]--3---5---2--[5] 1 2 2 5
|
1 3 5 | 3 1 4 5
|
1 5 5 4 1 5 5 5 2
|
2 2 2 1 1 4 1 3
|
1 1 3 3 [5]------3---5--[1] 5
1 5 4 2 5 1 3 1 5
1 1 4 5 2 4 3
К сожалению, в очередном обновлении разработчики допустили ошибку, из-за чего модуль расчёта пути сломался.
Вам предстоит починить его.
В качестве решения этого задания отправьте файл .js, в котором объявлена функция pathFinder:
function pathFinder(input) {
// ...
}
Формат ввода
В параметре input в функцию pathFinder приходит строка следующего формата:
<x1>:<y1>
<x2>:<y2>
<map line>
...
<map line>
-
<x1>:<y1>— начальная координата пути, например, 0:2 -
<x2>:<y2>— конечная координата пути, например, 8:7 -
<map line>— строка карты выражена последовательностью цифр от 0 до 9
Каждая цифра на карте - это то, на сколько шагов можно переместиться из этой точки. Например, из точки с значением 1 можно перейти только на соседние 4 точки.
Количество цифр в каждой строке карты одинаковое.
Количество строк на карте совпадает с количеством цифр в строках.
Максимальный размер карты: 40 x 40.
Формат вывода
Функция должна вернуть массив со списком оптимальных путей.
Порядок оптимальных путей в массиве не важен.
Пустой массив, если невозможно добраться до конечной точки.
Пример 1:
Ввод:
2:3
4:4
00014
30020
00000
70100
11100
Вывод:
[["2:3","2:4","1:4","0:4","0:3","0:1","3:1","3:0","4:0","4:4"]]
Пример 2:
Ввод:
0:2
8:7
0515320501
3150514510
0102010523
5510001000
1402152200
0310530201
0551451213
4101452055
0252411510
4110045253
Вывод:
[]
Пример 3:
Ввод:
2:3
3:0
2012
3001
7000
1920
Вывод:
[["2:3","0:3","0:2","0:0","2:0","3:0"],["2:3","0:3","0:2","0:1","3:1","3:0"]]
Примечания
- Решение будет проверяться в браузере (Chrome 78).
- Можно использовать синтаксис до es2018 включительно.
Hello Board
Книга героев Задача 30
| Название | Значение |
|---|---|
| Ограничение времени | 1 секунда |
| Ограничение памяти | 64Mb |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Вы пришли в Харбрант за волшебной книгой. Она достается только самым достойным, и вы пришли заявить на нее свое право. По пути вы наткнулись на засаду из императорских стражников. Ваш отряд сумел оторваться и пробраться на колокольню, а вы вынуждены искать выход, оказавшись в сплошном окружении. Единственный путь к отступлению — центральные ворота, которые заперты с помощью замка с шифром. Чтобы открыть его, нужно подобрать шифр из четырех числовых комбинаций.
Вы теряетесь в догадках, как быстро подобрать код, но вдруг слышите звон колоколов. Это явно знак. Кажется, это азбука Морзе. Вы пытаетесь расшифровать послание, но отряд так спешит, что иногда первый и последний символы меняются местами, а иногда вся комбинация оказывается перевернутой.
Постарайтесь получить верную комбинацию как можно скорее.
Формат ввода
// пример, входящей строки
--... ...-- ---.. .---- T...-- .---- T..--- E-.--. ----. T..--- E.-..- .---- --... ----. ..... T.----
Формат вывода
// пример, исходящей строки
7381 7182 9871 7959
Примечания
- Решение должно экспортировать функцию
- Функция должна принимать на вход строку
- Функция должна возвращать строку
- Для декодирования из кода Морзе используйте символы - и ., пробел для разделения цифр и три пробела для разделения комбинаций
- Для получения корректного кода Морзе сначала требуется декодировать каждую цифру в зависимости от встречающихся шифров
Шифры
- T — Транспозиция. Реверс строки
- E — Замена местами первого и последнего символа
Решение
Файл: HB_herobook.js
Комментарии:
Мое сообщение так и не опубликовали на Hello Board, показывался смайл с песочными часами типа грузится :(
module.exports = function(string) {
if (typeof string !== 'string') return null;
const morze = ['-----', '.----', '..---', '...--', '....-', '.....', '-....', '--...', '---..', '----.'];
const numGroups = string.split(' ');
const numGroupsArray = [];
for (let i = 0; i < numGroups.length; i++) {
const numGroup = numGroups[i].split(' ');
let decodeString = '';
for (j = 0; j < numGroup.length; j++) {
if (numGroup[j][0] === 'T') {
numGroup[j] = getReverseString(numGroup[j]);
}
else if (numGroup[j][0] === 'E') {
numGroup[j] = changeSumbolsPlace(numGroup[j]);
}
const findIndex = morze.findIndex((item) => item === numGroup[j]);
decodeString += findIndex !== -1 ? findIndex : '';
}
numGroupsArray.push(decodeString);
}
return numGroupsArray.join(' ') || null;
}
const getReverseString = (string) => {
const symbols = string.split('').slice(1);
const reverseSymbols = symbols.reverse();
const reverseString = reverseSymbols.join('');
return reverseString;
}
const changeSumbolsPlace = (string) => {
const symbols = string.split('').slice(1);
const c = symbols[0];
symbols[0] = symbols[symbols.length-1];
symbols[symbols.length-1] = c;
return symbols.join('');
}
const res = decode('--... ...-- ---.. .----');
console.log(res);
Космические пробки Задача 33
| Название | Значение |
|---|---|
| Ограничение времени | 100 секунд |
| Ограничение памяти | 64Mb |
| Ввод | input.json |
| Вывод | output.json |
Альянс внутренних планет системы Бета Скорпиона уже не в состоянии решить проблему космических пробок. В межпланетном пространстве накапливаются целые очереди звездолетов, которые не могут продолжать движение из-за опасных траекторий полетов мелких космических лайнеров.
Миллионы кубометров космического топлива выбрасываются в пространство, создавая вакуумный смог. Поэтому вам поручено разработать систему межпланетного сообщения, которая установит четкие траектории полетов и даст возможность заранее проложить свой маршрут, согласованный с Министерством космического транспорта.
Вам рекомендуют представить решение в виде графа, где вершинами выступят планеты, оборудованные космодромами. Новые пути, готовые к использованию, будут отправляться к вам в виде списка связей между планетами с учетом ограничений, наложенных Космическим Военным Флотом.
Необходимо добавлять их на граф в том порядке, в котором они были отправлены.Необходимо добавлять их на граф в том порядке, в котором они были отправлены.
На вход ф-я принимает 2 аргумента:
-
‘graph: Graph‘- описание графа -
‘connections: Connection[]‘- спиосок связей, которые требется добавить
На выход ф-я отдает объект succeeded, failed , где:
-
‘succeeded: string[]‘- список id связей, которые успешно добавлены на граф -
‘failed: string[]‘- список id связей, которые не удалось добавить на граф
Типы сущностей
Граф (Graph)
-
‘blocks: Block[]‘- список блоков внутри графа -
‘connections: Connection[]‘- список связей внутри графа Блок (Block) -
‘inputs: Anchor[]‘- список якорей-входов -
‘outputs: Anchor[]‘- список якорей-выходов -
‘maxConnections: number‘- максимальньное число связей в которых может участвовать блок
Якорь (Anchor)
-
‘id: string‘– собственный уникальны идетификатор якоря
Связь (Connection)
-
‘id: string‘– собственный уникальны идетификатор связи -
‘source: string‘– id якоря-выхода -
‘target: string‘– id якоря-входа
Ограничения
- Можно связать только выход-вход. Связать выход-выход или вход-вход нельзя
- Выход блока не может быть соединен со входом этого же блока
- Суммароное количество связей для всех якорей блока, в которых может участвовать блок, ограничено параметром ‘maxConnections‘. Если любой из блоков уже участвует в количестве связей равному параметру ‘maxConnections‘, то новую связь добавить нельзя
Примеры данных
Входные данные
{
"graph": {
"blocks": [
{
"inputs": [],
"outputs": [
{
"id": "a1"
},
{
"id": "a2"
}
],
"maxConnections": 2
},
{
"inputs": [
{
"id": "a3"
},
{
"id": "a4"
}
],
"outputs": [],
"maxConnections": 1
}
],
"connections": [
{
"id": "c0",
"source": "a1",
"target": "a3"
}
]
},
"connections": [
{
"id": "c1",
"source": "a2",
"target": "a4"
}
]
}
Выходные данные
{
succeeded: [],
failed: ["c1"]
}
Open Source Agenda Badge
