RE: [algorithms-and-data-structures] Algorithms Meetup Problem #3

From: Kervin P.
Sent on: Sunday, September 5, 2010 5:45 PM

I don’t have python installed.  Can someone post the first 10 or 20 numbers in the sequence generated by the python solution?

 

Best regards,

Kervin

 

 

Adevsoft Web Development

http://adevsoft.com/

 

From: [address removed] [mailto:[address removed]] On Behalf Of Nurettin DAG
Sent: Sunday, September 05,[masked]:40 PM
To: [address removed]
Subject: Re: [algorithms-and-data-structures] Algorithms Meetup Problem #3

 

I guess I was not clear on the formula  (m+n)! / m! * n! but I now recall from the probability course that it is the formula to calculate number of combinations of m and n distinct items.

Thanks Hugh for the explanation.
Nurettin

On Sun, Sep 5, 2010 at 4:22 PM, Hugh Brown <[address removed]> wrote:

Nurettin,

Think of a vertical block as a 1 and each pair of two stacked horizontal blocks being a 0. How many binary numbers can you create with n-blocks?

In the first two cases, it's obvious that you have these:

1 (all vertical) = fact(n)/(fact(n)*fact(0))
n-1 (n-2 ones and 1 zero) = fact(n-1)/(fact(n-2)*fact(1))

Each time you take two blocks out to make a zero, you have one more zero and two fewer ones. So the answer is the summation of
fact(n-y)/(fact(n-2*y)*fact(y)
for y in the range 0 to n // 2.

I think the code could be written more succinctly as:



def count_brick_configs(x):

        return sum(factorial(x - num_b) / (factorial(x - 2 * num_b) * factorial(num_b)) for num_b in range(1 + x // 2))




= fact(n-2)/(fact(x-4)*fact(2))




Hugh Brown
137 West 82nd Street, Apt. 5A
New York, NY[masked]
[masked]
[address removed]

http://www.IWebThereforeIAm.com/



--- On Sun, 9/5/10, Nurettin DAG <[address removed]> wrote:


From: Nurettin DAG <[address removed]>
Subject: Re: [algorithms-and-data-structures] Algorithms Meetup Problem #3
To: [address removed]
Date: Sunday, September 5, 2010, 11:49 AM

I found this too be a little tough. I have seen the solutions submitted but not sure if they are correct.
Recursive solution is based on
f(n) = f(n-1) + f(n-2);
f(0) = 0; f(1) = 1; f(2) = 2;

Formula seems to be working fine until n = 5 but I did not want to spend the time to manually calculate values after 6. Can someone elaborate on it?

Other solution submitted is based on a different algorithm

def count_brick_configs (x):
 
 

    if (x == 0):
        return 0
    
    max_b = x / 2

    retval = 1
    for num_b in range (1, max_b + 1):
        num_a = x - (2 * num_b )
        alphabet_len = num_b + num_a

        retval += factorial(alphabet_len) / ( factorial(num_a) * factorial(num_b))
    return retval


It would be nice to hear what this formula is based on. Thanks

On Sun, Jul 25, 2010 at 8:25 PM, Deepankar <[address removed]> wrote:

Okay Ive pushed a hopefully correct solution. Would be great to tie it
out with answers from other peoples solutions.


On Sun, Jul 25, 2010 at 6:37 PM, Deepankar <[address removed]> wrote:
> Just noticed a mistake in my solution - please disregard the current code.
>
> On Sun, Jul 25, 2010 at 6:21 PM, Deepankar <[address removed]> wrote:
>> Added the solution to this in python. the language hardly matters on
>> this one, its about analysing and coming up with an equation which you
>> can then implement in any language.
>>
>>
>> On Sun, Jul 25, 2010 at 3:20 PM, Andy Pliszka <andy+[address removed]> wrote:
>>> Hi,
>>>
>>> It is time for another problem of the week. The problems comes from
>>> UVa's database of problems. You can find problem description here:
>>>
>>> http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=841
>>>
>>> Just a reminder, we have a github code reposotory:
>>>
>>> http://github.com/AlgorithmsNYC/AlgorithmsNYC
>>>
>>> If you would like to share your solution; send me your github profile
>>> name, and I will add you to the repository.
>>>
>>> I also create a Facebook page:
>>>
>>> http://www.facebook.com/pages/Algorithms/111759635509475#!/pages/Algorithms-and-Data-Structures/[masked]?v=wall&ref=ts
>>>
>>> We also have a Twitter account:
>>>
>>> http://twitter.com/algorithmsnyc
>>>
>>> Please, follow our Twitter account, so we can follow each other.
>>>
>>> Thanks,
>>> Andy
>>>
>>>
>>>
>>> --
>>> Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
>>> http://www.meetup.com/algorithms-and-data-structures/
>>> This message was sent by Andy Pliszka (andy+[address removed]) from Algorithms and Data Structures.
>>> To learn more about Andy Pliszka, visit his/her member profile: http://www.meetup.com/algorithms-and-data-structures/members/11339609/
>>> To unsubscribe or to update your mailing list settings, click here: http://www.meetup.com/algorithms-and-data-structures/settings/
>>> Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]
>>>
>>>
>>
>>
>>
>> --
>> Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
>> http://www.meetup.com/algorithms-and-data-structures/
>> This message was sent by Deepankar ([address removed]) from Algorithms and Data Structures.
>> To learn more about Deepankar, visit his/her member profile: http://www.meetup.com/algorithms-and-data-structures/members/2125491/
>> To unsubscribe or to update your mailing list settings, click here: http://www.meetup.com/algorithms-and-data-structures/settings/
>> Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]
>>
>>
>
>
>
> --
> Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
> http://www.meetup.com/algorithms-and-data-structures/
> This message was sent by Deepankar ([address removed]) from Algorithms and Data Structures.
> To learn more about Deepankar, visit his/her member profile: http://www.meetup.com/algorithms-and-data-structures/members/2125491/
> To unsubscribe or to update your mailing list settings, click here: http://www.meetup.com/algorithms-and-data-structures/settings/
> Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]
>
>



--
Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
http://www.meetup.com/algorithms-and-data-structures/
This message was sent by Deepankar ([address removed]) from Algorithms and Data Structures.
To learn more about Deepankar, visit his/her member profile: http://www.meetup.com/algorithms-and-data-structures/members/2125491/
To unsubscribe or to update your mailing list settings, click here: http://www.meetup.com/algorithms-and-data-structures/settings/
Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]




--
Nurettin DAG




--
Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])

This message was sent by Nurettin DAG ([address removed]) from Algorithms and Data Structures.
To learn more about Nurettin DAG, visit his/her member profile


To unsubscribe or to update your mailing list settings, click here

Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]





--
Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])

This message was sent by Hugh Brown ([address removed]) from Algorithms and Data Structures.
To learn more about Hugh Brown, visit his/her member profile


To unsubscribe or to update your mailing list settings, click here

Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]




--
Nurettin DAG




--
Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
This message was sent by Nurettin DAG ([address removed]) from Algorithms and Data Structures.
To learn more about Nurettin DAG, visit his/her member profile
To unsubscribe or to update your mailing list settings, click here

Meetup, PO Box 4668 #37895 New York, New York[masked] | [address removed]

Our Sponsors

  • Pivotal Labs

    Pivotal Labs

  • Vendavo

    Vendavo is the leader in front-line profit optimization

  • Wolfram Research

    Mathematica is the world's ultimate application for computations.

  • Yodle

    Local online advertising for small businesses.

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy