Count stair-climbing routes that avoid broken steps
A platform game has a staircase level. The hero starts on the ground (step 0) and must reach step n. Each jump climbs one of the allowed step sizes, and some steps are broken: landing on one sends the hero back to the start, so those jumps are never allowed. The level designer wants to know how many different routes exist for each layout.
Implement countClimbs(n, stepSizes, broken), which returns the number of distinct jump sequences that land exactly on step n without ever landing on a broken step.
countClimbs(n, stepSizes = [1, 2], broken = []) // => number
n is a non-negative integer. With n = 0 the hero is already at the top, which counts as one route (the empty sequence).stepSizes holds distinct positive integers in any order. A jump of size s from step i lands on step i + s. Jumping past n is not allowed.broken holds step numbers between 1 and n; duplicates are allowed. A route may jump over a broken step but never land on it. If step n itself is broken, the answer is 0.1 then 2 and 2 then 1 are different routes.n can be up to 80. Answers in the tests fit in Number.MAX_SAFE_INTEGER. Trying every route one by one is far too slow.countClimbs(4); // => 5 (1111, 112, 121, 211, 22)
countClimbs(5, [1, 2], [2]); // => 2 (0→1→3→4→5, 0→1→3→5)
countClimbs(7, [2, 3], [4]); // => 2 (2+3+2, 3+2+2)
countClimbs(6, [1, 3, 5]); // => 8
countClimbs(5, [2]); // => 0 (odd height, even jumps)
countClimbs(3, [5, 3]); // => 1 (a single jump of 3)
countClimbs(0); // => 1
countClimbs(4, [1, 2], [4]); // => 0 (the top is broken)