Grandma's game piece
- O(2ⁿ) · Legendary
- Full plan
- Python
- JavaScript
- recursion
- lists
- indexes
Problem
Grandma Chelo is playing with her grandkids on a board whose squares are numbered from 0 to length. The dice have already been rolled and the results are written down in order, but the piece, which starts on square 0, has not moved yet. With each roll, the piece moves forward or back exactly that many squares, whichever you choose, as long as it stays on the board. Grandma wants to know how many ways it can end up right on the goal, square length, after using every roll.
Write a function that takes rolls, a list of positive whole numbers (it may be empty), and length, a whole number from 1 up, and returns a whole number: how many ways there are. Two ways are different if on some roll one moves forward and the other moves back. Passing through the goal early is not enough: what counts is where the piece ends up. With rolls 3, 2 and 4 and length 5, the piece has to move forward 3, because moving back would take it off the board. With the 2 it can go to 5 or to 1. From 5, the 4 can only take it back to 1; from 1, the 4 takes it to 5. There is a single way: it returns 1. With four rolls of 1 and length 2 there are two: 0, 1, 0, 1, 2 and 0, 1, 2, 1, 2.
Examples
The first example
[3, 2, 4], 5 → 1
It passes the goal and comes back
[1, 1, 1, 1], 2 → 2
No way to do it
[2, 2], 5 → 0
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def game_piece(rolls, length):
passJavaScript
function gamePiece(rolls, length) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.
More O(2ⁿ) challenges
- Grandpa's spoonsrecursion · lists · indexes
- Lilavati's sumsrecursion · strings · indexes
- Mansa Musa's bags of goldrecursion · lists · indexes
- Modules on rocketsrecursion · lists · booleans · division
- Monday's operating roomsrecursion · lists · comparisons
- Spelling with elementsrecursion · strings · indexes