return true: countOnMe
Привет! Сегодня разбираемся с задачкой countOnMe из второго сезона RT.
⚠️ Статья наполнена спойлерами. Если вы хотите сами решить задачу, то вернитесь к статье только после того как решите ее сами или если у вас закончится терпение 😉
countOnMe1
function countOnMe(x) {
if (!(x instanceof Array))
throw 'x must be an array.';
for (var i = 0; i < 20; i++) {
if (x[i] != i) {
throw 'x must contain the numbers 0-19 in order';
}
}
return true;
}Задача в том, чтобы передать в функцию массив, состоящий из цифр от 0 до 19.
Конечно, можно просто передать [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19], но это было бы слишком просто и очевидность этого решения намекает на то, что есть решение короче 51 байта.
Наша задача сделать так, чтобы условие x[i] != i никогда не выполнялось.
Можно попробовать создать Proxy, который будет перехватывать все попытки обратиться к какому-либо свойству и возвращать обратно имя свойства:
const x = new Proxy([], {
get: (target, key) => key
});
x[1] // '1'
x[100] // '100'
x['hi'] // 'hi'Таким образом, не важно сколько у нас элементов в массиве, на все попытки обратиться к элементу по индексу, мы будем возвращать этот индекс обратно. В итоге, используя new Proxy([],{get:(t,k)=>k}), мы получаем true за 28 байт ✅
Мы считаем именно байты, а не символы. Так например, один символ эмодзи будет занимать несколько байт (от 2 и более)
Видим в лидерборде, что лучшее решение - это 18 байт, поэтому думаем как можно сократить решение.
Еще один вариант решения основан на том, что мы можем сгенерировать массив указанной длины: Array(20)
Но это пустой массив, поэтому он не пройдет все проверки. Тем не менее, из этого массива мы можем получить ключи:
const keys = [...Array(20).keys()]; keys // [0,1,2,...,17,18,19]
Используем spread-оператор потому что Array#keys() возвращает не массив, а итерируемый объект.
Получаем true за 21 байт ✅, но это все еще не 18, поэтому думаем дальше.
Как еще можно получить массив из 20 элементов?
Можно применить подход с получением ключей, но будем получать не ключи массива, а ключи строки:
const keys = Object.keys('это строка в 20 байт');
keys // [0,1,2,...,17,18,19]Теперь нам осталось понять как сгенерировать строку длиной минимум в 20 байт (можно и больше, просто в задаче проверяются только первые 20). Вот варианты того, как это можно сделать:
Object.keys(9**-9+'') // решение в 21 байт ✅ Object.keys(9e19+'') // решение в 20 байт ✅ Object.keys(Date()) // решение в 19 байт ✅
Но 19 байт это все еще не 18.
Давайте вспомним про преобразование типов, которое мы применили для решения задачи length и используем его снова:
Set+1 // 'function Set() { [native code] }'
Object.keys(Set+1) // [0,1,2,3,...,29,30,31,32]Это и есть решение в 18 байт ✅
Решения
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]- 51new Proxy([],{get:(i,k)=>k})- 28[…Array(20).keys()]- 21Object.keys(9**-9+'')- 21Object.keys(9e19+'')- 20Object.keys(Date())- 19Object.keys(Set+1)- 18 🏆
countOnMe2
Рассмотрим еще один вариант этого задания:
function countOnMe2(x) {
if (!(x instanceof Array))
throw 'x must be an array.';
for (var i = 0; i < 1000; i++) {
if (x[i] !== i) {
throw 'x must contain the numbers 0-999 in order';
}
}
return true;
}Смысл тот же, но теперь нам нужен массив не из 20 элементов, а из 1000. Плюс ко всему, здесь используется строгое сравнение x[i] !== i, поэтому массив из строк нам уже не подойдет. Можем попробовать вариант с Proxy: new Proxy([],{get:(t,k)=>+k}). Получаем true в 29 байт ✅
Заметьте, что здесь мы возвращаем не просто k, а +k, чтобы привести строковый ключ к числу, чтобы сработало строгое сравнение. Видим, что лучшее решение состоит из 22 байт, поэтому думаем дальше.
Можем попробовать вернуться к решению с ключами массива: [...Array(1000).keys()] // [0,1,2,3,...,998,999]. Это true за 23 байта ✅
Нужно "выиграть" еще один байт. Идея в том, что 1000 можно записать как 1e3: 1000 === 1e3 // true
Заменяем 1000 на 1e3: [...Array(1e3).keys()] и получаем true за 22 байта ✅
Решения
new Proxy([],{get:(i,k)=>+k})- 29[...Array(1000).keys()]- 23[...Array(1e3).keys()]- 22 🏆
countOnMe3
И еще одна вариация этой задачи выглядит так:
function countOnMe3(x) {
var arrayElements = 1000;
if (!(x instanceof Array))
throw 'x must be an Array';
for (var i = 0; i < arrayElements; i++)
if (x[i] != i)
throw 'x must contain the numbers 0-999 in order';
for (element of x)
if (element != --arrayElements)
throw 'x must contain the numbers 999-0 in order';
if (x.length !== 0)
throw 'x must be empty';
return true;
}Судя по коду, нам нужно передать такой массив, который одновременно содержит числа от 0 до 999, от 999 до 0 и размер этого массива должен равняться нулю. Это три противоречащих друг-другу условия и это означает, что нам нужно придумать что-то на основе особенностей языка.
Обратим внимание на то, что второй проход по массиву происходит при помощи for-of, который использует итераторы, а значит нам нужен массив, в котором будут содержаться элементы от 0 до 999, а Symbol.iterator этого массива должен генерировать обратную последовательность. Таким образом мы покрываем все условия кроме последнего, а значит нужно придумать что-то еще.
Первое решение состоит в том, чтобы передать пустой массив, прототипом которого является массив с числами от 0 до 999:
const a = []; a.__proto__=[...Array(1e3).keys()] a // [ length: 0, __proto__: [0,1,2,3,...,998,999] ]
Таким образом элементы от 0 до 999 будут доступны через прототип, а вот Symbol.iterator будет выполняться в контексте пустого массива, а значит ни одной итерации for-of не будет выполнено. Ну и length пустого массив будет равен нулю. Итого, при помощи a=[],a.__proto__=[...Array(1e3).keys()] получает true за 39 байт ✅
В лидерборде мы видим, что лучшее решение занимает 34 байта, а значит нам нужно придумать что-то еще.
Я предлагаю пойти по другому пути и использовать уже знакомый нам подход с Proxy, но возвращать мы будем не просто переданный ключ, а ключ или существующее свойство. Посмотрите на код:
const x = new Proxy([], {
get: (target, key) => target[key] ?? key
});
x[0] // '0'
x[100] // '100'
x[Symbol.iterator] // function () {...}
x.length // 0Обратите внимание на конструкцию target[key] ?? key, она использует nullish coalescing operator который означает, что левая часть будет использована только если она не null и не undefined, иначе будет использована правая часть. Посмотрите на примеры выше чтобы понять как это может нам пригодиться. Если нужного нам ключа нет в массиве, то мы возвращаем сам ключ, а если есть, то возвращаем значение по этому ключу. Таким образом мы удовлетворим все проверки в задачи:
x instanceof Arrayбудетtrue, не смотря на то, что этоProxyx[i] != iвнутриfor (var i = 0; i < arrayElements; i++)никогда не сработает, потому что прокси всегда будет возвращать запрошенный ключfor (element of x)не выполнит ни одной итерации, потому чтоSymbol.iteratorвыполнится в контексте пустого массиваx.lengthбудет ноль, т.к. массив пуст
Итого, при помощи new Proxy([],{get:(t,k)=>t[k]??k}) получаем true за 34 байта ✅
Решения
a=[],a.__proto__=[...Array(1e3).keys()]- 39new Proxy([],{get:(t,k)=>t[k]??k})- 34 🏆
Вот мы и рассмотрели 3 варианта задачи countOnMe c абсолютно разными подходами к решению, зачастую не самыми очевидными. Пробуйте, экспериментируйте, ищите решения, даже если кажется, что ничего нельзя придумать.