Pointer jumping

Question

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]

Answer 1

JavaScript, 36 bytes

Modifies the original input array.

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

Try it online

Answer 2

Haskell, 56 bytes

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

Haskell and in-place updates are a bad match.

Try it online!

Answer 3

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.

Answer 4

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!

Answer 5

Swift, 68 53 bytes

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

Try it online!

-15 thanks to BMO

Answer 6

JavaScript (ES6), 41 bytes

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

Try it online!

Answer 7

05AB1E (legacy), 8 bytes

ΔDvDyèNǝ

Try it online!

Explanation

Δ          # apply until the top of the stack stops changing
 D         # duplicate current list
  v        # for each (element y, index N) in the list
   Dyè     # get the element at index y
      Nǝ   # and insert it at index N

05AB1E, 14 bytes

[D©vDyèNǝ}D®Q#

Try it online!

Answer 8

Japt, 15 13 7 bytes

Modifies the original input array.

££hYXgU

Try it (additional bytes are to write the modified input to the console)

££hYXgU
£           :Map
 £          :  Map each X at index Y
  hY        :    Replace the element at index Y
    XgU     :    With the element at index X

Answer 9

Java 8, 105 54 bytes

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

Modifies the input-array instead of returning a new one to save bytes.

-51 bytes by just modifying the array \$length^2\$ times, instead of until it no longer changes.

Try it online.

Explanation:

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

Answer 10

Japt, 17 bytes

®
£hYUgX
eV ?U:ß

Try all test cases

This feels like it should be shorter, but unfortunately my initial thought of UmgU doesn't work because each g accesses the original U rather than modifying it at each step. Preserving different components appropriately cost a handful of bytes as well.

Explanation:

           #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

Answer 11

C (clang), 32-bit, 49 44 bytes

i;f(**p,n){for(i=0;i<n*n;)p[i++%n]=*p[i%n];}

Try it online!

Uses pointers.

50 45 bytes with integers:

i;f(*p,n){for(i=0;i<n*n;)p[i++%n]=p[p[i%n]];}

Try it online!

Answer 12

Ruby, 37 34 bytes

->a{a.size.times{a.map!{|x|a[x]}}}

Try it online!

Returns by modifying the input array in-place.

Answer 13

Red, 63 bytes

func[b][loop(l: length? b)* l[repeat i l[b/:i: b/(1 + b/:i)]]b]

Try it online!

Modifies the array in place

Answer 14

R, 60 58 bytes

-2 bytes thanks to @digEmAll for reading the rules.

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

Try it online!

1-indexed.

n is the length of the input array.

rep(1:n,n) replicates 1:n n times (e.g. n=3 => 1,2,3,1,2,3,1,2,3)

Loop through the array n times. Steady state will be acheived by then for sure, in fact by the end of the n-1st time through I think. The proof is left to the reader.

Answer 15

Common Lisp, 59 58 bytes

(lambda(a)(dolist(j a)(map-into a(lambda(x)(elt a x))a))a)

Try it online!

Answer 16

Clean, 80 bytes

import StdEnv

limit o iterate\b=foldl(\l i=updateAt i(l!!(l!!i))l)b(indexList b)

Try it online!

Answer 17

Clojure, 136 bytes

(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))))))

Try it online!

Answer 18

Perl 5, 35 34 26 bytes

using the fact that convergence is reach at most for the size number of iterations

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

26 bytes

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

34 bytes

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

35 bytes

Answer 19

Clojure, 88 bytes

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

Try it online!

Answer 20

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.

Answer 21

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.

Answer 22

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]])

Answer 23

APL (Dyalog Unicode), 26 bytes^SBCS

Requires ⎕IO←0

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

Try it online!