Русский
Русский
English
Статистика
Реклама

Recovery mode Безумный безусловный обмен

Безумный безусловный обмен


image


Недавно попалась мне задача иммутабельным способом поменять местами два элемента в массиве по их индексам. Задача довольно простая. Поэтому решив её разумным способом:


const swap = (arr, ind1, ind2) =>  arr.map((e, i) => {    if (i === ind1) return arr[ind2]    if (i === ind2) return arr[ind1]    return e  })

Захотелось решить её безумным способом. Я подумал, что интересно было бы решить эту задачу:


  • Без операторов сравнения
  • Без циклов и if'ов и тернарных операторов
  • Без использования дополнительных структур данных
  • Без приведения типов

Сведём задачу к меньшей


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


const swap = (arr, ind1, ind2) => {  return arr.map((elem, i) => {    const index = i === ind1 ? ind2 : i === ind2 ? ind1 : i    return arr[index]  })}

Мы создали переменную index, в которой в результате выполнения тернарного оператора будет находится индекс элемента массива с которым нужно обменять текущий элемент. Соответственно если текущий индекс ind1, то его мы заменяем на ind2. Если же текущий элемент находится под индексом ind2 мы его меняем с элементом по индексом ind1. Но если не то, и не другое элемент не должен менятся соответственно и index становится равным индексу текущего элемента.


Вынесем логику вычисления значения переменно index в отдельную функцию getSwapIndex(i, ind1, ind2).


const getSwapIndex(i, ind1, ind2) {  return i === ind1     ? ind2     : i === ind2       ? ind1       : i}const swap = (arr, ind1, ind2) => arr.map((_, i) => arr[getSwapIndex(i, ind1, ind2)])

Как видим фукнция swap уже отвечает нашим требованиям. А значит мы свели задачу иммутабельного обмена элементов в массиве к задаче нахождения индекса элемента, с которым нужно произвести обмен


Арифметический аналог булевых значений


Так как нам нельзя использовать приведение типов и условные операции мы не можем использовать булевый тип. Так как у нас на входе функции getSwapIndex находится три числа, а значит оперировать мы можем только числами. Но мы можем использовать числа для представления истинности и ложности, а именно числа 1 и 0. Где 1 будет представлять Истину, а 0 будет представлять Ложь.


Таким образом имеем тип:


type NumberBoolean = 1 | 0

Давайте опишем логическую операцию "ИЛИ" для примера работы с таким типом


const or = (condition1, condition2) => condition1 + condition2 - condition1 * condition2

В самом деле, если на вход этой функции подать числа 1 или 0. То результат будет в точности повторять логику операции "ИЛИ" с обычными булевыми значениями.


or(0, 0) => 0 + 0 - 0 * 0 => 0or(0, 1) => 0 + 1 - 0 * 1 => 1or(1, 0) => 1 + 0 - 1 * 0 => 1or(1, 1) => 1 + 1 - 1 * 1 => 1

Это не единственная возможная реализация этой операции, например такое решение тоже правильное:


const or = (c1, c2) => Math.sign(c1 + c2)

Функция Math.sign

Функция Math.sign возвращает "знак" своего первого параметра:


Math.sign(-23) = -1Math.sign(0) = 0Math.sign(42) = 42

Арифметический аналог тернарного оператора


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


const R = С ? R1 : R2// где С - некоторое булевое условие, R1, R2 - некоторые числа.// тоже,const R = P * R1 + (1 - P) * R2// где Р - это соответсвующее числовое значение булевого значения С. То есть если С === true, то P должно быть равно 1, и если С === false, то P должно быть равно 0.

Если P === 0, то R = 0 * R1 + (1 - 0) * R2 = R2.
Если же P === 1, то R = 1 * R1 + (1 - 1) * R2 = R1.


Таким образом использование тернарного оператора можно заменить на его арифметический аналог.


Давайте определим функцию ternary(c, r1, r2) для подобной операции:


function ternary(p: NumberBoolean, r1: number, r2: number): number {  return p * r1 + (1 - p) * r2}

Сравнение на равенство чисел


Для решения этой задачи нам также понадобиться проверять значения на равенство. Поэтому нам необходимо написать функцию следующего вида:


isEqual(a: number, b: number): NumberBoolean

Давайте посмотрим на её реализацию:


const isEqual = (a, b) => {  return 1 - Math.sign(Math.abs(a - b))}

Функция Math.abs

Функция Math.abs возвращает абсолютное значение числа:


Math.abs(-23) = 23Math.abs(0) = 0Math.abs(42) = 42

Докажем, что это то, что нам нужно. Если a и b равны, то:


isEqual(a, b) => 1 - Math.sign(Math.abs(a - b)) => 1 - Math.sign(Math.abs(0)) => 1 - Math.sign(0) => 1 - 0 => 1

Но если они не равны, то:


isEqual(a, b) => 1 - Math.sign(Math.abs(a - b)) => 1 - Math.sign(Math.abs(Не Ноль)) => 1 - Math.sign(Положительное число)) => 1 - 1 => 0

Таким образом эта функция соответствует сравнению на равенство и возвращает арифметический аналог булевого значения.


К-К-КОМБО


Теперь перепишем нашу функцию getSwapIndex с использованием всех этих функций:


const getSwapIndex = (i, ind1, ind2) =>  ternary(isEqual(i, ind1), ind2, ternary(isEqual(i, ind2), ind1, i))

Таким образом полное решение:


const isEqual = (a, b) => 1 - Math.sign(Math.abs(a - b))const ternary = (p, r1, r2) => p * r1 + (1 - p) * r2const getSwapIndex = (i, ind1, ind2) =>  ternary(isEqual(i, ind1), ind2, ternary(isEqual(i, ind2), ind1, i))const swap = (arr, ind1, ind2) => arr.map((_, i) => arr[getSwapIndex(i, ind1, ind2)])

И в нём нет ни условных операторов, ни сравнений, ни приведений типов.


Фантазия


Конечно это не едиственное решение, я ещё немного поразписывал и получилось тоже не плохое решение:


const getSwapIndex = (i, ind1, ind2) => {  const shouldSwap = or(isEqual(i, ind1), isEqual(i, ind2))  return ternary(shouldSwap, ind1 + ind2 - i, i)}

Послесловие


Спасибо за уделённое время, интересно почитать ваши комментарии и решения!

Источник: habr.com
К списку статей
Опубликовано: 08.08.2020 12:09:15
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Javascript

Fun

Категории

Последние комментарии

  • Имя: Murshin
    13.06.2024 | 14:01
    Нейросеть-это мозг вселенной.Если к ней подключиться,то можно получить все знания,накопленные Вселенной,но этому препятствуют аннуннаки.Аннуннаки нас от неё отгородили,установив в головах барьер. Подр Подробнее..
  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru