# Pointer jumping

Suppose we have an array $$\\texttt{ps}\$$ of length $$\n\$$ with pointers pointing to some location in the array: The process of "pointer jumping" will set every pointer to the location the pointer it points to points to.

For the purpose of this challenge a pointer is the (zero-based) index of an element of the array, this implies that every element in the array will be greater or equal to $$\0\$$ and less than $$\n\$$. Using this notation the process can be formulated as follows:

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

This means (for this challenge) that the pointers are updated in-place in sequential order (ie. lower indices first).

## Example

Let's work through an example, $$\\texttt{ps = [2,1,4,1,3,2]}\$$:

$$\texttt{i = 0}: \text{the element at position }\texttt{ps[0] = 2}\text{ points to }\texttt{4} \\ \to \texttt{ps = [4,1,4,1,3,2]} \\ \texttt{i = 1}: \text{the element at position }\texttt{ps[1] = 1}\text{ points to }\texttt{1} \\ \to \texttt{ps = [4,1,4,1,3,2]} \\ \texttt{i = 2}: \text{the element at position }\texttt{ps[2] = 4}\text{ points to }\texttt{3} \\ \to \texttt{ps = [4,1,3,1,3,2]} \\ \texttt{i = 3}: \text{the element at position }\texttt{ps[3] = 1}\text{ points to }\texttt{1} \\ \to \texttt{ps = [4,1,3,1,3,2]} \\ \texttt{i = 4}: \text{the element at position }\texttt{ps[4] = 3}\text{ points to }\texttt{1} \\ \to \texttt{ps = [4,1,3,1,1,2]} \\ \texttt{i = 5}: \text{the element at position }\texttt{ps[5] = 2}\text{ points to }\texttt{3} \\ \to \texttt{ps = [4,1,3,1,1,3]}$$

So after one iteration of "pointer jumping" we get the array $$\\texttt{[4,1,3,1,1,3]}\$$.

## Challenge

Given an array with indices output the array obtained by iterating the above described pointer jumping until the array does not change anymore.

## Rules

Your program/function will take and return/output the same type, a list/vector/array etc. which

• is guaranteed to be non-empty and
• is guaranteed to only contain entries $$\0 \leq p < n\$$.

Variants: You may choose

• to use 1-based indexing or
• use actual pointers,

however you should mention this in your submission.

## Test cases

[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]
• Related: Jump the array – ბიმო Jan 23 '19 at 17:20
• Are we allowed to take the length n as additional input? – Kevin Cruijssen Jan 24 '19 at 8:55
• @KevinCruijssen, see this meta discussion. – Shaggy Jan 24 '19 at 12:26
• It's too bad the entries need to be updated sequentially; if they could be updated simultaneously, Mathematica would have the 21-character solution #[[#]]&~FixedPoint~#&. – Greg Martin Jan 25 '19 at 8:40

# JavaScript, 36 bytes

Modifies the original input array.

a=>a.map(_=>a.map((x,y)=>a[y]=a[x]))

Try it online

foldr(\_->([]#))=<<id
x#a@(b:c)=(x++[(x++a)!!b])#c
x#_=x

Try it online!

# Python 2, 53 bytes

def f(l):L=len(l);i=0;exec'l[i]=l[l[i]];i=-~i%L;'*L*L

Try it online!

-6 thanks to HyperNeutrino.

Alters l to the result in place.

# C++14 (gcc), 61 bytes

As unnamed generic lambda. Requires sequential containers like std::vector.

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

Try it online!

35 bytes

# Clojure, 88 bytes

#(reduce(fn[x i](assoc x i(get x(get x i))))%(flatten(repeat(count %)(range(count %)))))

Try it online!

# Charcoal, 16 bytes

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

Try it online! Link is to verbose version of code. Sadly all the usual mapping functions only operate on a copy of the array with the result being that they just permute the elements rather than jumping them, so the code has to do everything manually. Explanation:

Ｆθ

Repeat the inner loop once for each element. This just ensures that the result stabilises.

ＦＬθ

Loop over the array indices.

§≔θκ§θ§θκ

Get the array element at the current index, use that to index into the array, and replace the current element with that value.

Ｉθ

Cast the elements to string and implicitly print each on their own line.

# F#, 74 73 bytes

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

Nothing special. Uses the modulus idea seen in other answers.

## K, 27 Bytes

{{@[x;y;:;x x y]}/[x;!#x]}/
• {..}/ applies lambda {..} over arg (until convergence)

• inside outer lambda:

• {..}/[x;y] applies lambda iteratively over x (updated at each iteration) and an item of y (y is a list of values, and uses an item at each iteration). In this case arg y is !#x(til count x, that is, indexes of the array)

• @[x;y;:;x x y] amend array x (at index y assign x[x[y]])

# APL (Dyalog Unicode), 26 bytesSBCS

Requires ⎕IO←0

{m⊣{m[⍵]←m[m[⍵]]}¨⍳≢m←⍵}⍣≡

Try it online!