23
\$\begingroup\$

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
                                 [0]  [], [0]
                                 [3]  [], [3]
                             [-1, 2]  [-1], [2]
               [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]  [4], [-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]
\$\endgroup\$
10
  • \$\begingroup\$ Can we output two lists [a, b] where a has the elements visited, and b the loop? \$\endgroup\$ Aug 15 at 19:40
  • \$\begingroup\$ May I ask why such a restrictive output format? \$\endgroup\$
    – pxeger
    Aug 15 at 19:47
  • \$\begingroup\$ @Dudecoinheringaahing Hmm, I think I'll reconsider. Will edit in to allow visited once, in order and loop in order separately. \$\endgroup\$ Aug 15 at 19:49
  • 2
    \$\begingroup\$ The output format is impossible in many strictly typed languages. \$\endgroup\$
    – Bubbler
    Aug 15 at 19:49
  • \$\begingroup\$ @pxeger ... see ^ \$\endgroup\$ Aug 15 at 19:50

17 Answers 17

7
\$\begingroup\$

Haskell + hgl, 61 60 58 bytes

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ That link is dead. Is the repo private? \$\endgroup\$
    – pxeger
    Aug 16 at 7:20
  • \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    Aug 16 at 7:31
5
\$\begingroup\$

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.

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

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

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

Charcoal, 42 bytes

≔⁰ζW¬№υζ«⊞υζ≔﹪⁺ζ§θζLθζ»≔⌕υζζUMυ§θιI⟦…υζ✂υζ

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

≔⁰ζ

Start at index 0.

W¬№υζ«

Repeat until a duplicate index is found.

⊞υζ

Save the current index.

≔﹪⁺ζ§θζLθζ

Calculate the new index.

»≔⌕υζζ

Find the position of the repeat.

UMυ§θι

Replace the indices with the values.

I⟦…υζ✂υζ

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

\$\endgroup\$
3
\$\begingroup\$

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!

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

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

Husk, 32 29 25 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:

†!¹
\$\endgroup\$
6
  • \$\begingroup\$ 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. \$\endgroup\$
    – Razetime
    Aug 18 at 15:18
  • 1
    \$\begingroup\$ Try it online! annoyingly 1 byte longer. \$\endgroup\$
    – Razetime
    Aug 18 at 15:36
  • 1
    \$\begingroup\$ @Razetime - you should still post it. The Sȯ↕≠→hḟS≠u approach is really nice. \$\endgroup\$ Aug 18 at 15:40
  • \$\begingroup\$ @Razetime - and, stealing your ¡Sṙo!¹←ŀ trick, we can get to 23 bytes... \$\endgroup\$ Aug 18 at 15:46
  • \$\begingroup\$ neat, add it in. \$\endgroup\$
    – Razetime
    Aug 18 at 15:51
2
\$\begingroup\$

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!

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

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Nice, and different to mine... I'll post it shortly. \$\endgroup\$ Aug 16 at 23:24
2
\$\begingroup\$

05AB1E, 22 bytes

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

Try it online!

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

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 ',')
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ --$l-*$s? \$\endgroup\$
    – mazzy
    Aug 17 at 10:33
2
\$\begingroup\$

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...
                  ɗ    -   last three links as a dyad, f(partition, length(A)):
               §       -     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
\$\endgroup\$
2
\$\begingroup\$

R, 121 118 108 102 101 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.

\$\endgroup\$
3
  • \$\begingroup\$ 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... \$\endgroup\$ Aug 16 at 21:58
  • \$\begingroup\$ @DominicvanEssen, thanks! I was trying to make it work with T and also tried negative indexing, but with no success. Should have tried more... \$\endgroup\$
    – pajonk
    Aug 17 at 5:04
  • 1
    \$\begingroup\$ Some more byte-savings... (and output no longer reversed). \$\endgroup\$ Aug 17 at 8:08
2
\$\begingroup\$

jq, 146 bytes

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

Try it online!

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

BQN, 39 bytesSBCS

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

Try it here.

↕∘≠⊸{⊏⟜𝕩¨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
\$\endgroup\$
1
\$\begingroup\$

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[0][(t[j]=++*l)-1]=r[j],!t[j=(j%n+n)%n];);*l-=l[1]=t[j]-1;o[1]=*o+l[1];}

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[1] is discarded).

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @JonathanAllan fixed. \$\endgroup\$
    – att
    Aug 18 at 19:53

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.