Few more screen shots

The game is taking shape. : ) Here are few more screen shots from the game i am working on.

Card game

I have been busy creating a multiplayer card game in java for the past couple of weeks. I hope to make it live soon. : )

Lost and Found app

This is a simple app called lost and found  which i built for a class. The purpose of this app was to let students post lost items and found items. This is built with Flask and Twitter bootstrap.

Design

Source Code

XOR bug

I wanted to share an intriguing bug today.

I was trying out insertion and selection sort. Here is the code :

#include <iostream>
using namespace std;

void selectionSort(int nos[], int len){

//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};

for(int i=0;i<len;i++){

    int min_value = 0x7fffffff;
    int index_of_min_value;
 
    for(int j=i;j<len;j++){
         if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
    }

                    int temp = nos[i];
                    nos[i] = min_value;
                    nos[index_of_min_value] = temp;     
       
          }

}

void insertionSort(int nos[], int len){
     
    for(int i=1;i<len;i++){
          for(int j=i;j>0;j--){
                    if(nos[j] > nos[j-1]){
                              break;
                    }
         
                    int temp = nos[j-1];
                    nos[j-1] = nos[j];
                    nos[j] = temp;       
        }   
    }
}

void printElementsOfArray(int nos[], int len){
    for(int i=0;i<len;i++)
        cout << nos[i] << endl;
 
     cout << endl;
}

int main()
{

    int nos1[] = {24, 13, 9, 64, 7, 23, 34, 47};
    int nos2[] = {24, 13, 9, 64, 7, 23, 34, 47};
 
 
    int len = sizeof(nos1)/sizeof(int);
 
    insertionSort(nos1, len);
    printElementsOfArray(nos1, len);


    selectionSort(nos2, len);
    printElementsOfArray(nos2, len);
 

 
   return 0;
}

I got the input as expected.

7
9
13
23
24
34
47
64

7
9
13
23
24
34
47
64

But, now i wanted to try out xor swaps instead of temporary variable swaps. (something that i learnt recently : =) ) Below is the updated code for selection sort.

void selectionSort(int nos[], int len){

//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};

for(int i=0;i<len;i++){

    int min_value = 0x7fffffff;
    int index_of_min_value;

    for(int j=i;j<len;j++){
         if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
    }

       
          nos[i] ^= nos[index_of_min_value];
          nos[index_of_min_value] ^= nos[i];
          nos[i] ^= nos[index_of_min_value];

          }

}

Now the output

7
9
13
23
24
34
47
64

7
9
0
23
0
34
47
0

Hmm...interesting! I was puzzled. I knew that was the right code for swapping but what's that.

I printed out the array state after each swap in selection sort.

#include <iostream>

using namespace std;

void printElementsOfArray(int nos[], int len){
 
    for(int i=0;i<len;i++)
        cout << nos[i] << " ";
 
    cout << endl;

}


void selectionSort(int nos[], int len){


//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};


for(int i=0;i<len;i++){
 
 
    int min_value = 0x7fffffff;
    int index_of_min_value;
 
    for(int j=i;j<len;j++){
             
        if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
             
    }
 
          nos[i] ^= nos[index_of_min_value];
          nos[index_of_min_value] ^= nos[i];
          nos[i] ^= nos[index_of_min_value];
         
           printElementsOfArray(nos, len);

     
}
}


int main()
{
 
    int nos1[] = {24, 13, 9, 64, 7, 23, 34, 47};
    int nos2[] = {24, 13, 9, 64, 7, 23, 34, 47};
 
 
    int len = sizeof(nos1)/sizeof(int);
 
    insertionSort(nos1, len);

  //  printElementsOfArray(nos1, len);

    selectionSort(nos2, len);
 
//    printElementsOfArray(nos2, len);
 
   return 0;
}


I get the output


//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};

7 13 9 64 24 23 34 47  ->step 1
7 9 13 64 24 23 34 47  ->step 2
7 9 0 64 24 23 34 47    ->step 3
7 9 0 23 24 64 34 47
7 9 0 23 0 64 34 47
7 9 0 23 0 34 64 47
7 9 0 23 0 34 47 64
7 9 0 23 0 34 47 0
    
In step 3,  we know the problem. XOR swap works on two separate variables but in step 3 we are swapping it with itself. In other words we are doing a^a three times which will always be 0.

Ahh.. The lesson , If you want to use xor swaps, make sure you are not swapping the same place.

Here was a quick fix.

void selectionSort(int nos[], int len){


//    int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};


for(int i=0;i<len;i++){
 
    int min_value = 0x7fffffff;
    int index_of_min_value;
 
    for(int j=i;j<len;j++){
             
        if(nos[j] < min_value){
            min_value = nos[j];
            index_of_min_value = j;
        }
             
    }
         
            if( i  != index_of_min_value){  
                    nos[i] ^= nos[index_of_min_value];
                    nos[index_of_min_value] ^= nos[i];
                    nos[i] ^= nos[index_of_min_value];
            }
                 
}
   
}

Good Will Hunting Problem

This problem is popularized by the movie "Good Will Hunting"

Courtesy of singingbanana/numberphile for the problem.


Problem:


Draw all homeomorphically irreducible trees of size n = 10.

If you don't know what a mathematical tree is then i'd recommend a quick look at the following two links.

http://en.wikipedia.org/wiki/Tree_(graph_theory)

http://en.wikipedia.org/wiki/Graph_(mathematics)

So below are some trees

Basically a tree is a graph without any cycle. You can consider a tree being a series of dots connected together like a network but with one constraint. It shouldn't have any cycle. Following is a graph with a cycle. Since, it has a cycle it is a graph not a tree.

So, the question asks to draw all  homeomorphically irreducible trees of size 10. 

Mind you that the question isn't just asking to draw all trees of size 10 (size = number of nodes or vertices). It has two phrases "homemorphically and irreducible". That means

Structures like above should be counted as one. They aren't different. If you spread the edges of the second tree you can easily form the first tree. So, if one tree can be shown to be like another tree by stretching the edges then we should consider those trees as being the same tree.

Also, The following trees aren't allowed. As you can see, each has at least one vertex with two edges connected to it. If that was allowed then you could put arbitrary many points between two vertices to make infinitely many different kinds of trees. Those don't make interesting trees. 

So, the problem is to draw all homeomorphically irreducible trees of size n = 10 or 10 vertices.

Give it a try!! 

SPOILER!!!!!!

Below is my approach to solve this problem.

The general strategy that i have used to solve this problem is to start with the principle branch which i define as a node or a collection of nodes connected by a straight line from which edges branch out to form trees. Just like in a tree we have a stem from which branches branch out. You can consider principle branch to be the stem from which edges branch out.

Lets start with one vertex in the principle branch and generate all the possible trees from there.

 The following is obvious.

This one below wasn't so obvious.

Then lets move on to two vertices in principle branch. So, first i start with the principle branch with two vertices and then enumerate all possible trees from there.

Following are all trees with two vertices principle branch.

As you can see, with the principle branch set the problem of generating the different trees is just moving edges from one vertex to another.

Lets move on to three vertices principle branch.  

With this approach, you can easily see when you have exhausted the number of possible trees with that many vertices in the principle branch.

Finally, the only tree possible with 4 vertices principle branch.

This is because if we move any edge from any vertex then that vertex will have one edge less than three which will break our definition of being homeomorphically irreducible tree. We want each vertex of the tree to have at least three edges connected to it.

This concludes the solution to the problem of finding all homeomorphically irreducible trees of size 10 with cap reached at four vertices principle branch. 

Connect The Towns

Courtesy of singingbanana for the problem.

Imagine you work for a construction company, you are asked to find the best way to connect these towns that will optimize the building materials.(building materials -> materials required to build roads i.e cement, concrete, sand etc ) For convenience of calculation, the towns can be considered as being the four corners of a unit square.


How would you connect these four towns?


Give it a try!


One naive way to connect is as follows which has a total length of 4 units.

Can we do better?











SPOILER!!


A slightly better way is as follows with total length of 3 units.

any better way?

We can do even better than that with above. The above construction has total length of 2.82.


Turns out there is even a better approach than that. I confess i had to look up the solution for this one. This might not seem very intuitive but the best solution is as follows:

The angle between the lines is 120 degrees.


What's the reasoning behind such strange shape?


In order to better understand it. Lets consider the best way to connect three towns of unit length shown as corners of an equilateral triangle. The solution is as follows:

Forgive me for the length of one of the lines not being long enough but it carries the point.

So, the solution for 4 towns is basically hidden in the unit square as the combination of solutions of triangles whose bases are two opposite sides of the triangle.

Start by making an equilateral triangle with unit length sides with its base as one of the sides of the unit length square. Make another similar triangle with base as the opposite side of the unit square. Then, draw the solutions of these two triangles. Then finally connect these two minimal solutions. You can better see the solution if you rotate the above picture 90 degrees clock or counter clockwise direction. That's my reasoning.

Euler Trail

Problem:

Can you draw a continuous curve that crosses every line only once?



To make the word "line" clear i have marked below the lines that can be crossed. There are 16 of them.

So, can you do it?

One attempt can look something like the following:

In the above attempt although it crosses off most of the lines, it misses 1 of them. Can you cross every lines?



Give it a try!!




SPOILER ALERT!!!

Solution:

This problem can be solved in different ways. Your approach can differ from mine.

Lets look at these three structures which are parts of the original figure.

I have picked them particularly because they are unique. They have odd number of lines. i.e 5.


If i start drawing the curve from outside one of these structures then in order to finish crossing all the lines, ill end up inside the structure when i finish marking all the lines or if i start drawing the curve from inside then the final endpoint after crossing all the lines will fall outside the figure. In other words endpoint and startpoint cannot both fall in the same side.

The reason is that we have odd number of lines.



So, knowing this property, now we are ready to tackle the problem.

You will be entering two of these structures from outside. I hope you can see why. There are three of them and even if i start the curve from inside one of these, i will still be entering the rest two from outside. Now, we already saw above if we start from outside then when i finish crossing all the lines, ill be inside one of these from where i cannot move outside.  This is a problem. This also means we finish marking all the lines of one of these structures by entering inside the structure. But, wait!!! there are at least two of these. How can i be inside two of these at the same time if i want to finish marking all of their lines?

That's why its impossible to solve this puzzle.


Stay tuned for more fun puzzles!