Недавно в рабочем чате всплыла такая старая игра как ReturnTrue, и я подумал, что это неплохой повод рассказать о различных особенностях Джаваскрипта, с которыми мы редко сталкиваемся при разработке продуктовых проектов.
ReturnTrue — это набор головоломок, каждая из которых — хитро написанная функция. В эти функции нужно передать какие-то параметры, а в результате их выполнения должно получиться true. Причём именно честная булева истина, а не просто какое-то положительное значение.
Самой игре, кажется, уже больше пяти лет. Создал её Арлин Элинсен, программист из Норвегии.
Я привык писать , но возможно вы из тех, кому приятнее читать .
Простая задача, которая нужна только для того, чтобы мы поняли суть.
Очевидное решение:
id(true)
И сразу на ум приходит решение покороче:
id(!0)
2 символа.
Интересный факт. Название «id» тут использовано не просто так. В математике есть такое понятие как identity function (по-русски «тождественное отображение»). Это функция, которая возвращает свой аргумент, никак его не изменяя.
Может быть не сразу понятно, зачем оно нужно. Однако, когда мы имеем дело с числами, нам полезны «особые значения» вроде 0 или 1. Когда имеем дело со списками, полезны пустые списки. А когда имеем дело с функциями — полезна функция id.
Предположим, что нужно пройтись по массиву чисел, и каждое нечётное число увеличить на единицу, а чётные оставить как есть. Вот как это решение выглядело бы в Джаваскрипте, в относительно реальных условиях:
arr.map(x => x % 2 ? x + 1 : x)
Однако, несмотря на то, что тут есть map, код «недостаточно функционален». При функциональном подходе оперируют по большей мере функциями, а не напрямую данными.
И потому, если бы речь шла о функциональном программировании, код бы выглядел примерно так:
map(arr, when(isOdd, inc, id))
Здесь типичный для функционального программирования подход: один раз кладём данные в функцию, а дальше оперируем композицией других функций, выстраивая этакий пайплайн из них.
Реализация функций при этом была бы примерно такой:
const isOdd = x => x % 2 === 1;
const inc = x => x + 1;
const id = x => x;
const when = (cond, thenFn, elseFn) => x => cond(x) ? thenFn(x) : elseFn(x);
const map = (xs, fn) => xs.map(fn);
И вот тут уже видно, зачем может понадобиться функция, которая возвращает переданное ей значение. В контексте Джаваскрипта и веб-разработки это всё может выглядеть дико, но есть области, в которых это нормально. Та же математика.
Во-первых, что такое «reflexive». Если сильно упрощать, то отношение можно назвать рефлексивным на каком-то множестве, если каждый элемент множества находится в этом отношении с самим собой.
Допустим, есть множество натуральных чисел. И на нём определено отношение равенства. Можно взять любое число и проверить, равно ли оно самому себе:
> 1 == 1
true
Если равенство выполняется для всех чисел, значит на этом множестве это отношение «рефлексивно».
Аналогичным образом можем поступить с отношением неравенства. Оно «антирефлекивно», потому что не выполняется для каждого элемента множества:
> 1 != 1
false
Однако, NaN сам себе не равен. Потому для него отношение равенства — антирефлексивно, а это отношение неравенства — рефлексивно. Отсюда и название функции.
> NaN == NaN
false
> NaN != NaN
true
Во-вторых, поговорим о том, где и как мы можем встретиться с NaN в Джаваскрипте.
Если мы попытаемся привести строку к числу, и у нас ничего не получится, то Джаваскрипт не выкинет исключение, а вернёт NaN. Это в какой-то мере логично, но в то же время, Джаваскрипт — один из немногих языков, в которых с порога знакомят с таким специальным значением как NaN, в такой довольно частой для этого языка операции.
Например, в Пайтоне будет ошибка:
int("a")
$ python nan.py
Traceback (most recent call last):
File "./nan.py", line 1, in <module>
int("a")
ValueError: invalid literal for int() with base 10: 'a'
В ПХП — ноль:
<?
$str = "a";
$num = (int)$str;
echo $num;
?>
$ php -f nan.php
0
А в Джаваскрипте почему-то:
> Number('a')
NaN
Из-за этого про NaN знает каждый новичок, но обычно дальше понимания того, что NaN — это «ну когда не получилось превратить строку в число» новички не уходят. А мы попробуем копнуть чуть глубже.
Как известно, NaN можно получить, если у функции вроде parseInt не вышло распарсить строку в число:
> parseInt('a')
NaN
При этом есть глобальная функция isNaN. Но она не очень надёжная, потому что перед проверкой переданного параметра на NaN, сперва пытается привести его к числу. А потому вернёт true для любого значения, не приводимого к числу:
> isNaN({})
true
Поэтому есть ещё метод Number.isNaN, который так не делает:
> Number.isNaN({})
false
Помимо этого, при использовании NaN в вычислениях он всё превращает в NaN, а в отношениях — ничему не равен (даже самому себе):
> 1 + NaN
NaN
> false == NaN
false
> NaN != NaN
true
Из-за этого даже спека советует проверять значение на NaN простым неравенством. Считай, утиной проверкой:
A reliable way for ECMAScript code to test if a value X is a NaN is an expression of the form X !== X. The result will be true if and only if X is a NaN.
Помимо описанного выше способа получения NaN, в Джаваскрипте есть ещё разные, не связанные напрямую с арифметическими вычислениями. Например, можно попробовать получить код символа строки за пределами её длины:
> ''.charCodeAt(1)
NaN
Или распарсить невалидную дату:
> Date.parse('a')
NaN
В какой-то мере тот факт, что мы получаем во всех этих случаях NaN логичен, но не до конца. Например, невозможность получения кода символа строки теоретически должна выбрасывать исключение. Но Джаваскрипт так устроен, что попытка обращения к несуществующему индексу обычно не приводит к ошибкам:
А раз так, то и в случае получения кода символа строки вроде как нужно вернуть какое-то значение, которое не будет ошибкой, и будет при этом числом. А это и есть NaN. Ведь он тоже число:
> typeof NaN
"number"
На этом особенности работы с NaN в JS не заканчиваются. Так, если мы попытаемся получить NaN-й символ непустой строки, то сможем это сделать:
> 'a'.charAt(NaN)
"a"
Потому что, внезапно, NaN в некоторых контекстах приводится к нулю.
В спецификации описано много разных преобразований типов данных. Одно из них — ToInteger. Оно не используется в основных арифметических операциях, но присутствует при проверке типов параметров функций.
В большинстве своём, если где-то ожидается целое число в качестве параметра, то перед тем, как использовать этот параметр, над ним производится ToInteger. Один из шагов в таком преобразовании — проверка на NaN. Он всегда превращается в 0:
indexOf не находит, а includes — находит. А всё потому, что во время поиска indexOf использует строгую проверку на равенство, а так как NaN сам себе не равен, он и не находится. Проверка includes же чуть более сложная, и явным образом проверяет, не являются ли переданное и сравниваемое значение оба NaN.
Или вот, NaN вроде как все арифметические операции превращает в NaN, но если возвести его в нулевую степень, то получится единица:
> NaN ** 0
1
Но тут, правда, всё ещё сложнее. Алгоритм возведения в степень так описан, что не важно, что именно возводится в степень ±0 — результатом будет единица:
Да и в целом с возведением в степень не всё так просто:
> (-10) ** 1.2
NaN
Правда, тут мы уже получаем NaN не совсем из-за особенностей Джаваскрипта. Но об этом в следующий раз.
А что вообще такое NaN? Имплементации Джаваскрипта в браузерах с переменным успехом подчиняются спецификации ECMAScript, потому заглянем туда, в поисках объяснения:
Number value that is a IEEE 754 «Not-a-Number» value.
IEEE расшифровывается как «Институт инженеров электротехники и электроники». Это международная некоммерческая организация, которая разрабатывает стандарты для радиоэлектроники, электротехники и прочих смежных областей. В частности она разрабатывает стандарты для аппаратного обеспечения вычислительных систем и сетей.
Многие штуки, которые мы используем в повседневной жизни, завязаны на стандарты от IEEE. Например, IEEE 1003 — это POSIX, а IEEE 802 — группа стандартов, описывающих разные вычислительные сети. В частности, 802.11 описывает беспроводные коммуникации. Иными словами — Wi-Fi. Отсюда и «версии» Wi-Fi: 802.11a, 802.11b, и так далее — это всё разные версии этого стандарта.
Так вот, IEEE 754 — стандарт формата представления чисел с плавающей запятой. Если упрощать, то он рассказывает какой должна быть имплементация чисел с плавающей запятой и операций над ними. Что такое эти самые числа мы ещё обсудим позже.
Однако, этот стандарт помимо прочего определяет NaN как специальное значение числового типа, которое возвращается в случае, когда результат операции нельзя определить, или если сама операция ошибочна.
Примеров подобных операций достаточно много. Стандарт описывает в основном арифметические, например:
деление 0 на 0 и ∞ на ∞;
умножение 0 на ∞;
получение остатка от деления ∞ на 0;
вычитание бесконечностей с одинаковыми знаками;
и так далее.
NaN есть в большинстве современных языков, потому что его там не может не быть. При этом не всегда все перечисленные выше операции будут возвращать NaN. Какие-то из них могут выбрасывать исключение, если это предусмотрено разработчиками языка. В остальных же случаях чаще всего NaN.
Например, в Пайтоне делить на ноль нельзя, но сложение +∞ и −∞ вернёт NaN:
0/0
$ python zero.py
Traceback (most recent call last):
File "./zero.py", line 1, in <odule>
ZeroDivisionError: division by zero
float('inf') + float('-inf')
$ python inf.py
nan
В Гоу сработает аналогично. А вот в ПХП для разнообразия можно получить NaN попытавшись взять арккосинус от значения за пределами [−1; 1]:
<?
echo acos(2);
?>
$ php -f acos.php
NaN
Аналогично сработает и Си.
Подводя итог, можно сказать, что NaN — это специальное числовое значение, получаемое в арифметических операциях в тех случаях, когда результат не может быть определён или же сама операция невалидна.
Разные языки работают с NaN по-разному. Где-то наиболее критические ситуации обкладываются исключениями, где-то в таких случаях возвращается значение по умолчанию. А в иных языках NaN используется вовсю во всех непонятных случаях. Джаваскрипт — один из таких языков.
function transitive(x, y, z) {
return x && x == y && y == z && x != z;
}
Функция принимает три параметра, при этом:
первый параметр истинный;
первый параметр нестрого равен второму;
второй нестрого равен третьему;
но при этом первый нестрого не равен третьему.
Иными словами, нам нужно найти три таких значения, для которых отношение равенства не транзитивно, и при этом первый из них — истинен.
Первым делом нужно вспомнить, как работает нестрогое сравнение.
Если имеем x == y, то алгоритм примерно следующий:
Если типы x и y совпадают, то возвращаем результат строгого сравнения. То есть, сравниваем их значения (или ссылки, если это объекты). Единственная особенная ситуация тут — NaN, который не равен сам себе.
Если один из операндов null, а второй undefined, возвращаем true.
Если один из операндов типа String, а второй — Number, то приводим String к Number, а затем переходим к п. 1.
Если один из операндов типа Boolean, приводим его к Number.
Если один из операндов типа Object, приводим его к примитиву и начинаем сравнение заново, с п. 1.
Иначе возвращаем false.
(В реальности алгоритм чуть сложнее, и там ещё есть обработка BigInt, но нам это пока не принципиально.)
Из алгоритма выше следует, что если бы типы всех трёх параметров были одинаковыми, сравнение было бы транзитивно, а потому маловероятно, что их типы одинаковые.
Единственная «скользкая» ситуация тут — это тип Number с его NaN, но он не может быть x, ибо не положительный. И не может быть y или z, т. к. над ними выполняется операция равенства, а NaN не равен ничему.
Выходит, тип разный, и нас интересует его приведение.
Учитывая тот факт, что мы имеем x == y и y == z, но при этом x != z, можно предположить, что y — это какой-то примитив, а x и z — объекты. Потому что объекты сравниваются по ссылке, и если ссылка разная, то они не равны друг другу. Это могут быть даже одинаковые по содержанию объекты. Ссылка-то у них будет разной.
Плюс это укладывается в то, что x должен быть истинным. Объекты ведь всегда истинны. А раз так, то можем использовать это знание для поиска y.
Например, банально x и z — пустые объекты, а y — true. Пробуем:
> transitive({}, true, {})
false
Странно. Если начнём проверять пошагово, то окажется, что:
> ({}) == true
false
Непонятно! Мы ведь знаем, что в условии пустой объект ведёт себя как истинное значение:
> if ({}) console.log('True!')
True!
Да и первую проверку на истинность x пустой объект проходит. В чём же дело?
А дело в том, что согласно алгоритму нестрогого сравнения, что мы обсуждали ранее, если один из операндов типа Boolean, то он будет приведён к Number. И наш true после приведения к Number превращается в 1, конечно же. И при сравнении 1 с {} всё ломается.
Окей, тогда посмотрим, как приводятся объекты к примитивам. Это то, что нам пока не понятно из алгоритма сравнения.
Опуская детали, в нашем случае приведение объекта к примитиву выглядит так:
Если у объекта есть метод, который в доке называется @@toPrimitive, то:
Вызываем его.
Если вернулся не объект, возвращаем это значение.
Иначе выбрасываем ошибку.
Если такого метода нет, то проверяем наличие метода valueOf:
Если есть, то вызываем его.
Если вернулся не объект, возвращаем результат.
Если valueOf нет, проверяем аналогичным образом toString.
Если ничего не сработало, выбрасываем ошибку.
@@toPrimitive — это на деле Symbol.toPrimitive, и такой метод есть только у двух типов: Date и Symbol.
Для Symbol возвращается сам символ:
> Symbol('asd')[Symbol.toPrimitive]()
Symbol(asd)
Тут важно подчеркнуть, что это не строка. Возвращается именно тип Symbol:
От него нам явно никакой пользы, уж слишком он сложный. Символы равны друг другу только если у них совпадают ссылки. То есть, под наши условия они вроде бы не подходят.
А вот имплементация @@toPrimitive для Date такова, что там используется тот же алгоритм, что описан выше, только вызываемые методы поменяны местами: сперва тестируется toString, а потом valueOf. Получается, что решение с Date может быть таким:
transitive(new Date(), '<current date string>', new Date()))
Где <current date string> — текущее строковое представление даты. Можно попробовать использовать это знание, и с его помощью решить задачу. В этом случае решение будет похоже на эпизод из фильма вроде «Миссия невыполнима». У нас есть ровно секунда, чтобы оно сработало.
В моём случае получилось вот такое решение:
transitive(new Date(),'Sun Nov 22 2020 23:01:18 GMT+0200 (Eastern European Standard Time)',new Date())
Было сложно, да. Зато, вуа-ля! Мы нашли решение в 90 символов. Правда, судя по таблице рекордов, есть решение аж в 7!
Мы, конечно, можем вызывать конструктор без ключевого слова new, и это сэкономит нам 8 символов. А ещё можем подобрать таймзону таким образом, чтобы её текстовое представление было покороче. Но всё это точно не приблизит нас к 7 символам. А значит, думаем дальше.
Есть ещё много разных объектов, но для начала стоит протестировать самые базовые: Object и Array. Нас интересует, что возвращают их методы valueOf и toString.
Согласно алгоритму, что мы обсуждали раньше, если valueOf возвращает объект, то тестируется toString. А это как раз наша ситуация. Можем как-то использовать toString объекта и массива.
Например, раз у нас для Object всегда возвращается одна и та же строка, мы вполне можем это использовать в качестве решения:
transitive({},'[object Object]',{})
23 символа! Всё ближе к победе!
Однако, интереснее всего в проверках себя повёл массив. Раз для него toString работает аналогично вызову .join(), то вариант с пустым массивом мы вполне можем использовать:
transitive([],'',[])
8 символов! Осталось понять, как сократить ещё один. Для этого надо вспомнить ещё раз в алгоритм проверки на равенство.
Если есть выражение [] == '', то логика вычисления значения следующая:
Типы не совпадают.
Операнды не null и не undefined.
Операнды не String и Number.
Операндов типа Boolean нет.
Один операнд объект ([]). Приводим его к примитиву, получаем пустую строку (''). Начинаем заново.
Типы совпадают, сравниваем строки как строки.
Строки совпадают.
Поскольку мы тут ничего не можем сделать с массивом (кроме как изменить его, но пока не будем), то можно предположить, что второй операнд не строка, и посмотреть, что было бы дальше в таком случае.
Тогда после приведения объекта к строке типы бы не совпадали.
Операнды всё ещё не null и не undefined.
Операнды всё ещё не String и Number... о!
У нас один операнд точно строка, т. к. массив в неё превратился. А второй вполне себе может быть числом!
Если так, то:
Операнды String и Number. Приводим операнд типа String к типу Number и начинаем сравнение сначала.
Типы совпадают, сравниваем числа как числа.
Если мы приведём пустую строку к числу, то получим ноль. А раз так, то вот наше решение в семь символов:
В названии, как обычно, саркастическая усмешка автора над Джаваскриптом и компьютерными вычислениями в целом. Пеано — это фамилия итальянского математика Джузеппе Пеано. В XIX веке он сформулировал систему аксиом для натуральных чисел.
На этом наборе аксиом базируется истинность утверждения, что если к натуральному числу прибавить единицу, то получится следующее натуральное число:
x + 1 = S(x)
И шутка тут как раз в том, что функция в задаче идёт вразрез с этим утверждением, и как следствие, со всей аксиоматикой.
Итак, нам нужно что-то, что после добавления единицы изменится, а затем после добавления ещё одной единицы не изменится. В разработке на Джаваскрипте мы почти никогда не сталкиваемся с таким явлением как целочисленное переполнение, но тут всё намекает на что-то связанное с ним.
Целочисленное переполнение — это ситуация, в которой вычисленное в результате операции значение не может быть помещено в отведённую для него память. Все эти шутки про то, как к большому положительному числу прибавляют единицу и получают большое отрицательное — они вот как раз про переполнение.
Например, вот так это сработало бы в Си:
#include <stdio.h>
int main() {
int MAX_INT_VALUE = 2147483647;
printf("%d, %d", MAX_INT_VALUE, MAX_INT_VALUE + 1);
return 0;
}
То вроде бы подобного не происходит. Числа будто одинаковые. Если проверим, то так и окажется:
> Number.MAX_VALUE === Number.MAX_VALUE + 1
true
А почему так?
Чтобы в этом разобраться, сперва надо понять, как происходит работа с числами.
В Джаваскрипте числа хранятся в формате «с плавающей запятой». Как и в случае с NaN из второй задачи, тут снова речь о стандарте IEEE 754. Стандарт описывает много разного. Например то, как именно нужно округлять числа:
Но главное, он рассказывает о нескольких различных форматах хранения чисел:
binary16;
binary32;
binary64;
binary128;
binary256;
decimal32;
decimal64;
decimal128.
Джаваскрипт использует binary64. Он же double precision. По-русски это «число двойной точности». В отличие от того же Си, Джаваскрипт использует один единственный формат для чисел, и выбора у нас нет.
Как понятно из названия, число двойной точности занимает 64 бита в памяти компьютера. Но пока что это нам ни о чём не говорит, как и ничего не говорят слова «число с плавающей запятой». Разберёмся, как вообще хранятся числа в памяти компьютера.
Если мы имеем дело только с целыми числами, то это довольно просто, верно? Выбираем, сколько памяти у нас будет занимать представление числа (например, два байта, то есть 16 бит), и затем просто кодируем число двоичным кодом.
Допустим, есть у нас сто двадцать три в десятичной системе, а будет девять нулей, четыре единицы, ноль, две единицы в двоичной:
(Тут и далее мы двоичные числа заключаем в фигурные скобки, чтобы не путать их с десятичными.)
Довольно просто. Так, имея 16 бит мы можем подобным образом хранить числа от 0 до 2^16 − 1. То есть, до 65535.
Но предположим, что помимо положительных чисел, нам нужно хранить ещё и отрицательные. У нас не очень много вариантов решения этой проблемы. Мы просто выделяем один бит под знак. Говорим, что самый левый бит (он же «старший») теперь кодирует не значение, а знак. Если он равен нулю, то число положительное, а если единице, то отрицательное.
{|0|000 0000 0111 1011}
↑
sign
Тогда двоичное представление 123 у нас не изменится, а вот −123 будет отличаться от него значением старшего бита:
(На деле в жизни всё сложнее, и как только дело дошло бы до реализации сложения и вычитания этих чисел, появились бы такие понятия как обратный и дополнительный коды. Но это нас пока не волнует, мы упрощаем и говорим только о способе хранения. И в дальнейшем тоже будем опускать много крайних ситуаций, чтобы не вдаваться в детали.)
Обратим внимание на то, что раньше мы могли представлять целые числа от 0 до 65535. Теперь же, поскольку мы лишились одного байта, только от −32767 до 32767. Количество чисел то же, но максимальное возможное целое сократилось вдвое.
А теперь допустим, что нужно как-то с помощью тех же 16 бит записывать дробные числа. Что мы можем тут сделать?
Например, можем решить, что у нас первый бит всё так же отвечает за знак, а затем сколько-то следующих бит — это целая часть. А оставшиеся — дробная. Допустим, 8 на целую и 7 на дробную. Теперь получается, что имея вот такую запись в памяти:
В десятичной системе, с учётом новых правил хранения, это будет −255,9921875.
Да, теперь есть знаки после запятой, но вот диапазон возможных целых чисел заметно сократился. Так, 16 бит позволяют нам использовать лишь числа в интервале от −256 до 256. Зато мы можем перечислять числа с шагом в 0,0078125 (1/128), а не в единицу.
Круто. Вот только как-то не очень удобно. Ведь поскольку у нас число с фиксированной запятой, то мы не можем просто взять и переиспользовать биты с той или иной её стороны. Если нам захочется представить с помощью такой записи привычное число вроде 1000, то не получится, потому что нам не хватит на него бит.
Конечно, мы могли бы уменьшить количество бит, используемых для дробной части. Но в таком случае мы бы пожертвовали точностью, и шаг, с которым мы можем итерировать по числам, увеличился бы.
А что, если сделать так, чтобы положение запятой тоже как-то кодировалось? Что вообще такое — положение запятой?
Допустим, у нас есть десятичное число 123 456. Сейчас в нём нет запятых. Но если мы всунем её перед третьей с конца цифрой, то получим 123,456. С математической точки зрения мы уменьшили исходное число в тысячу раз. Или умножили его на 10^−3:
123,456 = 123456 × 10^-3
Запись, которая у нас получилась справа, называется ещё экспоненциальной. По-английски — scientific notation. Формально она выглядит так:
N = M × n^p
В этой записи три составляющих:
Число, которое мы умножаем — M. Оно называется «мантисса». По-английски — significand. В нашем случае это 123 456.
Основание степени — n. В нашем случае — 10.
Порядок — p. В нашем случае — −3.
Окей, всё красиво. Но как теперь это хранить в памяти компьютера? У нас ведь есть несколько способов представления одного и того же числа:
Какой из них нужно использовать? Тут нам на помощь приходят нормальная и нормализованная формы.
Нормальная форма — это такая экспоненциальная запись, в которой мантисса лежит в полуинтервале от 0 до 1. Иными словами, до запятой у мантиссы всегда ноль. То есть, в нашем случае запись была бы такой:
123,456 = 0,123456 × 10^3
Это довольно удобно, потому что мы можем вообще забыть о нуле и хранить в памяти компьютера только цифры после запятой.
Но с такой записью тоже есть проблема. Как представить с её помощью число вроде 0,0001? Это 0,1 × 10^−3? Или 0,01 × 10^−2? Неувязочка.
И для решения этой проблемы есть нормализованная форма!
(Да, предыдущая была нормальная, а эта нормализованная. Названия придумывал не я, если что.)
В нормализованной форме мантисса лежит в полуинтервале от 1 до n, где n — основание степени. Иными словами, до запятой всегда один знак, и это не ноль. Такая запись решает проблему, описанную выше:
0,0001 = 1 × 10^-4
Она, правда, порождает новые. Например, не понятно, как теперь записывать ноль. Но проблемы подобного рода нас пока не волнуют. А вот что волнует, так это то, что в двоичной записи у нормализованной формы есть ещё одна особенность. Цифра перед запятой — всегда единица.
Этот факт важен потому, что если в записи числа есть что-то постоянное, присущее всем числам, то мы можем это не хранить. Потому и не будем.
Получается, что двоичная форма записи нормализованной формы обладает в том числе и преимуществом нормальной формы.
Попробуем разобраться на примере, как хранить в памяти числа в нормализованной экспоненциальной форме.
Возьмём число 300,75, которое у нас не получилось бы сохранить в памяти с помощью записи с фиксированной запятой, что мы вывели раньше. Как минимум из-за того, что целая часть в нём больше 255.
Если просто перевести это число в двоичную систему счисления, то получим вот такое представление:
300,75 = {1 0010 1100,11}
Здесь у нас ещё первая единица не кодирует знак. Пока что это просто число в двоичной системе счисления.
Записываем его в нормализованной форме, сдвигая запятую влево:
(Заметим заодно, что так как мы перешли в двоичную систему счисления, основание степени у нас теперь 2, а не 10.)
Теперь надо разобраться, как будем это число хранить:
Первый бит будет всё так же отвечать за знак. Число положительное, значит — 0.
Затем нам нужно как-то хранить знак порядка. Будем делать это пока что по аналогии со знаком всего числа. Порядок положительный, потому тоже 0.
Сам порядок, то есть, 8, у нас вмещается в четыре бита — 1000.
Основание степени не храним, так как мы всегда оперируем степенями двойки.
А дальше мантисса. Она влезает в десять бит, поскольку мы отбрасываем единицу, что до запятой, ибо её нет смысла её хранить — 0010 1100 11.
Итого:
{0 0 1000 0010 1100 11}
Результат влезает в те же 16 бит, что и в случае с фиксированной запятой, только теперь мы можем хранить число побольше.
Чтобы уменьшить количество сущностей, мы можем ещё и совместить знак порядка с его значением. Для этого достаточно хранить его с помощью смещения.
Сейчас на значение порядка у нас отводится четыре бита, и один бит нужен для его знака. Минимальный возможный порядок при таком раскладе — −15, а максимальный — 15. При этом знак задаётся отдельным битом. Но мы можем кодировать порядок всегда положительным — значениями от 0 до 31. А реальное его значение высчитывать отнимая от имеющегося число 15.
Звучит сложно, но на самом деле не особо. Так, −15 превратится в ноль, а 15 в 30:
(На самом деле тут очередное упрощение, и в реальности значения были бы иные, но, как и раньше, такие подробности нам не очень важны.)
И вот, чтобы получить 8-ю степень, что у нас была ранее, нужно в порядке указать число 23, а бит знака убрать. А потому запись числа чуть поменяется:
{0 0 1000 0010 1100 11}
↓
{0 10111 0010 1100 11}
Теперь период у нас представляется пятью битами, без разделения на знак и значение. Интересный сайд-эффект такого решения — упрощённое сравнение чисел. Мы можем сравнивать порядки как числа без знака. То есть, если есть два числа с одним знаком, и у одного числа порядок больше, чем у другого, то оно гарантированно больше. Иными словами, нам не нужно больше заботиться о значении специального бита.
Итак, нарисовалась какая-то сложная схема, плюсы которой пока что не до конца понятны.
Раньше у нас была запись с фиксированной запятой. И она состояла из знака, целой и дробной части:
Раньше значения лежали в интервале от −256 до 256. Теперь же минимальное число, представимое новым форматом — −131 008. Максимальное, аналогично, 131 008. Сильно больше, чем раньше!
То, что мы тут получили, это неточное воспроизведение одного из форматов, описанных в IEEE 754 2008-го года. Называется этот формат half precision, или по-русски «число половинной точности». Он на деле сложнее, чем-то, что вышло у нас, но основные черты совпадают.
Так вот, возвращаясь к изначальной задаче. Джаваскрипт кодирует числа похожим образом, только использует для хранения не 16 бит, а 64. Из них 11 используются для представления порядка, а 52 — для мантиссы.
Например, вот так выглядела бы запись того же числа 300,75 в 64-битном формате:
Вроде бы разобрались, как Джаваскрипт кодирует числа. Но что нам это даёт? Как это знание объясняет вот это, например?
> Number.MAX_VALUE === Number.MAX_VALUE + 1
true
А дело в том, что у чисел с плавающей запятой ограничена точность. Причём что важно, она ограничена не только для дробной части числа, но и для его целой части.
В качестве примера посмотрим на число 2048 в 16-битном формате (уже в реальном, описанном в стандарте, а не в нашем выдуманном):
2048 = {0 11010 0000 0000 00} = 1 × 2^11
Что будет, когда мы попробуем прибавить к нему единицу? Единица в том же формате будет выглядеть вот так:
1 = {0 01111 0000 0000 00} = 1 × 2^0
Чтобы сложить два числа с плавающей запятой, нужно привести их к одному и тому же порядку. Для этого берём число с меньшим порядком, и приводим его порядок к числу с большим порядком. Получается, что нам нужно увеличить порядок в экспоненциальной записи единицы. А это значит, что нам надо сдвигать в нём запятую влево:
А теперь переведём результат обратно в используемый нами формат. Знак и порядок мы уже знаем, они такие же, как у 2048, а мантисса — это просто цифры суммы после запятой:
1,00000000001 × 2^11 = {0 11010 0000 0000 001}
Вроде бы просто. Но есть проблема. Если мы посчитаем количество бит в результате, то их будет 17, а не 16! У нас внезапно выпала единичка. Она просто не влезает в отведённые ей биты. И что нам с ней делать?
Возможны разные способы обработки такой ситуации. Как вариант, можно просто отбросить лишние биты. Тогда полученное нами число ничем не будет отличаться от того, что было изначально!
Мы прибавили к 2048 единицу, но вдруг всё равно получили 2048. Это и есть то, что называется «ограниченной точностью». В 16-битном формате целые числа между 2048 и 4096 округляются вниз до ближайшего кратного двум. А потому мы и получили 2048. Аналогичным образом в этом формате числа от 4096 до 8192 округляются вниз до ближайшего кратного четырём, и так далее.
Если бы мы прибавляли двойку, а не единицу, то при сложении получили бы на один ноль меньше после запятой:
Здесь roundTiesToEven — это название алгоритма округления. Его особенность в том, что это округление по обычным правилам математики, но с одним исключением. Когда нужно округлить значение, которое лежит точно посередине между какими-то двумя, оно будет округлено к ближайшему чётному. Чтобы лучше понять, как это работает, обратимся к примерам.
Допустим, нам нужно округлить число 1,2. Тут всё привычно, получится 1.
А если бы мы округляли 1,5, то получили бы 2. Кажется, что логично.
Однако, если бы мы округляли 2,5, то результат тоже был бы 2! Потому что 2,5 при округлении лежит чётко между двумя числами, до которых можно округлить: 2 и 3. И мы выбираем чётное.
Несмотря на такие странности, алгоритм довольно просто работает в случае с двоичной системой счисления.
Так вот, возвращаясь к нашему примеру. Если попробовать вручную прибавить к Number.MAX_VALUE единицу, то получится снова Number.MAX_VALUE:
> Number.MAX_VALUE === Number.MAX_VALUE + 1
true
Как мы теперь понимаем, это потому, что при прибавлении появляется лишний бит, который не влезает в отведённое для него пространство, и из-за округления обрезается.
Но если прибавить десять, то результат будет тем же:
Придётся добавить к этой константе число, состоящее из единицы и 292 нулей, чтобы единичка наконец-то добавилась, и результат превратился в бесконечность:
И это то, как работает переполнение в Джаваскрипте.
Теперь, зная обо всех этих деталях, мы можем найти число, которое при увеличении на единицу сперва изменяется, а затем нет.
В случае 16-битного формата, число 2048 было минимальным положительным целым, на котором сказывались проблемы округления. И в нём порядок был равен количеству бит мантиссы + 1, а все биты мантиссы были выставлены в ноль:
Потому в нашем случае начать поиски легче всего с подобного числа в 64-битном формате.
Ищем положительное число, потому в двоичной версии искомого числа первым будет ноль. А поскольку в этом формате для мантиссы используется 52 бита, то нам нужен порядок равный 53. С учётом смещения 53 будет кодироваться как 1076 (в 64-битном формате смещение равно 1023). А в мантиссе — нули. Получаем:
Если мы добавим к найденному числу единицу, то, как и в случае с 2048 в 16-битном формате, ничего не произойдёт. А это вполне подходит под вторую часть условия задачи!
> 9007199254740992 + 1
9007199254740992
А чтобы удовлетворить первую часть условия, нужно взять предыдущее число:
> 9007199254740991 + 1
9007199254740992
Если мы используем его в качестве решения, то при первом добавлении единицы всё пройдёт гладко, но уже со следующего добавления «цена последовательного изменения числа» будет стоить не единицу, а двойку. И потому добавление ещё одной единицы ничего не изменит.
Проверяем:
> peano(9007199254740991)
true
Подходит!
К слову, это как раз то самое число, для которого в Джаваскрипте есть константа Number.MAX_SAFE_INTEGER, название которой как бы намекает.
Итак, у нас есть решение в 16 символов. Вот только у других игроков как-то получилось найти решение в пять символов!
Что же делать? Можно вспомнить, что Number.MAX_SAFE_INTEGER — это 2^53 − 1. Но Math.pow(2,53)-1 — всё равно 16 символов.
Однако, у нас же есть ES6-синтаксис для возведения в степень! Вжух:
> peano(2**53-1)
true
Семь символов! Но как получить пять?
Вероятно, можно вычислить какое-то похожее по свойствам число возведением однозначного в двузначную степень или двузначного в однозначную. Попробуем перебрать:
const peano = x => (x++ !== x) && (x++ === x);
function find() {
for (let i = 0; i < 100; i++) {
for (let j = 0; j < 100; j++) {
if (`${i}**${j}`.length > 5) continue;
if (peano(i ** j)) {
console.log(i, j);
}
}
}
}
> find()
И ничего.
Если присмотреться к топу, то почему-то все те, кто нашёл решение в 5 символов, нашли его в старых версиях Хрома:
Возможно это и совпадение, но маловероятно.
Хром — это Хромиум, потому попробуем скачать старую версию Хромиума, в надежде найти в нём решение. Первым в топе числится Хром 65-й версии, потому с этой версии и начнём.
Если погуглить «как скачать старую версию Хромиума», то окажется, что лёгкого пути нет. Разработчики Хромиума предлагают алгоритм, который выглядит так себе:
Найти запись о подходящей стабильной версии браузера у них в блоге. А их там может быть несколько.
Затем пойти на специальный сайт, и по этой версии найти номер коммита.
После пойти на другой сайт и по номеру коммита найти билд. И возможно, что таковой не найдётся, и придётся перебирать номера коммитов.
Это несколько долго, потому есть другой способ:
Берём репозиторий, автор которого позаботился о выкачивании всех ссылок на все стабильные версии Хромиума.
Аргумент user-dir-data нужен чтобы Хромиум не пытался подгрузить профиль основного браузера, и не ругался на несовпадение настроек.
Вуа-ля, теперь у нас есть Хромиум:
Можем проверить наш код в нём:
> find()
Но снова почему-то ничего. В чём же тут дело?
Как вариант, в том, что ошибка происходит во время каких-то оптимизаций, и она не проявляется при использовании переменных. Движок Джаваскрипта ведь много чего оптимизирует, и вполне возможно, что между вот этими двумя записями мало общего:
let x = 1, y = 2
peano(x ** y)
peano(1 ** 2)
Потому что вторую можно точно оптимизировать на месте, а вот первую оптимизировать сложнее.
Проверить это предположение, нам поможет eval. Перепишем тест с его помощью и запустим:
const peano = x => (x++ !== x) && (x++ === x);
function find() {
for (let i = 0; i < 100; i++) {
for (let j = 0; j < 100; j++) {
if (`${i}**${j}`.length > 5) continue;
if (eval(`peano(${i} ** ${j})`)) { // <--
console.log(i, j);
}
}
}
}
> find()
3 34
7 19
9 17
63 9
99 8
И вот, теперь, у нас есть ответы. Проверим любую из этих пар чисел в 65-м Хромиуме:
> peano(3 ** 34)
true
И правда, работает. При этом, если мы запустим тот же код поиска в новом Хроме, то он нам ничего не выдаст.
Мы нашли решение в пять символов. Берём любую из этих пар чисел, подставляем её в поле на сайте, используя старый браузер, готово. Например, 9 и 17. Однако, теперь возникает другой вопрос. А почему оно работало так, а сейчас работает иначе?
Но это отдельное приключение на 20 минут...
Если проверить, то в последнем Хроме 9^17 — это вот такое число:
> 9 ** 17
16677181699666568
В то время как в 65-м Хромиуме такое:
> 9 ** 17
16677181699666570
Отличие в двух последних цифрах. Видимо, какая-то особенность округления. Причём, как мы помним, при вычислении с использованием переменных, результат в 65-м Хромиуме иной:
> let x = 9, y = 17
> x ** y
16677181699666568
Если мы пойдём дальше, и поищем первую версию браузера, в которой это починили, то окажется, что ещё в 73-й версии это работало так же странно:
А вот уже в версии 74-й всё так же, как и в последнем Хроме.
А раз так, то мы можем посмотреть, какие версии V8 использовались в обоих браузерах, и попробовать по исходникам V8 разобраться, в чём проблема.
Последняя забагованная версия браузера использовала V8 версии 7.3.492.1, а первая исправленная — 7.4.288. Получается, что где-то между этими двумя версиями баг исправили.
Если посмотрим на репозиторий V8, то увидим, что для каждой версии есть тег. В том числе для наших двух: 7.3.492.1, 7.4.288. Вот только разница между ними в два месяца, а с учётом скорости разработки V8, это сотни коммитов. Перебирать всё руками долго. Потому попробуем автоматизировать.
На сайте V8 написано, как можно собрать движок из исходников. И упомянуто, что можно при сборке автоматически запускать тесты. Получается, что если мы напишем необходимый нам тест, то потом сможем бисектом найти первый коммит, который всё поломал. Ну или починил, тут как посмотреть.
Чтобы упростить процесс и не устанавливать дополнительные зависимости глобально, как того требует документация, запустим всё в Докере.
Сайт V8, как и доки всех связанных с ним пакетов, не особо описывает, какие именно зависимости нужны для сборки, но методом тыка выяснилось, что вот этого списка нам для теста достаточно:
git, curl, python, pkg-config, binutils
Потому берём образ Дебиана, запихиваем всё туда и делаем всё по инструкции:
FROM debian:bullseye-slim
RUN apt-get update && apt-get upgrade -yqq
RUN DEBIAN_FRONTEND=noninteractive \
apt-get install \
git \
curl \
python \
pkg-config \
binutils \
nano \
-yqq
RUN git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
ENV PATH="/depot_tools:${PATH}"
RUN gclient
RUN fetch v8
(Я не настоящий докеростроитель, и каску на стройке нашёл, потому скорее всего в этом Докерфайле что-то не так. Но нам на секундочку и вообще только спросить, а потому и так сойдёт.)
Собираем образ:
$ docker build -t v8:latest .
[+] Building 415.1s (10/10) FINISHED
=> [internal] load build definition from Dockerfile 0.0s
=> => transferring dockerfile: 38B 0.0s
=> [internal] load .dockerignore 0.0s
=> => transferring context: 2B 0.0s
=> [internal] load metadata for docker.io/library/debian:bull 0.7s
=> [1/6] FROM docker.io/library/debian:bullseye-slim@sha256:6 0.0s
=> [2/6] RUN apt-get update && apt-get upgrade -yqq 12.4s
=> [3/6] RUN DEBIAN_FRONTEND=noninteractive apt-get inst 17.2s
=> [4/6] RUN git clone https://chromium.googlesource.com/chro 9.1s
=> [5/6] RUN gclient 58.0s
=> [6/6] RUN fetch v8 301.8s
=> exporting to image 15.8s
=> => exporting layers 15.8s
=> => writing image sha256:edcebc5c59a0e7fa230a2a03d551ab6af5 0.0s
=> => naming to docker.io/library/v8:latest 0.0s
После того, как собралось, запускаем контейнер и Баш в нём:
$ docker run -it --rm v8:latest /bin/bash
Теперь мы внутри контейнера. Исходники в процессе сборки образа должны были скачаться в папку v8. Проверим:
$ cd v8
$ ls
AUTHORS README.md include
BUILD.gn WATCHLISTS infra
CODE_OF_CONDUCT.md base out
ChangeLog benchmarks samples
DEPS bisect.sh snapshot_toolchain.gni
LICENSE build src
LICENSE.fdlibm build_overrides test
LICENSE.strongtalk buildtools testing
LICENSE.v8 codereview.settings third_party
LICENSE.valgrind custom_deps tools
OWNERS docs
PRESUBMIT.py gni
Похоже на правду. Теперь посмотрим, как тут устроены тесты. Они все лежат в папке test, разбитые по категориям:
$ ls test
BUILD.gn fuzzer message test262 webkit
benchmarks inspector mjsunit torque
cctest intl mkgrokdump unittests
common js-perf-test mozilla wasm-js
debugger memory preparser wasm-spec-tests
Всего там почти восемь сотен файлов, и, как мы видим, каждый тест состоит из файла с самими кейсами и файла с ожидаемым результатом. Для примера, вот часть файла с тестами для функции parseInt:
$ cat test/webkit/parseInt.js
description('Tests for the parseInt function.');
// Simple hex & dec integer values.
shouldBe("parseInt('123')", '123');
shouldBe("parseInt('123x4')", '123');
shouldBe("parseInt('-123')", '-123');
shouldBe("parseInt('0x123')", '0x123');
shouldBe("parseInt('0x123x4')", '0x123');
shouldBe("parseInt('-0x123x4')", '-0x123');
# ...
А вот часть файла с ожидаемыми значениями для него же:
$ cat test/webkit/parseInt-expected.txt
Tests for the parseInt function.
On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
PASS parseInt('123') is 123
PASS parseInt('123x4') is 123
PASS parseInt('-123') is -123
PASS parseInt('0x123') is 0x123
PASS parseInt('0x123x4') is 0x123
PASS parseInt('-0x123x4') is -0x123
# ...
PASS successfullyParsed is true
TEST COMPLETE
Попробуем запустить сборку и тесты parseInt:
$ /v8/tools/dev/gm.py x64.debug webkit/parseInt
# ...
Done. Made 166 targets from 96 files in 92ms
# autoninja -C out/x64.debug d8
ninja: Entering directory 'out/x64.debug'
[1869/1869] LINK ./d8
# "/usr/bin/python2" tools/run-tests.py --outdir=out/x64.debug webkit/parseInt
Build found: /v8/out/x64.debug
>>> Autodetected:
pointer_compression
>>> Running tests for x64.debug
>>> Running with test processors
[00:00|% 0|+ 1|- 0]: Done
>>> 1090 base tests produced 1 (0%) non-filtered tests
>>> 1 tests ran
Done! - V8 compilation finished successfully.
Работает. Теперь напишем свой небольшой тест и оформим его по аналогии с тестом parseInt:
$ cat test/webkit/peano.js
description('Tests for **.');
shouldBe('9 ** 17', '16677181699666570');
$ cat test/webkit/peano-expected.txt
Tests for **.
On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
PASS 9 ** 17 is 16677181699666570
PASS successfullyParsed is true
TEST COMPLETE
Ожидаем, что значением будет то число, что мы получали в старых версиях V8. И, конечно, если запустим этот тест сейчас, он упадёт:
$ /v8/tools/dev/gm.py x64.debug webkit/peano
# ...
>>> Running tests for x64.debug
>>> Running with test processors
=== webkit/peano ===
Tests for **.
On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
FAIL 9**17 should be 16677181699666560. Was 16677181699666568.
PASS successfullyParsed is true
TEST COMPLETE
# ...
--- FAILED ---
[00:00|% 0|+ 0|- 1]: Done
>>> 1092 base tests produced 1 (0%) non-filtered tests
>>> 1 tests ran
Error! - V8 compilation finished with errors.
А значит нужно найти первый коммит, в котором тест падает. Для этого воспользуемся бисектом. Напишем простенький скрипт, и сделаем его выполняемым:
В этом скрипте мы сперва удаляем кэш предыдущей сборки (просто потому что почему-то без этого новая не собирается; но, как я уже говорил ранее, я не настоящий строитель). Затем устанавливаем новые зависимости. Ключ -D затем, чтобы gclient удалял неиспользуемые зависимости. Нам это не важно, но иначе он просто шумит предупреждениями в выдаче.
Если последняя команда в файле упадёт (а она и запускает сборку и тесты), то скрипт завершится с кодом 1, иначе — 0. Так Гит поймёт, куда ему двигаться дальше во время бисекта.
Запускаем всё это счастье:
$ git bisect start
Previous HEAD position was a439a7a210 [ic] Rename FindFirstName & FindFirstMap to GetName & GetFirstMap
HEAD is now at fe8831f551 Update V8 DEPS.
$ git bisect bad 7.4.288
$ git bisect good 7.3.492.1
Bisecting: a merge base must be tested
[be213cfc485101c67efe00af1fffba84fa9fc8a5] [codegen] Use target architecture specific branch alignment
$ git bisect run ./bisect.sh
В ходе поиска Гит запускает наш скрипт, тот устанавливает зависимости и прогоняет тест. Первый шаг бисекта выглядит так:
$ git bisect run ./bisect.sh
running ./bisect.sh
Syncing projects: 100% (24/24), done.
# ...
[1150/1150] LINK ./d8
# tools/run-tests.py --outdir=out/x64.debug webkit/peano
Build found: /v8/out/x64.debug
>>> Autodetected:
embedded_builtins
>>> Running tests for x64.debug
>>> Running with test processors
[00:00|+ 1|- 0]: Done
>>> 1 tests ran
Done! - V8 compilation finished successfully.
Bisecting: 507 revisions left to test after this (roughly 9 steps)
[a439a7a210143b8dd574df3a8024243da0bd5f0a] [ic] Rename FindFirstName & FindFirstMap to GetName & GetFirstMap
Тесты прошли успешно, а значит, это какой-то из старых коммитов, в которые ещё не внесли правки, изменяющие работу оператора возведения в степень. В конце мы видим, что Гит выбрал следующий коммит для теста, и дальше всё это повторяется ещё девять раз.
Наконец, получаем ответ:
$ git bisect run ./bisect.sh
# ...
98453126c109016c9d32c6ebd89dd83f69dd8efb is the first bad commit
# ...
bisect run success
Так мы нашли первый коммит, в котором наш тест падает:
$ git show 98453126c109016c9d32c6ebd89dd83f69dd8efb
commit 98453126c109016c9d32c6ebd89dd83f69dd8efb
Author: Gus Caplan <me@gus.host>
Date: Thu Feb 7 18:32:59 2019 -0600
Reland^2 "[builtins] [turbofan] Refactor Float64Pow to use single implementation"
This is a reland of d7def9003df0e30f8a3eed2594f5101dac7e2b5a
Original change's description:
> Reland "[builtins] [turbofan] Refactor Float64Pow to use single implementation"
>
> This is a reland of I968a08cef6a6d49350aa79185b2c6fb856d15f23
>
> Original change's description:
> > [builtins] [turbofan] Refactor Float64Pow to use single implementation
> >
> > Remove platform-specific Float64Pow implementations and utils Pow in
> > favor of a base::ieee754::pow implementation.
> >
> > This unifies the implementation of pow for the compiler, wasm, and
> > runtime.
> >
> > Bug: v8:5848, v8:5086
> > Change-Id: I968a08cef6a6d49350aa79185b2c6fb856d15f23
> > Reviewed-on: https://chromium-review.googlesource.com/c/1403018
> > Commit-Queue: Clemens Hammacher <clemensh@chromium.org>
> > Reviewed-by: Clemens Hammacher <clemensh@chromium.org>
> > Reviewed-by: Georg Neis <neis@chromium.org>
> > Reviewed-by: Yang Guo <yangguo@chromium.org>
> > Reviewed-by: Jaroslav Sevcik <jarin@chromium.org>
> > Cr-Commit-Position: refs/heads/master@{#59229}
# ...
Судя по описанию, в нём рефакторили операцию возведения в степень. Если заглянем в дифф, то увидим файл с новой имплементацией, которая, если верить названию файла и комментариям в нём, соответствует IEEE 754:
diff --git a/src/base/ieee754.cc b/src/base/ieee754.cc
index 5203643ee5..4fcb4df001 100644
--- a/src/base/ieee754.cc
+++ b/src/base/ieee754.cc
@@ -2647,6 +2647,317 @@ double cosh(double x) {
return huge * huge;
}
+/*
+ * ES2019 Draft 2019-01-02 12.6.4
+ * Math.pow & Exponentiation Operator
+ *
+ * Return X raised to the Yth power
+ *
+ * Method:
+ * Let x = 2 * (1+f)
+ * 1. Compute and return log2(x) in two pieces:
+ * log2(x) = w1 + w2,
+ * where w1 has 53-24 = 29 bit trailing zeros.
+ * 2. Perform y*log2(x) = n+y' by simulating muti-precision
+ * arithmetic, where |y'|<=0.5.
+ * 3. Return x**y = 2**n*exp(y'*log2)
# ...
Помимо этого в теле коммита есть коды багов из багтрекера V8. И первый из них (v8:5848) как раз о том, что функция возведения в степень для переменных и для значений работает по-разному. Там выяснили, что есть сразу две проблемы.
Первая проблема в том, что, как мы догадались ранее, из-за оптимизаций вычисление возведения в степень чисел происходит во время компиляции, а вычисление возведения в степень переменных — в рантайме. Потому нам пришлось использовать eval.
А вторая проблема в том, что выполняют эти вычисления два разных куска кода, один из которых не соответствует стандарту.
Если разбираться дальше, то окажется, что новая имплементация внутри использует библиотеку, результат которой всё ещё не совсем точный. А потому не стоит ожидать того, что программа на Джаваскрипте выдаст тот же результат, что и программа на Пайтоне, например. Этого в принципе никогда не нужно ожидать, но даже в этом случае, когда имплементация вроде как соответствует IEEE 754, всё равно можно ждать подвоха.
P. S.: А ещё можно было бы найти решение в шесть символов. Например, такое: 1e16+2.
function counter(f) {
var a = f(), b = f();
return a() == 1 && a() == 2 && a() == 3
&& b() == 1 && b() == 2;
}
В этой задаче нужно написать функцию, которая бы возвращала функцию-счётчик, при вызове которой, в свою очередь, возвращалась сначала единица, затем двойка, тройка и так далее.
Довольно простая задача. Например, ответ мог бы быть таким:
function() {
let x = 1;
return function() {
return x++;
}
}
И это вполне себе решение. Если убрать все пробельные символы и вытянуть код в строчку, получим 50 символов:
Ясное дело, что в первую очередь нам тут нужно заменить всё на анонимные функции:
counter(()=>{let x=1;return ()=>x++})
28! Неплохо. Но, судя по таблице результатов, можно упростить аж до 11 символов:
Больше всего в текущем решении смущают let и return. Явно надо избавляться как-то от них. Если мы просто удалим let, оставив x без него, то код не заработает:
> counter(()=>{x=1;return ()=>x++})
false
x в таком случае объявляется не как локальная переменная функции, а как свойство глобального объекта (window, ибо мы в браузере). И каждый вызов внутренней функции переиспользует имеющийся счётчик, а каждый вызов внешней функции — сбрасывает его. Интересная фича, но не то, что нам нужно.
Однако, если нам нужно, чтобы x стал локальной переменной, достаточно просто передать его в качестве параметра:
counter(x=>{x=1;return ()=>x++})
Теперь присваивание работает только в рамках функции, а потому переменная не переиспользуется между всеми вызовами. Ну и, да, 23 символа.
С let разобрались, а значит нужно как-то избавляться от return.
В анонимной функции можно не использовать фигурные скобки и return, если вместо тела написать выражение, результат которого она должна вернуть. Но у нас ведь два выражения в функции, потому просто удалить return мы не можем.
Но можем использовать запятую. Оператор , вычисляет и левую, и правую часть, но возвращает только результат вычисления правой. А это как раз то, что нам нужно: объявить переменную и вернуть функцию.
Просто убрать фигурные скобки и заменить return на запятую мы не можем:
> counter(x=>x=1,()=>x++)
false
Тогда это просто будут две функции, записанные через запятую. Скобки всё же придётся добавить. Но круглые:
counter(x=>(x=1,()=>x++))
16 символов! Мы всё ближе.
С лёгкостью можем выиграть ещё один символ, заменив скобки вокруг параметров внутренней функции на какой-то параметр. На нижнее подчёркивание, например:
counter(x=>(x=1,_=>x++))
Правда, это всё ещё не 11.
Мы не можем никак избавиться от того факта, что у нас есть внешняя и внутренняя функция. И вроде никак не можем избавиться от инкремента. Но можем вместо определения x внутри функции, указывать для него значение по умолчанию:
counter((x=1)=>(_=>x++))
Правда, это заставляет нас добавлять скобки вокруг параметров внешней функции. Но зато можно убрать их вокруг внутренней, т. к. тело внешней у нас теперь состоит только из определения внутренней:
counter((x=1)=>_=>x++)
Скобки туда, скобки сюда, и получили мы 13 символов. Совсем близко.
Точно можно сократить ещё два символа, и это явно должны быть =1. Но если мы их просто уберём, то работать ничего не будет:
> counter(x=>_=>x++)
false
У нас ведь теперь x по умолчанию равен undefined, а при увеличении его на единицу мы получаем NaN. Дальше, увеличивая NaN, получаем снова его, и так далее. Значит, нужно как-то обработать первое присваивание, чтобы не падать в этот NaN-цикл. Можем сделать так:
counter(x=>_=>x=++x||1)
Теперь, даже если мы получаем NaN при приведении undefined к числу, мы всё равно присваиваем единицу.
Однако, это 14 символов. Нужен какой-то способ, который позволит превратить undefined в ноль, а затем увеличить его на единицу. Кажется, тут снова может помочь приведение типов.
Как мы уже уяснили, приведение undefined к числу нам не поможет, ибо получим NaN. Значит унарный плюс бесполезен:
> +undefined
NaN
Возможно нам помогло бы каким-то образом отрицание, ибо:
> !undefined
true
И если сделать двойное отрицание, то мы бы получили ноль. Но проблема в том, что вот в такой записи:
x=>_=>x=!!x+1
Мы получим единицу при первом вызове внутренней функции, а затем всегда будем получать только двойку, ибо x в первой части выражения во всех вызовах кроме первого будет приводиться к единице.
У нас остался ещё один оператор, который часто используется в разных хаках — битовое «не»:
> ~undefined
-1
И вон он даёт что-то интересное. Если мы применим его дважды, то получим:
> ~~undefined
0
Как раз то, что нам нужно. А поскольку двойное отрицание для числа возвращает само число, то подобная конструкция работает не только для первого присваивания, но и для всех последующих.
Получается, что решение в 13 символов выглядит следующим образом:
counter(x=>_=>x=~~x+1)
В примерах про использование undefined с разными унарными операторами можно заметить полезное для нас свойство битового отрицания:
> ~0
-1
> ~1
-2
> ~2
-3
> ~undefined
-1
Получается, что после использования побитового отрицания мы получаем необходимое для функции-счётчика число, просто с противоположным знаком. А раз так, то почему бы не сократить решение ещё немного:
counter(x=>_=>x=-~x)
Вжух! 11 символов.
Если посмотрим на таблицу результатов, то увидим там даже ребят с 9-символьными решениями:
Но все они схитрили, подставив в качестве выражения, возвращаемого из внешней функции, prompt. Так, каждый вызов внутренней функции становился вызовом prompt и позволял ввести нужное значение, которое затем и использовалось в сравнении.
Хитро! Но автор игры это уже пофиксил, потому мы не сможем использовать такую лазейку. А раз так, то можно остановиться на решении в 11 символов.
Можно остановиться и обсудить вот что. Как так вышло, что undefined после побитового отрицания превратился в 0, а не в NaN, как в случае использования унарного плюса? И как вообще происходит побитовое отрицание, если мы обсуждали ранее, что числа в Джаваскрипте хранятся в виде знака, мантиссы и периода, как это завещал IEEE 754. Какие же биты в таком случае инвертируются?
Дело в том, что побитовые операции в Джаваскрипте работают не совсем так, как арифметические. Чтобы в этом разобраться, сперва обсудим, как работает побитовое отрицание, не глядя на его реализацию в Джаваскрипте.
Когда мы разбирали четвёртую задачу, то моделировали разные способы хранения чисел в памяти. Там мы пришли к тому, что чтобы хранить целые знаковые числа в 16-битном формате, нужно старший бит выделить под знак:
{|0|000 0000 0111 1011}
↑
sign
И в таком формате 123 и −123 отличаются друг от друга только первым битом:
А теперь предположим, что мы хотим сложить эти два числа, имея только их битовое представление. Если мы просто будем складывать каждый бит друг с другом справа налево (в столбик), то получится какая-то шляпа:
(Сложение как операция происходит внутри компьютера сложнее, чем кажется на первый взгляд. Посмотрите «Как компьютеры складывают числа», чтобы понять, что к чему.)
Мы сложили 123 и −123, а получили −246. Да, наверное мы зря складывали старшие биты, они ведь знаковые. Но если бы не складывали, результат не стал бы лучше. Почему так происходит?
Как минимум потому, что мы неправильно реализовываем сложение. Если бы у нас были два положительных числа, всё сработало бы нормально:
Однако, реализовывать вычитание как отдельную операцию на машинном уровне — дорого. И лучше пойти другим путём.
(Если вы посмотрели видео «Как компьютеры складывают числа», то скорее всего понимаете, что для вычитания потребовались бы отдельные части АЛУ, отличные от сумматоров.)
Вычитание — это сложение уменьшаемого с вычитаемым, где у вычитаемого инвертирован знак. Примерно так это работает и внутри компьютера, только вместо отрицания вычитаемого, все его биты, кроме знакового, инвертируются. Это называется обратным кодом, в противовес прямому коду, который мы использовали ранее.
Вот как выглядел бы обратный код для числа −123:
-123 = [1 111 1111 1000 0100]
(Чтобы не путаться, будем биты в обратном коде заключать в квадратные скобки.)
Теперь, если мы захотим сложить 123 и −123, то выглядеть это будет так:
Инвертировать биты 123 не нужно. Обратный код положительного числа совпадает с его прямым кодом.
Ответ при сложении получается тоже в обратном коде. Поскольку он получился отрицательным, то чтобы перевести его в прямой, нужно снова инвертировать все биты, кроме знакового:
Самая левая единица не влезла в отведённое для неё место. В случае возникновения такой ситуации, компьютеру нужно взять эту единицу и добавить к получившемуся результату:
Сперва переведём −120 в дополнительный код. Для этого инвертируем все биты кроме знакового, получая обратный код, а затем добавим единицу к модулю получившегося значения:
Тут мы получили отрицательное число в дополнительном коде. Сперва отнимаем от него единицу, получая обратный код. А затем инвертируем биты и получаем прямой код, или −20.
(На самом деле при переводе из прямого в дополнительный, и при переводе из дополнительного в прямой, можно всегда сперва инвертировать биты, а затем добавлять единицу к модулю числа.)
Да, на преобразование отрицательного числа в обратный код уходит меньше времени, чем на преобразование его в дополнительный. Но сложение дополнительных кодов быстрее, чем обратных, ибо не нужно обрабатывать перенос. А потому компьютеры в большинстве своём хранят целые числа сразу в дополнительном коде. Это позволяет упростить операции сложения и вычитания (поскольку нужна только операция сложения), и тем самым упростить архитектуру вычислителя.
Обратный и дополнительный коды — это сущности из мира целых чисел. Как мы помним, Джаваскрипт оперирует числами с плавающей запятой, а потому ничего не хранит в дополнительных кодах. Однако, когда речь заходит о побитовых операциях, Джаваскрипт приводит имеющиеся операнды к 32-битным целым (со знаком или без), проводит над ними необходимую операцию, а затем переводит результат в 64-битное число с плавающей запятой.
Тут сразу может возникнуть вопрос, почему операции происходят над 32-битными целыми, а не над 64-битными? Но ответ на него очевиден. 64-битные целые не всегда можно перевести в формат с плавающей запятой без потерь:
А все 32-битные целые вполне влезают в имеющиеся ограничения.
Теперь мы знаем, как работает сложение чисел в дополнительном коде, и понимаем, что при работе с побитовыми операциями, Джаваскрипт сперва переводит числа в 32-битные целые, а затем обратно в число двойной точности. А раз так, то посмотрим, как работает оператор побитового отрицания.
Если не BigInt, то приводим значение к типу, обозначенному в спецификации как Int32.
Для получившегося числа вычисляем -x - 1.
-x - 1 — это арифметическое представление инвертирования битов и перевода дополнительного кода в прямой.
Предположим, что у нас есть всё то же число 123, и мы решили вычислить ~123. Согласно этому алгоритму, мы должны получить −124. Джаваскрипт подтверждает:
> ~123
-124
Дополнительный код 123 — (0 000 0000 0111 1011), и если в нём инвертировать биты, как это должен делать оператор ~, то получим (1 111 1111 1000 0100). Какое-то число в дополнительном коде. Переведём его в прямой:
Наконец, инвертируем знак этого получившегося числа и вычитаем из него единицу. Получаем ответ: 705_032_703.
О чём ещё тут можно было бы упомянуть, это о том, что такое «положительный остаток», который мы выше высчитывали. Несмотря на то, что «остаток от деления» — это что-то из курса математики за четвёртый класс, всё не так просто, как кажется на первый взгляд.
Нет никаких проблем найти остаток от деления, когда работаем с двумя положительными числами. При делении 52 на 6 получаем в неполном частном 8 и 4 в остатке:
52 = 8 * 6 + 4
Однако, что, если мы будем делить −52 на 6?
-52 = -8 * 6 + (-4)
-52 = -9 * 6 + 2
Внезапно появляются два возможных результата. Смотря какой будет остаток от деления — положительный или отрицательный. Потому, когда мы обсуждаем алгоритмы, зачастую нужно уточнять, о каком именно остатке идёт речь.
Некоторые языки программирования поддерживают несколько операций для поиска остатка от деления. Так, в Хаскеле есть как mod так и rem:
> mod (-52) 6
2
> rem (-52) 6
-4
При делении с остатком в этих операциях используется разное «усечение»: к нулю или к −∞. Так, rem делает целую часть ближе к нулю, а mod — к −∞. Иными словами, при rem знак остатка совпадает со знаком делимого, а при mod — со знаком делителя.
Если же говорить про Джаваскрипт, то в нём только одна операция для поиска остатка от деления — %. И в ней знак остатка совпадает со знаком делимого (аналогично rem):
> -52 % 6
-4
> 52 % -6
4
Напоследок можно сказать ещё вот о чём.
Иногда в целях дебага нужно найти битовое представление числа. Если нужно 32-битное представление переданного числа как целого, то подойдёт вот такая функция:
function getInt32Binary(n) {
return (n >>> 0).toString(2).padStart(32, '0');
}
Здесь n >>> 0 означает, что мы сдвигаем ноль битов вправо. То есть, никакого сдвига по факту и не происходит. Однако, из-за этой операции число неявно приводится к беззнаковому 32-битному целому.
А если мы хотим посмотреть на то, как выглядит число в Джаваскрипте по стандарту IEEE 754, то можем использовать вот такую запись:
function getFloat64Binary(n) {
const uint32 = new Uint32Array(new Float64Array([n]).buffer);
return getInt32Binary(uint32[1]) + getInt32Binary(uint32[0]);
}
Хитрая задача, которая рассказывает о тяжкой судьбе массивов в Джаваскрипте.
Дело в том, что до ES5 единственным некривым способом убедиться, что перед нами массив, была проверка на instanceof. Однако, со временем вскрылась проблема, которая не была актуальной во времена написания спецификации ES3: несколько версий глобальных объектов.
Когда мы создаём новое окно, получаем оттуда какие-то массивы и проводим над ними операции, то они будто из другой вселенной:
> [] instanceof Array
true
> let w = window.open('javascript:window.arr=[]')
> w.arr
[]
> w.arr instanceof Array
false
А всё потому, что в разных окнах глобальные объекты разные. В текущем окне массив — экземпляр глобального класса Array, принадлежащего этому окну. В новом же окне или айфрейме будет создан уже экземпляр другого класса Array.
Потому до ES5 разработчики обычно шли на хитрость и использовали метод toString объектов, который, согласно спецификации, был единственным, что позволяло взглянуть на внутреннее свойство [[Class]]:
The value of a [[Class]] property is used internally to distinguish different kinds of built-in objects. Note that this specification does not provide any means for a program to access that value except through Object.prototype.toString.
Однако, это больше похоже на хак, чем на легальный способ проверки. Да и он многословен. Плюс приходится надеяться на то, что ни Object.prototype.toString, ни Function.prototype.call не будут как-то изменены сторонними инструментами.
И вот, пришёл ES5 и всё починил.
В ES5 добавили Array.isArray, который делал ровно то же самое, что и проверка через Object.prototype.toString, только под капотом:
If the value of the [[Class]] internal property of arg is "Array", then return true.
Таким образом, Array.isArray стал легитимным способом проверки объекта «на массивность». Поскольку он сравнивал название внутреннего класса, а не объекты, то исправил проблему кросс-фреймовых массивов:
> [] instanceof Array
true
> let w = window.open('javascript:window.arr=[]')
> w.arr
[]
> Array.isArray(w.arr)
true
Причём его нельзя обмануть даже подменой прототипа:
Потому что __proto__ перезаписывает внутреннее поле [[Prototype]], а не [[Class]]. Более того, несмотря на то, что методы у этого массива больше не работают (ведь их нет в прототипе), он всё равно ведёт себя как массив:
> arr.length
0
> arr.push(1)
TypeError: arr.push is not a function
> arr[0] = 1
> arr.length
1
Отчасти с этим связан тот факт, что прототип массива — тоже массив. Это может быть не совсем очевидно:
> Object.prototype.toString.call(Date.prototype)
"[object Object]"
> Date.prototype.getTime()
TypeError: this is not a Date object
Все остальные объекты работают как обычные инстансы Object. И только у массива есть связь между нумерованными полями и свойством length.
(Эта связь между нумерованными полями и свойством length настолько типична для массивов, что в ES6 Array.isArray больше не проверяет [[Class]], а проверяет именно наличие этой связи, реализованной с помощью внутренних методов. Более того, в спеке вообще больше нет понятия [[Class]].)
Тем не менее, несмотря на такое поведение Array.prototype, у него в цепочке прототипов нет Array, а потому:
> Array.prototype instanceof Array
false
И это одно из возможных решений первой части задачи.
Чтобы найти решение для второй части, нужно разобраться, как работает instanceof. Если имеем Value instanceof Target, то, опуская некоторые детали, алгоритм в ES6 таков:
Если у Target есть метод @@hasInstance, то:
Вызываем его, передавая в него Value.
Полученное значение приводим к Boolean и возвращаем в качестве результата.
Если метода нет, то:
Находим Target.prototype.
Сверяем его по очереди с Value.[[Prototype]], Value.[[Prototype]].[[Prototype]] и так далее.
Если на очередном этапе проверки, какой-то прототип в цепочке Value равен null, возвращаем false.
Если в цепочке прототипов Value находим искомый Target.prototype, возвращаем true.
Иначе возвращаем false.
Исторически так сложилось, что браузеры имплементировали свойство __proto__, с помощью которого можно получить доступ к прототипу объекта ([[Prototype]]). До ES6 его даже не было в спецификации, но сейчас оно там описано.
И вот с его помощью вполне можно «обмануть» instanceof:
43 символа! В таблице, конечно, результаты получше:
Но и мы только начали.
Ещё раз посмотрев на то, как работает instanceof, мы можем сократить решение на 13 символов.
Поскольку instanceof проверяет прототипы переданного в левой части операнда по цепочке, то мы можем вместо Array.prototype использовать какой-то объект, в цепочке прототипов которого есть этот самый Array.prototype. А именно — инстанс обычного массива.
Вуа-ля:
> ({__proto__:[]}) instanceof Array
true
Получаем решение:
array(Array.prototype,{__proto__:[]})
Уже 30 символов!
Однако, дальше не понятно, куда двигаться. Можно было бы попробовать поиграться с @@hasInstance и как-то модифицировать Array. Но вот такое решение «в лоб» не заработает:
Если продолжать пытаться обманывать instanceof, то можно вместо Array.prototype использовать что-то покороче, чего не будет в цепочке прототипов Array, но что при этом будет массивом. Опять же, решение «в лоб» — взять массив и обнулить у него прототип:
array(x=[],{__proto__:[]},x.__proto__=null)
(И про то, что нельзя определять переменные прямо в момент вызова функции, тоже никто не упоминал. Джаваскрипт! Воруй-убивай!)
Однако, это 36 символов, и не понятно, куда тут короче.
Потому можно пойти другим путём. Как понятно из примеров выше, никто нам не запрещает модифицировать глобальные объекты, передавать третий аргумент, определять переменные прямо во время передачи параметров. А раз можно всё, то почему бы просто не поменять реализацию Array.isArray?
Мы можем не пытаться обмануть instanceof, а действительно передать два значения, где первое не будет массивом, а второе будет. И дополнительно к этому изменить Array.isArray. Например, как-нибудь так:
array(0,[],Array.isArray=x=>!x)
Здесь мы первым аргументом передаём 0, который по мнению instanceof точно не Array. А вторым передаём массив, который точно Array. А вот саму функцию Array.isArray меняем так, чтобы она, получив 0 вернула true, а получив массив вернула false.
И вот у нас есть решение в 24 символа.
Сразу напрашивается ещё одна хитрая оптимизация. Мы можем всунуть переопределение Array.isArray прямо внутрь массива! Ведь содержимое этого массива нам не принципиально.
array(0,[Array.isArray=x=>!x])
Избавились от запятой и получили решение в 23 символа.
В найденном выше решении сложно что-то сократить. 0 и запятую сократить вряд ли получится. Array.isArray тоже никак не сократить. Вот жаль, что Джаваскрипт — это не какая-нибудь Кложа, и в нём нет функции вроде not! Было бы так удобно! Можно было бы передавать не анонимную функцию, а существующую:
array(0,[Array.isArray=not])
А хотя постойте. not и правда нет. Но ведь есть всякие другие глобальные функции. И одна из самых коротких — isNaN! Правда, работает она в нашем случае наоборот:
Но и мы не лыком шиты! Поменяем местами аргументы, делов-то:
array(Array.isArray=isNaN,[])
Вуа-ля! Получили решение в 22 символа. В таблице рекордов, правда, нашлись пользователи с решениями в 14 и 20 символов:
Но один из них говорит, что считерил, да и оба решения не верифицированы, потому возможно, что и первый тоже как-то что-то подхачил. А может быть и нет. Попробуйте сами найти более короткое решение, вдруг у вас получится.
function instance(x, y) {
return x instanceof y && y instanceof x && x !== y;
}
В предыдущей задаче мы уже вспоминали, как работает instanceof, потому знаем, что надо или искать такие объекты, которые есть в цепочках прототипов друг у друга, или как-то подменять @@hasInstance.
Как ни странно, начнём с первого, а не со второго. Потому что заранее определённых глобальных объектов, которые чаще всего используются для проверки на instanceof не то чтобы много.
Как мы знаем, «в Джаваскрипте всё — объект». А раз так, то посмотрим на цепочку прототипов Object с помощью вот такой функции:
function printPrototypeChain(object) {
let proto = Object.getPrototypeOf(object);
let result = `[${object.name}]`;
while (proto) {
result += ` -> ${proto.constructor.name}`;
proto = Object.getPrototypeOf(proto)
}
return result;
}
Функция очень простая. Мы поочерёдно вытаскиваем из цепочки прототипов следующего «родителя» и добавляем его название в строку.
Вот, что она выводит для Object:
> printPrototypeChain(Object)
"[Object] -> Function -> Object"
И ведь действительно, Object — это не только объект, но и функция! Работает она, кстати, довольно интересно:
То есть, она превращает примитивы в их объектные версии. А при передаче обычного объекта возвращает его. Нам это сейчас не принципиально, но грех не проверить:
> let obj = {a: 1}
> obj === Object(obj)
true
Да, это тот же объект.
Энивэй, для задачи нам важнее другое — в цепочке примитивов есть Function, а раз всё в Джаваскрипте объект, то и Function, конечно, тоже:
> printPrototypeChain(Function)
"[Function] -> Function -> Object"
Потому ответ для задачи напрашивается сам собой:
instance(Object,Function)
15 символов. Неплохо! Варианты с @@hasInstance даже нет смысла рассматривать, потому что решение с ним будет куда длиннее.
Однако, в результатах есть те, у кого решение ещё короче:
Рассматривать вариант с решением в три символа не будем, потому что он не верифицирован, а потому скорее всего пользователь, оставивший его, считерил. А вот варианты в 12 символов похожи на правду. Маловероятно, что они смогли как-то избавиться от Object, но вот от Function — вполне. Надо только понять, как.
Из объектов, которые бы были «с изюминкой» в голову приходит только Proxy, однако:
> printPrototypeChain(Proxy)
"[Proxy] -> Function -> Object"
Более того:
> instance(Object,Proxy)
TypeError: Function has non-object prototype 'undefined' in instanceof check
А всё потому, что Proxy, согласно документации, не имеет поля prototype, которое используется при проверке на instanceof:
The Proxy constructor [...] does not have a «prototype» property because Proxy exotic objects do not have a [[Prototype]] internal slot that requires initialization.
Однако, решение Object,Proxy — это ровно 12 символов, как и у ребят в топе. Ещё, если приглядеться, то увидим, что их решения снова были в каких-то старых браузерах, как и в случае с четвёртой задачей.
Что ж, сперва убедимся, что в современном Хроме ничего не работает:
> Object instanceof Proxy
Uncaught TypeError: Function has non-object prototype 'undefined' in instanceof check
Теперь откроем один из тех старых Хромиумов, что использовался в четвёртой задаче, а именно — 65-й. В нём вот так:
Если же откроем 52-й, который у некоторых ребят из топа, то в нём будет так:
Вероятно, когда выкатили Proxy, налажали с прототипами, и получилась обратная ситуация: любой объект — инстанс Proxy. Чтобы узнать точнее, нужно так же пройтись бисектом по репозиторию V8, как в четвёртой задаче. Попробуйте, если интересно.
Во-вторых, проверка instanceof так устроена, что значение, возвращаемое из @@hasInstance само приводится к булеву типу. А потому можем просто вернуть единицу:
У нас уже есть Object и Function, потому в качестве третьего аргумента можно взять функцию, но попробовать сделать так, чтобы она вела себя как объект. Следите за руками:
Чтобы понять, что именно тут происходит, надо разбираться в том, как работает прототипное наследование в JS. Когда мы создаём обычную анонимную функцию fn, её цепочка прототипов выглядит следующим образом:
> const fn = () => {}
> let proto = Object.getPrototypeOf(fn)
> proto === Function.prototype
true
> proto = Object.getPrototypeOf(proto)
> proto === Object.prototype
true
> proto = Object.getPrototypeOf(proto)
> proto === null
true
От первого прототипа у функции есть методы вроде apply и call. От второго, например, __proto__ (да, это свойство берётся из Object.prototype, потому его нельзя удалить у объектов).
Затем, когда устанавливаем fn прототип в виде Object, получаем:
fn -> Object
Но при этом, у Object ведь есть своя цепочка прототипов, а потому:
И вот, такая странная цепочка прототипов и «ломает» instanceof. Посмотрим на это пошагово:
Object instanceof Function && Function instanceof fn && fn instanceof Object
С первой частью мы разобрались ещё в прошлой задаче, потому опускаем её.
Вторая часть:
Function instanceof fn
Здесь первым делом вычисляется fn.prototype. Однако, у fn нет такого поля, ведь мы его туда не записывали. А потому оно возьмётся из прототипа — из Object. Это как раз то место, где происходит основная магия:
> fn.prototype === Object.prototype
true
А дальше по цепочке будут вычисляться прототипы Function, и там будет Object.prototype, и они будут равны и жить долго и счастливо.
Третья часть скорее всего уже очевидна:
fn instanceof Object
Object превратится в Object.prototype, а он есть в цепочке прототипов fn, и потому это тоже true.
Зная о существовании __proto__ мы можем ещё подсократить решение:
Кстати, тоже 43 символа, как и в случае с решением с @@hasInstance. Можем даже сократить его до 40 символов, если заменим дублирование Object на переменную:
А ещё нам не принципиально, что именно возвращает функция в третьем аргументе, потому можем сократить её сигнатуру:
instance2(o=Object,Function,f=x=>0,f.__proto__=o)
38 символов! Куда дальше сжимать не совсем понятно, но вот, поскольку при присваивании возвращается правая часть выражения, то можем избавиться от одной из переменных:
instance2(f=x=>0,Function,f.__proto__=Object)
34 символа.
34 всё ещё не 26, как у ребят в топе:
Значит, надо попробовать поискать другие варианты. Например, обязательно ли нам завязываться на Function? Что, если сделать три таких полуфункции-полуобъекта, которые мы раньше использовали в третьем аргументе?
Тут не понятно, куда дальше сокращать. От __proto__ не избавиться, синтаксис функций не сократить. Правда, можно одну из функций заменить на Object, если использовать f(f):
Наверное, вычисление конструктора нам тоже не поможет.
Может быть использовать Proxy? Конечно, так, как в старом Хроме мы не сможем его использовать. Но ведь мы можем действительно создать какой-то прокси-объект, который будет инстансом оригинального объекта, но при этом не будет равен ему по ссылке. Например:
Вторым аргументом Proxy ждёт объект с определёнными ключами, но нам-то всё равно, что туда попадёт. Потому можно и так:
instance2(o=Object,new Proxy(o,o),new Proxy(o,o))
(o,o) выглядит как анимешный смайлик, но, увы, решение получается в 38 символов. Вроде как мы не можем взять и сделать три прокси, потому что компактно их нагенерировать не получается:
Но, как и в прошлых решениях, можем заиспользовать Function:
instance2(o=Object,Function,new Proxy(o,o))
А это уже 32 символа! Правда, что дальше делать, тоже не ясно. Object уже сократили, Function никуда не деть, вызов Proxy тоже максимально сжат.
Надо искать другие пути. И наверное без Function, ибо он слишком длинный.
Если не понятно, что делать, надо перечитать спецификацию. Раньше мы уже разбирались с тем, как работает instanceof, но опускали некоторые «детали». Однако, эти детали сейчас важны.
Так, если имеем Value instanceof Target, и при этом у Target нет @@hasInstance, то:
Если Target не «callable», то вернётся false.
Если у Target есть [[BoundTargetFunction]], то дальше проверка начнётся с самого начала, но при этом вместо Target будет уже Target.[[BoundTargetFunction]].
Пункт про «вызываемость» Target нас в данном случае не волнует (хотя и объясняет, почему мы в наших первых попытках изменяли прототип функции, а не объекта). А вот что волнует, так это то, что, судя по второму пункту, забинженные объекты тоже могут участвовать в проверке instanceof. И проверка будет выполняться как раз относительно того объекта, который изначально был забинжен. Иными словами:
function proto1(x) {
return x && !("__proto__" in x);
}
В прошлой задаче мы уже касались темы того, что __proto__ нельзя удалить из объекта, потому что он берётся из его прототипа. Потому сразу может быть и не очевидно, как же нам тогда поступить. Как удалить __proto__ из объекта, чтобы его там не было?
Раз оно берётся из прототипа, то может быть просто подменить прототип на null, чтобы его не было?
proto1({__proto__:null})
Вжух! И внезапно работает! 16 символов. Почти самое короткое решение!
Но почему? Ведь __proto__ в объекте есть, просто он равен null. А всё дело в том, что за in отвечает проверка OrdinaryHasProperty, суть которой в том, что она перебирает объекты в цепочке прототипов в поиске того, в котором это поле есть. И ищет до тех пор, пока не наткнётся на прототип равный null. А поскольку __proto__ — это и есть ссылка на прототип, то алгоритм завершается, когда на неё натыкается.
Можно было бы сказать, что спецификация должна предусматривать такой вариант развития событий, и сделать исключение для __proto__, добавив дополнительную проверку. Но __proto__ — костыль, и было бы странно размазывать его по всем частям спеки.
Более легитимный вариант решения, выглядел бы вот так:
proto1(Object.create(null))
Но он длиннее на 3 символа, потому нас не интересует.
В таблице результатов есть пользователь с решением в 8 символов:
И, судя по комментарию, он нашёл в 12-м Эдже что-то, что обладает теми же свойствами, но при этом умещается всего в 8 символов.
К сожалению, проверить это без каких-то суровых костылей не предоставляется возможным, так как политика Майкрософта (как и остальных компаний) в том, что они не предоставляют старые сборки браузеров. Наверное такое решение играет какую-то роль в плане безопасности, но это очень неудобно.
Тем не менее, быстрый поиск среди глобальных объектов в ИЕ 11 показывает, что такой элемент есть:
> for (var key in window) {
> try {
> if (window[key] && !('__proto__' in window[key])) {
> console.log(key);
> }
> } catch(err) {}
> }
external
window.external — это устаревший интерфейс для добавления дополнительных поисковых провайдеров. В ИЕ 11 он сделан как-то криво, и потому у него вообще нет поля __proto__:
> window.external.__proto__
undefined
Вероятнее всего, реализация этого интерфейса в 12-м Эдже была аналогичной.
Увы, использовать Интернет Эксплорер для того, чтобы отправить это решение, у нас не получится, т. к. для работы сайта нужна поддержка промисов, а там её нет. Теоретически, можно что-то где-то подхачить и подпереть, чтобы заставить всё это работать. Ну или использовать Браузерстэк или пиратскую Виндоус 8 нужной версии. Но настолько изощрённые методы пусть останутся самым любознательным. Пока что с уверенностью можно утверждать, что external — решение задачи в 8 символов.
В этой задаче нужно подобрать такой аргумент, тип которого был бы равен undefined, но сам он при этом не был бы равен undefined. Ибо если он будет равен undefined, то вернётся !1, т. е. false. Если же тип не будет равен undefined, то ключ, полученный при вычислении typeof x не будет найден в объекте, вернётся undefined, а из него нельзя достать какое-то свойство.
Начать имеет смысл с того, как же работает typeof. Скорее всего читатель знаком с тем, что значение typeof вычисляется «по таблице». Мол, Джаваскрипт вычисляет тип значения, и результат этой проверки просто соотносит со значением в этой таблице:
Тип
Результат
Undefined
"undefined"
Null
"object"
Boolean
"boolean"
Number
"number"
String
"string"
Symbol
"symbol"
BigInt
"bigint"
Function
"function"
Всё остальное
"object"
Отсюда, например, и странности с тем, что typeof null — это "object".
(Изначально, кстати, никакой таблицы не было, и такое поведение null было просто ошибкой в коде первой версии Джаваскрипта. Аксель Раушмайер писал об этом.)
Однако, для этой таблицы есть одно исключение. Если у объекта есть внутреннее свойство [[IsHTMLDDA]], то он ведёт себя как undefined в некоторых выражениях. В частности, при вычислении typeof. Объекты с таким свойством не определяются самой спецификацией, но могут быть определены производителями браузеров. Описание такого поведения в спеке — это скорее узаконивание некоторых браузерных решений задним числом. Но к счастью, ведёт себя таким образом только один объект в браузере — document.all.
Такое поведение было добавлено производителями браузеров специально, чтобы обойти часто используемую в прошлом проверку на определение того, насколько браузер старый. Матиас Байненс рассказывал об этом подробнее в 2013-м.
Таким образом, единственное решение этой задачи выглядит так:
function symmetric(x, y) {
return x == y && y != x;
}
Задача, в которой явно нужно перечитать алгоритм сравнения двух значений. Правда, в нём вроде бы нет каких-то логических багов, и приведение типов от перестановки мест не меняется. То есть, вот эти две операции дадут одинаковое значение:
При приведении объекта к примитиву, первым делом проверяется наличие у него метода @@toPrimitive. Если он есть, то используется возвращаемое им значение. А раз так, то можем в качестве решения использовать объект и число, причём объект будет возвращать разные значения при первом и втором вызове.
Однако, Symbol.toPritimive слишком длинный и всё рушит. А потому стоит пойти дальше по алгоритму приведения объекта к примитиву, и взять вместо @@toPrimitive свойство valueOf. Для нас оно будет работать один-в-один так же:
symmetric({valueOf:()=>window.x=-~window.x},1)
И вот, уже 35 символов. Правда, в топе вон у всех 20:
Значит надо искать, что ещё сократить. Очевидный кандидат на эту должность — window. Но мы не можем просто убрать его:
> symmetric({valueOf:_=>x=-~x},1)
ReferenceError: x is not defined
Такое решение не работает, потому что x не объявлен внутри функции. Но нам ведь ничего не мешает объявить x!
> symmetric({valueOf:_=>x=-~x},x=1)
false
Теперь всё ломает хак с -~, но нам это даже на руку, потому что вместо него можно использовать обычный постфиксный инкремент:
(Название отсылает к уроборосу — змею, кусающему себя за хвост.)
Маловероятно, что возможна такая ситуация, когда объект будет содержаться внутри самого себя. Единственное, что приходит на ум в таком случае, — это циклические ссылки, но они тут никак не подходят, ибо in проверяет наличие ключа в объекте.
И вот поскольку in нужно передать имя ключа, скорее всего тут всё дело в том, как приводятся типы при выполнении этой операции. В спецификации про это сказано, что левый операнд сперва приводится к строке, а только потом используется в вычислении. (На деле там всё сложнее, но даже этого знания нам уже достаточно.)
Получается, что нам нужно найти такой объект, который при приведении к строке превратится в своё же свойство. В третьей задаче мы уже затрагивали приведение объектов к строке, и заметили тогда, что от обычных объектов в этом случае пользы не очень много, они просто превращаются в "[object Object]". А вот массив превращается в строку, в которой перечисляются все его ключи.
Раскручивая эту цепочку дальше, получаем, что нам нужен какой-то такой массив, который бы при приведении к строке превратился в свойство, которое бы нашлось в этом массиве. Так, у массивов есть свойство length, а потому:
ouroborobj(['length'])
А это уже решение в 10 символов.
Но если посмотрим на ключи этого массива, то увидим, что у него есть ещё и свойство 0, что вполне себе ожидаемо:
> Reflect.ownKeys(['length'])
["0", "length"]
А раз так, более короткое решение напрашивается само собой:
Мы уже ни раз встречались с valueOf в предыдущих задачах, потому знаем, что можем без проблем его подменить на нужный нам метод. Однако, если сделаем это в лоб, то ничего не получим:
> truth({ valueOf: () => true })
false
А всё потому, что вторая часть выражения не использует valueOf. Согласно спеке, при логическом отрицании используется операция приведения к булеву типу, которая в данном случае работает привычным нам образом — получила на вход объект, выдала true.
Получается, что нужно передать какое-то такое значение в качестве параметра, которое при приведении к булеву типу превратится в false, но у которого при этом будет метод valueOf. Например, пустую строку!
> Boolean('')
false
Пробуем:
> truth(x='',x.valueOf=_=>true)
''
Ничего не работает. Но тут дело не в том, что мы неправильно выбрали значение, а в том, что нельзя просто взять и записать в примитив какой-то метод.
В Джаваскрипте мы можем получать какие-то свойства примитивов или вызывать их методы, как делаем это с объектами. Но лишь потому, что в этот момент они на летупревращаются в объекты. Работает это так:
Мы решили вызывать метод примитива или добавить его.
Джаваскрипт создаёт новый объект на основе этого примитива (для строки используется конструктор String, для булева типа Boolean и так далее).
Вызывает его метод (или добавляет, если мы добавляли).
Возвращает нам результат (при использовании use strict может ещё и ошибку выкинуть).
Примитив при этом никак не меняется, и новый созданный объект тоже никуда не возвращается, а просто удаляется сборщиком мусора, когда приходит время.
Потому, когда мы пытаемся записать valueOf в примитив — строку — у нас ничего не получается. Метод просто записывается в промежуточный объект и теряется, не доходя до нас.
Но поскольку при вызове метода примитив на лету конвертируется в объект, то это значит, что мы можем добавить метод в прототип этого объекта. Например, так:
> truth('',String.prototype.valueOf=_=>true)
true
35 символов и решение готово!
Можем подсократить и получить доступ к прототипу через примитив:
truth('',''.__proto__.valueOf=_=>true)
Уже 31. Очевидно, что можно сократить ещё и true:
truth('',''.__proto__.valueOf=_=>1)
28. Чтобы получить 27, как у ребят в топе, можем вместо строки использовать число. Нам ведь всё равно, какой будет примитив. Лишь бы он был отрицателен при булевой проверке, а потому:
function wat(x) {
return x('hello') == 'world:)' && !x;
}
В прошлой задаче мы уже обсудили, что унарное отрицание работает в лоб, а потому x должен быть чем-то, что приводится к false. Вариантов не много:
Undefined
Null
False
NaN
±0
Пустая строка
0 (BigInt)
Что-то из этого должно быть ещё и функцией, ведь x вызывается.
Вроде как нельзя просто взять примитив и сделать из него функцию. «Функциональность» — это не какое-то свойство, которое можно «добавить» объекту, как в случае с методом из предыдущей задачи. Объект должен быть функцией сам по себе.
Первым делом думается: «А что, если мы при вызове функции как-то обнулим x?». Вроде такого:
В теории можно было бы не использовать стрелочную функцию:
> wat(function() { x = false; return 'world:)'; })
false
Но не работает оно по той же причине, что и раньше — x берётся из лексического окружения создаваемой функции, а не из «внутренностей» wat.
Потому попытки манипулировать ссылками на функции кажутся тщетными.
В то же время, нельзя просто взять примитив и использовать его как функцию. И объекты, в которые оборачиваются эти примитивы, тоже никак не подходят, потому что во второй части выражения они не вызываются. Иначе бы мог подойти Boolean, так как при вызове он возвращает false.
Получается, что ни один из встроенных примитивов нам ничем не помогает. Но может быть есть что-то, что приравнивается к ним?
И тут, внезапно, вспоминается document.all, который в некоторых контекстах превращается в undefined. Его отрицание как раз даёт true:
> !document.all
true
При этом оказывается, что этот объект не только псевдо-массив, но и функция, которая возвращает DOM-элемент по его индексу или имени!
Последнее как раз нам подходит.
Если верить спеке, то «именем» элемента может быть или то, что указано у него в атрибуте id, или то, что указано у него в атрибуте name. Но последнее справедливо только для некоторого набора элементов.
Для простоты пока обдумаем вариант с id. Проверим, что он вообще работает:
Переписывание с использованием name нам не особо поможет. Список элементов, которые могут использовать этот атрибут, ограничен, и даже если взять самый короткий из них — a — всё равно получим решение в 110 символов:
Тут довольно хитро, потому что на первый взгляд кажется, что теперь первым аргументом должно стать значение a, или по крайней мере [a]. Но, несмотря на деструктуризацию, тут всё ещё присваивание, а результат присваивания — значение в его правой части. Оно (document.all) и становится первым аргументом функции.
Наконец, помня алгоритм приведения к примитиву, что разбирали в третьей задаче, можем заменить toString на valueOf:
Казалось бы, должно работать (1 < 2, 3 == 3, 5 > 4), но нет. Если добавить логирование и чуть подебажить выражение, то окажется, что для пары x == x не вызывается valueOf!
Можно начать грешить на браузеры и их оптимизации, но на самом деле всё по спецификации. Нестрогое сравнение для значений с одинаковыми типами сводится к строгому сравнению. А поскольку мы сравниваются у нас объекты, то никакой valueOf не вызывается. Объекты ведь сравниваются по ссылке.
В то же время при вычислении результата отношений двух значений, они в первую очередь приводятся к примитивам. И тут-то указанный нами valueOf играет яркими красками.
Получается, что передаваемый массив можно сократить:
total({valueOf:_=>a.pop()},a=[4,5,2,1])
32 символа и решение готово.
Вероятно, чтобы сократить количество символов, нам нужно избавиться от массива и как-то вычислять значения.
Более того, получается, что мы можем вернуть три числа, идущих друг за другом по порядку, а затем четвёртое меньше, чем третье (а то и меньше, чем все остальные). Раз нам нужно «обрубить» ряд чисел после третьего, то можем воспользоваться остатком от деления на 3:
total({valueOf:_=>n++%3},n=0)
Решение в 22 символа найдено.
Как вариант, можно считерить и сделать так:
total({valueOf:Math.random})
С первого раза true может не выдать, но рано или поздно точно получится. 21 символ.
Но интереснее пойти другим путём. Поскольку нам нужно сделать так, чтобы сперва числа нарастали, а потом в определённый момент следующее число стало меньше предыдущего, то можно попробовать воспользоваться переполнением.
В Джаваскрипте нет «полноценного» переполнения при не-побитовых операциях. Увеличивая число сложением, умножением или возведением в степень, мы рано или поздно упрёмся в бесконечность.
Однако, при переполнении во время побитовых операций, самое большое число может вдруг стать самым маленьким, и наоборот. Потому что в таком случае Джаваскрипт интерпретирует значения как целочисленные. Иными словами, Integer (со знаком и без), а не Double.
Получается, что мы можем соорудить примерно такое решение:
total({valueOf:_=>n<<=8},n=2)
Сперва n равен 2, затем, после сдвига на 8 бит влево, — 512 (первое значение), потом 131 072 (второе), после — 33 554 432 (третье), и, наконец, наступает переполнение и мы получаем 0.
Однако, это всё ещё решение в 22 символа. Чтобы получить 21, нужно как-то перенести инициализацию n внутрь объекта, но при этом так, чтобы она не происходила при каждом вызове valueOf.
Кажется, что единственный из возможных вариантов — это присвоить n функцию, которую мы передаём в качестве valueOf:
> total({valueOf:n=_=>n<<=8})
false
Только так оно не работает, конечно.
Во время приведения типов операндов n сперва превращается в текстовое представление функции, которое затем превращается в NaN, которое уж после этого превращается в 0. И получается, что мы пытаемся сдвинуть биты у нуля, а у него и двигать-то нечего.
Однако, можно вывернуть выражение наизнанку, и вместо того, чтобы сдвигать биты n, двигать их у какого-то иного числа, но на n. А результат записывать в n. Иными словами, вот так:
> total({valueOf:n=_=>n=1<<n})
false
Остаётся только подобрать подходящее число, в котором будем двигать биты. Например, двойку:
После этого объявляется функция, которая принимает два аргумента. Сразу же первый аргумент становится ключом в объекте vault, а второй — значением.
Затем этот объект зачем-то замораживается и превращается в строку.
И вот наступает самое интересное. Во-первых, почему-то не работает eval этой строки. Видимо, нам нужно записать какой-то такой ключ или какое-то такое значение, которые делают JSON невалидным Джаваскриптом.
Во-вторых, после того, как строка будет превращена обратно в объект с помощью JSON.parse, переданное нами значение должно измениться.
Начнём с первого — неудачного превращения вроде бы валидной JSON-строки в JS.
Если читатель следит за обновлениями браузеров и движков, то может вспомнить, что когда-то в блоге V8 писали о том, что JSON не так давно стал полным подмножеством ECMAScript. А до этого не был им, поскольку, в отличие от Джаваскрипта, строки в JSON могли содержать символы U+2028 LINE SEPARATOR и U+2029 PARAGRAPH SEPARATOR.
И действительно. Если открыть 65-й Хромиум, то:
> const LS = " ";
Uncaught SyntaxError: Invalid or unexpected token
В строке между кавычек используется символ U+2028, а потому всё падает. Получается, что это ещё одна задача, которую нужно решать в старом браузере.
Казалось бы, всё просто — надо взять и передать ключ и значение такими, чтобы в одном из них был запрещённый символ. Однако:
Добавленное значение не появляется в объекте. И дело тут не в том, что мы добавили «запретный символ». Просто JSON.stringify сериализует только перечисляемые ключи. А поскольку при добавлении свойства в дескрипторе не указывается enumerable: true, оно добавляется как неперечисляемое.
Теперь по крайней мере понятно, зачем в vault добавляются ключ-значение сгенерированные случайным образом. Мы не можем определить новое свойство, но можем перезаписать существующее. Осталось только найти способ это сделать.
Когда сервис тестирует введённые нами данные, он делает следующее:
Берёт строку с заданием.
Добавляет к ней '; return fn', где fn — тестируемая функция.
Вызывает созданную функцию, получая в виде результата ту функцию, которую нужно протестировать (не совсем, но не принципиально).
Вызывает тестируемую функцию с указанными нами аргументами.
Таким образом, у нас нет доступа к тем переменным, которые объявлены вокруг тестируемой функции. Мы не можем напрямую обратиться к vault. И мы даже не можем перезаписать crypto.getRandomValues, чтобы как-то повлиять на те значения, которые попадают в объект.
Потому мы можем влиять только на аргументы и на те глобальные функции, что используются внутри json.
Поскольку внутри функции объект конвертируется в строку, то можно определить ему метод toJSON, который будет отвечать за эту конвертацию. Логика такая:
toJSONполучает в качестве контекста сериализуемый объект.
Мы достаём из этого объекта неизвестный там ключ.
Присваиваем ему в качестве значения строку, состоящую из одного из запрещённых символов.
JSON.stringify превращает этот объект в строку.
При запуске eval всё падает.
После запуска JSON.parse получаем наш объект.
А дальше искомый ключ находится в объекте, но значение уже иное, ибо мы его перезаписали.
Единственная проблема с toJSON — мы не можем для его определения использовать стрелочную функцию. Потому что нам нужно получить доступ к контексту. Как-то так:
Смущает, правда, что мы строку руками выстраиваем. Это дополнительные накладки в виде кавычек и интерполяции строк. А вот если перезаписать Object.freeze, то можно этого избежать:
Вероятно, должен быть какой-то способ достать ключ из объекта без Object.keys. Но он как-то в голову не приходит. А вот что приходит, так это то, что скорее всего можно каким-то образом заиспользовать напрямую запрещённый символ, а не его кодовое представление. Но если мы сделаем так:
> json(Object.freeze=v=>({[Object.keys(v)[0]]:" "}))
SyntaxError: Invalid or unexpected token
(В кавычках в качестве значения — запрещённый символ.)
Увы. Однако, речь ведь только о кавычках, но никто не говорил, что для бэктиков запрет тоже работает :-)
var eval = window.eval;
function evil1(x) {
return eval(x+'(x)') && !eval(x)(x);
}
Странная задача, решение к которой часто подбирают случайным образом.
Судя по тому, что eval изначально выносится в переменную, мы не сможем его перезаписать. А потому нужно передать какой-то x, который подойдёт под условия:
Его текстовое представление плюс '(x)' должно превратиться в валидный JS-объект. Не конкретно в Object, а в любой, но обязательно положительный.
Этот x можно вызвать, да так, что при вызове он вернёт отрицательное значение.
Если можно вызвать, то вероятно это должна быть функция. Попробуем:
> evil1(function a(){})
true
Всё. Работает довольно просто. Функции при конвертировании в строку превращаются просто в своё текстовое представление. Потому первый eval получает такое:
'function a(){}(x)'
Судя по всему, это вполне валидное выражение. Работает примерно так:
Определяется функция.
Вычисляется x.
Результат п. 2 становится значением выражения.
А поскольку x — это и есть функция, а она положительна, то переходим ко второй части выражения.
!eval(function a(){})(function a(){})
evalтак работает, что если ему передать не строку, а значение, то он просто его вернёт. Потому при вызове eval возвращается наша функция.
Дальше она вызывается с аргументом в виде самой себя и возвращает undefined. Результат инвертируется и получается true. Такие дела.
Но это решение в 14 символов. Можно сделать короче, если заиспользовать стрелочную функцию. Главное, чтобы она возвращала отрицательное значение, чтобы вторая часть выражения успешно его инвертировала.
В голову сходу приходит вот такое простое решение:
evil1(_=>0)
Вторую часть выражения нет смысла объяснять, а вот первая чуть забавная, потому что eval получает такое:
'_=>0(x)'
Если такую функцию вызвать, то конечно будет ошибка, что 0 is not a function. Но при этом определить такую функцию без проблем можно.
var eval = window.eval;
function evil2(x) {
return eval('('+x+')(x)') && !eval(x)(x);
}
Задача, похожая на предыдущую, с той лишь разницей, что тут в первом случае функция тоже вызывается.
Если использовать тот же аргумент, что и в прошлый раз, то получим ноль:
> evil2(_=>0)
0
Потому что в первой части выражения получится так:
'(_=>0)(x)'
Определение и вызов функции с аргументом в виде какого-то x. Возвращается, конечно, ноль.
Получается, что в первом случае нам нужно вернуть что-то положительное, а во втором отрицательное. Можно пойти в лоб:
evil2(x=>y--,y=1)
10 символов, готово.
Однако, у ребят в таблице есть решения и по восемь символов. Вероятно имеет смысл присмотреться к eval, которые используются в условии.
Как мы уже разбирали в предыдущей задаче, если в eval передать не строку, то он просто вернёт аргумент. Получается, что первый eval исполняет функцию в локальном скоупе. Этой функции доступны все те значения, что доступны внутри evil2. В то же время второй eval возвращает ту функцию, что была передана изначально, и только после этого она исполняется.
Иными словами, мы можем оформить передаваемую функцию таким образом, что в одном случае она будет принимать параметр «извне», а в другом — использовать тот, что мы предопределили. Например, так:
evil2(_=>x,x=0)
8 символов. Первый eval выполняет функцию в контексте evil2, и там x — это переданная нами функция. И потому возвращаемый результат положителен. Второй же eval возвращает переданную нами функцию, которая берёт значение x из того скоупа, в котором была определена. А мы позаботились заранее присвоить x отрицательное значение.
var eval = window.eval;
function evil3(parameter) {
return eval('('+parameter+')(parameter)') &&
!eval(parameter)(parameter);
}
Очень похожая на предыдущую задача, однако, теперь вместо x используется parameter. А потому то же самое решение будет куда длиннее:
evil3(_=>parameter,parameter=0)
Аж 24 символа.
Но можно использовать альтернативное решение из прошлой задачи:
evil3(_=>x--,x=1)
10 символов. Уже достойно. Осталось придумать, как сократить ещё символ, чтобы попасть в таблицу к крутым ребятам.
Можно воспользоваться трюком с побитовым отрицанием из пятой задачи:
evil3(x=_=>x=~x)
Разберём, как это работает.
В первый eval попадает такая строка:
'(_=>x=~x)(parameter)'
Поскольку x мы определили при передаче параметра в функцию, никаких ошибок о неопределённости переменной мы не получаем. Результат же — функция, к которой применили побитовое отрицание. При приведении типов функция сперва превращается в NaN, который затем превращается в ноль, а уж к нему потому и применяется побитовое отрицание. В итоге — −1. Несмотря на то, что число отрицательное, с логической точки зрения оно положительно.
А второй eval просто выполняет эту функцию ещё раз. На этот раз −1 при побитовом «не» превращается в 0.
Однако, операции над числами определены таким образом, что знаковый бит иногда может «подвиснуть» и на нуле. Например, очевидно, что если мы умножаем отрицательное число на положительное, то должно получиться отрицательное. То есть, с единицой в знаковом бите.
Но что, если мы умножаем −1 на 0? В таком случае у нас получится такое:
По значению вроде бы ноль, но отрицательный. Получается −0.
Наличие такого значения немного смущает, но на деле от него только выигрывают. Не нужно придумывать костыли на каждом шагу, которые бы приравнивали −0 к 0.
(Отрицательный ноль существует и за пределами программирования.)
Несмотря на наличие двух разных нулей, их равенство сводится к истине, потому что с точки зрения нормальной человеческой повседневной логики, всё же, −1 * 0 = 0, а не какой-то там особенный −0.
Тем не менее, при делении чего-то на эти нули их знак сохраняется, потому 1/0 = ∞, но 1/−0 = −∞.
function random1(x) {
return Math.random() in x;
}
Со всем тем багажом хаков, что мы набрали по пути, не сложно сходу придумать решение:
random1({1:2},Math.random=_=>1)
22 символа.
А если вспомнить, что in работает ещё и для массивов, проверяя в них наличие индекса, то:
random1([1],Math.random=_=>0)
20 символов.
Наконец, можно совместить одно с другим, и, поскольку нам не принципиально, каким будет значение внутри массива, то засунуть туда переопределение функции, как делали в одном из решений шестой задачи:
var rand = Math.random();
function random2(x) {
return rand in x;
}
Тут уже не получится перезаписать Math.random, потому что он вызывается за пределами функции.
Но мы можем использовать прокси в качестве значения. Один из методов, который можно определить у прокси — has — как раз нужен для того, чтобы перехватывать работу оператора in.
Вжух:
random2(new Proxy({},{has:_=>1}))
24 символа.
(Кстати, MDN говорит, что has должен возвращать булево значение, но на деле то значение, что он вернёт, по спеке должно автоматически приводиться к булеву типу, потому мы тут и возвращаем единицу.)
var key = crypto.getRandomValues(new Uint32Array(4));
function random3(x) {
var d = 0;
for (var i=0; i<key.length; i++) {
d |= key[i] ^ x[i];
}
return d === 0;
}
Эта задача куда сложнее предыдущих. Тут тоже случайные числа уже предопределены, но не одно, а целых четыре. При этом от нас, якобы, требуется подобрать четыре других числа, которые бы после операций побитового сложения и вычитания дали ноль.
У нас нет способа повлиять на то, как определяется массив key. И у нас нет способа определить значения, которые в нём лежат. А значит и подобрать значения для x мы тоже не можем.
Однако, мы можем сделать так, чтобы цикл вообще не выполнился. Там ведь проверяется значение length у key. И если мы запишем туда 0, то цикл не запустится.
Правда, напрямую в прототип мы записать не сможем:
Поскольку нужно сравнить число (i) с длиной массива и получить отрицательный результат, то можем сравнивать не число с числом, а число с undefined, например. Таким образом, можно не доопределять length, а просто удалить его:
var rand = Math.random();
function random4(x) {
return rand === x;
}
Если вы очень упорный, то Math.random() — решение. С какого-то раза точно сработает.
А если серьёзно, то кажется, что простого решения нет. Так или иначе смысл в том, чтобы как-то сломать или процедуру проверки, или «псевдо-случайность» в Math.random.
Как сломать процедуру проверки — это уж на любителя. Скажу лишь только, что «Local Overrides» сильно упрощают задачу.
А вот псевдослучайность в Хроме можно отключить. Достаточно запустить его с флагом --random-seed. Например: --js-flags=--random-seed=1157259157. После этого для каждого URL будет всегда генерироваться одна и та же последовательность значений, получаемых из вызовов Math.random.
Дальше дело техники — открыть вручную URL, который ReturnTrue запускает в iframe, вызвать Math.random, скопировать значение и ввести его в поле с ответом. В зависимости от сида можно получить решение даже в один символ.
Можно ли считать это решением? Открытый вопрос. Скорее это всё же читерство.
Решением можно считать реализацию алгоритма, который бы высчитывал по нескольким вызовам Math.random значение следующего такого вызова и подставлял его в аргумент функции.
Например, вот отличная статья, рассказывающая о том, как подобное реализовать для Фаерфокса, но на Пайтоне.
А вот в этой рассказывают про генератор псевдослучайных чисел в старом Хроме.
