- Описание
- Решения
- Разборы
- Кодерун AI β
660. Минификация JS-скриптов
Наталья, инженер по оптимизации кода в Яндекс Маркете, отвечает за подготовку клиентских скриптов Jedi Script (JS) к быстрой доставке и выполнению у пользователей. Каждый исходный файл содержит:
- комментарии, начинающиеся с
#до конца строки, - лишние пробелы и переносы строк,
- слова-идентификаторы, числа и зарезервированные токены (операторы, разделители и имена библиотечных функций).
Чтобы ускорить загрузку, Наталья должна собрать все
строк исходного кода в единственную строку с минимальным числом пробелов, сохранив при этом точно ту же последовательность токенов, но переименовав все встречающиеся в коде «слова» (идентификаторы), не входящие в список зарезервированных токенов, в самые короткие возможные имена: сначала a, b, …, z, затем aa, ab и т.д.
Парсинг исходного кода происходит построчно:
Убираются все символы комментариев
#…конец строки.Повторяя до конца строки: пропускаются пробелы, затем выбирается длиннейший токен из трёх типов:
- один из заранее заданных зарезервированных токенов (фиксированные строки без
#), - число: непрерывная последовательность цифр
0–9, - слово: буква или
_/$, за которой следуют буквы, цифры,_или$.
- один из заранее заданных зарезервированных токенов (фиксированные строки без
Если та же строка символов распознаётся и как «слово» и как «зарезервированный токен», ей отводится роль зарезервированного токена.
Нужно вывести одну строку – результат «минимизации»:
- все исходные токены (после удаления комментариев) сохранены,
- каждое исходное «слово» (не зарезервированное) переименовано в следующий свободный идентификатор из списка (
a,b, …, пропуская зарезервированные токены), - числа и зарезервированные токены не меняются,
- вставлено минимально необходимое число пробелов, чтобы при повторном парсинге алгоритмом выше получилась та же последовательность токенов.
Формат ввода
Входные данные выглядят следующим образом:
n
R_1 R_2 … R_n
m
L_1
L_2
…
L_mЗдесь:
n( ) — число зарезервированных токенов.- Строка из
nзарезервированных токеновR_i(символы ASCII с кодами 33…126, кроме#), разделённых пробелами. m( ) — число строк исходного JS-кода.- Затем
mстрокL_jдлиной до 80 символов (ASCII 32…126), возможно с начальными и конечными пробелами и символами комментариев#… до конца строки.
Формат вывода
Одна строка — минимизированная версия исходного кода, которая при описанном парсинге даёт ту же последовательность токенов, но где все исходные «слова» переименованы в первые свободные идентификаторы (a, b, …), а общее число пробелов минимально.
Ограничения
- Ограничение времени
- 1,5 с
- Ограничение памяти
- 512 МБ
Примеры
Пример 1
16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
var return_value = 1, prev = 0, temp;
while (num > 0) {
temp = return_value; return_value = return_value + prev;
prev = temp;
num--;
}
return return_value;
}
fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}