HolyJS 2019: Разбор задач от компании SEMrush (Часть 1) / Хабр

На прошедшей 24-25 мая в Санкт-Петербурге очередной конференции для JavaScript-разработчиков HolyJS стенд нашей компании предлагал всем желающим новые задачки. В этот раз их было 3 штуки! Задачи выдавались по очереди, а за решение каждой последующей полагался знак отличия (JS Brave > JS Adept > JS Master), что послужило хорошей мотивацией не останавливаться. Суммарно мы собрали порядка 900 ответов и спешим поделиться разбором наиболее популярных и уникальных решений.

Предлагаемые испытания ожидают от храбрых и понимания базовых «особенностей» языка, и осведомленности в новых фичах ECMAScript 2019 (на самом деле, последнее — не обязательно). Важно, что эти задачи — не для собеседований, не практичны и надуманы только с целью поразвлечься.

Задача 1 ~ Countdown Expression

Что вернет выражение? Переставьте один любой символ, чтобы

выражение возвращало 2
выражение возвращало 1

+(_ => [,,~1])().length

Дополнительно: возможно ли перестановками получить 0?

Что вернет выражение?

Тут думать не долго: выражение вернет 3. Мы имеем анонимную функцию, просто возвращающую массив из трех элементов, первые два из которых пустые (empty). Вызов функции отдает нам этот массив, мы берем от него д��ину (length), а унарный оператор плюс ничего не решает.

Выражение возвращает 2

Быстрым решением кажется уменьшить количество элементов возвращаемого массива. Для этого достаточно просто выкинуть одну запятую:

[,~1].length // 2

Просто так выкинуть символ по условию задачи нельзя: его нужно переставить в другое место исходного выражения. Но мы знаем, что свойство массива length учитывает пустые элементы, перечисленные в литерале массива, за исключением одного случая:

If an element is elided at the end of an array, that element does not contribute to the length of the Array.

То есть, если пустой элемент находится в конце массива, то он игнорируется:

[,10,] // [empty, 10]

Таким образом, исправленное выражение выглядит так:

+(_ => [,~1,])().length // 2

Есть ли еще вариант избавиться от этой запятой? Или поехали дальше.

Выражение возвращает 1

Получить единицу путем уменьшения размера массива уже не получится, так как придется сделать по крайней мере две перестановки. Придется искать другой вариант.

На решение намекает сама функция. Вспомним, что функция в JavaScript — это объект, у которого есть свои свойства и методы. И одно из свойств — это тоже length, который определяет количество аргументов, ожидаемых функцией. В нашем случае функция имеет один единственный аргумент (underscore) — то, что нужно!

Для того, чтобы length мы брали от функции, а не от массива, нужно прекратить ее вызывать через круглые скобки. Становится очевидным, что одна из этих скобок — претендент на перестановку. И вариантов приходит на ум уже пара:

+((_ => [,,~1])).length // 1
+(_ => ([,,~1])).length // 1

Может есть что-то еще? Или следующий уровень.

Выражение возвращает 0

В дополнительном задании количество перестановок не ограничено. Но мы можем попробовать выполнить его, совершив минимальные телодвижения.

Развивая предыдущий опыт с length от объекта функции, можно быстро прийти к решению:

+(() => [,_,~1]).length // 0

Тут есть несколько производных, но вся суть в том, что мы сократили количество аргументов функции до нуля. Для этого нам потребовалось аж три перестановки: две скобки и символ underscore, который стал элементом массива.

Хорошо, но может пора прекратить игнорировать в наших рассуждениях операторы сложения (+) и побитового NOT (~)? Кажется, что арифметика в этой задаче может сыграть нам на руку. Чтобы не листать в начало, вот оригинальное выражение:

+(_ => [,,~1])().length

Для начала посчитаем ~1. Побитовое NOT от числа x вернет -(x+1). То есть ~1 = -2. А еще у нас есть в выражении оператор сложения, который как бы намекает, что где-то надо найти еще 2 и все получится.

Совсем недавно мы вспомнили про «невлияние» пустого последнего элемента в литерале массива на его размер, а значит наша двойка где-то здесь:

[,,].length // 2

И все очень удачно складывается: мы достаем элемент ~1 из массива, сокращая его длину до 2, и добавляем его первым операндом для нашего сложения в начало выражения:

~1+(_ => [,,])().length // 0

Таким образом, мы достигли цели уже за две перестановки!

А что, если это не единственный вариант? Немного барабанной дроби…

+(_ => [,,~1.])(),length // 0

Тоже требует две перестановки: точка после единицы (так можно, ведь численный тип только number) и запятая перед length. Это кажется ерундой, но «иногда» работает. Почему иногда?

В этом случае, выражение через comma operator делится на два выражения и результатом будет вычисленное значение второго. Но второе выражение — это же просто length! Дело в том, что здесь происходит обращение к значению переменной в глобальном контексте. Если среда исполнения — это браузер, то — window.length. И у объекта window действительно есть свойство length, которое возвращает количество фреймов (frame) на странице. Если наш документ пустой, то length вернет 0. Да, вариант с допущением… поэтому остановимся на предыдущем.

А вот еще несколько обнаруженных интересных вариантов (уже за разное количество перестановок):

(_ => [,,].length+~1)() // 0
+(~([,,].len_gth) >= 1) // 0
~(_ => 1)()+[,,].length // 0
~(_ => 1)().length,+[,] // 0
~[,,]+(_ => 1()).length // 0

Тут без комментариев. У кого-то найдется что-то еще веселее?

Мотивация

Старая-добрая задача про «переставьте одну-две спички, чтобы получился квадрат». Всем известная головоломка на развитие логики и творческого мышления превращается в «мракобесие» в такой JavaScript-вариации. Полезно ли это? Скорее нет, чем да. Мы затронули многие особенности языка, некоторые даже вполне концептуальные, чтобы докопаться до решений. Однако, реальные проекты не про length от функции и выражения на стероидах. Эта задача предлагалась на конференции в качестве этакой затягивающей разминки, чтобы вспомнить, каким бывает JavaScript.

Eval-комбинаторика

Рассмотрены были не все возможные варианты ответов, а чтобы и вовсе ничего не пропустить обратимся к настоящему JavaScript! Если интересно попробовать их найти самостоятельно, то выше было достаточно подсказок, а дальше лучше пока не читать.

Итак, у нас есть выражение из 23 символов, в строковой записи которого мы будем делать перестановки. Всего нам надо выполнить n * (n — 1) = 506 перестановок в исходной записи выражения, чтобы получить все варианты с одним переставленным символом (как того требуют условия задачи 1 и 2).

Определим функцию combine, принимающую на вход выражение строкой и предикат для проверки пригодности значения, полученного в результате выполнения этого выражения. Функция будет брутфорсить все возможные варианты и вычислять выражение через eval, сохраняя результат в объект: key — полученное значение, value — список мутаций нашего выражения для этого значения. Что-то такое получилось:

const combine = (expr, cond) => {
  let res = {};
  let indices = [...Array(expr.length).keys()];
  indices.forEach(i => indices.forEach(j => {
    if (i !== j) {
      let perm = replace(expr, i, j);
      try {
        let val = eval(perm);
        if (cond(val)) {
          (res[val] = res[val] || []).push(perm);
        } 
      } catch (e) { /* do nothing */ }
    }
  }));
  return res;
}

Где функция replace от переданной строки выражения возвращает новую строку с переставленным символом с позиции i в позицию j. А теперь, не сильно боясь, выполним:

console.dir(combine('+(_ => [,,~1])().length', val => typeof val === 'number' && !isNaN(val)));

В итоге мы получили наборы решений:

{
"1": [
  "+(_ => [,,~1]()).length",
  "+((_ => [,,~1])).length",
  "+(_ =>( [,,~1])).length", 
  "+(_ => ([,,~1])).length"
],
"2": [
  "+(_ => [,~1,])().length"
]
"3": [/* ... */]
"-4": [/* ... */]
}

Решения для 3 и -4 нас не интересуют, для двойки мы нашли единственное решение, а для единицы наблюдается интересный новый кейс с [,,~1](). Почему не TypeError: bla-bla is not a function? А все просто: это выражение не имеет ошибки для синтаксического парсера, а в рантайме оно просто не выполняется, так как функция не вызывается.

Как видно, в одну перестановку не получается решить задачу для нуля. Может попробуем в две? Решая задачу таким перебором в лоб, в этом случае мы будем иметь сложность O(n^4) от длины строки и «эвалить» так много раз преследуемо и наказуемо, но любопытство берет верх. Не сложно самостоятельно доработать приведенную функцию combine или написать более хороший перебор, учитывающий особенности конкретного выражения.

console.dir(combine2('+(_ => [,,~1])().length', val => val === 0));

В конце концов, набор решений для нуля будет таким:

{
"0": [
  "+(_ => [,~.1])(),length",
  "+(_ => [,~1.])(),length",
  "~1+(_ => [,,])().length"
]
}

Любопытно, что в рассуждениях мы переставили точку после единицы, но забыли, что точка перед единицей тоже возможна: запись 0.1 с опущенным нулем.

Если выполнить все возможные перестановки по два символа, то можно обнаружить, что есть достаточно много ответов для значений в диапазоне от 3 до -4:

{ "3": 198, "2": 35, "1": 150, "0": 3, "-1": 129, "-2": 118, "-3": 15, "-4": 64 }

Таким образом, путь решений Countdown Expression на двух перестановках может быть длиннее, чем предложенный от 3 до 0 на одной.

Это была первая часть разбора наших задач на HolyJS 2019 и скоро должна появиться вторая, где мы рассмотрим уже решения второго и третьего испытаний. Будем на связи!

HolyJS 2019: Разбор задач от компании SEMrush (Часть 1)