Moving Blog

This blog has now moved to: http://www.codeonaboat.com

Posted in Uncategorized | Leave a comment

So how many ways can you…

I get obsessive about math puzzles. Not crazy ones that will take some sort of Aryabhata to figure out but little interesting ones that require intuition and a little obsession to crack. Probability and its puzzles fall right in this zone and most often, books and courses will teach people the formulae but not really instill an understanding of why things work the way they do. So… I decided to put some information down in a post. It is mostly in the form of definitions of basic concepts and clarifications of what those basics really mean.

So here goes…

Universe

This is the set of things you have available to you, to choose from. So if you have a bag with 2 red balls and 3 green balls, then those 5 balls are your universe. If you have 10 kinds of candy bars from which you can choose, say 4, that set of 10 candy bars is your universe.

Events and Outcomes

Events are something you are trying to achieve at a higher level, and outcomes are the different ways in which you can achieve that higher level objective or event.

For example if a problem asks you to choose 3 vegetables out of a bag of 10 vegetables, the event is the picking of any 3 vegetables. The outcomes that go to make that event are however many more,

10C3 = 10!/(3! * 7!) = 120

to be precise.

Similarly if you are trying to pick out 2 Aces from a pack of 52 cards, your event is exactly that, picking out of any 2 Aces, where as the outcomes that enable that event are 6 in number,

4C2 = 4!/(2! * 2!)  = 6

“With Replacement” Vs. “Without Replacement”

If you have a universe of things to choose from (letters, numbers, balls, whatever…), and after you choose one of the things in the universe, you do not put it back into that universe, it’s called “Without Replacement”. If you do put it back, it’s called “With Replacement”. Another way to look at it is that you modify the universe every time you pick one thing in the “Without Replacement” case, and do reset the universe to what it was originally in the “With Replacement” case.

“Order Matters” or “Order Does not Matter”

In some problems, the order in which you extract things out of your universe is significant (think about a lottery number, the order of numbers picked is important). In some other cases, the order in which you extract things may not be important (think about the case where you need to pick 3 toys from a basket of toys – usually what order those toys will be picked out is not important).

Whether order is important or not is critical in determining how many ways (or more formally outcomes), there are to satisfy a certain event. To clarify this, lets say I have to figure out how I can extract the letters ‘A’ and ‘D’ from a universe, (‘A’, ‘B’, ‘C’, ‘D’). In other words, my event is the case where ‘A’ and ‘D’ have been extracted out from the universe. If order is important, the number of outcomes is 2 – (‘A’, ‘D’) and (‘D’, ‘A’). If order is not important, the number of outcomes is one, because we are not differentiating between the case where ‘A’ was picked first and ‘D’ last from the case where ‘D’ was picked first and ‘A’ last.

As a rule of intuition, when order is not important you have much fewer outcomes to satisfy the same event.

The Math

There really is not much math involved in this kind of problems; it’s really about understanding the question, and then imagining  and categorizing the solution. Once you have done that, to save time you can just use one of the existing formulae to give you an answer and save some time.

Factorial

n! = n * (n-1) * (n-2) * … 3 * 2 * 1

Permutations

If there is no replacement, and you care about the order in which you extract items out of your universe, then the number of ways, or outcomes, you have to extract `r` items from a universe containing `n` items is represented by the expression

nPr,

and can be computed as

nPr = n!/(n-r)!

Combinations

If there is no replacement, and you do not care about the order in which you extract items out of your universe, then the number of ways, or outcomes, you have to extract `r` items from a universe containing `n` items is represented by the expression

nCr,

and can be computed as

nCr = n!/(r! * (n-r)!)

As mentioned above, intuitively it should be clear that if you don’t care about the order of extraction, you will have much fewer outcomes. And this formula confirms that intuition.

Bringing it Together

Ok, with those basics under your belt, lets try an example that brings together many of these concepts.

Question

If a menu has 10 different dishes available, and any customer is allowed to choose 4 of them, how many combinations of dishes must the chef be prepared to make, in each of the following scenarios.

  1. If the customer can choose a dish only once, and the order they pick the dishes in is relevant (meaning “Wonton soup, Lomein, Pot  Sticklers, and General Tso’s Chicken” and “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup” are to be regarded as 2 separate combinations).
  2. If the customer can choose a dish only once, and the order they pick the dishes in is irrelevant (meaning “Wonton soup, Lomein, Pot  Sticklers, and General Tso’s Chicken” is the same as “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup”; the order is irrelevant).
  3. If the customer can choose a dish multiple times, and the order they pick the dishes in is relevant (meaning “Wonton soup, Lomein, Pot  Sticklers, and General Tso’s Chicken” and “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup” are to be regarded as 2 separate combinations).
  4. If the customer can choose a dish multiple times, and the order they pick the dishes in is irrelevant (meaning “Wonton soup, Lomein, Pot  Sticklers, and General Tso’s Chicken” is the same as “Lomein, Pot Sticklers, Genral Tso’s Chicken and Wonton Soup”; the order is irrelevant).

Answer

Before getting into each case, lets look at the question as a whole. The following is a break up of what’s supplied as a part of the question:

Universe: The set of 10 dishes

Event: The picking of 4 dishes

When the customer can pick one dish only once, it’s really a way to say there is no replacement. When the customer can pick the same dish multiple times, its a way of saying that there is replacement.

Ok, now lets look at each case

    1. This is simply the number of permutations in which 4 things can be picked from 10.
10P4 = 10!/(10-4)! = 5040
    1. This is simply the number of combinations in which 4 things can be picked from 10.
10C4 = 10!/(4! * (10-4)!) = 210
    1. Since there is replacement here, or in other words the customer can pick the same dish one, two, three or four times, we have many more ways in which 4 dishes can be picked. Also order is relevant, meaning every different combination is valid. So the total number of ways that 4 dishes can be picked out of 10 is
10 * 10 * 10 * 10 = 10,000

Basically at every point you have the option of picking any of the 10 dishes and you have 4 of these opportunities.

    1. This is the most interesting of the 4 scenarios. Like in (c) you have 10 dishes to choose from all 4 times. However order is not relevant and hence those outcomes where the same things were picked have to be eliminated. Lets start with the answer we have in (c), 10,000. If from those you delete all outcomes that included a dish only once treating order as relevant (a) and then add back the outcomes that included a dish only once treating order as irrelevant (b) you get the following:
10,000 – 10P4 + 10C4
=> 10,000 – 10!/6! + 10!/(4! * 6!)
=> 5170

However, in that total you still have the outcomes are the same (though their order of dishes is different) that included 1 repeat, 2 repeats and 3 repeats, and they need to be removed from that total. If you figure that one out, post the solution in a comment!

Here’s a bonus question, and something I will probably ask you if I ever interview you for a software engineering position. (Don’t worry, i’ll be able to figure out whether you knew it before hand :-) )

A spider eats at most 3 flies a day, and stops trying to catch more flies once he has eaten 3 for the day. Until he fills his quota, he has a 50% chance of catching any fly that pass by his web. What are a fly’s chances of survival, given that five 5 have passed by the spider’s web today?

Posted in logic, math | Tagged , , | Leave a comment

Netflix should tie up with Movie Theaters

I love watching movies, and in New York City, where I live, the cost of watching one movie in a theater is around $13-$15. For two people, that’s almost $30, and if you have a family of four, that’s pretty darn pricey.

No wonder lesser and lesser people are “going to the movies”. Well, there are other reasons too I guess. Home theater systems for one, but I don’t know if their penetration has reached the point that they are causing the masses to stay home. Shitty movies might be another, but shittyness doesn’t have that great a track record of keeping the masses away from anything. I mean we have this and this! Maybe piracy? Now that’s a whole new conversation, but at the end of the day I do believe; provide something compelling and people will pay (a little).

I was in a bus passing by the United Artists Theater on 1st Ave & 85th St, and its currently playing Black Swan, and thought hmm, it would be good to get off the bus and go watch it until my impulse to not pay $30 to some production house kicked in. You can argue if that is justified, but afford it or not, it doesn’t pass my cost-benefit analysis-o-meter!

So here’s my idea; I googled it a bit and doesn’t seem like its been talked about publicly. Netflix, feel free to steal and implement it. Okay, maybe not really. If it works, I would like 50% of the profits. Just putting it out there in the universe, you never know what sticks!

I currently pay somewhere around $10 to get one DVD at home and unlimited streaming of the movies available for instant watching. Pretty good deal, as my cost-benefit analysis-o-meter tells me. Charge me $20, if you can also give me the ability to go to a theater and pay a small amount, say $5 and see a movie.

There are currently around 20 million Netflix subscribers in the US and Canada, and here is how much the top grossing movies of 2010 made. Table copied from here.

Rank Movie Title (click to view) Studio Total Gross /Theaters Opening / Theaters Open Close
1 Toy Story 3 BV $415,004,880 4,028 $110,307,189 4,028 6/18 12/2
2 Alice in Wonderland (2010) BV $334,191,110 3,739 $116,101,023 3,728 3/5 7/8
3 Iron Man 2 Par. $312,433,331 4,390 $128,122,480 4,380 5/7 8/19
4 The Twilight Saga: Eclipse Sum. $300,531,751 4,468 $64,832,191 4,468 6/30 10/21
5 Harry Potter and the Deathly Hallows Part 1 WB $292,890,256 4,125 $125,017,372 4,125 11/19 -

So i’m not really a finance guy but maybe there is a way to make the numbers work here. Infact, there will probably be a lot of interest in such an offer, even at a higher price point, say $30. Besides it will create economic activity that could be tied back to Netflix, and the movie business in the long run.

I don’t care about the shitty butter covered corn and sugar they serve at the theater, and yea, noisy idiots do bother me, but i’ll figure that one out. However, I do love to watch movies on the big screen, and will jump at this offer. Hopefully many others will too.

Finally I would like to say that these opinions are solely mine and I do own a minuscule amount of stock in Netflix, so if their share price was to increase because of this post, maybe I will go and watch a couple more movies at the local theater.

Posted in business, ideas | Tagged , , | Leave a comment

Invoking the DELETE verb with the Mootools Request.JSON class

Recently, I was trying to use the DELETE verb on a URL (using the MooTools Request.JSON class), and found (using Firebug) that the even though I was invoking the request correctly, the actual request going out was a POST. The code looks something like this.

var req = new Request.JSON(
{
    method: “DELETE”,
    url: url,
}); 

req.addEvent("failure", failurefn);
req.addEvent("success", successfn);
req.send(args);
On debugging I found that the following piece of code in the MooTools library’s Request class (which is the base class for Request.JSON)
if (this.options.emulation && !['get', 'post'].contains(method)){
    var _method = '_method=' + method;
    data = (data) ? _method + '&' + data : _method;
    method = 'post';
}

was converting the DELETE request into a POST request, and adding the actual method (DELETE in this case as part of the POST data. It appears that if you want to send any other verb besides a GET or POST as the actual HTTP verb using the Request class, you must set the “emulation” option to false. This is documented in the MooTools documentation for the Request class.

image

The value of the emulation option defaults to true in the class. So my code now looks something like this (notice the emulation: false):

var req = new Request.JSON(
{
    method: method,
    url: url,
    emulation: false
}); 

req.addEvent("failure", failurefn);
req.addEvent("success", successfn);
req.send(args);

And everything works as expected.

Posted in Mootools, Uncategorized, web services | Tagged , | Leave a comment

NYC Startup Weekend

I recently attended the NYC Startup Weekend. Initially I was reluctant thinking it would be a waste of time, not productive etc, but I was surprised. It was an awesome experience, and after the chaos of Friday night, Saturday and Sunday were exciting days when I worked in a team of 5 people to come up with an interesting concept, and also picked up some Android/Java  programming.

Our idea “Sound Spot” got a shout out from the Technoverse Blog. Thank You!!

Overall the quality of  pitches was excellent and it was a learning experience through and through. Everything thing from what VCs look for, to how to appeal to an audience, to a completely new platform for development. I highly recommend attending one if possible.

Besides all this there was excellent food at the event (surprisingly I must admit). It was served by Organique. So good!!!

Posted in collaboration, Mobile, startup | Tagged , | Leave a comment

NAnt, NAntContrib & How can I use msbuild with NAnt?

I had a simple need…

I wanted to check if my NAnt .build file changes were correct before checking them into source control. We already have Cruise Control.NET setup and it works but I did not have any way to test my changes locally. So I thought I would install NAnt and try to test my changes.

So there I went… at first I googled my way to nant.sourceforge.net and found NAnt binaries. Downloaded them, unzipped them and tried to run nant.exe on my build file. Failed. Then I googled my way to discovering that I need something called NAntContrib because it has the definition of the task msbuild that I was using in my .build file. OK so I downloaded NAntContrib. But it wasn’t clear what I should do next. How could I tell nant.exe to load the definition of the msbuild task from NAntContrib binaries?

Anyway, I figured it out (we always do) but had to struggle and google my way around a lot of stuff to get to the point where I was able to run everything.

Here are simple instructions I wish I had. Hopefully they help you out if you’re stuck with the same issue.

What is NAntContrib?

From the NAntContrib readme.txt

“NAntContrib is the project for tasks and tools that haven’t made it into the main NAnt distribution yet or for whatever reason don’t belong there.”

How can I install NAnt and NAnt contrib on my machine?

1. Install NAnt

  • Get the latest Release from here: http://nant.sourceforge.net
  • You can just get the binaries in zip form and unzip on a folder in your machine (say c:\Program Files\nant)

2. Install NAntContrib

  • Get the latest release from here: http://nantcontrib.sourceforge.net
  • Again you can download the binaries in zip form and unzip into a folder in your machine (say c:\Program Files\nantcontrib)

How can I use tasks from NAntContrib in my NAnt?

I was trying to use msbuild which is a task to build a Visual Studio Solution (.sln) file. Here is how I got it to work.

This is how I defined my “build” target in the my .build file

<target name="build" description="Compiles the .Net solution">
      <!-- build the solution -->
      <echo message="Building ${project::get-name()} v${project.version}" />
      <!-- need nant.contrib.tasks.dll for msbuild -->
      <loadtasks assembly="C:/Program Files/nantcontrib/bin/NAnt.Contrib.Tasks.dll" />
      <msbuild project="mysolution.sln">
            <arg value="/p:Configuration=${target}" />
            <arg value="/p:Platform=Any CPU" />
            <arg value="/t:Rebuild" />
      </msbuild>
</target>

By adding the tag in there with the path to the NAnt.Contrib.Tasks.dll, I point nant to the dll to find the msbuild task and it just works.

The command line to run nant on the build file was as follows

c:\Projects\myproject>"c:\program files\nant\bin\nant.exe" -buildfile:mysolution.build build

This tells nant.exe to find mysolution.build in the current folder and execute the “build” target in it.

Posted in development tools | Tagged , , | 4 Comments

MooTools Request.JSON “success” event – Some Undocumented Behavior

Request.JSON is a simple extension of the Request class that MooTools provides for making HTTP request. According to the MooTools documentation for the Request.JSON class the handler for the “success” event will receive two arguments. The first one being the response JSON object, and the second, the response in text form. The signature of the handler function would then be something like this:

OnSuccess(responseJSON, responseText)

Now when a request is made without any arguments, like below

var req = new Request.JSON(
{
    method: method,
    url: url
});

req.addEvent("failure", failurefn);
req.addEvent("success", successfn);
req.send();

that is indeed the case. The success function gets the responseJSON and the responseText.

However if the request includes arguments, like so:

var req = new Request.JSON(
{
    method: method,
    url: url
});

req.addEvent("failure", failurefn);
req.addEvent("success", successfn);
req.send(args);

the 2 arguments to the success function are first the response JSON object and second the arguments (args) that were originally passed into the request. In other words the signature of the success function is like this:

OnSuccess(responseJSON, args)

I couldn’t find any mention of this in the MooTools documentation, and I think this might be a behavior of the underlying XmlHttpRequest object itself and not something introduced by the MooTools class.

Digg This
Posted in JavaScript, Mootools | Tagged , | 4 Comments