Комментарии 31
[arr[i1], arr[i2]] = [arr[i2], arr[i1]];
return arr
}
Если бы не было требования к иммутабельности — то ваше решение одно из лучших.
Ну, тогда
const swap = (inputArray, i, j) => {
const arr = [...inputArray];
[arr[i], arr[j]] = [arr[j], arr[i]];
return arr;
};
Разумеется, с оговоркой spread
-оператора.
"Без использования дополнительных структур данных"
В данном случае используется дополнительный массив из пары элементов)
Так что всё равно не помещается в те ограничения
const swap = (arr, i1, i2) => {
const tmp = [...arr];
[tmp[i1], tmp[i2]] = [arr[i2], arr[i1]];
return tmp
}
const swap = (arr, i1, i2) => ((a) => ([a[i1], a[i2]] = [a[i2], a[i1]], a))([...arr]);
Тут есть отличное решение от Alexandroppolus в котором не создаётся дополнительный массив для пары
Эта задача не может быть решена без всех этих штук под капотом, поэтому ограничения я накладывал на свой код — а не на то, как это под капотом. Да и забава всё это)
Я имею в виду, что в любом случае цикл создания нового массива под капотом использует какие-то условия.
Поэтому нет смысла переписывать эти функции, потому что они как бы часть API которое предоставляет язык.
Если я их перепишу то возникнет вопрос — почему я только их переписал, а метод массива map не переписал.
Поэтому я решил эти ограничения ставить на свой код, а не на внутреннюю реализацию.
Кстати не удивился бы, если бы узнал, что эти функции без ифов уже под капотом написаны.
Интересно, если будет желание написать решение совсем-совсем без условий, то напишите, это было бы очень круто
foo = function(i) {
return Boolean(i) && (console.log(i) || foo(i - 1))
};
foo(5);
//⇒ 5 4 3 2 1 false
Это решение мне известно, я просто не так выразился. Я хотел сказать, что написать цикл с теми условиями которые оговоренны в начале статьи, а не просто без условных операторов.
Без операторов сравнения и логических операторов(&&, ||, ...)
Без приведения типов
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);
В рамках ограничений в статье — тут используется дополнительная структура данных
Но это крутое решение!
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 я знаю, как. А тут что-то не придумывается сходу.
Держите версию сравнения только на делении с остатком, умножении и сложении:
const isEqual = (a, b) => {
d = (a - b) * (a - b) + 2
return 1 - d % (d - 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),
];
};
Строго один проход по списку, только рекурсия и паттерн матчинг. Эликсир. Уверен, что можно и на 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]}})
Перебор.
<source lang="javascript">
const swap = (array, index1, index2) => {
array.splice(
index2,
1,
array.splice(index1, 1, array[index2])[0]
)
return array
};
Безумный безусловный обмен