Указатель прыжки

21

Предположим, у нас есть массив длины с указателями, указывающими на какое-то место в массиве: процесс « прыжка с указателем » установит каждый указатель на то место, на которое указывает указатель.п.с.N

Для этой задачи указатель - это (основанный на нуле) индекс элемента массива, это означает, что каждый элемент в массиве будет больше или равен и меньше, чем . Используя эту запись, процесс можно сформулировать следующим образом:0N

for i = 0..(n-1) {
  ps[i] = ps[ps[i]]
}

Это означает (для этой задачи), что указатели обновляются на месте в последовательном порядке (т. Е. Сначала более низкие индексы).

пример

Давайте рассмотрим пример, :пс = [2,1,4,1,3,2]

я = 0:элемент в положении ps [0] = 2 указывает на 4→ps = [4,1,4,1,3,2]я = 1:элемент в положении ps [1] = 1 указывает на 1→ps = [4,1,4,1,3,2]я = 2:элемент в положении ps [2] = 4 указывает на 3→ps = [4,1,3,1,3,2]я = 3:элемент в положении ps [3] = 1 указывает на 1→ps = [4,1,3,1,3,2]я = 4:элемент в положении ps [4] = 3 указывает на 1→ps = [4,1,3,1,1,2]я = 5:элемент в положении ps [5] = 2 указывает на 3→ps = [4,1,3,1,1,3]

Итак, после одной итерации « прыжка с указателем » мы получаем массив .[4,1,3,1,1,3]

Вызов

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

правила

Ваша программа / функция будет принимать и возвращать / выводить один и тот же тип, список / вектор / массив и т. Д., Которые

  • гарантированно будет не пустым и
  • гарантированно содержит только записи .0≤п<N

Варианты: вы можете выбрать

  • использовать индексирование на основе 1 или
  • использовать фактические указатели,

однако вы должны упомянуть об этом в своем представлении.

Контрольные примеры

[0] → [0]
[1,0] → [0,0]
[1,2,3,4,0] → [2,2,2,2,2]
[0,1,1,1,0,3] → [0,1,1,1,0,1]
[4,1,3,0,3,2] → [3,1,3,3,3,3]
[5,1,2,0,4,5,6] → [5,1,2,5,4,5,6]
[9,9,9,2,5,4,4,5,8,1,0,0] → [1,1,1,1,4,4,4,4,8,1,1,1]
code-golf array-manipulation graph-theory ბიმო
источник
Связанный: Перейти массив
მოიმო
Разрешено ли нам брать длину в nкачестве дополнительного ввода?
Кевин Круйссен
2
@KevinCruijssen, посмотрите эту мета-дискуссию .
лохматый
Жаль, что записи должны обновляться последовательно; если бы они могли быть обновлены одновременно, Mathematica имела бы решение из 21 символа #[[#]]&~FixedPoint~#&.
Грег Мартин

Ответы:

5

C ++ 14 (gcc) , 61 байт

В качестве неназванной родовой лямбды. Требуются последовательные контейнеры типа std::vector.

[](auto&c){auto d=c;do{d=c;for(auto&x:c)x=c[x];}while(d!=c);}

Попробуйте онлайн!

Bierpfurz
источник
5

Swift , 68 53 байта

{a in for _ in a{var i=0;a.forEach{a[i]=a[$0];i+=1}}}

Попробуйте онлайн!

-15 благодаря BMO

Шон
источник
2
Добро пожаловать в PPCG! Я не знаю Swift, но на codegolf.SE по умолчанию принято принимать типизированные лямбда-функции, которые, как я полагаю, будут считаться закрытием. Таким образом, это может быть 53 байта (вам не нужно считать f=). Наслаждайтесь вашим пребыванием здесь!
მოიმო
Спасибо за приветствие и советы, которые я использовал, чтобы обновить мой ответ.
Шон
Как насчет использования mapвместо того, forEachчтобы сделать его короче?
Джей Чжун спел
4

JavaScript (ES6), 41 байт

f=a=>a+''==a.map((x,i)=>a[i]=a[x])?a:f(a)

Попробуйте онлайн!

Arnauld
источник
Г! Я ждал, когда этот вызов будет опубликован, чтобы я мог опубликовать точно такое же решение: «Черт возьми свои навыки ниндзя! : p
Лохматый
2
@shaggy 🐱‍👤 (предполагается, что это кошка-ниндзя ... но, вероятно, это не везде поддерживается)
Арно
4

Japt, 15 13 7 байт

Изменяет исходный входной массив.

££hYXgU

Попробуйте (дополнительные байты для записи измененного ввода в консоль)

££hYXgU
£           :Map
 £          :  Map each X at index Y
  hY        :    Replace the element at index Y
    XgU     :    With the element at index X
мохнатый
источник
4

Java 8, 105 54 байта

a->{for(int l=a.length,i=0;i<l*l;)a[i%l]=a[a[i++%l]];}

Изменяет массив ввода вместо того, чтобы возвращать новый для сохранения байтов.

LеNграммTчас2

Попробуйте онлайн.

Объяснение:

a->{                // Method with integer-array parameter and no return-type
  int l=a.length,   //  Length of the input-array
  i=0;i<l*l;)       //  Loop `i` in the range [0, length squared):
    a[i%l]=         //   Set the (`i` modulo-length)'th item in the array to:
      a[            //    The `p`'th value of the input-array,
        a[i++%l]];} //    where `p` is the (`i` modulo-length)'th value of the array
Кевин Круйссен
источник
3

Japt , 17 байт


®
£hYUgX
eV ?U:ß

Попробуйте все тестовые случаи

Такое ощущение, что это должно быть короче, но, к сожалению, моя первоначальная мысль UmgUне работает, потому что каждый gобращается к оригиналу, Uа не изменяет его на каждом шаге. Сохранение различных компонентов также стоит несколько байтов.

Объяснение:

           #Blank line preserves input in U long enough for the next line

®          #Copy U into V to preserve its original value

£hY        #Modify U in-place by replacing each element X with...
   UgX     #The value from the current U at the index X

eV ?U      #If the modified U is identical to the copy V, output it
     :ß    #Otherwise start again with the modified U as the new input
Камил Дракари
источник
2

R , 60 58 байт

-2 байта спасибо @digEmAll за чтение правил.

function(x,n=sum(x|1)){for(i in rep(1:n,n))x[i]=x[x[i]];x}

Попробуйте онлайн!

1-индексироваться.

n длина входного массива

rep(1:n,n)повторяет 1:n nвремя (например n=3 => 1,2,3,1,2,3,1,2,3)

Цикл по массиву nраз. К тому времени устойчивое состояние будет достигнуто наверняка, на самом деле к концу 1-го раза, я думаю. Доказательство оставлено читателю.

НГМ
источник
1
Я думаю, что вы можете удалить +1и просто взять ввод, основанный на 1, сообщение гласит: вы можете выбрать индексирование на основе 1
digEmAll
-4 путем переключения scan()на вход. Я всегда чувствую, что мои scan()решения неоптимальны, поэтому следите за более коротким способом назначения xи nвместе: n=length(x<-scan());for(i in rep(1:n,n))x[i]=x[x[i]];x попробуйте это онлайн!
Преступно-
2

Clojure , 136 байт

(defn j[a](let[f(fn[a](loop[i 0 a a](if(= i(count a))a(recur(inc i)(assoc a i(a(a i)))))))](loop[p nil a a](if(= p a)a(recur a(f a))))))

Попробуйте онлайн!

Этан МакКью
источник
Привет и добро пожаловать в PPCG. Можно ли предоставить ссылку на онлайн-переводчика, чтобы можно было легко проверить ваше решение? Кроме того, loop [не может стать loop[?
Джонатан Фрех
1
Последнее редактирование должно исправить ошибки теста. Приносим извинения за неудобства всем.
Этан МакКью
1

Perl 5, 35 34 26 байт

используя тот факт, что сходимость достигается не более для размера числа итераций

$_=$F[$_]for@F x@F;$_="@F"

26 байт

$_=$F[$_]for@F;/@F/ or$_="@F",redo

34 байта

$_=$F[$_]for@F;$_="@F",redo if!/@F/

35 байт

Науэль Фуйе
источник
1

Древесный уголь , 16 байт

ＦθＦＬθ§≔θκ§θ§θκＩθ

Попробуйте онлайн! Ссылка на подробную версию кода. К сожалению, все обычные функции отображения работают только с копией массива, в результате чего они просто переставляют элементы, а не перепрыгивают их, поэтому код должен делать все вручную. Объяснение:

Ｆθ

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

ＦＬθ

Цикл по индексам массива.

§≔θκ§θ§θκ

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

Ｉθ

Приведите элементы к строке и неявно напечатайте каждый на отдельной строке.

Нил
источник
1

F #, 74 73 байта

fun(c:'a[])->let l=c.Length in(for i in 0..l*l do c.[i%l]<-c.[c.[i%l]]);c

Ничего особенного. Использует идею модуля в других ответах.

LSM07
источник
1

К, 27 байт

{{@[x;y;:;x x y]}/[x;!#x]}/

  • {..}/ применяет лямбду {..} к аргументу arg (до схождения)

  • внутри внешней лямбды:

    • {..}/[x;y]применяет лямбду итеративно к x (обновляется на каждой итерации) и элементу y (y - список значений и использует элемент на каждой итерации). В этом случае arg y равно !#x(до количества x, то есть индексов массива)

    • @[x;y;:;x x y] изменить массив x (по индексу y назначить x [x [y]])

Дж. Сендра
источник