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

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 2 месяца
Сообщений: 27286

news_bot ^® написал(а)
08-Авг-2020 14:31

Цитировать

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

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

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 => 0
or(0, 1) => 0 + 1 - 0 * 1 => 1
or(1, 0) => 1 + 0 - 1 * 0 => 1
or(1, 1) => 1 + 1 - 1 * 1 => 1

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

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

Функция Math.sign

SPL

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

Math.sign(-23) = -1
Math.sign(0) = 0
Math.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

SPL

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

Math.abs(-23) = 23
Math.abs(0) = 0
Math.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) * r2
const 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
===========
Похожие новости:

Теги для поиска: #_javascript, #_javascript, #_fun, #_javascript

Профиль ЛС

Ответить на тему

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

Текущее время: 29-Апр 22:07
Часовой пояс: UTC + 5