30
\$\begingroup\$

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

Task

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
\$\endgroup\$
2
  • \$\begingroup\$ May I take input as a list of suffixes? i.e., [[1],[1,1],[1,1,1]] \$\endgroup\$
    – hakr14
    Jan 22 at 23:46
  • 7
    \$\begingroup\$ @hakr14 No. You must make your own suffixes. \$\endgroup\$
    – Wheat Wizard
    Jan 23 at 0:01

21 Answers 21

11
\$\begingroup\$

05AB1E, 11 bytes

.sε.Γ¬.$]ζg

Try it online! or Try all cases!

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

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.

\$\endgroup\$
8
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

Vyxal G, 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.
\$\endgroup\$
6
\$\begingroup\$

Python 3, 61 57 54 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!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ 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 \$\endgroup\$
    – ovs
    Jan 22 at 12:36
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Jan 22 at 12:51
  • 2
    \$\begingroup\$ 53 bytes \$\endgroup\$
    – ovs
    Jan 22 at 13:13
  • \$\begingroup\$ 51 bytes \$\endgroup\$
    – DialFrost
    Jan 23 at 3:07
  • \$\begingroup\$ @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 \$\endgroup\$
    – AnttiP
    Jan 23 at 7:25
6
\$\begingroup\$

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):

enter image description here

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

Wolfram Language (Mathematica), 71 70 68 64 62 52 50 47 bytes

A|->Max[i=0;#0@@Check[!#+A[[#]],-1]+1&@++i&/@A]

–3 thanks to att!

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 47 bytes \$\endgroup\$
    – att
    Jan 22 at 20:05
4
\$\begingroup\$

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

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
\$\endgroup\$
5
  • \$\begingroup\$ Is there any online link to run this? \$\endgroup\$ Jan 22 at 22:40
  • \$\begingroup\$ @DominicvanEssen Not yet. There has been a proposal to add Nibbles to ATO, but I have no idea what the progress on that is :/ \$\endgroup\$
    – xigoi
    Jan 22 at 22:55
  • \$\begingroup\$ Current ATO works in progress from the repo are Vyxal only, it seems. Probably requires a new issue for Nibbles. \$\endgroup\$
    – Razetime
    Jan 23 at 6:08
  • \$\begingroup\$ @DominicvanEssen you can run latest Nibbles on golf.shinh.org , but adding your own input to it may not be easy. \$\endgroup\$
    – Razetime
    Jan 23 at 6:09
  • \$\begingroup\$ @Razetime chat.stackexchange.com/transcript/message/60076726#60076726 \$\endgroup\$
    – xigoi
    Jan 23 at 8:28
3
\$\begingroup\$

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).

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

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

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.

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

Charcoal, 30 bytes

F⌈θ⊞θ⁰F⮌…Lθ§≔θι∧§θι⊕§θ⁺ι§θιI⌈θ

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

F⌈θ⊞θ⁰

Append sufficient zeros so that we never jump off the end of the array.

F⮌…Lθ

Iterate over the array in reverse order.

§≔θι∧§θι⊕§θ⁺ι§θι

Update each non-zero element with 1 more than the number of skips of its next skip.

I⌈θ

Output the maximum number of skips.

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

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.

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

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.

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

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.

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

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

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

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[_])
\$\endgroup\$
4
  • 2
    \$\begingroup\$ 40 bytes \$\endgroup\$
    – Roman
    Jan 25 at 10:08
  • 1
    \$\begingroup\$ @Roman Probably every answer where Clear's been used before can be improved in the same way. Thanks :) \$\endgroup\$
    – att
    Jan 25 at 20:19
  • \$\begingroup\$ Could you please add it to the tips? g=h@# is a keeper! \$\endgroup\$
    – Roman
    Jan 26 at 8:22
  • \$\begingroup\$ @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). \$\endgroup\$
    – att
    Jan 27 at 2:32
2
\$\begingroup\$

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.

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

Wolfram Language (Mathematica), 71 bytes

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

Try it online!

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

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.

\$\endgroup\$

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.