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

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

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

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

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

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

Топовые решение из комментов:

Решение с изначальным клонированием массива

Послесловие

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

Автор: Andrew Beletskiy

Источник