Algorithm H4ckz

Birthday Puzzle

2008-07-26T11:27:00.000-07:00

Today, I was just reading some stuff and one of my friends who was surfing on the internet stumbled upon this puzzle and asked me the answer for that. Infact, I vaguely remember that I heard of this puzzle before, from one of my friends (who was questioned by some person in one of the interviews for a software job, at a good firm). The puzzle goes like this:

Birthday Puzzle: In a software company (or any other place) of 48 employees, what is the percentage/probability that atleast 2 employees share the same birthday?

Answer: Most of the times, when someone comes across with questions like this, they make a guess and respond to that. But when asked a general question like that, the immediate thing that one should think about is "probability" and 'probability' gives you the best guess (doesnt guarantee you with the answer).

Ok..The approach to solving this problem, is to calculate the probability that 'no two share the same birthday' and then subtract this from "1" (as the probabilty logic says), to arrive at the answer for the posed question. Here's the java code that I wrote:


import java.util.Scanner;

public class BirthdayPuzzle
{
  public static void main(String[] args) 
  {
    System.out.println("Enter The Year : ");
    Scanner scanner = new Scanner(System.in);

    String strYear = scanner.nextLine();

    System.out.println("Enter 'Number Of People' : ");
    String strNumOfPeople = scanner.nextLine();
    
    try
    {
      int iYear = Integer.parseInt(strYear);
      int iNumOfPeople = Integer.parseInt(strNumOfPeople);      

      BirthdayPuzzle bp = new BirthdayPuzzle();
      double probability = bp.findProbability(iNumOfPeople,iYear);
      System.out.println("Probability : " + probability);
      System.out.println("Exact Percentage : " + (probability * 100) + "%");
      System.out.println("Rounded Percentage : " + 
        Math.round((probability * 100)) + "%");
    }
    catch (Exception ex) {
      System.out.println("Wrong Input!");
      System.exit(0);
    }
  }

  public double findProbability(int numOfPeople, int year) {
    double probability = 1;

    int numOfDays = numOfDaysInAYear(year);
    System.out.println("Num of days in " + year + " : " + numOfDays);

    for(int i=0;i<numOfPeople;i++) {
      probability *= ((numOfDays-i) * 1.0)/numOfDays;
    }
    System.out.println("Probability That 2 people dont " + 
      "share the same birthday : " + probability);

    return (1.0 - probability);
  }

  public int numOfDaysInAYear(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
      return 366;
    } else {
      return 365;
    }
  }
}

The above program asks for 'number of people' and 'year' as input and responds with the probabilty/percentage that atleast 2 people share the same birthday. Since, we are considering the 'year' also, I have taken care of leap years too.

So, for '48' people and '2001' year, the above program responds with an probability of '0.9605979728794225'. (96%).

And for '48' people and '2000' as input, it responds with '0.9602316176183399' (96%).

Spiral Walking

2008-07-04T13:14:00.000-07:00

In this post, I'm gonna write down my Java solution to a problem/algorithm, called 'Spiral Walking', which is indeed well-known among folks who deal with or well-versed in algo's or any other important technical implementations. Some of the algo's sound familiar for developers (or would have implemented them in some of the other way, without knowing that), but when it comes to implementing them (as fast as possible) in any software language (in which, they are proficient), they would fail to do so, in most of the cases. This applies to all (including me). Infact, it aint that easy. They are all hard earned skills.

I've implemented the solution for this 'Spiral Walking' problem, in Java. This solution might not be the best (or even upto the mark) and there might be many other ways to implement this, but I'm posting it any way, as its my soultion and I'm trying to do my best in coming up with a good and clear solution, for you folks to read and comment/suggest.

Problem: Spiral Walking

Description: The problem is to traverse a rectangular grid of cells, starting from the top first cell on the left. Initially, you start in the "right" direction and move through the grid, cell by cell. Each and every cell must be visited only once. If you end up in a cell, which is the last in that direction (or already visited), change direction and move forward. This should be done til you cover all the cells in that rectangular grid.

Example: (for a 4*3 grid)

- - >
^ > |
| v |
< - v

Java Solution: In this solution, I'm using direction flags and a boolean matrix (to identify if a cell has been already visited or not) and returning a string[][] array of the resulting spiral path. I've not optimised the code for clarity and other reasons. Please feel free to comment/suggest with any other ideas or positive criticism. The Java implementation is as below:


public class SpiralWalking {
    public static void main(String[] args)
    {
        SpiralWalking sw = new SpiralWalking();
       
        String res[][] = sw.walkSpirally(10,10);
        for(int i=0;i<10;i++) {
            System.out.println();
            for(int j=0;j<10;j++) {
                System.out.print(res[i][j] + " ");
            }
        }
    }

    public String[][] walkSpirally(int row, int col) {
        boolean[][] matrix = new boolean[row][col];
        String[][] res = new String[row][col];

        for(int i=0;i<row;i++) {
            java.util.Arrays.fill(matrix[i], false);
        }
       
        boolean east = true;
        boolean south = false;
        boolean west = false;
        boolean north = false;
        int x=0,y=0;

        while(true) {
            if(east) {
                if(y < (col-1) && !matrix[x][y]) {                   
                    res[x][y] = "-";
                    matrix[x][y] = true;
                    y++;
                } else {
                    if(!matrix[x][y]) {
                        res[x][y] = ">";
                    } else {
                        y--;
                        res[x][y] = ">";
                    }
                   
                    x++;
                    if(x >= row || matrix[x][y]) {
                        break;
                    }
                    east = false;
                    south = true;                   
                }
            } else if(south) {
                if(x < (row-1) && !matrix[x][y]) {
                    res[x][y] = "|";
                    matrix[x][y] = true;
                    x++;
                } else {
                    if(!matrix[x][y]) {
                        res[x][y] = "v";
                    } else {
                        x--;
                        res[x][y] = "v";
                    }
                   
                    y--;
                    if(y < 0 || matrix[x][y]) {
                        break;
                    }
                    south = false;
                    west = true;                   
                }
            } else if(west) {
                if(y > 0 && !matrix[x][y]) {
                    res[x][y] = "-";
                    matrix[x][y] = true;
                    y--;
                } else {
                    if(!matrix[x][y]) {
                        res[x][y] = "<";
                    } else {
                        y++;
                        res[x][y] = "<";
                    }
                   
                    x--;
                    if(x < 0 || matrix[x][y]) {
                        break;
                    }
                    west = false;
                    north = true;                   
                }
            } else if(north) {
                if(x > 0 && !matrix[x][y]) {
                    res[x][y] = "|";
                    matrix[x][y] = true;
                    x--;
                } else {
                    if(!matrix[x][y]) {
                        res[x][y] = "^";
                    } else {
                        x++;
                        res[x][y] = "^";
                    }
                   
                    y++;
                    if(y >= col || matrix[x][y]) {
                        break;
                    }
                    north = false;
                    east = true;                   
                }
            }
        }

        return res;
    }
}

Since each and every cell has to be visited, this algo might be slow for large input values. But for this Java implementation, I've used 'int' for 'row' and 'col'. So, you cant specify large input values anyways, although it still matters.

The code above outputs the following string[][] array, when provided with an input of 10 rows and 10 columns:

- - - - - - - - - >
^ - - - - - - - > |
| ^ - - - - - > | |
| | ^ - - - > | | |
| | | ^ - > | | | |
| | | | < v | | | |
| | | < - - v | | |
| | < - - - - v | |
| < - - - - - - v |
< - - - - - - - - v

This solution can be optimised and customised, as per the requirements.

nth Fibonacci Number

2008-06-29T13:06:00.000-07:00

If someone asks you how to find the nth number in the Fibonacci sequence, remember the below formula:

This formula is called 'Binets Formula' and is based on the 'Golden Ratio'.

Other References:

1) Wolfram Mathworld

2) Let Me Google For You

-----------------------------------------------------------------------------------------------------------------------------------------

Famous Math Equations

2007-10-06T04:24:00.000-07:00

Time and again, there's this question/speculation about the famous 'Math Equations and Inequalities' (which are related to Physics too), that changed the world (or perception of the world) and helped in many ways. Infact, you can see their applications in everyday life. Here are some of the equations and inequalities, that I know (having read/used 'em long back in school and still dig 'em, for the love of math):

Euler's Number (e):

This equation is one of the ways to calculate the Euler's number 'e'.

Pi:

'Pi' is defined as the ratio of the circumference of any circle to its diameter.

Equation Connecting 'e', 'Pi' and 'i':

All the 3 major constants in Mathematics are in this equation. Euler's number 'e', the most famous ratio of the circumference of a circle to its diameter 'pi' and the square root of '-1' (i).

Pythagoras/Pythagorean Theorem:
a² + b² = c²
In any "Right Triangle", the square of the 'Hypotenuse' is equal to the sum of the squares of the other 2 sides of the triangle.

Albert Einstein's Equation:
E=mc²
This equation connects 'mass', 'energy' and 'speed of light' which is considered by many, as the most famous equation in the world. This equation says that the amount of energy in a piece of mass ie equal to the mass multiplied with the square of the speed of light.

Equation For Gravitational Force:
F = G(m1)(m2)/d²
If two objects 'm1' and 'm2' are separated by a distance 'd', then the 2 objects will attract each other with a force 'F' given in this formula. 'G' is the gravitational constant (which approximately equals to 6.67*10-11Nm²kg-².

Apart from this stuff, there are many other equations that I haven't listed. If you have some of your fav set of equations, feel free to comment/suggest. :-)

--------------------------------------------------------------------------------------

Disclaimer

2003-07-03T14:37:00.000-07:00

DISCLAIMER:

1) Someone said: "Thanks to the internet, stupid people all over the world can pedal their own shit while simultaneously imbibing the shit of millions of others leading to an exponential growth in shit, the full meaning of which we are still struggling to grasp. But it's bound to be shit".

The Internet contains all sort of information. Some sources are genuine and some are fake (or scribbled by morons without proper knowledge in that field). So folks..its upto to you to use your intuition, do some research and cross-check with different sources of information and judge for yourself, what is right and what is wrong.

2) I'm just one face in the IT-crowd and I'm 100% sure that I do mistakes and I dont know everything. So, this blog might contain mistakes too, as nothing is perfect and there is no Utopian place.

5) I'm not trying to deal with any 'Politically Incorrect' stuff and I'm not trying to deal with (or hurt) anyone's sentiments.

6) Finally, if there's anything that sounds/looks wrong, please feel free to correct me and I'm all ears for that.

Happy Surfing! :-)