660. Минификация JS-скриптов

Не решаласьНе определена

Наталья, инженер по оптимизации кода в Яндекс Маркете, отвечает за подготовку клиентских скриптов Jedi Script (JS) к быстрой доставке и выполнению у пользователей. Каждый исходный файл содержит:

  • комментарии, начинающиеся с # до конца строки,
  • лишние пробелы и переносы строк,
  • слова-идентификаторы, числа и зарезервированные токены (операторы, разделители и имена библиотечных функций).

Чтобы ускорить загрузку, Наталья должна собрать все m m строк исходного кода в единственную строку с минимальным числом пробелов, сохранив при этом точно ту же последовательность токенов, но переименовав все встречающиеся в коде «слова» (идентификаторы), не входящие в список зарезервированных токенов, в самые короткие возможные имена: сначала a, b, …, z, затем aa, ab и т.д.

Парсинг исходного кода происходит построчно:

  1. Убираются все символы комментариев #…конец строки.

  2. Повторяя до конца строки: пропускаются пробелы, затем выбирается длиннейший токен из трёх типов:

    • один из заранее заданных зарезервированных токенов (фиксированные строки без #),
    • число: непрерывная последовательность цифр 0–9,
    • слово: буква или _/$, за которой следуют буквы, цифры, _ или $.

Если та же строка символов распознаётся и как «слово» и как «зарезервированный токен», ей отводится роль зарезервированного токена.

Нужно вывести одну строку – результат «минимизации»:

  • все исходные токены (после удаления комментариев) сохранены,
  • каждое исходное «слово» (не зарезервированное) переименовано в следующий свободный идентификатор из списка (a, b, …, пропуская зарезервированные токены),
  • числа и зарезервированные токены не меняются,
  • вставлено минимально необходимое число пробелов, чтобы при повторном парсинге алгоритмом выше получилась та же последовательность токенов.

Формат ввода

Входные данные выглядят следующим образом:

n
R_1 R_2 … R_n
m
L_1
L_2
…
L_m

Здесь:

  • n ( 0 ≤ n ≤ 40 0\le n\le40 ) — число зарезервированных токенов.
  • Строка из n зарезервированных токенов R_i (символы ASCII с кодами 33…126, кроме #), разделённых пробелами.
  • m ( 1 ≤ m ≤ 40 1\le m\le40 ) — число строк исходного 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;}

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти