# Show me the trajectory

Given a list of integers find the "trajectory" that results from indefinitely moving the instructed steps to the right (left if negative), wrapping if necessary, starting at the first element.

A "trajectory", here, is defined as a list containing the elements that are visited only one time, in the order they are visited, and a list containing those visited repeatedly, also in order i.e.:

[first, second, ...], [first_of_loop, second_of_loop, ...]


Note that:

• Multiple elements may have the same value, yet these are distinct from each other when considering if they have been visited.
• The empty list need not be handled (given an empty list your code may error).

#### Example

Given

[6, 0, -6, 2, -9 , 5, 3]


we

• start at the first element, the 6
• step right $$\6\$$ to the 3,
• step right $$\3\$$ to the -6,
• step left $$\6\$$ to the 2,
• step right $$\2\$$ to the 5,
• step right $$\5\$$ back to the 2.

Thus the trajectory is

[6, 3, -6], [2, 5]


...where the second list shows the final loop (we first encounter 2, then 5, then loop forever).

#### Test Cases

                                  in  out
  [], 
  [], 
[-1, 2]  [-1], 
[5, 2, 4, 6, 7, 3, 1]  [], [5, 3, 2, 6, 4, 1]
[6, 0, -6, 2, -9 ,5 ,3]  [6, 3, -6], [2, 5]
[4, 5, 2, 6, -2, 7, 8]  , [-2, 2]
[6, 10, 10, 0, -9, -4, 6]  [6, 6], [-4, 10, -9, 10]
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]  [], [9, 9, 9, 9]

• Can we output two lists [a, b] where a has the elements visited, and b the loop? Aug 15 at 19:40
• May I ask why such a restrictive output format? Aug 15 at 19:47
• @Dudecoinheringaahing Hmm, I think I'll reconsider. Will edit in to allow visited once, in order and loop in order separately. Aug 15 at 19:49
• The output format is impossible in many strictly typed languages. Aug 15 at 19:49
• @pxeger ... see ^ Aug 15 at 19:50

# Haskell + hgl, 6160 58 bytes

(i:y)#x|i?>y=m(x!)&@sp(/=i)(rv y)|u<-(i+x!i)%l x:i:y=u#x
(#)


hgl is an experimental golfing library I am developing for Haskell. I started a few days ago and this is my first answer, and it's proof there is still a lot of room for improvement.

From this post I've learned that:

• I should probably make a dedicated function for m.(!), since it is likely to come up more than just here.
• I need versions of sp (span) and bk (break) that include the element that matches / doesn't match the predicate in the first part. I had to use a hack with rv, which is costly and only works in this specific scenario.
• I should make an infix version of e (elem). It would have saved me at least a byte here. Turns out I had already done this ((?>)). Maybe what I actually need is better documentation that makes it easier to find this stuff.
• I should make an infix version of jB. It would have saved me at least 2 bytes here. This also existed and I didn't realize ((&@)). There might be a pattern here.
• It might be a good idea to make an infix of sp. It could have saved me a byte here if I hadn't made an infix of jB.
• I have probably overall underestimated the usefulness of infixes and I should in general just make more of them.

### But here's how it actually works:

Vocab:

• (?>): checks if a list contains an element (elem)
• m: map (fmap)
• (!): index a list (sort of (!!))
• (&@): maps function across both parts of a tuple.
• sp: splits a list at the first element that matches a predicate (span)
• rv: reverses a list (reverse)
• (%): modulo infix (mod, yes Haskell does not have a modulo infix)

So this builds up a list of indices, when a index is added that is already in the list it stops and splits at the last occurrence of that index, and converts the indices to their values.

• That link is dead. Is the repo private? Aug 16 at 7:20
• @pxeger It was initially public but I accidentally set it to private at some point. It is fixed now, and hopefully it will stay public. Aug 16 at 7:31

# J, 53 48 bytes

-5 thanks to Jonah!

(_2{.{~</.~]+./\@e.r)(]~.@,r=.(#@[|]+{~){:)^:_&0


Try it online!

• r=.(#@[|]+{~){: take the last index (starting with 0 &0), get the corresponding value, add it to the index and take the mod.
• ]~.@, … ^:_ append the new value to the indices list and repeat that process until the list does not change after removing duplicates
• ]+./\@e.r the next index is a duplicate, so we find it in the indices list and have a bitmask: 0 for visited once, 1 for loops.
• _2{.{~</.~ group the values based on the indices. Because there might be no items that are visited once, we can pad the output with taking the last two items _2{.

Another approach would be to not build a list, but just repeat the index-shift-mod-loop <@# times, keeping the results, and then search for the loop. But I didn't get it shorter than this.

• 51 bytes with </. with after all: Try it online! Aug 16 at 2:38
• Here's my alternative 53 byte solution. Maybe you can see a way to get it below 51: Try it online! Aug 16 at 4:13
• @Jonah Right, there can't be an output with only visited-once but no loops. Clever _2{. trick!
– xash
Aug 16 at 13:00
• New 51 byte version of alternative method: Try it online! (I can almost taste 49!) Aug 16 at 15:43
• 48 removing extra parens from yours! Try it online! Aug 16 at 20:23

# JavaScript (ES6), 92 bytes

a=>[(g=p=>a=1/(i=g[p%=w=a.length])?[]:[q=a[p],...g(p+q+w*q*q,g[p]=k++)])(k=0).splice(0,i),a]


Try it online!

### Commented

a => [                 // a[] = input array
( g = p =>           // g is a recursive function taking a position p
// the underlying object of g is also used to keep
// track of the positions that are visited
a =                // update a[]
1 / (            //
i = g[         // reduce the position modulo the length w of the
p %= w =     // array and load g[p] into i
a.length   //
]              //
) ?              // if i is defined:
[]             //   we've found the loop: stop the recursion
:                // else:
[              //   update the output array:
q = a[p],    //     load a[p] into q
...g(        //     do a recursive call:
p + q +    //       add q to p
w * q * q, //       also add w*q² to make sure it's >= 0
g[p] = k++ //       save the index k into g[p] and increment k
)            //     end of recursive call
]              //   end of array update
)(k = 0)             // initial call to g with p = k = 0
.splice(0, i),       // extract the non-looping part
a                    // append the looping part
]                      //


# Pip -xp, 32 bytes

^:iT(Yy+a@y%:#a)NiiPBya@i^@:i@?y


Takes the list (formatted like so: [1;2;-3]) as a command-line argument, and outputs a list of two lists. Try it here! Or, verify all test cases at TIO.

### Explanation

^:iT(Yy+a@y%:#a)NiiPBya@i^@:i@?y
a is cmdline input, eval'd (-x flag);
i is 0, y is "" (implicit)
^:i                               Split i and assign back to i: i is now 
T                              Loop until
y                            current index
+a@y                        plus number at current index
%:                      mod
#a                    length of list
Y                             (yank into y, making this the new index)
(          )Ni                 is already in the list of indices traversed:
iPBy              Push the new index onto the list of indices
After the loop, we have the list of unique
indices traversed in i and the first repeated
index in y
a@i         Values from a at each index in i
^@:      split at
i@?y  the index of y in i


# Charcoal, 42 bytes

≔⁰ζＷ¬№υζ«⊞υζ≔﹪⁺ζ§θζＬθζ»≔⌕υζζＵＭυ§θιＩ⟦…υζ✂υζ


Try it online! Link is to verbose version of code. Explanation:

≔⁰ζ


Start at index 0.

Ｗ¬№υζ«


Repeat until a duplicate index is found.

⊞υζ


Save the current index.

≔﹪⁺ζ§θζＬθζ


Calculate the new index.

»≔⌕υζζ


Find the position of the repeat.

ＵＭυ§θι


Replace the indices with the values.

Ｉ⟦…υζ✂υζ


Output the values before and after the repeat as separate arrays.

# Ruby, 91 bytes

->l{*r=a=b=0;r<<a until b=r.index(a=(a+l[a])%l.size);[z=r[0,b],r-z].map{|x|l.values_at *x}}


Try it online!

# C (clang), 137 bytes

a,i,j;
#define f(l,z){int t[z]={i=j=0},h[z];for(;!(a=t[i]);i=(z+i+l[i]%z)%z)h[j]=l[i],t[i]=++j;for(i=0;i<j;)printf("! %d"+!!--a,h[i++]);}


Try it online!

l : list , z : length
int t[z] : kinda sieve, every step sets the visited item to step number
h[z] : save the trajectory values in order for output
for(;!(a=t[i]) : we iterate until we find a visited item, saving in a the first already visited
;i=(z+i+l[i]%z)%z) : modulo hack

at each iteration :
h[j]=l[i] : add item to output list
,t[i]=++j; : and update sieve

Output
for(i=0;i<j;) : j is the number of items visited
printf("! %d"+!!--a,h[i++])
a is the beginning of loop so we
put a separator by including '!' in format string


# Husk, 322925 23 bytes

Edit: -2 bytes thanks to Razetime

†!¹G-§eoUṠ-UUm←¡Sṙo!¹←ŀ


Try it online!

Outputs loop first, then first-visited.

Piece by piece:

Make an infinite list of lists of indices by repeatedly shifting by the input value indexed by the first element:

¡Sṙo!¹←ŀ


And get the first element of each of these: this is the list of indices:

m←


Now, get the longest non-repeating prefix (this includes one copy of the repeating elements):

U


And get the repeating indices:

oUṠ-U


Join these together into a list of 2 lists:

§e


And remove the first (the repeating indices) from the second (the prefix):

G-


Finally, use these to index into the original input:

†!¹

• I was trying to find a way to use span but Sȯ↕≠→hḟS≠uḣm←¡Sṙ← is wrong since it's not considering indices. Was thinking there would be a better way to do this. Aug 18 at 15:18
• Try it online! annoyingly 1 byte longer. Aug 18 at 15:36
• @Razetime - you should still post it. The Sȯ↕≠→hḟS≠u approach is really nice. Aug 18 at 15:40
• @Razetime - and, stealing your ¡Sṙo!¹←ŀ trick, we can get to 23 bytes... Aug 18 at 15:46
• neat, add it in. Aug 18 at 15:51

# Python 3, 116 bytes

f=lambda a,i=0,k=[]:i in k and[[a[q]for q in x]for x in[k[:k.index(i)],k[k.index(i):]]]or f(a,(i+a[i])%len(a),k+[i])


Try it online!

• Save four with a walrus: ...for x in[k[:(z:=k.index(i))],k[z:]]]. Aug 15 at 20:15
• @JonathanAllan tried that, but you can't use those in list comprehensions Aug 15 at 20:46
• Oh, I forgot that; ah well. Aug 15 at 20:47
• 113 bytes
– ovs
Aug 16 at 9:05

# Jelly, 26 bytes

L‘0ị+ị¥%L}ɗƬɗƬ%LḊḣ2fQ,ḟʋ/ị


Try it online!

A monadic link taking a list of integers and returning two lists of integers, with the looped integers first.

• Nice, and different to mine... I'll post it shortly. Aug 16 at 23:24

# 05AB1E, 22 bytes

0¸Δ¤DIsè+Ig%©ªÙ}D®QÅ¡è


Try it online!

# PowerShell Core, 156 145 bytes

for($v=@();!(($s=$v.IndexOf($i))+1);$i%=$l){$v+=,+$i
$t+=,($u=$args[+$i])
$i+=$u+($l=$args.Count)}if(--$l*$s){$t[$s..$l],$t[0..--$s]}else{$t,@()}


Try it online!

Takes a list as parameter.

Returns two lists: loop first then trajectory

Saved:

• 2 bytes by swapping the loop / trajectory in the result
• 2 bytes by reusing $args[$i] as $u • 1 byte by merging the declaration and first usage of $l
• 3 bytes by not initialising $i anymore • 3 bytes thanks to mazzy! #### Not golfed: $index = 0
$length =$args.Count
for ($indices = @(); ($truncateAt = $indices.IndexOf($index)) -eq -1) {
$indices += ,$index
$trajectory += ,$args[$index]$index = ($index +$args[$index] +$length) % $length } if (--$length -and $truncateAt) { ($trajectory[0..--$truncateAt] -join ','), ($trajectory[++$truncateAt..$length] -join ',')
}
else {
'', ($trajectory -join ',') }  # Jelly, 23 22 bytes Quite possibly still beatable... ĖUṙFḢƊƬḢ€⁺JœṖ€$§ṪọɗƇLṪ


A monadic Link that accepts the list and yields a list of lists.

Try it online!

### How?

ĖUṙFḢƊƬḢ€⁺JœṖ€$§ṪọɗƇLṪ - Link: list of integers A=[a,b,...,x,y,...] Ė - enumerate -> [[1,a],[2,b],...,[n,x],[m,y],...] U - upend -> [[a,1],[b,2],...,[x,n],[y,m],...] Ƭ - collect until a repeat under: Ɗ - last three links as a monad, f(current=[[x,n],[y,m],...]): F - flatten (current) -> [x,n,y,m,...] ṙ - rotate (current) left by (each of [x,n,y,m,...]) Ḣ - head -> rotation by x Ḣ€ - head each -> leftmost of each, [[a,1],...,[x,n],...] ⁺ - repeat Ḣ€ -> visited elements in order, [a,...,x,...,last_of_loop]$        - last two links as a monad, f(V=[a,...,x,...,last_of_loop]):
J            -   range of length -> [1,2,...,length(V)]
œṖ€         -   partition (V) before each (of those) indices
Ƈ   - filter (all of these 2-partitions) keeping if:
L  -   use length (of A) on the right of...
§       -     sums
Ṫ      -     tail -> length of the potential loop
ọ     -     how many times is that divisible by length(A)?
(positive (truthy) if an actual loop, else 0 (falsey))
Ṫ - tail


# R, 121118108102101 99 bytes

-10 bytes and another -6 thanks to @Dominic van Essen

function(a,t=1){while(!(t=(t+a[t]-1)%%sum(a|1)+1)%in%T)T=c(T,t)
split(a[T],cut(cumsum(T==t),-1:1))}


Try it online!

The outputted lists have weird names (two intervals), but it I hope it's ok.

• Great! My best attempt was much, much worse than this! Well done. I think you can even save a handful more bytes, and one more by reversing the output... Aug 16 at 21:58
• @DominicvanEssen, thanks! I was trying to make it work with T and also tried negative indexing, but with no success. Should have tried more... Aug 17 at 5:04
• Some more byte-savings... (and output no longer reversed). Aug 17 at 8:08

# jq, 146 bytes

length as$l|def x:((.+.[-1])%$l+$l)%$l;def n:x as$x|.|index($x);. as$i|[0,[],[]]|until(n;[$i[x],.+[x],.+[\$i[x]]])|.[:n],.[n:]


Try it online!

# BQN, 39 bytesSBCS

↕∘≠⊸{⊏⟜𝕩¨2↑⊒⊸/⊸(+⊑⊸=)⊸⊔0∾⊑˜⍟𝕨⟜⊑≠⊸|𝕨+𝕩}

↕∘≠⊸{⊏⟜𝕩¨2↑⊒⊸/⊸(+⊑⊸=)⊸⊔0∾⊑˜⍟𝕨⟜⊑≠⊸|𝕨+𝕩} # 𝕩 is input, 𝕨 is indices 0,1,..,length-1
↕∘≠⊸{                                 } # pass indices into the main function as 𝕨
≠⊸|𝕨+𝕩  # add indices to the input mod the length
⊑˜⍟𝕨⟜⊑        # traverse from the first element a number
#  of steps equal to the length,
#  accumulating results
0∾              # prepend 0
⊒⊸/⊸(+⊑⊸=)⊸⊔                # find the first value to repeat and
#  partition by occurrences
2↑                             # take the first 2 groups
⊏⟜𝕩¨                               # and use them to index into the input


# C (gcc), 115 131 bytes

f(r,n,o,l,j)int*r,**o,*l;{int*t=malloc(4*n);for(*l=j=0;j+=o[(t[j]=++*l)-1]=r[j],!t[j=(j%n+n)%n];);*l-=l=t[j]-1;o=*o+l;}


Try it online!

Outputs [prefix, loop] into o and [len(loop), len(prefix)] into l. Expects these to have allocated enough memory to fit the output (though o` is discarded).

• @JonathanAllan fixed.
– att
Aug 18 at 19:53