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!

So You Inserted A Table, huh?

Aim

To make sense of LibreOffice source code. I plan to put a breakpoint in the  constructors of SwTableBox, and then get the back trace to see the flow and gain a little understanding of what's going on. This is post is aimed at beginners, so a little knowledge of C++/Java should be able to get one through this.

A Little Background Info (Skip this)

I'm a programmer from the Center for Development of Advanced Computing (CDAC), India, currently on a joint project with King Abdulaziz City for Science and Technology, Saudi Arabia, tasked with fixing bugs/improving LibreOffice. This is part of my efforts to understand (and help my team-mates understand) the source code. Any comments/suggestions/edits to this will be GREATLY APPRECIATED ;) You can fork this at https://gist.github.com/3038116

Initial Steps

I started to debug LibreOffice by following the steps listed in the official debugging guide after creating a build with --enable-debug --enable-symbols set in autogen.sh

Starting the Debugger

I started soffice with ddd after sourcing ooenv. Next, I set a breakpoint in line 1717 and 1738, constructors of SwTableBox in the file libo/sw/source/core/table/swtable.cxx, by typing  break /home/jesso/Downloads/libreoffice/libo/sw/source/core/table/swtable.cxx:1717, at the GDB console in the bottom of the DDD window, hoping these lines would be executed when a new table was created, and clicked on Run to start the execution.

In Writer, I inserted a new table, and as expected, the breakpoint at 1717 was hit!  Clicking on Status -> Backtrace in ddd, opens a pop up window with the Backtrace. I am reproducing it below, skipping the memory addresses alone.

Backtrace

#36 in main () at main.c:24
#35 in sal_main () at main.c:25
#34 in soffice_main () at sofficemain.cxx:77
#33 in SVMain () at svmain.cxx:210
#32 in ImplSVMain () at svmain.cxx:173
#31 in desktop::Desktop::Main () at app.cxx:1764
#30 in Application::Execute () at svapp.cxx:414
#29 in Application::Yield () at svapp.cxx:469
#28 in ImplYield () at svapp.cxx:435
#27 in GtkInstance::Yield () at gtkinst.cxx:538
#26 in GtkData::Yield () at gtkdata.cxx:578
#25 in g_main_context_iteration () from libglib-2.0.so.0
#24 in ?? () from libglib-2.0.so.0
#23 in g_main_context_dispatch () from libglib-2.0.so.0
#22 in ?? from libglib-2.0.so.0
#21 in call_userEventFn () at gtkdata.cxx:950
#20 in GtkData::userEventFn () at gtkdata.cxx:940
#19 in SalGenericDisplay::DispatchInternalEvent () at gendisp.cxx:102
#18 in SalFrame::CallCallback () at salframe.hxx:281
#17 in ImplWindowFrameProc () at winproc.cxx:2575
#16 in ImplHandleUserEvent () at winproc.cxx:2003
#15 in Link::Call () at link.hxx:143
#14 in SfxHintPoster::LinkStubDoEvent_Impl () at hintpost.cxx:65
#13 in SfxHintPoster::DoEvent_Impl () at hintpost.cxx:61
#12 in SfxHintPoster::Event () at hintpost.cxx:71
#11 in GenLink::Call () at genlink.hxx:45
#10 in Link::Call () at link.hxx:143
#09 in SfxDispatcher::LinkStubPostMsgHandler () at dispatch.cxx:1215
#08 in SfxDispatcher::PostMsgHandler () at dispatch.cxx:1244
#07 in SfxDispatcher::Call_impl () at dispatch.cxx:259
#06 in SfxShell::CallExec () at shell.hxx:199
#05 in SfxStubSwTextShellExecInsert () at swslots.hxx:2376
#04 in SwTextShell::ExecInsert () at textsh.cxx:466
#03 in SwBaseShell::InsertTable () at baseh.cxx:2654
#02 in SwEditShell::InsertTable () at edtab.cxx:77
#01 in SwDoc::InsertTable () at ndtbl.cxx:545
#00 in SwTableBox::SwTableBox () at swtable.cxx:1717

So, that's 36 calls, but I guess only calls from #21 are related to my table insertion actions.

What happens in each call

I am skipping calls #36 - #25 for now as they are mostly related to application startup. Calls #25 - #22 are inside glib (so, i'm not going to bother much about them).

#25 g_main_context_iteration () from libglib-2.0.so.0

Checks whether any event sources are ready to be processed. More details can be found here.

#23 in g_main_context_dispatch () from libglib-2.0.so.0

This dispatches all sources. More details are here.

#21 in call_userEventFn () at gtkdata.cxx:950

It is called by g_main_context_dispatch () with a pointer to a generic pointer name data. I was unable to dereference it.

#20 in GtkData::userEventFn () at gtkdata.cxx:940

The generic data pointer becomes a GtkData pointer here. Displaying the value pointed to by the pointer reveals a SalGenericData object(?) containing a SalData object (?) and a m_pUserEvent pointer. Dereferencing the m_pUserEvent pointer I found it contained, pointers to callback_funcs, source_funcs, callback_data etc. All these are interesting but I am unable to dereference these now as they are still generic pointers. Well, on the GtkData pointer, GetGtkDisplay() method is called, which returns a GtkSalDisplay object, on which the DispatchInternalEvent() method is called (the method is inherited from SalGenericDisplay).

Note -
* pThis seems to be concerned with the data directly resulting from the event (?),
*pData seems to contain the general details of the whole parent window (?), getting it from the GetGenericData() call which returns the variable pImplSVData.

#19 in SalGenericDisplay::DispatchInternalEvent () at gendisp.cxx:102

Here the lock is acquired, to get the values from m_aUserEvents. So, this seems to be where the actual user event and the corresponding data are fetched (?). The nEvent value is 22. The SalFrame is obtained and the CallCallback method is called on this object.

#18 in SalFrame::CallCallback () at salframe.hxx:281

This just calls the function stored in its own m_pProc variable.

#17 in ImplWindowFrameProc () at winproc.cxx:2575 

This contains the message loop. This function seems to handle *all* the user's inputs on the LibreOffice window. Seems to be a gold mine for putting breakpoints when we don't have a clue about any bug, and then we can step from here to where we want! The nEvent = 22 is SALEVENT_USEREVENT. Off we go to the next call in the same file.

#16 in ImplHandleUserEvent () at winproc.cxx:1986 

This just calls the function stored in the pointer.

#15 in Link::Call () at link.hxx:143  

The function pointed to by the pointer is called. Printing pFunc we get
(PSTUB) 0xb758ebbe

#14 in SfxHintPoster::LinkStubDoEvent_Impl () at /libo/sfx2/source/notify/hintpost.cxx:56 

Simply passes the data along to the next function (?).

#13 in SfxHintPoster::DoEvent_Impl () at /libo/sfx2/source/notify/hintpost.cxx:52

It passes the pointer it received on to the next function.

#12 SfxHintPoster::Event () at hintpost.cxx:60

I guess now it comes directly here. Seems to pass a function pointer deeper down.

#11 GenLink::Call () at /libo/sfx2/inc/sfx2/genlink.hxx:45 - Calls the function pointer.

#10 Link::Call () at /libo/solver/unxlngi6.pro/inc/tools/link.hxx:143

We've come back (?) to Call #15. It took the else part in the previous call, and we're back. But now we are calling a different function.

Printing pFunc here -
(PSTUB) 0xb73d97ba

I guess this Link::Call seems to be used to resolve function pointers in general (?).

#09 SfxDispatcher::LinkStubPostMsgHandler () at /libo/sfx2/source/control/dispatch.cxx:1205 

This function is commented. (Yay!) Helper method to receive the asynchronously executed s.

#08 SfxDispatcher::PostMsgHandler () at /libo/sfx2/source/control/dispatch.cxx:1234 

Stuff is added to SfxSlotServer and the next call is made. Expanding the pSlot pointer variable in ddd shows the structure containing variables which have subsequent calls (SfxStubSwTextShellExecInsert) stored in them.

#07 in SfxDispatcher::Call_Impl () at /libo/sfx2/source/control/dispatch.cxx:249

Its a helper function to check whether a slot can be executed and check the execution itself (from the comments in the code). It passes the target function SfxStubSwTextShellExecInsert to method CallExec in class SfxShell.

#06 in SfxShell::CallExec () at /libo/sfx2/inc/sfx2/shell.hxx:190

It simply executes the function pointed to by the function pointer.

#05 in SfxStubSwTextShellExecInsert () at /libo/workdir/unxlngi6.pro/SdiTarget/sw/sdi/swslots.hxx:2376

Now you'll find a line SFX_EXEC_STUB(SwTextShell,ExecInsert). I spent some time grepping for that, so I'll reproduce that macro here. Btw, macro is defined in 'sfx2/inc/sfx2/msg.hxx'.
 
  #define SFX_EXEC_STUB( aShellClass, aExecMethod) \
  void SfxStub##aShellClass##aExecMethod( \
    SfxShell *pShell, SfxRequest& rReq) \
   { \
     (( aShellClass* ) pShell )->aExecMethod( rReq ); \
   }
 
IMHO, this file seems to be a gold mine for putting break points, because, like winproc.cxx in #17, all the control seems to flow through these two areas, but I'm not sure about putting breakpoints on macros (?).

#04 in SwTextShell::ExecInsert () at /libo/sw/source/ui/shells/textsh.cxx:466

The code is more understandable at these layers. This function seems to be concerned with the insertion of *all* the objects into the document (is the document itself called as the shell?). It has one huge switch case for handling the various types of objects that can be inserted. Talking about that, the function gets value of the slot from the SfxRequest variable that it received as an argument, whose value the  ddd is showing as 20330 (ie. variable nSlot=20330, of type unsigned short), that maps to FN_INSERT_TABLE.

How? These details are in /libo/clone/binfilter/binfilter/inc/bf_sw/cmdid.h, in line 349 we have FN_INSERT + 30, and line 38 has FN_INSERT = (SID_SW_START + 300), and SID_SW_START = 20000 (this is defined in /libo/binfilter/inc/bf_sfx2/sfxsids.hrc). So the question becomes, where did it calculate 20330 first, I have to look keenly in the upper layers and update :( . Inside the case, it simply calls
InsertTable function with the argument that it received.

#03 -> SwBaseShell::InsertTable () in libo/sw/source/ui/shells/baseh.cxx:2654

This is where all the options entered in the dialog are finally retrieved. The data is present in the _rRequest variable and you can notice the retrieval of the table name, number of rows and columns etc. in lines 2582 - 2586, using SFX_REQUEST_ARG macros. The values that are finally stored in pName, pRows etc. were all entered in the Table dialog box, and ddd displays the values as these are ordinary integers. The items are then added once again as to _rRequest in proper Sfx formats(?) in lines 2641 to 2644.

Finally at 2654, the table is inserted! Notice that this call is sandwiched between rSh.StartAllAction () and rSh.EndAllAction (). After this layer, the parameters are passed expicitly, that is, not packaged in SfxRequest object anymore.

#02 -> SwEditShell::InsertTable () at libo/sw/source/core/edit/edtab.cxx:77

Again all the contents of the function are sandwiched between StartAllAction () and EndAllAction (). The current position of the cursor is obtained from GetCrsr()->GetPoint(), and the GetDoc() function returns the current document object, on which the next call happens.

#01 -> SwDoc::InsertTable () in libo/sw/source/core/docnode/ndtbl.cxx

This seems to deal at the table level. It gets the boxes/cells from SwTableBox::SwTableBox () and stores it in the variable pBox. It then constructs the table and returns a table node (?) - the variable pNdTbl (of type SwTable).

#00 -> SwTableBox::SwTableBox () in libo/sw/source/core/table/swtable.cxx:1717 

This is where I put he break point blindly, well all the constructors in this class had one. This constructor gets called four times, that is, for each cell in the table (am I right about the cell -> box mapping?).

The journey isn't over yet, the damned table hasn't even been printed to the screen, and every single function has to return the data. I'll edit this again as I make my journey upwards all the way back!

Takeaways



Files in Calls #17 and #5 are great places to put break points when we have no idea about any bug etc. as they are the critical points through which the flow must happen. There seem to be a couple of important Get* functions like GetGenericData (), GetDoc (), GetCur () etc. which can be used to get important objects.

pImplSVData - seems to be an important variable, used to get the display etc (?). Get it using GetGenericData().


SwWrtShell Object
More details about that can be found here. It is used in many functions, and in each case is retrieved by using GetShell ().


SfxRequest Object

SfxRequest object seems to be a container through which the data are passed around generally.

* Items are added to it using, reqObj.AppendItem ( ).

* After all items are appended method Done() is called on the object. ie. reqObj.Done()

* Items are retrieved using SFX_REQUEST_ARG macro.
    - It is defined in libo/sfx2/inc/sfx2/request.hxx
    - #define SFX_REQUEST_ARG(rReq, pItem, ItemType, nSlotId, bDeep) \
        const ItemType *pItem = (const ItemType*)

Python - Somthing similar to curry

Currying is a pretty neat idea. However python has its own partial in functools module.

So, left with nothing better to do, I had an idea of a function that waits till it has been called with the required number of arguments to return the result. That is, the arguments from the previous calls should be saved somewhere and used later.

So, here is the result almost_curry!


class almost_curry():
    def __init__(self,func):
        import inspect as insp
        self.func = func
        self.argsInFunc = insp.getargspec(func)[0]
        self.argsReq = len(self.argsInFunc)
        self.args = []
        self.kwargs = {}
   
    def __call__(self,*args,**kwargs):
        if args:
            self.args.extend(args)
            if len(self.args) == self.argsReq:
                targs = list(self.args)
                self.args = []
                return self.func(*targs)
               
        if kwargs:
            self.kwargs.update(kwargs)
            if len(self.kwargs) == self.argsReq:
                tkwargs = self.kwargs.copy()
                self.kwargs = {}
                return self.func(**tkwargs)

If we have a normal function, say sumxy,


def sumxy(x,y):
    return x+y

Now, we can do something like,
csumxy = almost_curry(sumxy)

If we call the our csumxy (its an object, not a function, but, functions are objects, oh I am getting loopy, never mind...)

csumxy(4) #just a normal call
csumxy(5) #target function has got the required number or args, so
9               # it has output the result! yay!

Takeaway: I found one use for the inspect module in python. Pulling this off without getargspec() in inspect would have required some other kind of hackery. If you have any suggestions please comment.

Google Code Jam - C++ base code

The qualification round is over! I found myself checking other people's code and I decided for the next rounds I'd need some common code to cut short the development time. There is no point in keeping this a secret, because, anyone can read other people's code and *a lot of far better, and really good code* are there if you check the code of the top 20 or so.

I plan to stick with python, however if speed of execution becomes very crucial, this will be my plan B (my plan A - using pypy ;) ).

I am treating each test case as a separate object. And since there is usually no common data  shared between  test cases, they can and should be parallelized. Pthreads are doing the job well enough, though I will try to check something with OpenMP's #pragma directive.

Note that while using pthreads and treating each test case as completely different gives us some gain, memoizing becomes a little bit more painful.

I also couldn't resist the urge to implement an ugly forAll kind of function. The doWork() is just something to test the performance gain, run this using perf in linux... and read the code and do comment if you have any suggestion, or I'll simply hunt your code down and read and learn from it ;)

#include < iostream >
#include < vector >
#include < pthread.h >

using namespace std;

class TestCase{

    private:
        int begin,end,result;

    public:
        TestCase(){begin = end = result = 0;}
        TestCase(int x, int y):begin(x),end(y){}
        void doWork();
        friend ostream & operator < < (ostream & out1,TestCase &t1);
        friend istream & operator >> (istream & in1,TestCase &t1);
};

void TestCase::doWork(){
    for(int i = 0; i < begin; i++){
        for(int j = 0; j < end*10;j++){
            for(int k = 0; k < begin; k++){
                result += 1;
            }
        }
    }
}

ostream & operator << (ostream & out1,TestCase &t1){
    out1&lt&ltt1.result;
    return out1;
}

istream & operator >> (istream & in1,TestCase &t1){
    in1 >> t1.begin &gt&gt t1.end;
    return in1;
}


inline void forAllTestCases(const int &num_testcases, vector<TestCase *> &tarr, void (*func)(TestCase * tptr)){
    int i = 0;
    while(num_testcases - i){
        func(tarr[i++]);
    }
}

void try1(TestCase * tptr){
    tptr-&gtdoWork();
}

void *doWork(void *threadArg){
    TestCase *tmp;
    tmp = reinterpret_cast<TestCase *>(threadArg);
    tmp->doWork();
}

int main(){
    int num_testcases,i;
    vector<TestCase *> tarr;
    cin>>num_testcases;

//read the input - I usually redirect the stdin
    TestCase *tptr;
    for(i=0;i<num_testcases;i++){
        tptr = new TestCase;
        cin >> *tptr;
        tarr.push_back(tptr);
    }

    vector<pthread_t> mythreads(100);
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_JOINABLE);
    void *status;
    int rc;

   
    for(i=0;i<num_testcases;i++)
    {
        rc = pthread_create(&mythreads[i],&attr,doWork, (void *) tarr[i]);
    }

    pthread_attr_destroy(&attr);

    //forAllTestCases(num_testcases,tarr,&try1);

//print the output
    for(i = 0; i < num_testcases; i++){
        rc = pthread_join(mythreads[i],&status);
        cout<<*tarr[i]<<endl;
    }

   
}

Facebook posts spam code sample - do it yourself!

Here is a small piece of code from one Facebook spamming website, which gets publishes shit on people's walls, and, well embarrasses the ruined guy.

Here we go,

Click on Google Chrome's wrench icon -> Tools -> Javascript console

Paste this  and press enter and see it change into something meaningful. This is how code obfuscation works.

unescape('%20%20%76%61%72%20%77%69%64%67%65%74%4a%53%4f%4e%20%3d%20%7b%20%20%20%20%22%62%72%61%6e%64%73%74%61%74%69%63%22%3a%20%22%73%74%61%74%69%63%2e%63%70%61%6c%65%61%64%2e%63%6f%6d%22%2c%20%20%20%20%22%62%72%61%6e%64%77%77%77%64%6f%6d%61%69%6e%22%3a%20%22%77%77%77%2e%63%70%61%6c%65%61%64%2e%63%6f%6d%22%2c%20%20%20%20%22%62%72%61%6e%64%63%6f%64%65%22%3a%20%22%63%70%61%6c%65%61%64%22%2c%20%20%20%20%22%64%61%74%61%64%6f%6d%61%69%6e%22%3a%20%22%64%61%74%61%2e%63%70%61%6c%65%61%64%2e%63%6f%6d%22%2c%20%20%20%20%22%74%72%61%63%6b%64%6f%6d%61%69%6e%22%3a%20%22%74%72%61%63%6b%69%6e%67%2d%74%65%63%68%6e%6f%6c%6f%67%79%2e%63%6f%6d%22%2c%20%20%20%20%22%70%75%62%22%3a%20%22%31%31%37%38%33%33%22%2c%20%20%20%20%22%73%75%62%69%64%22%3a%20%22%31%32%32%2e%31%37%34%2e%39%2e%31%31%30%22%2c%20%20%20%20%22%63%6f%75%6e%74%72%79%22%3a%20%22%49%4e%22%2c%20%20%20%20%22%67%61%74%65%69%64%22%3a%20%22%31%33%34%36%38%32%22%2c%20%20%20%20%22%67%61%74%65%69%64%36%34%22%3a%20%22%4d%54%4d%30%4e%6a%67%79%22%2c%20%20%20%20%22%67%61%74%65%74%79%70%65%22%3a%20%22%30%22%2c%20%20%20%20%22%67%61%74%65%68%61%73%68%22%3a%20%22%66%61%31%31%35%33%37%35%36%39%63%63%63%38%38%65%30%36%38%33%39%32%66%37%33%38%66%65%39%62%35%39%22%2c%20%20%20%20%22%69%63%6f%6e%6d%61%78%77%69%64%74%68%22%3a%20%22%35%39%2e%32%35%22%2c%20%20%20%20%22%69%63%6f%6e%69%74%65%6d%77%69%64%74%68%22%3a%20%22%35%39%2e%32%35%22%2c%20%20%20%20%22%70%72%6f%74%65%63%74%66%69%6c%65%22%3a%20%22%30%22%2c%20%20%20%20%22%70%72%6f%6d%70%74%65%6d%61%69%6c%22%3a%20%22%30%22%2c%20%20%20%20%22%61%63%63%65%73%73%74%69%6d%65%22%3a%20%22%32%34%22%2c%20%20%20%20%22%66%6f%6e%74%63%6f%6c%6f%72%22%3a%20%22%23%30%32%36%30%63%34%22%2c%20%20%20%20%22%62%61%63%6b%67%72%6f%75%6e%64%75%72%6c%22%3a%20%22%68%74%74%70%3a%2f%2f%69%2e%69%6d%67%75%72%2e%63%6f%6d%2f%4f%38%35%32%4f%2e%70%6e%67%22%2c%20%20%20%20%22%64%6f%77%6e%6c%6f%61%64%22%3a%20%22%4d%54%45%33%4f%44%4d%7a%66%44%45%7a%4e%44%59%34%4d%6e%77%77%22%2c%20%20%20%20%22%6c%65%66%74%74%69%6d%65%22%3a%20%22%66%6f%72%20%3c%73%74%72%6f%6e%67%3e%3c%75%3e%32%34%3c%2f%75%3e%3c%2f%73%74%72%6f%6e%67%3e%20%68%6f%75%72%73%20%6f%6e%6c%79%22%2c%20%20%20%20%22%61%6c%6c%6f%77%61%6e%63%65%22%3a%20%22%32%34%22%2c%20%20%20%20%22%61%6c%6c%6f%77%61%6e%63%65%75%6e%69%74%73%22%3a%20%22%68%6f%75%72%73%22%2c%20%20%20%20%22%61%6c%65%72%74%22%3a%20%22%31%22%2c%20%20%20%20%22%61%6c%65%72%74%74%65%78%74%22%3a%20%22%50%72%65%6d%69%75%6d%20%43%6f%6e%74%65%6e%74%20%55%6e%6c%6f%63%6b%65%64%21%22%2c%20%20%20%20%22%6c%65%61%64%74%65%78%74%22%3a%20%22%22%2c%20%20%20%20%22%63%61%63%68%65%75%72%6c%22%3a%20%22%61%48%52%30%63%44%6f%76%4c%33%4e%6c%5a%57%68%76%64%33%52%76%63%6d%56%7a%64%47%39%79%5a%58%6c%76%64%58%4a%68%59%32%4d%75%59%6d%78%76%5a%33%4e%77%62%33%51%75%61%57%34%76%50%33%64%68%64%47%4e%6f%22%2c%20%20%20%20%22%74%72%61%66%66%69%63%72%65%74%61%69%6e%65%72%22%3a%20%22%31%22%2c%20%20%20%20%22%63%6c%6f%73%65%62%75%74%74%6f%6e%22%3a%20%22%30%22%2c%20%20%20%20%22%72%65%64%69%72%65%63%74%65%6e%61%62%6c%65%64%22%3a%20%22%30%22%2c%20%20%20%20%22%72%65%64%69%72%65%63%74%75%72%6c%22%3a%20%22%22%20%20%20%7d%3b%20%20%20')

SICP Journey - 1

I have started learning Scheme as functional programming is raising its head once again! Haskell, Clojure, Coffee Script in javascript.

Boy, so here i go,

Here is my fibonacci program,
(define (fibo n)
        (cond ((= 0 n) 0)
              ((= 1 n) 1)
              (else (+ (fibo (- n 1))
                   (fibo (- n 2))
                      ))))

And here is a factorial program,

(define (factprog x)
        (cond ((= 0 x) 1) 
            (else (* x (factprog (- x 1)))
        ))
    )

Yup, that's it. So short and so sweet. Better versions of these programs are going to appear, so, watch out!

Ultra cool commands

I planned to make a good cheat sheet from http://www.reddit.com/r/linux/comments/mi80x/give_me_that_one_command_you_wish_you_knew_years/,
well, here are some..., i'll keep updating this when I am bored..

• units - conversion between more than 2000 kinds of units (kg to pounds, kilometers to miles etc.)
• ctrl + e - opens current command in $EDITOR and runs the altered version
• fc - similar to above, but opens previous command
• ctrl + r - reverse searches what you've entered in command history
• bind '"\e[A": history-search-backward' - binds your UP arrow key to only search whatever you've entered partially
• bind '"\e[B": history-search-forward' - binds your DOWN arrow key to only search whatever you've entered partially
•  lsof - ultra powerful so go here for detailed usage http://danielmiessler.com/study/lsof/
• find . -print0 | xargs -0 command -Runs command on all the files found.
• ctrl + a - Go to beginning of line
• cd - - Go to previous working directory. The directory you were in, before cd ing to some other directory.
• :w ! sudo tee %  - in vim when you forgot to open the file in sudo mode
• pushd  - Pushes a directory to stack and cds there
• popd - removes current directory from stack and cds to prevoius directory
• tmux - read here http://blog.hawkhost.com/2010/06/28/tmux-the-terminal-multiplexer/
• man -k searchstring - Search whether a tool is available for some task in your machine

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);

}

Some of my Django errors I faced and solved

This post is practically written for my sake alone - so that I'll know what to do later, if I face the same issues again.

Well here I go,

• "django.core.exceptions.ImproperlyConfigured: Error loading psycopg2 module: No module named psycopg2":  In django 1.3.1 settings.py file, if the database backed for Postgresql is simply given as 'postgresql' instead of postgresql_psycopg2, django simple gives the error as psycopg module not found. 

• "django error no module named messages": If you install Ubuntu 10.04's django version, well I have to confess that i never updated, it was a fresh vm, and straightway run your django app, it throws this. Download and install the latest django version. Solved.

• "django psycopg2.OperationalError: FATAL:  Ident authentication failed for user": Another classy misleading error. Just add 'localhost' in settings.py HOST, even though the helpful comment asks you to just leave it empty.

I LOVE DJANGO!!! This post is just to help another poor soul like me hunting in google and stackoverflow.

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