La Fée Verte @Absinthe@qoto.org

@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(

@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.

@khird @freemo

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)

@remulacfrommars if live gives you melons... you might be dyslexic :)

@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()

@freemo Or magic as you said before :)

@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.

@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?

#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 @serra I am trying here. It is tough thinking up new challenges especially if they have to be doable by those starting out as well as PhD experts and theoreticians :)

@freemo @serra Solved the math problem, but it still leaves a cool programming challenge, and a funky word challenge besides :)

Whose to say my solution is the only viable one? Just saying.

@serra @freemo No, that would make things impossible because the solution involving a base smaller than 10 would require places longer for similar numbers.

That aside, the real problem comes from translating into base(6) for the first 6 chars, then coming up with a permutation based value for all 4 of the last 4 of the word.

So simply creating a price and converting it to a base(6) representation, with capital letters as whole numbers and lower case as the right of the decimal, avoids having to use a decimal point character. Then having a 4 character code that can represent a discount or premium following that would do it.

@freemo @serra right, but I never said that. I said you choose a 10 character isogram. so you have 10 unique characters.

@serra @freemo well in that case I challenge you to do a simple encoder/decoder for it.

I think the base(6) for the price and a permutation of the remaining letters to handle 100% 10%, 15%, 30% discount (and premium if you like)

I see Capital letters as whole numbers and lower case as decimals.

But the test should be, making a bunch of prices. Then changing the isogram and decoding them to their different discount values. Extra points if the whole isogram is a word, and if each of the permuted anagrams are also words (or at least pronounceable)

@freemo @serra I think we could make it easier by saying the new word would effect a premium or discount across the store. With what I did, one could simply not put the second part on the tag and then the price would be firm and not subject to discounts. One of our local thrift stores does it with colored tags. But I digress. :)

#toyprogrammingchallenge

Here's a freebie,

This problem was asked by Airbnb.

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?