return true
February 28, 2021

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] - 51
  • new Proxy([],{get:(i,k)=>k}) - 28
  • […Array(20).keys()] - 21
  • Object.keys(9**-9+'') - 21
  • Object.keys(9e19+'') - 20
  • Object.keys(Date()) - 19
  • Object.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()] - 39
  • new Proxy([],{get:(t,k)=>t[k]??k}) - 34 🏆

Вот мы и рассмотрели 3 варианта задачи countOnMe c абсолютно разными подходами к решению, зачастую не самыми очевидными. Пробуйте, экспериментируйте, ищите решения, даже если кажется, что ничего нельзя придумать.