Keep jumping till a cycle

Question

Objective

You're on a nonempty list of integers that wraps around. You start at the leftmost entry of the list, and keep jumping to the right to the amount of the integer entry you're at.

Eventually, you'll end up in a cycle. The objective is to output the length of this cycle.

I/O format

Provided that the inputted list has \$n\$ entries, each entry \$m\$ is assumed to satisfy \$0 \leq m < n\$. Otherwise flexible.

Examples

Input, Output
[0], 1
[0, 1, 2], 1
[1, 0, 2], 1
[1, 1, 2], 2
[2, 2, 2, 2], 2
[2, 3, 2, 1], 2
[3, 3, 3, 2], 3
[1, 1, 1, 1], 4

Worked Example

[1, 2, 3, 2]
 ^
[1, 2, 3, 2]
    ^
[1, 2, 3, 2]
          ^
[1, 2, 3, 2]
    ^
Cycle detected; halt. The output is: 2.

Answer 1

Jelly, 9 bytes

Ėṙ`ḢṪƊÐḶL

A monadic Link that accepts a list of integers and yields the cycle length.

Try it online!

How?

Keep a record of the original indices along with their jump-values and repeatedly rotate this left by its first jump-value to find the cycle and output its length.

The implementation actually rotates by all indices and jump-values then picks out the one we want (rotated by first jump-value).

Ėṙ`ḢṪƊÐḶL - Link: list of integers, Jumps
Ė         - enumerate  -> [[1, jump1], [2, jump2], ...]
      ÐḶ  - start with that and collect up while distinct then yield loop, applying:
     Ɗ    -   last three links as a monad - f(Current):
  `       -     use as both arguments of:
 ṙ        -       rotate {Current} left by {Current} (vectorises)
   Ḣ      -     head -> rotations by the first index and first jump
    Ṫ     -     tail -> rotation by the first jump
        L - length

Answer 2

R, 65 bytes

\(a){while(!(T=(T+a[+T]-1)%%sum(a|1)+1)%in%F)F=c(T,F)
match(T,F)}

Attempt This Online!

Answer 3

Python, 62 bytes

-4 bytes, thanks to loopy walt

lambda L,i=0:len({*[i:=(i+L[i])%len(L)for _ in 2*L][len(L):]})

Attempt This Online!

Explanation

1. compute list of first 2*len(L) jumps
2. find the number of unique indices in the last len(l) jumps

---

Python, 93 bytes

lambda l,i=0,s=[0]:1+len([(s:=s+[i:=j])for _ in l if(j:=(i+l[i])%len(l))not in s])-s.index(j)

Attempt This Online!

Explanation

1. go through the first len(l) jumps, stop if a duplicate is found
2. return the (1-based) index of the duplicate element in the list of indices counted from the end of the list

Answer 4

JavaScript, 56 bytes

a=>(g=t=>t-(a[i=(i+a[i|0])%a.length]||=t++)||g(t))(i=.5)

f=

a=>(g=t=>t-(a[i=(i+a[i|0])%a.length]||=t++)||g(t))(i=.5)


t = `
[0], 1
[0, 1, 2], 1
[1, 0, 2], 1
[1, 1, 2], 2
[2, 2, 2, 2], 2
[2, 3, 2, 1], 2
[3, 3, 3, 2], 3
[1, 1, 1, 1], 4
`.trim().split('\n').map(l => JSON.parse(`[${l}]`));
t.forEach(([i, e]) => {
  console.log(f([...i]) == e, f([...i]))
});

Answer 5

JavaScript (ES6), 54 bytes

f=(a,i=j=0)=>j-a[~i]||f(a,(i+a[i])%a.length,a[~i]=j++)

Try it online!

---

JavaScript (ES12), 52 bytes

-2 bytes by using nullish coalescing assignment, as suggested by @tsh.

f=(a,i=j=0)=>j-(a[~i]??=j++)||f(a,(i+a[i])%a.length)

Attempt This Online!

Answer 6

Python, 99 bytes

lambda x,y=0,z={}:next(i-z[y]for i in range(len(x)+1)if y in z or[z:=z|{y:i},y:=(y+x[y])%len(x)]*0)

Attempt This Online!

Answer 7

05AB1E, 16 bytes

0λIā<+sè}Igô1èÙg

Try it online!

Answer 8

Jelly, 11 10 bytes

+J,1ị@\ÐḶL

Try it online!

-1 thanks to Bubbler

+J            Add every jump number to its 1-index.
  ,1          Pair that with 1.
       ÐḶ     Loop while unique then extract the cycle:
      \       scan by
    ị@        modular 1-index right into left.
      \ÐḶ     (Dyadic ÐḶ doesn't reuse the right argument.)
         L    Take the length of the cycle.

Answer 9

Vyxal, 12 bytes

ẏYd‡hǓ~↲t$↲L

Try it Online!

Answer 10

Scala, 95 bytes

Golfed version. Try it online!

l=>{var(r,a)=(Seq[Int](),0);while(!r.contains(a)){r:+=a;a=(a+l(a))%l.size};r.size-r.indexOf(a)}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    println(f(List(2,3,2,1)))
  }

  def f(l: List[Int]): Int = {
    var r = List[Int]()
    var a = 0
    while (!r.contains(a)) {
      r = r :+ a
      a = (a + l(a)) % l.size
    }
    r.size - r.indexOf(a)
  }
}

Answer 11

J, 41 34 31 30 29 bytes

##@~.@}.0]F:.(#@[|]+{~)2###,:

Attempt This Online!

-3 thanks to a nice observation by ovs: If you run the simulation 2*n times, as I was, you can ensure you get only the cyclic elements by removing the first n

I also shaved another byte off by applying a trick from another of ovs's suggestion

This is a combination of two suggestions from ovs, using F:. for folding.

J, 41 34 31 30 bytes, saved for a new J trick

##@~.@}.<@+:@#@[(#@[|]+{~^:)&0

Attempt This Online!

• <@+:@#@[(#@[|]+{~^:)&0 Simulate the jumps 2*n times. For J lang enthusiasts, we are using a partially applied conjunction as an adverb here: (#@[|]+{~^:) -- it modifies the verb <@+:@#@[, and is equivalent to the standard form (#@[|]+{~)^:(<@+:@#@[). It is acting here as a syntactic trick that allows us to save to some parens.
• ##@~.@}. Now remove the first n elements (ensuring we only have cyclic elements left), and take the count of the uniq

Answer 12

Ruby, 62 bytes

->l{*r=a=0;1while r!=r|=[a=(a+l[a])%l.size];r.size-r.index(a)}

Try it online!

Answer 13

Charcoal, 29 bytes

ＵＭθ⁺ικ⊞υ⁰Ｆ⁺θθ⊞υ§θ↨υ⁰Ｉ⊕⌕Φ⮌υκ⊟υ

Try it online! Link is to verbose version of code. Explanation: Port of @bsoelch's Python answer.

ＵＭθ⁺ικ

Add the index to each element to give its (cyclic) destination index.

⊞υ⁰

Start on the leftmost index.

Ｆ⁺θθ

Repeat enough times to guarantee a cycle.

⊞υ§θ↨υ⁰

Get the next index.

Ｉ⊕⌕Φ⮌υκ⊟υ

Find the length of the cycle.