La Fée Verte @Absinthe@qoto.org

@freemo well I will lay out the rules that are important to the project. It will be simple. Well, simple in that there are only a small subset of the rules addressed in the problem. :)

#toyprogrammingchallenge

I think I may have an idea for the problem this week. Who likes "Craps?" I will work on the specifics, and think of some additional what-ifs as well.

Here us my attempt in python:

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

@timorl something that comes to the eye, since you are constructing your point with the same function calls, why not make that part of the constructor as defaults? Something like :

Point(long double ix = dis(gen), long double iy = dis(gen))

Then you have the option of calling
Point().inCircle(); without creating unnecessary extra doubles.

If you return 1 or 0 instead of boolean, then you can simply :

inCircle += Point.inCircle();

Not sure if any of that makes too much difference. But I figured I would mention.

Okay, here is my try in python

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

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.