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
, не смотря на то, что этоProxy
x[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 абсолютно разными подходами к решению, зачастую не самыми очевидными. Пробуйте, экспериментируйте, ищите решения, даже если кажется, что ничего нельзя придумать.