Thursday, January 30, 2014

Smart Car Project

smart Car 

Connection diagram











Arduino code


#define led 13

//for Fwd and Backward
#define pin1 2
#define pin2 4

//for Right and left
#define LR1  7
#define LR2  8

int inByte = 0;

void setup()
{
  Serial.begin(9600);
  Serial.println("Hello World");

  pinMode(led, OUTPUT);

  pinMode(pin1, OUTPUT);
  pinMode(pin2, OUTPUT);

  pinMode(LR1,  OUTPUT);
  pinMode(LR2, OUTPUT);

  digitalWrite(pin1, LOW);
  digitalWrite(pin2, LOW);
  digitalWrite(LR1, LOW);
  digitalWrite(LR2, LOW);
}

void loop()
{
  if (Serial.available() > 0)
  {
    inByte = Serial.read();
    int stp = 0; //Stop wheels
    int fwd = 1; //run in fwd direction
    int bw = 2;  //backward dir
    int right = 3; //right
    int left = 4;  //left
 
    Serial.println(inByte, DEC);
    if (inByte == stp)
    {
       digitalWrite(pin1, LOW);
       digitalWrite(pin2, LOW);
       Serial.println(stp, DEC);
    }
    if (inByte == fwd)
    {
       digitalWrite(pin1, HIGH);
       digitalWrite(pin2, LOW);
       Serial.println(fwd ,DEC);
    }
    if (inByte == bw)
    {
      digitalWrite(pin1, LOW);
      digitalWrite(pin2, HIGH);
      Serial.println(bw, DEC);
    }
    if (inByte == right)
    {
      digitalWrite(LR1, LOW);
      digitalWrite(LR2, HIGH);
      Serial.println(right, DEC);
    }
    if (inByte == left)
    {
      digitalWrite(LR1, HIGH);
      digitalWrite(LR2, LOW);
      Serial.println(left, DEC);
    }
 
    Serial.println("done");
  }
}


udp_server.c

Thursday, May 24, 2012

My experiments with tic tac toe


Was writing a tic tac toe app for android recently as was familiar with the rules of the game :-).
The last time I wrote a tic tac toe game was in college time, and then most focus was on the gui design. The lousiest algorithm in the background.

One of the algorithm was to check the state of the game i.e win or draw etc. Gave it a thought this time and  made some optimization in the row, col, diagonal checks. Its mainly decided in the first nested loop if we need to check a particular column or diagonal. So, we avoid checking of columns or diagonals saving time. This makes big impact when the board size is more and a significant number of the cells are not filled.


Next time I will post the nextMove implementation, for the computer to decide its next move.

Here is the java code for the gamestate algorithm.

  int gameState(int values[][], int boardSz) {


boolean colCheckNotRequired[] = new boolean[ boardSz ];
boolean diag1CheckNotRequired = false;
boolean diag2CheckNotRequired = false;
boolean allFilled = true;


int x_count = 0;
int o_count = 0;
/* Check rows */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
for (int j = 0; j < boardSz; j++) {
if(values[i][j] == x_val)x_count++;
if(values[i][j] == o_val)o_count++;
if(values[i][j] == 0)
{
colCheckNotRequired[j] = true;
if(i==j)diag1CheckNotRequired = true;
if(i + j == boardSz - 1)diag2CheckNotRequired = true;
allFilled = false;
//No need check further
break;
}
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}


/* check cols */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
if(colCheckNotRequired[i] == false)
{
for (int j = 0; j < boardSz; j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
//No need check further
if(values[i][j] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
}

x_count = o_count = 0;
/* check diagonal 1 */
if(diag1CheckNotRequired == false)
{
for (int i = 0; i < boardSz; i++) {
if(values[i][i] == x_val)x_count++;
if(values[i][i] == o_val)o_count++;
if(values[i][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}

x_count = o_count = 0;
/* check diagonal 2 */
if( diag2CheckNotRequired == false)
{
for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
if(values[j][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
x_count = o_count = 0;
}


if( allFilled == true)
{
for (int i = 0; i < boardSz; i++) {
for (int j = 0; j < boardSz; j++) {
if (values[i][j] == 0) {
allFilled = false;
break;
}
}
if (allFilled == false) {
break;
}
}
}


if (allFilled)
return DRAW;


return INPROGRESS;
}


Thursday, May 17, 2012

Yet Another HashMap ...

There are several implementations of hashmaps available, this is just another implementation that I did when I  was too lazy to google for existing implementations.

This implementation is having 2 basic traits:
1. A strong hash function.
2. An efficient tree

To implement this I have used the hash implementation provided by Bob Jenkins http://burtleburtle.net/bob/hash/doobs.html

And the tree chosen is a basic red black tree implementation. 

A very simple API which enables insertion/deletion of the entries.

To insert entries:
hash_insert(void* key, uint32 key_len, void* data, uint32 data_len);

To Check if the entry is present in the table
hash_find(void* key, uint32 key_len);

To retrieve the data for a key
hash_getData(void* key, uint32 key_len, void* data, uint16* data_len)

To delete an entry
hash_deleteEntry(void* key, uint32 key_len);

Here is a sample code, to show how to use it.

#include "hashmap.h"#include
#include
#include
#define MAX_KEY_LEN 128
int main(){
      char key[MAX_KEY_LEN];
      uint16_t data;
      uint16_t dataLen;
      int i = 10000000;
      // First insert
      strcpy(key, "hello");
      data = 123;
      hash_insert((void*)key, strlen(key), &data, sizeof(data));
   
      //Lets retrieve it
      strcpy(key, "hello");
      uint16_t temp;
      hash_getData((void*)key, strlen(key), &temp, &dataLen);
      //Remove the entries
      strcpy(key, "hello");
      hash_deleteEntry((void*)key, strlen(key));
}

The default number of entries in the hashmap is defined in hashmap.h as follows

#define HASH_MAX_CAPACITY 10000000

This can be modified as per requirement.

How to Use

Just hit make in the extracted package. This generates a  library libQuickHash.so and libQuickHash.a.  There is a sample program testHash.c which can be of help. 

The compressed package is here

enjoy ...

Wednesday, November 9, 2011

How smart are the smart pointers ?

Untitled document

smart_pointer is a blessing for a carefree programmer who wants to allocate memory in heap and forget about deleting it. Sounds great. Its really tough to track a pointer and carefully release the heap memory captured.

Also it relies on the fact that its easy to clear stack than heap. So, lets see how it works.

First lets see, how can we use a smart pointer class in our program and then we will go ahead to implement it. Please follow the comments for understanding.

We take an example class

class A

{

        public:

        //This variable is meant to track the

        // number of instances of the class that are existing.

        static int count;

        //Constructor

        A()

        {

                //New instance is created so increment.

                count++;

        }

        //Copy contstructor

        A(A& obj)

        {

                //New instance is created so increment

                count ++;

        }

        //Assignment operator

        A& operator =(A& obj)

        {

                //New instance is created so increment

                count ++;

        }

        ~A()

        {

                //Instance removed, so decrement the value.

                count --;

        }

        void display()

        {

                cout << "Its me \n";

        }

};

Now we look at the main function where we will be using the smart_ptr class.

int main()

{

        //This is how we create a smart_ptr object

        // see the pointer of type A is stored inside the

        // smart_ptr object

        smart_ptr<A> ptr(new A());

        smart_ptr<A> ptr1;

        //Testing assignment operator

        ptr1 = ptr;

        //Testing self assignment

        ptr = ptr;

        // Verifying how many instances of A are there.

        cout << "A::count = " << A::count << endl;

        //Using overloaded -> operator to call

        // member functions of class A

        ptr->display();

}

Now we implement the smart_ptr class, as per the usage. So, here it is.

template <class T>

class smart_ptr

{

        private:

               // The pointer which is managed

                // by the smart_ptr class

                T* m_ptr;

                //Keeps track of the number of references

                //the allocated memmory.

int ref_count;

        public:

                smart_ptr()

                {

                        m_ptr = 0;

                        ref_count = 0;

                }

                smart_ptr(T* ptr)

                {

                        m_ptr = ptr;

                        //increment the ref count

                        //as this is the first reference

                        ref_count = 1;                

                }

                smart_ptr(smart_ptr& obj)

                {

                        cout <<  "Copy Contstructor\n";

                        ref_count++;

                }

                //Assignment  operator overload

                smart_ptr* operator =(smart_ptr& obj)

                {

                        if(&obj != this)

                        {

                                ref_count++;

                        }

                        else

                        {

                                cout << "Self assignment\n";

                        }

                }

                // Destructor

                ~smart_ptr()

                {

                        cout << "Deleteing the smart_ptr instance\n";

                        // Decrement the reference count as

                        // the instance is released

                        ref_count --;

                        if(ref_count == 0)

                        {

                                // Delete the pointer

                                // as there are no references to it.

                                delete m_ptr;

                        }

                }

                T* operator ->()

                {

                        return m_ptr;

                }

};

Tuesday, October 11, 2011

A Gram of Anagram


Last week attended an interview, and this was the question the interviewer came up with to test my problem solving.

" Give a logic to generate valid anagrams of a word, provided you have a dictionary to confirm the validity"

After a while of scribbling on the blank paper I came up with the following answer.

If I take a dictionary as a Hash Map as every word is unique and the Key is a binary(or Hex) representation of the word. Then if I have a word I can easily find the meaning of it with O(1) complexity.

Now, if we have to generate all the valid anagrams, we need to verify if the generated anagram is in the dictionary, if it is present in dictionary, its a valid one else we need to ignore that.

I will assume that there can be a word of max 100 characters(or more but there is a limit).

So any word we take it as a sequence of indexes like a word "hello" can be represented like "1234". Now the anagrams of "1234" are "1243", "1242" ..etc

The only thing we need to do is to store all such combinations of indexes for a particular number of characters. This is an one time task. And then words can be generated from the combinations by picking the characters from the index.Hence we get the anagrams.

To verify if the anagrams are valid or not, just index into the dictionary and validate.

The only thing need to be handled is the duplicates.That can be done easily. As an when we need to compare with the previous ones that has been searched in dictionary.

And I said the solution emphasizes on performance.

I don't know if this is the answer the interviewer was expecting or something else but I can guess it now as I did not get any response for further rounds.

Really need to work on my problem solving skills.

Tuesday, December 14, 2010

Multi Key Maps.. myth or reality


What the heck ? Never heard of these, is it possible to access the same entry with multiple keys? Just somedays back thought of this, and said y not .

Our good old friend Map allows us to have an unique key which is mapped to a value. To access a value we must have an index which is unique. But what if we want to access the same entry but using multiple indices we need a slightly different mechanism.

Ok , so here I would discuss a way to achieve it. And we will put into use something we learned in school and that is Prime Number. These are basically the numbers that are divisible by themselves except 1.

Euclid’s Fundamental Theorem of Arithmetic states that Every integer can be written as a product of primes in an essentially unique way. And Euclid's second theorem states that the number of prime numbers is infinite.

Now, as per the first rule we conclude that prime numbers are the ones upon multiplication of which we can generate any number. So, can we say they are the basic components of any number.

Based on this we try to create a key of a map. Lets say we want to create a map in which a value can be accessed using 2 keys.
Here are the various keys that we are going to use and the index values they generate.
2*3 = 6
5*7 = 35
11*13 = 143 .. and so on. Note that each of the index has only 2 factors except 1.

Now we create a map from integer to a string with the above indices
6 --> “Hello”
35 --> “ World”
143 ---> “Sanjiv”

Say in c++, the search code will look something like this.

map my_map.begin ;
string get(int key)
{
for(map::iterator iter = my_map.begin(); iter != my_map.end(); iter++)

{

if(iter->first % key == 0) //Key matches with the index

return iter->second;

}

}

It looks so dumb that we are have to traverse the whole map to find the match. This completely denies the whole purpose of an associated storage.

I hope I will be able to come up with a better way to do the same.

Friday, June 11, 2010

What the Hell are Allocators ???

Writing this is like a compulsive need to understand wht the heck is all about Allocators in c++. I see these whenever I check a process core dump with vectors, maps etc , and they make the complete stack look so scary. And also not to mention the compilation errors. You do some teeny weeny mistake in vector or map or some crazy stl declaration and bammm the compilation error scares the hell out of you, and you wonder where did I declare with those allocators n all.

Here I will try to get over my fears and try to understand properly what are these things. And not embarrass my self because of the fact that being a 3.5 years experienced c++ programmer c++ allocators have eluded me for a long, and will now make an attempt to do it along with explaining to you guys.

The definition as understood by me is that an allocator is a class that handles the allocation/de-allocation of various STL, especially containers. For example take vector, its just a linked list. Whenever we call push_back() on a vector object, it has to allocate some memory for the entry and attache it to the existing linked list. This allocation of memory is hidden to us and is handled by a class specifically designed for the purpose i.e  the allocator.
Now what is the functionality  that we are looking for in the Allocator class
1. Allocation/Deallocation
2. Hopefully Thats it...

Lets take it forward and try to implement an allocator.

#include <iostream>

#include <vector>



using namespace std;



template<typename T>

class Allocator

{

        public:

                typedef T value_type;

                typedef value_type* pointer;





        public:

                inline explicit Allocator()

                {

                        cout << "Constructor of Allocator\n";

                }

                inline ~Allocator()

                {

                        cout << "destructor of Allocator\n";

                }

                inline explicit Allocator(Allocator const&) {}



};



int main()

{

        vector<int, Allocator<int> > vec;

}


Guess what when I compiled I got a really long list of errors. Probably these compilation errors will help us understand Allocators better. So, here is the listing.

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In instantiation of `std::vector<int, Allocator<int> >':

test_allocator.cxx:29:   instantiated from here

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:152: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:153: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:154: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:157: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:158: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:322: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:338: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:354: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:370: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:462: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:476: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:500: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:514: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:521: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:528: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:535: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:542: error: no type named `const_reference' in `class Allocator<int>'

test_allocator.cxx: In function `int main()':

test_allocator.cxx:29: error: no matching function for call to `Allocator<int>::Allocator(Allocator<int>)'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182: error: in passing argument 1 of `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In member function `void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(_Tp*, size_t) [with _Tp = int, _Alloc = Allocator<int>]':

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:106:   instantiated from `std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int, _Alloc = Allocator<int>]'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182:   instantiated from `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'

test_allocator.cxx:29:   instantiated from here

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:117: error: 'struct std::_Vector_base<int, Allocator<int> >::_Vector_impl' has no member named 'deallocate'



So, you can see there are various declarations/definitions missing in the allocator class. I hate to tell this, but its a fact that allocators follow some C++ standards guideline as per how the class should look like. 
(ISO C++ standard, section 20.4.1)
And it looks like the following. I have provided brief description next to each declaration.

//Template definition for allocator as it will be used to allocate 
// any pointer type
    template <class T>  class allocator {
    public:
            //Set of typedefs to be used in various

            //methods for allocation/deallocation/construction

            // destruction etc.


            typedef size_t    size_type;

            //Unsigned integral value that can represent the difference between two pointers
            typedef ptrdiff_t difference_type;

            // Pointer type for the class

            typedef T*        pointer;

            // Const pointer type for the class
            typedef const T*  const_pointer;

            //Reference type for the class 
            typedef T&        reference;

            //Const Reference for the class
            typedef const T&  const_reference;

            // Value type    
            typedef T         value_type;
      
            //template structure, which allows any allocator might allocate memory of another type indirectly.

            template <class U> struct rebind { typedef allocator<U>
                                         other; };

            allocator() throw();
            allocator(const allocator&) throw();
            template <class U> allocator(const allocator<U>&) throw();
            ~allocator() throw();

            pointer address(reference x) const;
            const_pointer address(const_reference x) const;

            // This function will be called, whenever a new memory 
            // allocation is required. As in vector push_back      
            pointer allocate(size_type,
                       allocator<void>::const_pointer hint = 0);

            // This function will be called when the memory location needs to be 

            // freed.

            void deallocate(pointer p, size_type n);
            size_type max_size() const throw();

            // Following are required to initialize/de-initialize the allocated
            // memory location.
            void construct(pointer p, const T& val);
            void destroy(pointer p);
    };


Now after we have understood how our Allocator class should look like, lets put some life into this class. Lets make it usable by defining atleast allocate/deallocate functions. 

Here is how I have defined it in my test program.
            pointer allocator::allocate(size_type sz, std::allocator<void>::const_pointer hint = 0)
            {
                     cout << "Allocating\n";
                     char* ch = (char*)malloc(sizeof(sz));
                     return (pointer)(ch);
            }
            void allocator::deallocate(pointer p, size_type n)
            {
                    cout << "De-Allocating\n";
                    free(p);
            

            }


Now lets see, how does it work in real use.

            int main()
            {
                vector<int> myVector;


                myVector.push_back(1);

  

            }

On compiling and running the program following out put is obtained.
            Allocating

            De-Allocating


At this point atleast we are aware of some internals of allocators, and we know "wht the hell allocators are" . Going further we can define our pool of memory and allocate from that pool and handle all allocations/deallocations in that chunk of memory using our own creative memory management algorithm. 

I hope I will cover that advanced topic some other day , till then cya .....