#toyprogrammingchallenge

Okay, here is another freebie.

This problem was asked by Amazon.

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.

@freemo I understand that the solution is the nth fib for any n when the choice is 1 or two at a time. And my guess is that it goes with a similar function for other numbers of stairs. I also know that for n stairs there is a summation of each number of permutations with repetition n , 1, 0 + n-1, 2,8 8 + n-2 , 3, 4 and so forth. But I don't understand why the fib() works?

@Absinthe Fibonocci sequence is just magic, accept it :)

Honestly I still try to understand its magic, and sometimes i get glimpses but I struggle with it too. I think if i get the bandwidth ill do the math on this one and maybe it will help us both understand.

Usually I dont have an instinct for fibonacci sequences in math until I am a step or two away from the derivation being complete.

@freemo

My starting thing was that for n =10 The summation of the permutations was of these:

n n1 n2
perm_cnt(10, 0, 10) 10! / (0!*10!)
perm_cnt( 9, 1, 8) 9! / (1!*8!)
perm_cnt( 8, 2, 6) 8! / (2!*6!)
perm_cnt( 7, 3, 4) 7! / (3!*4!)
perm_cnt( 6, 4, 2) 6! / (4!*2!)
perm_cnt( 5, 5, 0) 5! / (5!*0!)

But if you just sit down and do how many ways for 1 step, 2 steps, 3 steps, 4 steps... you see the 1, 2, 3, 5, 8... form.

@Absinthe well part of that would require you to understand the various ways the golden ratio is derived so that when you see similar patterns in math you might connect them. Those factorial fractions are getting a bit close to some forms like this

\[
\varphi=\frac{13}{8}+\sum_{n=0}^{\infty}\frac{(-1)^{n+1}(2n+1)!}{4^{2n+3}n!(n+2)!}
\]

@freemo Or magic as you said before :)

@Absinthe @freemo

The number of solutions can be found inductively.

One stair can be walked in exactly one way: a single one-step.

Two stairs can be walked in exactly two ways: a single two-step, or two consecutive one-steps.

Knowing the solutions for 1, 2, ..., N-1, we can divide the number of ways to walk N stairs into two classes: a one-step followed by any valid way of walking N-1 stairs, or a two-step followed by any valid way of walking N-2 stairs. These are mutually exclusive (no valid walk is a member of both classes) and exhaustive (any valid walk is a member of one of these classes) so we can simply add the number of members of each class: F(N) = F(N-1) + F(N-2).

As it happens, this is the definition of the Fibonacci numbers.

@khird @freemo

How's this look?
def N(x):
if (x < 0):
return 0
if (x == 0 or x == 1):
return 1
return N(x-1) + N(x-2)

def N135(x):
if (x < 0):
return 0
if (x == 0):
return 1
return (N135(x-1) + N135(x-3) + N135(x-5))

def NArr(x, arr):
if (x < 0):
return 0
if (x == 0):
return 1
return sum([NArr(x - i, arr) for i in arr])

def main():
for n in range(10):
print(n, N(n))

for n in range(10):
print(n, N135(n))

for n in range(10):
print(n, NArr(n, [1,3,5]))

if __name__ == "__main__":
main()

@Absinthe @freemo

That will find the answer eventually, but at the cost of exponential time complexity. N(40) calls N() recursively over 200 million times.