15
\$\begingroup\$

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.
\$\endgroup\$

13 Answers 13

6
\$\begingroup\$

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

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!

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

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
\$\endgroup\$
1
  • \$\begingroup\$ A "pure" walrus right before for in a comprehension doesn't need parentheses. And you can save another 2 \$\endgroup\$
    – loopy walt
    Sep 20, 2023 at 17:00
3
\$\begingroup\$

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

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

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 52: f=(a,i=j=0)=>j-(a[~i]??=j++)||f(a,(i+a[i])%a.length) \$\endgroup\$
    – tsh
    Sep 18, 2023 at 11:07
3
\$\begingroup\$

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ lambda x,z={},y=0:next(i-z[y]for i in range(len(x)+1)if z.get(y,-1)+1or((z:=z|{y:i})and(y:=(y+x[y])%len(x))&0))? \$\endgroup\$ Sep 18, 2023 at 10:51
  • \$\begingroup\$ @UndoneStudios I thought I couldn't because mutable default arguments but you are correct I can since I overwrite it every time \$\endgroup\$
    – mousetail
    Sep 18, 2023 at 10:53
2
\$\begingroup\$

05AB1E, 16 bytes

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

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Alternative 16-byter based on bsoelch's first Python answer: g·0λ£Iā<+sè}Rćk>. I have the feeling this challenge can be done shorter in 05AB1E though, but haven't found anything yet. \$\endgroup\$ Sep 18, 2023 at 13:26
  • 1
    \$\begingroup\$ Found a 13-byter: .āIv¬н._D})Ùg - verify all test cases. \$\endgroup\$ Sep 18, 2023 at 13:39
  • 1
    \$\begingroup\$ @KevinCruijssen The 13-byter fails on [1, 1, 0, 2] — it counts the warmup, if it's more than one element. \$\endgroup\$ Sep 18, 2023 at 13:46
  • \$\begingroup\$ Ah. I already kinda had my doubts on the 13-byter despite it giving the correct results for all test cases. :( I assume adding a ¦ before the uniquify and an û before the v won't be enough either? It does fix that [1,1,0,2] without breaking the other test cases: verify all test cases. Although a -1 byte save compared to your current solution isn't as substantially as I had hoped. \$\endgroup\$ Sep 18, 2023 at 13:50
  • 1
    \$\begingroup\$ @KevinCruijssen Adding ¦ before the uniquify only fixed the problem for length 2 warmup, [1,1,1,0] still fails. The number of elements you remove has to be at least n-2. It does feel like there should be a shorter solution, but I can't find it \$\endgroup\$ Sep 18, 2023 at 13:58
2
\$\begingroup\$

Vyxal, 12 bytes

ẏYd‡hǓ~↲t$↲L

Try it Online!

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

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)
  }
}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ You could go for an explicit function for -1 or use F:.: for 32 bytes \$\endgroup\$
    – ovs
    Sep 19, 2023 at 16:26
  • 1
    \$\begingroup\$ And there is another 32 similar to Jonathan Allan's Jelly answer: {{#~.<@#g#(g=.{.@,|.]^:)y,./:y}} \$\endgroup\$
    – ovs
    Sep 19, 2023 at 16:40
  • 1
    \$\begingroup\$ 31 bytes \$\endgroup\$
    – ovs
    Sep 19, 2023 at 16:43
  • \$\begingroup\$ @ovs tyvm. i have a theory that solutions using F:. can never be the shortest golf, which was in jeopardy for a moment, but you saved it. \$\endgroup\$
    – Jonah
    Sep 19, 2023 at 19:36
  • 1
    \$\begingroup\$ Also I really think it has it's niche in golfing. If you have a scan/fold that requires a seed value of a different type than the elements of the array, it will very likely be shorter than / or `\`. Also linear-time scans can be nice. (FWIW I'm using variants on three holes on code.golf) \$\endgroup\$
    – ovs
    Sep 19, 2023 at 21:07
1
\$\begingroup\$

Ruby, 62 bytes

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

Try it online!

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

Charcoal, 29 bytes

UMθ⁺ικ⊞υ⁰F⁺θθ⊞υ§θ↨υ⁰I⊕⌕Φ⮌υκ⊟υ

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

UMθ⁺ικ

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

⊞υ⁰

Start on the leftmost index.

F⁺θθ

Repeat enough times to guarantee a cycle.

⊞υ§θ↨υ⁰

Get the next index.

I⊕⌕Φ⮌υκ⊟υ

Find the length of the cycle.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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