HolyJS 2019: Разбор задач от компании SEMrush (Часть 1)
- среда, 29 мая 2019 г. в 00:19:22
https://habr.com/ru/company/semrush/blog/452114/
На прошедшей 24-25 мая в Санкт-Петербурге очередной конференции для JavaScript-разработчиков HolyJS стенд нашей компании предлагал всем желающим новые задачки. В этот раз их было 3 штуки! Задачи выдавались по очереди, а за решение каждой последующей полагался знак отличия (JS Brave > JS Adept > JS Master), что послужило хорошей мотивацией не останавливаться. Суммарно мы собрали порядка 900 ответов и спешим поделиться разбором наиболее популярных и уникальных решений.
Предлагаемые испытания ожидают от храбрых и понимания базовых «особенностей» языка, и осведомленности в новых фичах ECMAScript 2019 (на самом деле, последнее — не обязательно). Важно, что эти задачи — не для собеседований, не практичны и надуманы только с целью поразвлечься.
Что вернет выражение? Переставьте один любой символ, чтобы
Дополнительно: возможно ли перестановками получить 0?
Тут думать не долго: выражение вернет 3. Мы имеем анонимную функцию, просто возвращающую массив из трех элементов, первые два из которых пустые (empty). Вызов функции отдает нам этот массив, мы берем от него длину (length), а унарный оператор плюс ничего не решает.
Быстрым решением кажется уменьшить количество элементов возвращаемого массива. Для этого достаточно просто выкинуть одну запятую:
Просто так выкинуть символ по условию задачи нельзя: его нужно переставить в другое место исходного выражения. Но мы знаем, что свойство массива length учитывает пустые элементы, перечисленные в литерале массива, за исключением одного случая:
То есть, если пустой элемент находится в конце массива, то он игнорируется:
Таким образом, исправленное выражение выглядит так:
Есть ли еще вариант избавиться от этой запятой? Или поехали дальше.
Получить единицу путем уменьшения размера массива уже не получится, так как придется сделать по крайней мере две перестановки. Придется искать другой вариант.
На решение намекает сама функция. Вспомним, что функция в JavaScript — это объект, у которого есть свои свойства и методы. И одно из свойств — это тоже length, который определяет количество аргументов, ожидаемых функцией. В нашем случае функция имеет один единственный аргумент (underscore) — то, что нужно!
Для того, чтобы length мы брали от функции, а не от массива, нужно прекратить ее вызывать через круглые скобки. Становится очевидным, что одна из этих скобок — претендент на перестановку. И вариантов приходит на ум уже пара:
Может есть что-то еще? Или следующий уровень.
В дополнительном задании количество перестановок не ограничено. Но мы можем попробовать выполнить его, совершив минимальные телодвижения.
Развивая предыдущий опыт с length от объекта функции, можно быстро прийти к решению:
Тут есть несколько производных, но вся суть в том, что мы сократили количество аргументов функции до нуля. Для этого нам потребовалось аж три перестановки: две скобки и символ underscore, который стал элементом массива.
Хорошо, но может пора прекратить игнорировать в наших рассуждениях операторы сложения (+) и побитового NOT (~)? Кажется, что арифметика в этой задаче может сыграть нам на руку. Чтобы не листать в начало, вот оригинальное выражение:
Для начала посчитаем ~1. Побитовое NOT от числа x вернет -(x+1). То есть ~1 = -2. А еще у нас есть в выражении оператор сложения, который как бы намекает, что где-то надо найти еще 2 и все получится.
Совсем недавно мы вспомнили про «невлияние» пустого последнего элемента в литерале массива на его размер, а значит наша двойка где-то здесь:
И все очень удачно складывается: мы достаем элемент ~1 из массива, сокращая его длину до 2, и добавляем его первым операндом для нашего сложения в начало выражения:
Таким образом, мы достигли цели уже за две перестановки!
А что, если это не единственный вариант? Немного барабанной дроби…
Тоже требует две перестановки: точка после единицы (так можно, ведь численный тип только number) и запятая перед length. Это кажется ерундой, но «иногда» работает. Почему иногда?
В этом случае, выражение через comma operator делится на два выражения и результатом будет вычисленное значение второго. Но второе выражение — это же просто length! Дело в том, что здесь происходит обращение к значению переменной в глобальном контексте. Если среда исполнения — это браузер, то — window.length. И у объекта window действительно есть свойство length, которое возвращает количество фреймов (frame) на странице. Если наш документ пустой, то length вернет 0. Да, вариант с допущением… поэтому остановимся на предыдущем.
А вот еще несколько обнаруженных интересных вариантов (уже за разное количество перестановок):
Тут без комментариев. У кого-то найдется что-то еще веселее?
Старая-добрая задача про «переставьте одну-две спички, чтобы получился квадрат». Всем известная головоломка на развитие логики и творческого мышления превращается в «мракобесие» в такой JavaScript-вариации. Полезно ли это? Скорее нет, чем да. Мы затронули многие особенности языка, некоторые даже вполне концептуальные, чтобы докопаться до решений. Однако, реальные проекты не про length от функции и выражения на стероидах. Эта задача предлагалась на конференции в качестве этакой затягивающей разминки, чтобы вспомнить, каким бывает JavaScript.
Рассмотрены были не все возможные варианты ответов, а чтобы и вовсе ничего не пропустить обратимся к настоящему JavaScript! Если интересно попробовать их найти самостоятельно, то выше было достаточно подсказок, а дальше лучше пока не читать.
Итак, у нас есть выражение из 23 символов, в строковой записи которого мы будем делать перестановки. Всего нам надо выполнить n * (n — 1) = 506 перестановок в исходной записи выражения, чтобы получить все варианты с одним переставленным символом (как того требуют условия задачи 1 и 2).
Определим функцию combine, принимающую на вход выражение строкой и предикат для проверки пригодности значения, полученного в результате выполнения этого выражения. Функция будет брутфорсить все возможные варианты и вычислять выражение через eval, сохраняя результат в объект: key — полученное значение, value — список мутаций нашего выражения для этого значения. Что-то такое получилось:
Где функция replace от переданной строки выражения возвращает новую строку с переставленным символом с позиции i в позицию j. А теперь, не сильно боясь, выполним:
В итоге мы получили наборы решений:
Решения для 3 и -4 нас не интересуют, для двойки мы нашли единственное решение, а для единицы наблюдается интересный новый кейс с [,,~1](). Почему не TypeError: bla-bla is not a function? А все просто: это выражение не имеет ошибки для синтаксического парсера, а в рантайме оно просто не выполняется, так как функция не вызывается.
Как видно, в одну перестановку не получается решить задачу для нуля. Может попробуем в две? Решая задачу таким перебором в лоб, в этом случае мы будем иметь сложность O(n^4) от длины строки и «эвалить» так много раз преследуемо и наказуемо, но любопытство берет верх. Не сложно самостоятельно доработать приведенную функцию combine или написать более хороший перебор, учитывающий особенности конкретного выражения.
В конце концов, набор решений для нуля будет таким:
Любопытно, что в рассуждениях мы переставили точку после единицы, но забыли, что точка перед единицей тоже возможна: запись 0.1 с опущенным нулем.
Если выполнить все возможные перестановки по два символа, то можно обнаружить, что есть достаточно много ответов для значений в диапазоне от 3 до -4:
Таким образом, путь решений Countdown Expression на двух перестановках может быть длиннее, чем предложенный от 3 до 0 на одной.
Это была первая часть разбора наших задач на HolyJS 2019 и скоро должна появиться вторая, где мы рассмотрим уже решения второго и третьего испытаний. Будем на связи!
- Блог компании SEMrush
- Ненормальное программирование
- Занимательные задачки
- JavaScript
На прошедшей 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 и скоро должна появиться вторая, где мы рассмотрим уже решения второго и третьего испытаний. Будем на связи!