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!

The Monty Hall Problem

Mathematics is full of fun puzzles. Many puzzles seem so simple yet the solution turns out so counter intuitive. When i first saw this problem i should confess i also fell in the trap of relying on my intuition and i was wrong. I used to wonder why mathematicians are so careful about proofs. Even to prove some theorems whose solution seem obvious, why would the author take such great pain to formulate a long formal mathematical proof? I think, now, i have a little better understanding why so. Our intuition can backfire sometimes in very unimaginable ways but mathematics is always right.



Monty Hall Problem

The problem is basically a probability question and is a puzzle based on an american television game show called "Let's make a deal".

You are in a game show and are presented with three doors. You are told that behind one of these doors is the grand prize (a car) and behind other two, goats.  Your goal is to pick the one with the car. So, the host asks you to make a pick. After your pick, the host opens a door with the goat and asks you if you would like to change your choice and pick the other one. What would you do? Would you stay with your previous choice or would you make a switch to the other door?


Some people think it would make no difference at all. I think this mostly comes from intuition. I would have picked the other door that i was about to switch to in the very first place and that would add no more to my knowledge of my chance of winning. From the book "The man who loved only numbers" by Paul Hoffman, " "Physical scientists tend to believe in the idea that probability is attached to things". said Vazsonyi. "Take a coin. You know the probability of a head is 1/2. Physical scientists seem to have the idea that the probability of 1/2 is fused with the coin. Its a property. Its a physical thing. But say i take a coin and toss it a 100 times and each time it comes up tails. You'll say something is wrong,  the coin is false but the coin hasn't changed. Its' the same coin that it was when i started to toss it. So, why did i change my mind? because my mind has been upgraded with information. This is the Bayesian view of probability. It took me much effort to understand that the probability is a state of mind " ".


Some people think switching would give an advantage of 1/2 of winning over previous 1/3. I fell into this group when i first saw the question. I was convinced that it would improve my chance but i thought it would improve my chance by 1/2 since there were two doors left out of 3. So, 1 pick out of 2 would give 1/2 probability of winning.


After knowing the real answer to the question, i was puzzled too in the beginning. It was completely off from my intuition. It didn't make sense. How would my chance improve so drastically i.e from 33% to 66%.  Only after some serious thought,  i could see the logic behind the answer. It turns out the problem of winning is the problem of choosing the wrong door in the very first pick. This is because if you choose the wrong door in the first pick, in the second step you are destined to win because the host will have to pick the one with the goat leaving behind the door with the car.  The probability of picking the wrong door in the first pick is 2/3.

This has added further to my conviction to rely more on mathematical approach when intuition collide with reality.

Collatz Conjecture

Problem:

Pick a  natural number n, if it is odd multiply by 3 and add 1. If it is even divide it by 2. Repeat the process
indefinitely. The conjecture says no matter what number you pick it will eventually reach 1.

This conjecture hasn't been proven yet.

Here are two things that you would want to prove that would help with the overall proof.

1) Prove that there is no cycle other than the 1 -2 - 4 cycle. If there was to be a cycle then it would not converge to 1 but loop indefinitely. That would prove that this conjecture is wrong.

2) The next thing worth proving is that there are no such sequence such that its odd and even numbers alternate indefinitely i.e odd - even - odd - even.... . If that happens then since on odd we are multiplying each time by 3 and in even we are dividing by 2. The sequence diverges instead of converging (shrinking) to 1.


I think if we know that there are no cycles and no indefinite alternating sequence such as odd - even -odd- even then we can prove that any number you pick will converge down to 1. In order to converge to 1,  the sequence has to finally hit a power of 2 i.e 1,2,4,8,16.... I think you can see why that is so. The only way to get 1 is through the sequence of power of 2.

I visualize this as a barren tree i.e a tree without leaves.

 We can consider the stem as the sequence of power of 2 and each branch as some arbitrary sequence which finally meets the sequence of power of 2 at some point.

Below is the tree structure with some numbers. You can see all the branches finally meeting the stem sequence and hence converging down to 1.

I can see the difficulty involved in proving something such as this. We are basically trying to see if this infinite tree contains all the natural numbers there are. Since the branches branch out from its own branches and the sequence is very random, it is very hard to see what the behaviors of large numbers are. Its like trying to find patterns in the sequence of prime numbers.

CHIP-8 Emulator

Chip 8 is an interpreted programming language created to program games in computers in mid 1970s. Since the language just has 36 instructions, this is probably a good place to start if you want to get into emulator programming.

The following resources proved very helpful while i was coding the interpreter.

Chip 8 Technical Specifications

Active Chip 8 forum

My interpreter is done in JAVA and can be accessed here. The repository also has sample ROMS and also executable file.

CHIP 8 code 

Card game

Jut Pati

Jut Pati is a popular game in Nepal. This game is very much based on luck.7 cards get dealt to each player. The idea is simple. Just match pairs. (i.e 7, 7 8, 8 A, A). Each takes turn taking a card from the deck, doing necessary matching and then throwing a card to the other player. The other player tries to match the thrown card. If it doesnt. He picks another card from the deck do necessary matching and throws the card. This cycle continues until one player matches all the cards so he has no card in his hand. The one who matches all the pairs first wins.


Note: Because the game doesn't have a pre-loader, please wait some time for the game to appear. Initially, it'll show a blank screen because the game is loading.

Jut Pati

Garden Match

A game about solving garden puzzle and designing your own garden. This game was sold to flashgirlgames.com. 


https://www.youtube.com/watch?v=Zm01jySfZ2s&t=1s

GardenMatch

Fun with flash

List of prototypes for testing game ideas.

View Website