Leap Frog Solution



Abi and Maddy enjoy going to school at ECDC. Besides reading poems, drawing pictures, and singing songs, the girls are learning about numbers. To make this discovery more exciting, the teachers decide to play a variant of the classic Leap Frog game:

Each child is placed in a line and is given a non-negative number. This number represents up to how many spaces someone can jump from that position (always moving to the end of the line). The game is played by one new student jumping to the first position. Then, the current student at that position must jump to a new position based on their number (ie. given the number n they can jump up to npositions from their current place). Once this jump happens, the process is repeated until either no further jumps are possible.

For instance, suppose there are five children with the following numbers:

2 3 1 1 4

In this case, a child moves to the first position forcing the child there to make a jump. This child can jump up to 2 spaces and thus reach the third position. From there, the next child can jump 1space to the fourth position. Finally, the proceeding child can jump 1 space to the final position and which forces the last child out of the line.

On the other hand, suppose the five children have the following numbers:

3 2 1 0 4

In this case, all children will eventually reach the fourth position. From this spot, they can only jump 0 spaces (ie. not jump at all), so they will never reach the final position.

Because this game involves a lot of numbers and the children are tired of actually jumping over their classmates, they once again ask “daddy’s students” to come up with a program that can programmatically determine if it is possible to make it to the end of the line and force the last child out.


You will be given a series of lines where each line consists of 1
<= N <= 1000
integers which correspond to how far each child can jump from that position.

Example Input

2 3 1 1 4
3 2 1 0 4


For each line of input, output “Yes” if the children can reach the last position. Otherwise, output “No”.

Example Output


Programming Challenges

This is based on the Jump Game problem on LeetCode.


To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge10               # Create and checkout challenge10 branch

$ $EDITOR challenge10/program.cpp           # Edit your code

$ git add challenge10/program.cpp           # Stage your changes
$ git commit -m "challenge10: done"         # Commit your changes

$ git push -u origin challenge10            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge10 assignment ...
Submitting challenge10 code ...
  Result Success
   Score 6.00
    Time 0.02

$ curl -F source=@challenge10/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge10
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 05 TA List to determine your corresponding TA for the merge request.