La Fée Verte @Absinthe@qoto.org

Here is my attempt in python

https://git.qoto.org/Absinthe/montecarlopi

I tried it basing on a sample size of attempts, and also trying until I got so many successful points in circle.

@timorl while discussing this with an associate, he suggested waiting for a place to 'calm down'. In general you would keep going until it stopped mirroring and that might be as far as it might be able to go

#toyprogrammingchallenge

Here's another freebie, but I am not really sure how to solve it. Guess I wouldn't be getting that job at Google :)

This problem was asked by Google.

The area of a circle is defined as πr^2. Estimate π to 3 decimal places using a Monte Carlo method.

Hint: The basic equation of a circle is x2 + y2 = r2.

#toyprogrammingchallenge

Here's a fun freebie! Only because I just recently saw a problem similar :)

This problem was asked by Facebook.

Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.

@freemo @khird like how do you know to type :
\ [
\ binom {n}{k} = \ frac(n!){k! (n-k)!}
\ ]

@khird so I d/l octave hopefully I will get to run some of your stuff soon

@freemo @khird I don't think I can do that on Tusky, and I am not sure I know how to do it on the desktop.

Also, that is for combination rather than permutation isn't it? Wouldn't I need the one with the big P and the little n over the little k? But I am not sure how to make that on the input here

@freemo @khird how would I do that? I mean syntactically?

#toyprogrammingchallenge

Here's another freebie:

This problem was asked by Amazon.

Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".

@khird but hey, it's not about getting the right answer, but how you solve the problem :)

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

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

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