Store Credit - Google Code Jam 2010

Here is a solution for Google's Code Jam 2010 Store Credit problem.

In Python the code is very simple. It is a brute force kindda solution.

if __name__ == "__main__":
   
    fin = open('storeInput.inp','r')
    inputdata = fin.readlines()
    fin.close()
   
    it = iter(inputdata)

    numTestCases = int(it.next())
   
    fout = open('storeOutput.txt','w')

    for i in range(1,numTestCases+1):
        str1 = "Case #%d: " %(i)
        fout.write(str1)
       
        mycredit = int(it.next())
       
        num_items = int(it.next())

        items_cost = [int(y) for y in it.next().split()]
       
        found = False
        for j in range(len(items_cost)-1):
            if found:
                break
            for k in range(j+1,len(items_cost)):
                if((items_cost[j]+items_cost[k])==mycredit):
                    fout.write(str(j+1) + " "+ str(k+1) + "\n")
                    found = True
                    break
    fout.close()

In C, code for the same process is as follows,

#include
#include

void process(FILE *fin, FILE *fout)
{
    int storeCredit,I,*p, i,iActual = 0,j;
    fscanf(fin,"%d",&storeCredit);
    fscanf(fin,"%d",&I);
   
    p = (int *)malloc(sizeof(int)*I);
    for(i=0;i   

    for(i=0;i < I - 1; i++)
      for(j = i+1; j < I; j++)
            if((*(p+i) + *(p+j)) == storeCredit)
            {
                fprintf(fout,"%d %d\n",i+1,j+1);
                i = I;
                break;
            }
    free(p);
}

int main()
{
    FILE *fin,*fout;
    int N,i;
    fin = fopen("storeInput.inp","r");
    fout = fopen("storeOutput.txt","w");
   
    fscanf(fin,"%d",&N);
    for(i=0;i    {
        fprintf(fout,"Case #%d: ",i+1);
        process(fin, fout);
    }

    fclose(fin);
    fclose(fout);
}

To make the C code, even faster, I tried another one using pthreads. I'll update that later.

Monty Hall Simulation

The Monty Hall probability  proof always baffled me. Read more in Wikipedia for the description.

But for those who don't know, and don't want to know the whole deal I'll give the tl;dr friendly version.

Assume that you're presented with 3 boxes (A, B, C) and are asked to choose one. One of them contains a prize. After you've chosen, I'll open an empty box from the other two. Now, you have the option of sticking together with your choice, or, you may change your choice. According to math, your chances of winning are more if you switch.

Let me explain in an easier way, you choose box B. Then I open box C and show that it is empty. Again, I ask you to choose between A and B. Are you better off by choosing A?

Common sense wrongly suggests that switching between A and B makes no difference. (probability remains 1/3rd - wrong intuition). Psychology makes us stay with B (people are reluctant to change). But, probability shows that switching produces a definite boost to our chance of winning - double!

Though I understood the math, I really wanted to verify.

So here is some crappy C simulation.

Let us not switch for 100 times and see how much we win.
Later, we'll switch for 100 times after choosing, and see how much we win.

Code:

#include
#include
#include

int doMontyNoSwitch();

int doMontySwitch();

int main(void)

{

        int choice = 0,i;

        int winCountNS=0,winCountS=0;

        //Seed the randomizer

        srand(time(NULL));

        //100 times without switching

        for(i=0;i<100;i++)

        {

                //Increment win count for no switch if we win

                if(doMontyNoSwitch() == 1) winCountNS++;

        }

        for(i=0;i<100;i++)

        {

                //Increment win count for switch if we win

                if(doMontySwitch() == 1) winCountS++;

        }

        printf("\nNS:%d S:%d",winCountNS,winCountS);

        return 0;

}

//Here we'll switch

int doMontySwitch()

{

        int r1,correct,choice,reveal,switchedChoice,i;

        r1 = rand()%3;

   

        //Let me randomly set the correct box/door

        correct = r1;

        //Choose randomly

        choice = rand()%3;

        for(i=0;i<3;i++)

        {

                //Show the door/box which does not contain the prize and what I didn't choose

                if(i!=correct && i!=choice)

                {

                        reveal = i;

                        break;

                }

        }

        for(i=0;i<3;i++)

        {

                //Reveal the box which was not chosen and the wrong one

                if(i!=choice && i!=reveal)

                {

                        //Change our choice her, that is, "the switch"

                        choice = i;

                        break;

                }

        }

        if(choice == correct)

        {

                //return 1 to indicate we've won here        

                return 1;

        }

        else

        {

                //return 0 to indicate we've lost here

                return 0;

        }

}

//Without switching

int doMontyNoSwitch()

{

        int r1,correct,choice,reveal,switchedChoice,i;

        r1 = rand()%3;

        correct = r1;

        choice = rand()%3;

        for(i=0;i<3;i++)

        {

                if(i!=correct && i!=choice)

                {

                        reveal = i;

                        break;

                }

        }

        if(choice == correct)

        {

                return 1;

        }

        else

        {

                return 0;

        }

}

So, when I compile and run this thrice,


NS:31 S:63
NS:32 S:62
NS:25 S:60

The probability is right. So right! Ideally it should have been 33 and 66, but it is so damn close, wow!


So, next time I'm going to switch no matter what!


By the way, the code above is not well designed or thought out, I'll work on it later....

Why Indian Railways Online Ticketing is so bad

I found another rant on the state of Indian Railways' online ticket booking website in Hacker News. It is horrible and here I am going to tell you why.

Monopoly

We may have cleartrip, makemytrip, and yatra, but, these services cannot book special tatkal tickets which are open only from 8:00 AM - 9:00 AM three days before the day of travel. For frequent travelers, this is the only type of ticket which matters.

So, even though other sites exists, IRCTC as such is a monopoly.

API Access

For getting the API access, the company needs to have been around for 3 years. All startups banned by default. Nice.

Anyway when you annually make $15M profit by being a monopoly you want the status quo...m and when the status quo is being a monopoly, you don't mind being a wreck...

Jesso busts a Madras Mom - Explaining the cnbc scam

One of my friends in facebook just put this on his status,

 "are you serious about starting your own business in 2011? you have to check this out - http://t.co/q4bfMkga"

Now, if you visit this link it takes you to "http://www.cnbc.com-id.us/t/?blabla=1?t=38627"

Which is CNBC, the CNBC we all know, or wait is it really???

Let me break the URL apart.

"http://www.cnbc.com-id.us/" Note the bold part. So, really the website is NOT cnbc.com

To be clear "http://www.cnbc.com-id.us/" is NOT EQUAL TO http://www.cnbc.com

Why not?

well the extension  -id.us shows us that it is something like http://developers.facebook.com. So, facebook could similarly very well have something like google.com.facebook.com/ It would still belong to facebook. Things don't end at .com, if that is not the last thing in the address bar.

So google has something like mail.google.com, that is mail in google's domain. Similarly google could have named google plus as facebook.com-google.com!!! It would go to google's servers.

The scam site is really *cnbc* in "com-id.us" domain. Well, this is the one line which really matters...
To make the scam complete all the hyperlinks point to the real cnbc.com BUT all the links which are related to the scam go to http://www.cnbc.com-featured.us/

But for people who took so much pain, the real joke is Patrica Feeney - Madras Mom, come on, how about Chennai Mom, Ooops, I'm sorry I just found out that there is some Madras in Jefferson County in Oregon, but to find other Chennai guys dreaming of making big bucks sitting in your home or just dreaming about seeing Patrica Feeney in your neighborhood, sorry...

Using ctime

Well gprof is saying the factorial is quite fast, execution time is 0, so, I'll roll out my own time keeper,

Now, the main function is modified as,

int main(void)
{
        int number,result;
        time_t startTime,endTime;

        printf("\nEnter number: ");
        scanf("%d",&number);

        time(&startTime);

        result = factorial(number);
        time(&endTime);

        printf("\nStart Time: %d\nEnd Time: %d\n%d! = %d",startTime,endTime,number,result);
        printf("\nTime for calculation: %d",difftime(endTime,startTime));

        return 0;
}

Executing I get,

Enter number: 19

Start Time: 1320051528
End Time: 1320051528
12! = 479001600
Time for calculation: 0

Bad, bad factorial is too simple... A better challenge is needed....

Flogging factorial

I have decided to post atleast once per day, so for want of a better topic, I am going to write a simple factorial program in C and flog it to death. Well here we go, let me start with a childish

#include
int main(void) 
{ 
       int number, i = 1,result=1; 
       printf("\nEnter number: "); 
       scanf("%d",&number); 
       for(i=1;i<=number;i++) result = result*i; 
       printf("%d! = %d",number,result); 
       return 0; 
} 
Simple, but if i want to use gprof to profile, i need to put the code for factorial in a separate function.

So, 

#include
int factorial(int n) 
{ 
    int i=1, result = 1; 
    for(i=1;i<=n;i++)result = result*i; 
    return result; 
} 

int main(void) 
{ 
    int number; 
    printf("\nEnter number: "); 
    scanf("%d",&number); 
    printf("%d! = %d",number,factorial(number)); 
    return 0; 
} 

And compile using cc -o flogFact flogFactorial.c -g -pg 

Well, after running  ./flogFact I get the gmon.out 

Now let me run gprof flogFact 
judge@boss:~/delete$ gprof flogFact -b 

Flat profile: Each sample counts as 0.01 seconds. 
no time accumulated 

% cumulative self                 self total 
time    seconds    seconds    calls    Ts/call    Ts/call   name 
0.00     0.00          0.00           1           0.00       0.00       factorial 

Call graph granularity: each sample hit covers 4 byte(s) 
no time propagated 

index % time     self     children       called         name 
                           0.00     0.00              1/1              main [5] 
[1]            0.0      0.00     0.00              1                 factorial [1] ----------------------------------------------- 

Index by function name 

[1] factorial 

Shit, no useful info just as yet, grr.. some more stuff to do, but i'm off for lunch...

A Story, That Couldn't End Wrong

I was reading a story, well a novel. And as all novels have to go, it suddenly got tough for the hero. Real TOUGH. He was going to die! But of course, he couldn't, I had covered only half the book! Well some novels have their hero dying, but, it has to happen only in the end. Its all about the hero, right?

So there I found myself quite gripped by the turn of events but telling myself that hero was going to live after all. And he did. It was a story, yes, just a story, which couldn't end wrong. Which takes me to another story.

I've been kicking around for twenty two years in this world. Ain't much, I know. But I've seen a couple of stories. Stories from close quarters. Maybe you can say I even played a guest role in them. Stories. Stories, which couldn't end wrong. It got bad. It got worse. Sometimes there seemed to be absolutely no way out. Given the chance, I'd still change the plot sometimes. But, well, they were stories. Real. Lives. Which. Couldn't. Go. Wrong.

The story of my grandmother who I never met, you could say, ended. And ended wrong. A woman dying leaving four children with nothing is a wrong ending after all. What else can it be? But, well, after 39 years, I'm having some doubts. If you think I still believe it ended wrong, I've got a clue for you. No! It could have ended better, but I can't say it ended wrong.

With Jesus as the hero of your story, your own story, the story of your life, your very own story, you have a story, a story which simply can't end wrong.