Life Before Templates

Recently functional languages are exploding on the scene. Old languages are slowly but steadily gaining new features. C++ 11 has a whole lot of new stuff. But, in this post I want to go back to some good old code. Code that was probably written when I was crawling as a toddler. C++ templates were introduced in mid-80s, so how did programmers code before that? Pre-processor

Have a look at http://docs.libreoffice.org/svl/html/svarray_8hxx.html It contains a lot of macros which create whole classes! (If you have time, see where each macro is being called, and do the whole stuff on your own to get the final class, and you'll appreciate the ingenuity of the programmers of old).

I have never used complex macros since in C and C++ since use of macros are kindaa frowned upon, so I decided to post a small and ugly use of these macros.

If I had been a programmer before C++ had templates, this is what I'd have done to add ;)

#define ADD_FUNC(ret,typedesc) \
typedesc add##ret(typedesc a, typedesc b){\
        typedesc c; \
        c = a + b; \
        return c;\
    }
The above code can be used by the following macro calls,
ADD_FUNC(int,int);
ADD_FUNC(float,float);

This would get me two neat functions for addition - addint(int,int), addfloat(float,float)

I can use these functions directly as,
cout<<addint(4,5)<<endl;
cout<<addfloat(4.3,5.2)<<endl;

Note that the above macro is very different from a normal macro function like,
#define MACRO_ADD(a,b) (a+b)

The first macro *creates new functions* which are then called directly by name. The second macro will be called differently,
cout<<macro_add(1,5)<<endl;
cout<<macro_add(2.2,3.1)<<endl;

Here is a full file to make everything very clear,

In LibreOffice code, you'll find that the calls to the macro generated functions/classes are themselves created using other macros. However all the old stuff is now being replaced by STL containers, so hurry you might miss some beautiful/ugly old code. (Its ugly in 2012, but it shows the ingenuity of the programmers of old! So that's the jackassery that was going on there!

Binary Search Tree - C

I got a bit bored today, and wrote this to pass some time. Nothing's special here, but a normal binary search tree implementation in C. I just felt that some other stuff found online to be a little complicated for beginners, well, here is the simplest I could manage.

#include<stdio.h>

#include<stdlib.h>

#include<time.h>




//Create a node, well in layman's terms, a layout for a container, ie. the container should have one compartment to store the actual data, and two compartments to store the addresses of the children




struct node

{

    struct node *left,*right;

    int item;

};




//To insert something we need the data, passing the head could have been avoided had I kept it as a global variable




void insert(int item,struct node *head)

{

    struct node *tmpNode;

    tmpNode =  (struct node *)malloc(sizeof(struct node));

    tmpNode->item = item;

    tmpNode->right = tmpNode->left = NULL;

    findplaceNinsert(tmpNode,head);

    return;

}

//Keep traversing by going either left or right depending on the values, and insert as soon as we find an empty slot




void findplaceNinsert(struct node *tmpNode, struct node *parent)

{

    if(tmpNode->item > parent->item)

    {//Go right

        if(parent->right == NULL) parent->right = tmpNode;

        else findplaceNinsert(tmpNode,parent->right);

    }

    else

    {//Go left

        if(parent->left == NULL) parent->left = tmpNode;

        else findplaceNinsert(tmpNode,parent->left);

    }

    return;

}

//Inorder traversal

void printInorder(struct node *tmpNode)

{

    if(tmpNode->left != NULL) printInorder(tmpNode->left);

    printf("%d ",tmpNode->item);

    if(tmpNode->right != NULL) printInorder(tmpNode->right);

}




int main()

{

    struct node *head;

    int i,item;




    srand(time(NULL));

    

    head = (struct node *)malloc(sizeof(struct node));

    head->left = head->right = NULL;

    head->item = rand()%100;




    printf("\nInserting random numbers...\n");

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

    {

        item = rand()%100;

        insert(item,head);

        printf("%d ",item);

    }

    

    printf("\n");

    printInorder(head);

}

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

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