21
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Related: Jump the array \$\endgroup\$ – ბიმო Jan 23 at 17:20
  • \$\begingroup\$ Are we allowed to take the length n as additional input? \$\endgroup\$ – Kevin Cruijssen Jan 24 at 8:55
  • 2
    \$\begingroup\$ @KevinCruijssen, see this meta discussion. \$\endgroup\$ – Shaggy Jan 24 at 12:26
  • \$\begingroup\$ 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~#&. \$\endgroup\$ – Greg Martin Jan 25 at 8:40

23 Answers 23

8
\$\begingroup\$

JavaScript, 36 bytes

Modifies the original input array.

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

Try it online

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! I don't know Swift, but on codegolf.SE the default is to accept typed lambda-functions which I guess a closure would count as. So this can be 53 bytes (you don't need to count f=). Enjoy your stay here! \$\endgroup\$ – ბიმო Jan 24 at 20:48
  • \$\begingroup\$ Thank you for the welcome and advice which I have used to update my answer. \$\endgroup\$ – Sean Jan 24 at 22:39
  • \$\begingroup\$ How about using map instead of forEach to make it shorter? \$\endgroup\$ – jaeyong sung Feb 10 at 6:47
4
\$\begingroup\$

JavaScript (ES6), 41 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Gah! I was waiting for this challenge to be posted so I could post the exact same solution :\ Damn your ninja skills! :p \$\endgroup\$ – Shaggy Jan 23 at 17:53
  • 2
    \$\begingroup\$ @shaggy 🐱‍👤(this is supposed to be a Ninja Cat ... but it's probably not supported everywhere) \$\endgroup\$ – Arnauld Jan 23 at 18:10
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 37 34 bytes

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

Try it online!

Returns by modifying the input array in-place.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can remove the +1 and simply take the 1-based input, the post states : You may choose to use 1-based indexing \$\endgroup\$ – digEmAll Jan 24 at 7:51
  • \$\begingroup\$ -4 by switching to scan() for input. I always feel like my scan() solutions are suboptimal, so keep an eye out a shorter way to assign x and n together: n=length(x<-scan());for(i in rep(1:n,n))x[i]=x[x[i]];x Try it online! \$\endgroup\$ – CriminallyVulgar Jan 25 at 11:47
2
\$\begingroup\$

Common Lisp, 59 58 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Clean, 80 bytes

import StdEnv

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Hello and welcome to PPCG. Would it be possible for you to provide a link to an online interpreter such that one could easily verify your solution? Furthermore, can loop [ not become loop[? \$\endgroup\$ – Jonathan Frech Jan 23 at 21:47
  • 1
    \$\begingroup\$ The most recent edit should fix the test failures. Sorry for the inconvenience everybody. \$\endgroup\$ – Ethan McCue Jan 25 at 18:32
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Clojure, 88 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 16 bytes

FθFLθ§≔θκ§θ§θκIθ

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:

Fθ

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

FLθ

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.

Iθ

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 26 bytesSBCS

Requires ⎕IO←0

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.