Сергей Мелюков

codewars: square every digit

2021-03-02T23:22:36.339Z

⚠️ Статья наполнена спойлерами. Если вы хотите сами решить задачу, то вернитесь к статье только после того как решите ее сами или если у вас закончится терпение 😉

Недавно я откапал свой логин/пароль к codewars и наткнулся на задачку с таким описанием:

You are asked to square every digit of a number and concatenate them.
For example, if we run 9119 through the function, 811181 will come out, because 9^2 is 81 and 1^2 is 1.
Note: The function accepts an integer and returns an integer

Смысл в том, что на вход функции поступает число, каждый разряд которого нужно возвести в квадрат. Полученные квадраты разрядов нужно объединить и вернуть из функции.

На входе и на выходе должны быть именно числа (typeof x === 'number'). Примеры:

fn(3212) // 9414
fn(9119) //811181

Я решил задачку по-своему - так, как считал оптимальным, затем посмотрел как решили другие, сделал определенные выводы, которые показались мне интересными. Затем задал вопрос подписчикам моего telegram-канала - как они решили бы эту задачу. Собрал варианты, которые они предложили, сгруппировал их, и в этой статье хочу сравнить их. Все решения будем сравнивать относительно моего (его приведу ближе к концу).

Замеры я производил на основе 1,000,000 заранее сгенерированных чисел от 0 до 1,000,000

Итак. Конечно же, первое, что приходит в голову - это решение при помощи строк. Оно просто и короткое:

превратили число в строку
смапили символы-разряды на их квадраты
соединили

Но здесь не все так однозначно и решение на строках может быть разным.

Рассмотрим пример:

const fn = val => +[...'' + val].map(n => n ** 2).join('');

Это простое решение не эффективно с точки зрения утилизации ресурсов.

Здесь мы делаем много лишних действий:

преобразуем число в строку
преобразуем строку в массив
каждый символ строки преобразуем в число (n ** 2)
преобразуем получившийся массив в строку
преобразуем получившуюся строку в число

Этот вариант в 6.9 медленнее эталона 📉

Из этого делаем вывод, что преобразования - это плохо для производительности и нам нужно постараться свести их к минимуму.

Попробуем еще одно решение на строках, но с меньшим количеством преобразований:

function fn(val) {
  let res = '';
  val = val + '';
  
  for (let i = 0; i < val.length; i++) {
    res += val[i] ** 2;
  }
  
  return +res;
}

преобразуем число в строку (val + '')
преобразуем каждый символ в число и обратно (res += val[i] ** 2)
преобразуем строку в число (+res)

Этот вариант уже в 3.6 раза медленнее эталона 📉

Роман Дворнов предложил интересное решение

function fn(val) {
  return +String(val).replace(/./g, m => m * m);
}

Здесь мы используем замену по регулярному выражению, чтобы заменить все числа на их квадраты. Не смотря на небольшое количество преобразований, оно в 10.9 раз медленнее эталона из-за регулярных выражений 📉

Так же Роман предложил развитие идеи:

const xs = ["0", "1", "4", "9", "16", "25", "36", "49", "64", "81"];

function fn(val) {
  return +String(val).replace(/[2-9]/g, m => xs[m]);
}

Суть в том, что мы заранее высчитываем квадраты чисел от 0 до 9 и записываем их в массив в виде строк (это важно!).

В самой функции мы заменяем числа от 2 до 9 на их предрассчитанные значения из массива. Единицы и нули не имеет смысла заменять, т.к. они останутся без изменений в какую бы степень мы их не возвели.

Предрассчитанные квадраты чисел хранятся в массиве в виде строк чтобы при замене не было приведения числа к строке.

Этот вариант в 9.8 раз медленнеее эталона 📉

Не смотря на низкую производительность, мы вернемся к этому варианту позже.

Очевидно, что преобразования на строках - это не лучшее решение с точки зрения производительности.

Если важна скорость и что-то можно сделать при помощи математики, то лучше деать это при помощи математики.

Возьмем для примера число 3212, оно должно превратиться в 9414.

Как можно проделать с ним все нужные нам операции без пробразований?

Число можно разделить на разряды:

9 - разряд тысяч
4 - разряд сотен
1 - разряд десятков
4 - разряд единиц

Как собрать число имея каждый разряд по отдельности?

Необходимо найти сумму произведений каждого разряда на значение этого разряда. Проще говоря:

9414 = (4 * 1) + (1 * 10) + (4 * 100) + (9 * 1000)

Как получить то же самое из числа 3212?

9414 = (2^2 * 1) + (1^2 * 10) + (2^2 * 100) + (3^2 * 1000)

Как реализовать это в виде кода?

function fn(num) {
  let multiplier = 1;
  let res = 0;
  
  while (num !== 0) {
    const digit = num % 10;
    const sqr = digit ** 2;
    
    num = ~~(num / 10);
    res += sqr * multiplier;
    multiplier *= (sqr < 10 ? 10 : 100);
  }
  
  return res;
}

Если у вас есть вопросы по логике кода, пожалуйста, пишите в комменты.

Подписчики предлагали похожие решения, например:

function fn(n) {
  let pow = 0;
  const getNum = () => {
    let res = Math.floor(n / (10 ** pow));
    return res > 0 ? res % 10 : 0;
  }
  
  let num;
  let result = 0;
  let resultPow = 0;
  
  while ((num = getNum()) > 0) {
    result += (num * num) * (10 ** resultPow);
    resultPow += (num > 3) ? 2 : 1;
    pow++;
  }
  
  return result;
}

Но не смотря на то, что здесь нет преобразований, этот вариант в 6.2 раз медленнее эталона и в 1.7 раз медленне оптимального варианта со строками 📉. Это позволяет сделать вывод, что наличие большого количества операций и вызова функций (добавляют манипуляций со стеком) может нивелировать профит от отсутствия преобразований.

Ближе всего к моему варианту был такой пример:

function fn6(number) {
  let result = 0;
  let signs = 1;
  
  while (number > 0) {
    let digit = number % 10;
    
    result += digit * digit * signs;
    signs *= digit > 3 ? 100 : 10;
    number = Math.floor(number / 10);
  }
  
  return result;
}

Он всего на 10% медленнее моего . Но за счет чего?

Дело в том, что Math.floor - это дополнительная логика под капотом и если заменить Math.floor(number / 10) на ~~(number / 10) то мы получим ту же производительность.

Бонус

А теперь давайте вернемся к варианту, который предлагал Роман Дворнов и позаимствуем оттуда идею с предрассчитанными квадратами, объединим с моим вариантом и получим более производительную функцию:

const xn = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81];

function fn(num) {
  let multiplier = 1;
  let res = 0;
  
  while (num !==0) {
    const digit = num % 10;
    
    num = ~~(num / 10);
    res += xn[digit] * multiplier;
    multiplier *= (num < 4 ? 10 : 100);
  }
  
  return res;
}

Этот вариант на ~13% быстрее моего изначального варианта за счет того, что мы избавились от математической операции 📈

Ну а позже Роман предложил еще один вариант, до которого у меня самого дошли только мысли, но не руки - заменить часть ариметики на побитовые операции:

const xn = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81];

function fn(num){
  let multiplier = 1;
  let res = 0;
  
  while(true) {
    const digit = num % 10;
    
    res += xn[digit] * multiplier;
    
    if (num === digit) break;
    
    num = ~~(num / 10);
    multiplier = digit < 4 ? 
      (multiplier << 3) + (multiplier << 1) :
      (multiplier << 6) + (multiplier << 5) + (multiplier << 2);
  }
  
  return res;
}

Плюс ко всему, за счет break, мы можем не высчитывать num и multiplier на последней итерации.

Хотя такой код и труднее читать, он на ~20% быстрее моего изначального варианта 📈

Подводя итог

К сожалению, JS в какой-то степени расслабляет и часто мы пишем простой, но не производительный код.

Если вашему коду жизненно важна производительность, то ее надо буквально "выгрызать" любыми доступными способами, экономя любые операции. Но если нужно просто написать производительный код, то пишите его так, чтобы не было лишних операций и тем более ненужных преобразований. Соблюдайте баланс между производительностью и читаемостью.

#codewars

#js

#javascript

#решениезадач

#алгоритмы

return true: countOnMe

2021-02-28T20:23:12.428Z

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

#returntrue

#js

#javascript

return true: length

2021-02-27T11:46:57.990Z

Привет! Разбираем решение задачки length из второго сезона RT.

⚠️ Статья наполнена спойлерами. Если вы хотите сами решить задачу, то вернитесь к статье только после того как решите ее сами или если у вас закончится терпение

Задача:

function length(x) {
  return typeof x !== 'object' && !Array.isArray(x) && x.length == 4
}

Нам необходимо передать такой аргумент, который и не объект и не массив, но его свойство length равно 4.

Передать { length: 4 } мы не можем, потому что это объект. [1,2,3,4] тоже не сработает.

Что кроме массивов имеет свойство length и не является при этом объектом?

Функции
Строки

Свойство length у функции возвращает количество параметров этой функции:

function f(a,b,c,d) {}
console.log(f.length); // 4

Пробуем передать function(a,b,c,d){} и получаем true за 19 байт ✅

Но, минимальный длина решения в лидерборде - 5 байт, а значит нам нужно придумать что-то еще. Попробуем сократить функцию до (a,b,c,d)=>1 - это 12 байт ✅

Лучше, но все равно не то.

Попробуем вариант со строками, например '1234' - получаем true за 6 байт ✅

Это еще лучше, но все еще не 5 байт.

Тут мы оказываемся в ситуации, когда ни функции, строковые литералы нам не подходят.

Как получиться строку длиной в 4 байта потратив при этом 5 байт?

Можно воспользоваться преобразованием типов и привести что-нибудь к строке.

Подробнее здесь (попроще) и здесь (посложнее).

1 + '' // '1'
[] + '' // ""
NaN + '' // 'NaN'
undefined + '' // 'undefined'
true + '' // 'true'

Строка 'true' как раз состоит из 4 байт, это то, что нам нужно!

Но true+'' - это 7 байт, но мы-то с вами знаем, что true можно еще записать как !0, поэтому попробуем сократить: !0+'' - получаем true за желанные 5 байт ✅

Хронология решений

function(a,b,c,d){} - 19
(a,b,c,d)=>1 - 12
'1234' - 6
true+'' - 7
!0+'' - 5 🏆

#returntrue

#javascript

#js