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

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


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

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


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

Функция 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)
}

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


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


Послесловие


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

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Забавляете себя чем-то подобным в свободное время?

  • 29,2%Да14
  • 70,8%Нет34

Похожие публикации

Средняя зарплата в IT

113 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 5 709 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 31

    –1
    const swap = (arr, i1, i2) => {
    [arr[i1], arr[i2]] = [arr[i2], arr[i1]];
    return arr
    }
      0

      Если бы не было требования к иммутабельности — то ваше решение одно из лучших.

        +1

        Ну, тогда


        const swap = (inputArray, i, j) => {
          const arr = [...inputArray];
          [arr[i], arr[j]] = [arr[j], arr[i]];
          return arr;
        };

        Разумеется, с оговоркой spread-оператора.

          0

          "Без использования дополнительных структур данных"
          В данном случае используется дополнительный массив из пары элементов)
          Так что всё равно не помещается в те ограничения

            +1

            const swap = (inputArray, i, j) => {
            const arr = [...inputArray];
            arr[i] = inputArray[j];
            arr[j] = inputArray[i];
            return arr;
            };

              0

              Добавлю ссылку на ваше решение в статью

      +1
      с иммутабельностью:
      const swap = (arr, i1, i2) => {
        const tmp = [...arr];
        [tmp[i1], tmp[i2]] = [arr[i2], arr[i1]];
        return tmp
      }
      
        0

        Одно из ограничений было: "Без использования дополнительных структур данных"


        В данном случае используется дополнительный массив из пары элементов. Так что всё равно не помещается в те ограничения

        0
        Можно имутабельно сделать с помощью внутренней функции и оператора spread:
        const swap = (arr, i1, i2) => ((a) => ([a[i1], a[i2]] = [a[i2], a[i1]], a))([...arr]);
        
          0

          Тут есть отличное решение от Alexandroppolus в котором не создаётся дополнительный массив для пары

          +1
          По хорошему вам бы надо sign и abs реализовать без сравнений и условных конструкций. Иначе и вы не укладываетесь в свои ограничения.
            0

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

              +1
              Ну почему же. И то, и другое можно реализовать без if-ов.
                0

                Я имею в виду, что в любом случае цикл создания нового массива под капотом использует какие-то условия.


                Поэтому нет смысла переписывать эти функции, потому что они как бы часть API которое предоставляет язык.


                Если я их перепишу то возникнет вопрос — почему я только их переписал, а метод массива map не переписал.


                Поэтому я решил эти ограничения ставить на свой код, а не на внутреннюю реализацию.


                Кстати не удивился бы, если бы узнал, что эти функции без ифов уже под капотом написаны.

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

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

                      0
                      foo = function(i) { 
                        return Boolean(i) && (console.log(i) || foo(i - 1))
                      };
                      foo(5);
                      //⇒ 5 4 3 2 1 false
                        0

                        Это решение мне известно, я просто не так выразился. Я хотел сказать, что написать цикл с теми условиями которые оговоренны в начале статьи, а не просто без условных операторов.


                        Без операторов сравнения и логических операторов(&&, ||, ...)
                        Без приведения типов
                          0
                          for 0:N-1 рекурсией без if-ов и логических выражений
                          function end(){
                            //nop
                          }
                          
                          function loop(i, N){
                            const next = [loop, end];
                            console.log(i); i++;
                            next[(i - i%N)/N](i, N);
                          }
                          
                          loop(0, 100);
                          
                            0

                            В рамках ограничений в статье — тут используется дополнительная структура данных


                            Но это крутое решение!

                              0
                              Ну, у нас же JavaScript, поэтому избежать дополнительного массива довольно легко. Среда исполнения сама его создаст.
                              function select(bit, f0, f1, i, N){
                                arguments[bit+1](i, N);
                              }
                              
                              function end(){
                                //nop
                              }
                              
                              function loop(i, N){
                                console.log(i); i++;
                                select((i - i%N)/N, loop, end, i, N);
                              }
                              loop(0, 100);
                              

                              Другой вопрос, можно ли без рекурсии. С асинхронными вызовами не хочется. А без них… В C я знаю, как. А тут что-то не придумывается сходу.
                          0
                          Рекурсия — вариант, если не бояться переполнения стека ,)
                            0

                            Я там ниже показал вариант на эликсире, в котором TCO из коробки. Без единого условия и логического оператора.


                            JS — слишком ущербен, чтобы играть в такие игры.

                              0
                              Насколько я понимаю, мы тут хотим, чтобы процессор вообще не выполнял сравнений и условных переходов.
                                0

                                В рамках статьи — нет
                                В рамках этой дискуссии да)

                  +1

                  Держите версию сравнения только на делении с остатком, умножении и сложении:


                  const isEqual = (a, b) => { 
                      d = (a - b) * (a - b) + 2
                      return 1 - d % (d - 1)
                  }
                    0
                    Класс!
                +1
                const swap = (array, i1, i2) => {
                  if (i1 === i2) {
                    return array;
                  }
                  if (i1 > i2) {
                    [i1, i2] = [i2, i1];
                  }
                  return [
                    ...array.slice(0, i1),
                    array[i2],
                    ...array.slice(i1 + 1, i2),
                    array[i1],
                    ...array.slice(i2 + 1),
                  ];
                };
                0

                Строго один проход по списку, только рекурсия и паттерн матчинг. Эликсир. Уверен, что можно и на JS переписать, если подождать, пока в js завезут паттерн матчинг.


                defmodule Swapper do
                  def swap(list, idx1, idx2),
                    do: do_swap(Enum.with_index(list), idx1, idx2, {nil, nil, {[], [], []}})
                
                  # exhausted: time to return the result
                  defp do_swap([], _, _, {nil, _, _}), do: :error
                  defp do_swap([], _, _, {_, nil, _}), do: :error
                  defp do_swap([], _, _, {e1, e2, {r1, r2, r3}}) do
                    [r1, r2, r3] = Enum.map([r1, r2, r3], &Enum.reverse/1)
                    r1 ++ [e2] ++ r2 ++ [e1] ++ r3
                  end
                
                  # not any found yet, `idx`≡`idx`, pattern match
                  defp do_swap([{e, idx} | rest], idx, i2, {nil, nil, acc}),
                    do: do_swap(rest, idx, i2, {e, nil, acc})
                  defp do_swap([{e, idx} | rest], i2, idx, {nil, nil, acc}),
                    do: do_swap(rest, i2, idx, {e, nil, acc})
                
                  # one already found, `idx`≡`idx`, pattern match
                  defp do_swap([{e, idx} | rest], i1, idx, {e1, nil, acc}),
                    do: do_swap(rest, i1, idx, {e1, e, acc})
                  defp do_swap([{e, idx} | rest], idx, i2, {e1, nil, acc}),
                    do: do_swap(rest, i2, idx, {e1, e, acc})
                
                  # no match on index, updating accumulator
                  defp do_swap([{e, _} | rest], i1, i2, {nil, nil, {r1, r2, r3}}),
                    do: do_swap(rest, i1, i2, {nil, nil, {[e | r1], r2, r3}})
                  defp do_swap([{e, _} | rest], i1, i2, {e1, nil, {r1, r2, r3}}),
                    do: do_swap(rest, i1, i2, {e1, nil, {r1, [e | r2], r3}})
                  defp do_swap([{e, _} | rest], i1, i2, {e1, e2, {r1, r2, r3}}),
                    do: do_swap(rest, i1, i2, {e1, e2, {r1, r2, [e | r3]}})
                end

                Как работает:


                По сути, это имплементация традиционного reduce через рекурсию с аккумулятором в виде {значение_по_первому_индексу, значение_по_второму_индексу, три куска}. Идем рекурсивно по списку (с индексами), если значений нет, а индекс совпал — запоминаем значение, иначе — добавляем в нужный кусок.


                Когда ввод закончился, проверяем, что оба элемента были найдены, возвращаем :error если нет, или result, если да.


                Swapper.swap 1..10, 2, 4
                #⇒ [1, 2, 5, 4, 3, 6, 7, 8, 9, 10]
                Swapper.swap 1..10, 4, 2                                                    
                #⇒ [1, 2, 5, 4, 3, 6, 7, 8, 9, 10]
                Swapper.swap 0..10, 0, 4
                #⇒ [4, 1, 2, 3, 0, 5, 6, 7, 8, 9, 10]
                Swapper.swap 0..10, 0, 10
                #⇒ [10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
                Swapper.swap 0..10, 0, 11
                #⇒ :error
                Swapper.swap 0..10, 0, 1 
                #⇒ [1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                Swapper.swap 0..10, 0, 0
                #⇒ :error

                На самом деле, как только оба нашли, надо сразу возвращать остаток в r3, но так нагляднее. А вернуть хвост — быстрее:


                  defp do_swap([{e, _} | rest], i1, i2, {e1, e2, {r1, r2, r3}}),
                    do: do_swap([], i1, i2, {e1, e2, {r1, r2, Enum.reverse(Enum.map(rest, &elem(&1, 1))) ++ [e | r3]}})
                  0
                  А почему бы не попробовать Array.prototype.splice?

                  Перебор.
                  
                  <source lang="javascript">
                  const swap = (array, index1, index2) => {
                      array.splice(
                          index2,
                          1,
                          array.splice(index1, 1, array[index2])[0]
                      )
                      return array
                  };
                  

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое