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

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

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(-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(-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)}

Послесловие

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