Stepping Stones Across the Pond
A garden pond has a straight line of n stepping stones. The last stone touches the far bank. A child stands on the near bank and crosses one move at a time. Each move is either a step onto the next stone, or a hop that skips one stone and lands on the stone after it.
She wants to cross a different way every day. How many different crossings are there before she has to repeat one?
Your task
Write countCrossings(n). Return the number of different sequences of steps and hops that start on the near bank and end exactly on stone n.
The near bank is position 0 and the stones are positions 1 to n. A step moves 1 position, a hop moves 2. Two crossings are different if their sequences of moves are different. She may not hop past stone n.
countCrossings(n: int) → int
Examples
n = 3
3
The three crossings are step-step-step, step-hop and hop-step. Step-hop and hop-step land on different stones on the way, so they count as two different crossings.
n = 5
8
No hops: step-step-step-step-step, 1 way. One hop: 4 moves in total, and the hop can be any of the 4, so 4 ways. Two hops: 3 moves, and the single step can be first, second or third, so 3 ways. Three hops would be 6 positions, past the last stone. 1 + 4 + 3 = 8.
Constraints
- 1 ≤ n ≤ 70
- The answer fits in a normal integer (it is below 10¹⁵ for n = 70).
Start with brute force
Write the rule as a recursive function: count(i) = count(i - 1) + count(i - 2), stopping at the bank. It is short and correct.
It is also exponential. count(70) calls count(69) and count(68), and count(69) calls count(68) again, and so on. The number of calls grows like the answer itself: hundreds of trillions for n = 70. The same few subproblems get solved over and over.
Hints
0 of 4 shown- Hint 1
Forget the whole crossing and look only at the very last move onto stone 5. Where could she have been standing just before it?
- Hint 2
She was on stone 4 (and stepped) or on stone 3 (and hopped). Those two groups never overlap, so the total is (ways to reach stone 4) + (ways to reach stone 3).
- Hint 3
That rule works for every stone:
ways(i) = ways(i - 1) + ways(i - 2). What are the starting values? There is exactly 1 way to be on the bank (do nothing) and 1 way to reach stone 1. - Hint 4
Fill the answers from stone 1 upward instead of recursing down. Each value only needs the two before it, so two variables are enough. Avoid plain recursion: for n = 70 it recomputes the same stones trillions of times.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Counting whole crossings directly is messy. Counting by the last move is easy: every crossing that ends on stone i either stepped from i - 1 or hopped from i - 2. So ways(i) = ways(i - 1) + ways(i - 2).
Fill a small table for n = 5, left to right:
- Bank: 1 way (you are already there). Stone 1: 1 way (one step).
- Stone 2: 1 + 1 = 2 (step-step, hop).
- Stone 3: 2 + 1 = 3.
- Stone 4: 3 + 2 = 5.
- Stone 5: 5 + 3 = 8.
Each entry is computed once, from two entries you already have. That is the whole difference from the recursive version, which recomputes stone 3 many times. Since each step only looks two entries back, you can keep just two variables instead of the full table.
function countCrossings(n) {
let twoBack = 1; // ways to be on the bank (position 0)
let oneBack = 1; // ways to be on stone 1
for (let i = 2; i <= n; i++) {
const here = oneBack + twoBack; // last move was a step or a hop
twoBack = oneBack;
oneBack = here;
}
return oneBack;
}def count_crossings(n):
two_back = 1 # ways to be on the bank (position 0)
one_back = 1 # ways to be on stone 1
for _ in range(2, n + 1):
# last move was a step (from i - 1) or a hop (from i - 2)
two_back, one_back = one_back, one_back + two_back
return one_backRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.