How many times can I skip a stone?

Let's have a list of positive integers

[6,1,9,3,7,4,6,3,2,7,6,6]


this will represent a river. We would like to skip a stone across this river. We can throw the stone as far as we want and whatever number it lands on it will skip that many places. So if we start by throwing it 2 spaces, it will land on the 1 skip forward one place, land on the 9 skip forward 9 places, land on the final 6 and skip out of the river.

[6,1,9,3,7,4,6,3,2,7,6,6]
^
[6,1,9,3,7,4,6,3,2,7,6,6]
^
[6,1,9,3,7,4,6,3,2,7,6,6]
^


The question for us is: "How do we throw the stone so it skips the largest number of times?" In the above case 2 skips 3 times and indeed we can see that this is the optimum.

Here's all the ways to throw the stone with the number of skips labeled:

[6,1,9,3,7,4,6,3,2,7,6,6]
2 3 2 2 2 2 1 2 2 1 1 1


Given a list of positive integers as input output the maximum skips that can be achieved on that river.

This is so the goal is to make your source code as small as possible as measured in bytes.

Test cases

[1] -> 1
[1,1,1] -> 3
[9,1,1,1] -> 3
[9,3,1,2,2,9,1,1,1] -> 5
[6,6] -> 1
[6,1,9,3,7,4,6,3,2,7,6,6] -> 3
[1,1,9,1,1] -> 3

• May I take input as a list of suffixes? i.e., [[1],[1,1],[1,1,1]] Jan 22 at 23:46
• @hakr14 No. You must make your own suffixes. Jan 23 at 0:01

05AB1E, 11 bytes

.sε.Γ¬.$]ζg  .sε # map over the suffixes of the list .Γ # iterate until reaching a fixed point, collecting intermediate results: ¬.$  #     get the first value, and drop that many values from the front
ζ         # after the map: transpose, padding with spaces
g        # get the length


JavaScript (ES6), 49 bytes

a=>Math.max(...a.map(g=(v,i)=>v&&-~g(a[i+=v],i)))


Try it online!

We turn the input array into a list of number of skips for each starting point, using the recursive callback function g:

g = (          // g is a recursive function taking:
v,           //   v = value at the current position
i            //   i = current position
) =>           //
v &&         // abort if v is undefined
-~g(         // otherwise increment the result of a recursive call:
a[i += v], //   add v to i and pass a[i] as the new value
i          //   pass the new position
)            // end of recursive call


We then return the maximum of this list.

J, 25 bytes

[:#[:+./ .*^:a:~#\=/~]+#\


Try it online!

We think of it as a graph problem.

Consider 1 1 9 1 1

• ]+#\ Add 1 2 3 4 5 to the input:

2 3 12 5 6

• #\=/ Create an equality table showing where that is equal to 1 2 3 4 5:

    1 2 3 4 5
+----------
2| 0 1 0 0 0
3| 0 0 1 0 0
12| 0 0 0 0 0
5| 0 0 0 0 1
6| 0 0 0 0 0


This is the adjacency of matrix of the directed graph showing connections between the indices.

• [:+./ .*^:a:~ "OR" matrix multiply that graph with itself until we reach a fixed point, saving intermediate steps:

0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0

0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

• [:# Return the length, which is also the length of the longest path:

3


J, Bonus port of ovs's answer, 25 bytes

[:>./<:@#@(({.}.])^:a:)\.


Try it online!

VyxalG, 20 16 bytes

żƛ{D?L<|?i+1$}!⇩  Try it Online! This feels too long That's better. Explained żƛ{D?L<|?i+1$}!⇩
ż                 # The range [1, len(input)] - this represents all possible starting throw lengths
ƛ                # over each item N in that range:
{D?L<|          #   while the top of the stack (the position of the rock on the lake) (initially N) is less than the length of the input: - this keeps the top of the stack on the stack
?i+       #     index into the input list at the current position of the rock and add the skip value to the position of the rock. This is what keeps track of how far the rock has travelled.
1$# and push a 1 to the stack, placing it underneath the position of the rock - this keeps track of how many jumps have been made. } # end loop !⇩ # push the length of the stack minus 2 - this is the number of jumps made accounting for the remaining rock positions. # the -G flag returns the maximum number of jumps from the resulting list.  Python 3, 615754 53 bytes -4 bytes thanks to @ovs Further -3 bytes thanks to @xnor And an additional -1 byte thanks to @ovs f=lambda l,b=1:l>[]and max(1+f(l[l[0]:],-1),f(l[b:]))  Try it online! • You can save two bytes with ...and-min(~f(l,i+l[i]),~-i*f(l[1:],i)). And you might be able to drop the ,i on the second recursive call, but I'm not sure about that – ovs Jan 22 at 12:36 • I think this works with always truncating the list from the start, and explicitly tracking whether we're allowed to step right. Probably can be done shorter. – xnor Jan 22 at 12:51 • 53 bytes – ovs Jan 22 at 13:13 • 51 bytes Jan 23 at 3:07 • @DialFrost this is a recursive function, so it's customary to leave the f= as part of the code, since using any other variable name for the function breaks the code Jan 23 at 7:25 x86-16 machine code, 24 bytes 00000000: 33c0 33db 5399 4202 183b d97e f93b d07c 3└3█SÖB☻↑;┘~∙;╨| 00000010: 028b c25b 43e2 edc3 ☻ï┬[CΓφ├  Listing: 33 C0 XOR AX, AX ; AX = max skip count 33 DB XOR BX, BX ; BX = starting point offset THROW_LOOP: 53 PUSH BX ; save starting point 99 CWD ; clear skips counter for this throw (DX = 0) SKIP_LOOP: 42 INC DX ; increment skip counter 02 18 ADD BL, BYTE PTR[BX+SI] ; add it's value to place offset 3B D9 CMP BX, CX ; did it skip out of the river? 7E F9 JLE SKIP_LOOP ; if not, let it keep skipping END_SKIP: 3B D0 CMP DX, AX ; is skip counter higher than best? 7C 02 JL NOT_BEST ; if not, try next starting offset 8B C2 MOV AX, DX ; if so, save as current best score NOT_BEST: 5B POP BX ; restore starting point 43 INC BX ; go to next starting point E2 ED LOOP THROW_LOOP ; loop until end of array C3 RET  Input array at [SI], length in CX. Output most skips in AX. Tests with DOS DEBUG (in Dark Mode): Wolfram Language (Mathematica), 71706864625250 47 bytes A|->Max[i=0;#0@@Check[!#+A[[#]],-1]+1&@++i&/@A]  –3 thanks to att! Try it online! • 47 bytes – att Jan 22 at 20:05 Jelly, 11 bytes ṫ‘ḢƊƬÐƤẈṀ_2  A monadic Link accepting a list of integers that yields an integer. Try it online! Or see the test-suite. How? Unfortunately, while Ḣ pops off and yields the head of a list it affects the original list given to ÐƤ (for suffixes of the list) as well as the suffix being dealt with at the time and so affects the remaining suffixes. Without the popping we need to increment for ṫ (tail from) to do the correct thing so I've incremented all elements, tailed from each of those and then kept the head of those lists. Maybe there is a better way to do this challenge that will take less bytes...? ṫ‘ḢƊƬÐƤẈṀ_2 - Link: list of integers, River ÐƤ - for each suffix of River: Ƭ - collect input values while distinct, applying: Ɗ - last three links as a monad: ‘ - increment all values ṫ - tail (vectorises, so tail at from incremented value) Ḣ - head (the list that used the first incremented value) Ẉ - length of each Ṁ - maximum _2 - subtract two (the final [] and the 0 that heading [] (or 0) yields)  This one is 13 bytes, but maybe the idea can lead to a shorter solution? JŒPịṖ⁼I{ʋƇ⁸ṪL  Nibbles, 10 bytes (19 nibbles) /.,,$-,.$+=~$_$~]  Explanation /.,,$-,.$+=~$_$~] / ] Maximum of list: . Map over ,,$                each index i of the input:
.$Iterate starting at j = i, collecting all values: + Add =~$_          the j-th element of the input or 0 if out of bounds
$to j , Get length - ~ Subtract 1  • Is there any online link to run this? Jan 22 at 22:40 • @DominicvanEssen Not yet. There has been a proposal to add Nibbles to ATO, but I have no idea what the progress on that is :/ Jan 22 at 22:55 • Current ATO works in progress from the repo are Vyxal only, it seems. Probably requires a new issue for Nibbles. Jan 23 at 6:08 • @DominicvanEssen you can run latest Nibbles on golf.shinh.org , but adding your own input to it may not be easy. Jan 23 at 6:09 • Jan 23 at 8:28 Pyth, 21 bytes eSmlP.u.x>NhN[)_d).__  Test suite Explanation: eSmlP.u.x>NhN[)_d).__ | Full code eSmlP.u.x>NhN[)_d).__Q | with implicit variables filled -----------------------+---------------------------------------------------------------------------------------------------------------- m _ .__Q | Map over the list of suffixes d of the input: .u d) | Repeat the following on N, starting with d, until a repeated value is given, collecting results in a list: >NhN | N from index (the first value of N) on .x [) | (or the empty list if an error is thrown) lP | Length of the resulting list - 1 eS | Get the max value of the resulting list  The final 7 bytes can be omitted if input is taken as a list of suffixes (not allowed by challenge author). Husk, 11 bytes ←▲mȯLU¡S↓←ṫ  Try it online! Explanation ←▲mȯLU¡S↓←ṫ ṫ suffixes m map each to ¡S↓← infinite list: drop first element no. of elements LU length of unique prefix ←▲ decrement maximum  Jelly, 11 bytes ;0µ+J«LịƬL  Try it online! Feels like there ought to be one more byte to shave off, perhaps dealing with the final step with something shorter than ;0µ, but it at least ties. ;0µ Append a 0 to the list. +J Find the sum of each element and its 1-index «L capped at the list's length. ịƬ Index this into itself (constant) until it doesn't change, L and return the number of iterations that took.  Ṗ’o¥\ċ1‘µÐƤṀ and ’o¥\ÐƤI>-§Ṁ‘, a byte longer and completely different, also work. Charcoal, 30 bytes Ｆ⌈θ⊞θ⁰Ｆ⮌…Ｌθ§≔θι∧§θι⊕§θ⁺ι§θιＩ⌈θ  Try it online! Link is to verbose version of code. Explanation: Ｆ⌈θ⊞θ⁰  Append sufficient zeros so that we never jump off the end of the array. Ｆ⮌…Ｌθ  Iterate over the array in reverse order. §≔θι∧§θι⊕§θ⁺ι§θι  Update each non-zero element with 1 more than the number of skips of its next skip. Ｉ⌈θ  Output the maximum number of skips. Retina 0.8.2, 61 bytes .+ ,$&;
\d+
$* +,1(1)*;((?<-1>1*,)*(1*)) ;1$3,$2 O^1+ \G;?1  Try it online! Link includes test cases. Explanation: .+ ,$&;


Wrap the input list with an extra prefix , and a trailing marker ;.

\d+
$*  Convert to unary. +  Repeat until the marker has reached the beginning of the array. ,1(1)*;((?<-1>1*,)*(1*))  Try to skip ahead to find how many additional skips to take. (If there aren't enough values then this just runs off the end of the array and finds no skips.) ;1$3,\$2


Replace the current value with 1 more than the number of additional skips.

O^1+


Sort the numbers of skips in descending order.

\G;?1


Convert the maximum to decimal.

C (gcc), 78 77 75 bytes

i;c;m;f(a,n)int*a;{for(m=0;n--;++a)for(c=i=0;i<=n;m=++c>m?c:m)i+=a[i];i=m;}


Try it online!

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Returns the maximum number of skips.

Brain-Flak-r, 106 bytes

{({}(<()>)){({}<<>({}<>)>[(())])}{}<>(([(({})<><{{}({}<>)<>}{}>)]<>{}){(<{}>)[()]}{}<>({}()<>))<>}<>({}<>)


Try it online!

Starting from the end (which is the top of the stack since I used the -r flag), computes the number of skips from each position as 1 more than the previously calculated number of skips from its destination. The implicit zeros on the right stack account for the initial running maximum and number of skips from positions beyond the river.

In each iteration, the left stack has the positions not handled yet, and the right stack has the running maximum on top, followed by the number of skips from already handled positions.

Full code breakdown later.

T-SQL, 96 bytes

WITH c(a,b,x)as(SELECT*,1FROM t
UNION ALL
SELECT t.*,x+1FROM c,t
WHERE a+b=i)SELECT max(x)FROM c


Try it online

Wolfram Language (Mathematica), 41 39 bytes

-1 (-2) thanks to Roman

Depth[g=h@#;i=0;(g@i=g[++i+#]!)&/@#]-3&


Try it online!

      g=h@#;                            associate g with this input
i=0;       ++i     &/@#     for indices i of input l:
(g@i=g[  i+#]!)           g[i]->Factorial[g[i+l〚i〛]]
Depth[                             ]    depth
-3  offset (-1 List, -2 g[_])

• 40 bytes Jan 25 at 10:08
• @Roman Probably every answer where Clear's been used before can be improved in the same way. Thanks :)
– att
Jan 25 at 20:19
• Could you please add it to the tips? g=h@# is a keeper! Jan 26 at 8:22
• @Roman I just realized that I jumped the gun on how applicable it is - Clear still has its use cases. Whoops (still works here, though).
– att
Jan 27 at 2:32

BQN, 19 bytes

⌈´·{⟨⟩:0;1+𝕊⊑⊸↓𝕩}¨↓


Anonymous function that takes a list of integers and returns an integer. Run it online!

Explanation

⌈´·{⟨⟩:0;1+𝕊⊑⊸↓𝕩}¨↓
↓  Get the suffixes of the input list
{            }¨   Apply this function to each of them:
⟨⟩:0                If the argument is an empty list, return 0
;               Else:
𝕩         Take the argument
⊸↓          Drop a number of elements from it
⊑            equal to its first element
(If there aren't that many elements, the result is empty)
𝕊             Call this function recursively with that shorter list
1+              Add 1 to the result of the recursive call
⌈´·                  Get the maximum of the resulting list of integers


For example, with input ⟨1,1,9,1,1⟩, the suffixes are ⟨⟨1,1,9,1,1⟩, ⟨1,9,1,1⟩, ⟨9,1,1⟩, ⟨1,1⟩, ⟨1⟩, ⟨⟩⟩. When the inner function is called with the suffix ⟨1,9,1,1⟩:

• ⟨1,9,1,1⟩ is not empty, so drop the first 1 element and recurse
• ⟨9,1,1⟩ is not empty, so drop the first 9 elements and recurse
• ⟨⟩ is empty, so return 0
• Add 1 to 0 and return 1
• Add 1 to 1 and return 2

This is the number of skips that are possible starting from the second 1 in the original list.

Wolfram Language (Mathematica), 71 bytes

Max[l@Most@NestWhileList[#+w[[#]]&,#,#<=l@w&]&/@Range@(l=Length)[w=#]]&


Try it online!

Pip, 30 24 bytes

FnRglAE:Uv<n|1+(lv-n)MXl


Takes the input numbers as separate command-line arguments. Attempt This Online!

Implements the spec somewhat directly. Still searching for a golfier approach.