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.
🇳🇱
discussion of solution
@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.
discussion of solution
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.
discussion of solution
@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)!}
\]
discussion of solution
@freemo Or magic as you said before :)
Try to write your program before reading this - it also covers the arbitrary-set case.
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.
Try to write your program before reading this - it also covers the arbitrary-set case.
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()
@khird @freemo I was trying to illustrate what you described.
However, I don't have my stack turned up so I have maximum of 1000-3 levels of recursion. Are you sure about the 200 million? It can get slow, but even at 40 it didn't blow the stack.
Anyway, I would use Phi if I were interested in getting a specific fib value, If I could feel comfortable with the concept that the nth fib number is equal to the number of ways up an n step stair case, then that would be my solution. However, not sure how to apply that to the 1,3,5 problem.
Yeah I worked it out to about 204 million. To clarify - all 200 million aren't on the stack simultaneously; imagine a binary tree 40 levels deep with 200 million nodes - you're never more than 40 steps away from the root node but visiting all nodes still takes a long time.
I don't understand your uncertainty about the 1,3,5 problem - doesn't NArr() apply the same concept to an arbitrary array of integers? What's left to do after that?
@khird @freemo I am satisfied that all of these functions solve the original question. So merely accepting that the fib sequence solution works those functions do it. However, originally when I was trying to solve it, I did so by calculatng the different combinations then the permutations thereof. I see how to do that with the fib sequence calculation the way you illustrated, but not the way I originally came up with it and tryign to apply an arbitrary array is not quite comig to me.
@khird @freemo Sure! For clarity let me choose 10 instead of talking about N as it feels more natural.
So if you have 10 steps and you are going to walk them one step at a time. You have exactly 1 way to do it. But that is really a permutation calculation (permutation with repetition to be specific) So you are looking at 10! / (10!*0!) Which comes out to one.
If you are going to do only one 2 step and all the rest are 1. Then you are looking at taking 9 leaps. 8 for 1 and 1 for 2. When you calculate the permutation with 2 different values that is where the bottom numbers come from:
So now we have (total leaps = 9)
9! / (8! * 1!) <-- 8 one's an 1 two That comes out to 9 ways.
As you keep adding 2 step leaps you reduce the number of leaps. So 8 has 2 2 step leaps and 6 ones, and 7 has 3 twos and 4 ones looks like 7! / (4! * 3!) Eventually it goes all the way to 5 which no longer needs any 1 steps and it is all 2 step leaps so it looks like 5! / (5! * 0!)
So when you add all these together you get all the different ways to go up the stairs.
If I want to do this with 1,3,5 I start off with a table like this:
N ones threes fives
10 10 0 0
8 7 1 0
6 4 2 0
6 5 0 1
4 1 3 0
3 2 1 1
2 0 0 2
I would have to calculate 10!/10!*0!*0! and add that to 8!/7!*1!*0! ... and so on down the sum of all them is the number of ways with those three numbers.
Any of that make sense? When I did the one NFact() I saw what the pattern looked like and implemented it accordingly. Not sure how to do it for arbitrary list on the fly.
@Absinthe Your approach makes more sense now. Generating that table for an arbitrary combination of numbers and sum is a hard problem: stackoverflow.com/questions/4632322
There happens to be a nice closed-form solution for "ones" and "twos" when X = {1, 2}, so it's convenient for that specific case but I don't think it will generalise nicely.
@khird so I just tried to do the 1,3,5 and somehow I am coming up 9 short. So I think I missed something in my table but here, maybe a second set of eyes:
def NFact135():
def fact(x):
_fact = 1
for i in range(1, x+1):
_fact = _fact * i
return _fact
# Leaps Ones threes fives
return (fact(10) // ( fact(10) * fact(0) * fact(0) ) +
fact(8) // ( fact( 7) * fact(1) * fact(0) ) +
fact(6) // ( fact( 4) * fact(2) * fact(0) ) +
fact(6) // ( fact( 5) * fact(0) * fact(1) ) +
fact(4) // ( fact( 1) * fact(3) * fact(0) ) +
fact(3) // ( fact( 2) * fact(1) * fact(1) ) +
fact(2) // ( fact( 0) * fact(0) * fact(2) ) )
I believe the penultimate line should begin with fact(4) rather than fact(3).
@khird Thanks! that did it. Who know I couldn't add 2+1+1 ... that usually comes out to 4 on a good day :)
@khird but hey, it's not about getting the right answer, but how you solve the problem :)
@khird @freemo the NFact() function, which was my original design of calculating/counting the permutations seems pretty snappy. I just goosed it up to 1000 and it slows down as it fills the screen with crazy big numbers still seems to run just fine and doesn't blow the )stack. Definitely faster than any of the N(), N135(), or NArr(
Try to write your program before reading this - it also covers the arbitrary-set case.
Okay, so with all that, here is the actual longhand using the permutations, but I am not sure how to handle this if I passed an array of numbers like in the 1,3,5 example
def NFact(x):
def fact(x):
_fact = 1
for i in range(1, x+1):
_fact = _fact * i
return _fact
def r_NFact(num):
twos = x - num
ones = x - (2 * twos)
if ones < 0:
return 0
return r_NFact(num - 1) + ( fact(num) // (fact(ones) * fact(twos)))
return r_NFact(x)
Octave solution
This implementation uses memoization, resulting in a space complexity linear in K and time complexity linear in K*|X| for some K between 1 and N inclusive.
function count = step_orders(distance, permissible_steps = [1, 2])
memos = sparse(distance, 1);
hits = (memos ~= 0);
count = step_orders_stateful(distance);
function sub_count = step_orders_stateful(sub_distance)
sub_count = 0;
for first_step = permissible_steps
remainder = sub_distance - first_step;
if remainder > 0
if ~hits(remainder)
memos(remainder) = step_orders_stateful(remainder);
hits(remainder) = true; end;
sub_count += memos(remainder);
elseif remainder == 0
sub_count += 1; end; end; end; end;
discussion of solution
@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?