Google Code Jam Problem A. Tic-Tac-Toe-Tomek

Below is my solution for Problem A: Tic-Tac-Toe-Tomek

Well I qualified for Google Code Jam 2013 with only 60 points.

Problem

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single 'T' symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X's symbol is 'X', and player O's symbol is 'O'.
After a player's move, if there is a row, column or a diagonal containing 4 of that player's symbols, or containing 3 of her symbols and the 'T' symbol, she wins and the game ends. Otherwise the game continues with the other player's move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.
Given a 4 x 4 board description containing 'X', 'O', 'T' and '.' characters (where '.' represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:
• "X won" (the game is over, and X won)
• "O won" (the game is over, and O won)
• "Draw" (the game is over, and it ended in a draw)
• "Game has not completed" (the game is not over yet)
If there are empty cells, and the game is not over, you should output "Game has not completed", even if the outcome of the game is inevitable.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 4 lines with 4 characters each, with each character being 'X', 'O', '.' or 'T' (quotes for clarity only). Each test case is followed by an empty line.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is one of the statuses given above. Make sure to get the statuses exactly right. When you run your code on the sample input, it should create the sample output exactly, including the "Case #1: ", the capital letter "O" rather than the number "0", and so on.

Limits

The game board provided will represent a valid state that was reached through play of the game Tic-Tac-Toe-Tomek as described above.

Small dataset

1 ≤ T ≤ 10.

Large dataset

1 ≤ T ≤ 1000.

Sample

Input	Output
6 XXXT .... OO.. .... XOXT XXOO OXOX XXOO XOX. OX.. .... .... OOXX OXXX OX.T O..O XXXO ..O. .O.. T... OXXX XO.. ..O. ...O	Case #1: X won Case #2: Draw Case #3: Game has not completed Case #4: O won Case #5: O won Case #6: O won

Note

Although your browser might not render an empty line after the last test case in the sample input, in a real input file there would be one.

write a function to check given string matches with given pattern

write a function to check given string matches with given pattern
Condition: only one wildcard used in the pattern, that is '*', but can be used in the pattern more than once.
Example: 

pattern: *abc*def*.doc*
string: adsfabcxyzdefgh.docx
output : Matching


pattern: *abc*def*.doc*
string: adsfabcxyzdefgh.do1cx
output : Not Matching

public class isMatchingWithWildcard {

public static void main(String [] args){

String pattern = "*abc*def*.doc*";

String str = "adsfabcxyzdefgh.do1docx";

if(isMatching(str, pattern))

System.out.print("Matching");

else

System.out.print("Not Matching");

}

public static Boolean isMatching(String str, String pattern){

int l = pattern.length();

if(pattern.lastIndexOf("*") == l-1)

pattern= (String) pattern.subSequence(0, l-1);

if(pattern.charAt(0) == '*')

pattern= (String) pattern.subSequence(1, pattern.length());

pattern = pattern.replace("*", "__");

String [] patternArray = pattern.split("__");

String sorttenString =str;

for(String aPattern:patternArray){

String [] temp = sorttenString.split(aPattern);

if(temp.length==1 && (aPattern == patternArray[patternArray.length-1] 

&& !sorttenString.toLowerCase().contains(aPattern.toLowerCase())))

return false;

str.substring(temp[0].length()+aPattern.length());

}

return true;

}

}

Let me know your thoughts

Finding Pythagorean triplets in an array.

Finding Pythagorean triplets in an array.
Input :     3 9 4 8 6 11 12
Output :  No such solution exist


Input :    3 5 4 8 6 11 10
Output : 5.0, 3.0, 4.0    10.0, 6.0, 8.0

//   WORKING code in java with  time O(n^2)

import java.util.Arrays;

public class PythagoreanTripletsInArray {

public static double [] getSquare(String [] args){

double [] array = new double[args.length];

for(int i=0;i<args.length;i++){

double j=Integer.parseInt(args[i]);

array[i]=j*j;

}

return array;

}

public static void main(String [] args ){

double [] array =getSquare(args);

Arrays.sort(array);

Boolean flage = true;

for(double aInt : array){

for(int i=0,j=(array.length-1);i<j;){

double sum = array[i]+array[j]; 

if(aInt == sum){

System.out.println(Math.sqrt(aInt)+", "+Math.sqrt(array[i])+", "+Math.sqrt(array[j]));

flage = false;

break;

}

else if(aInt > sum)

i++;

else

j--;

}

}

if(flage)

System.out.print("No such solution exist");

}

}

Let me know your thoughts

Re-arrange the odd/even to odd/even places

Given an array of integers [3,1,4,5,7,6,10,8],
re arrange elements such that either even numbers in even locations or odd numbers in odd locations.
in O(n)

output :  6 1 4 5 8 3 10 7

#include<stdio.h>

void Swap (int A[], int i, int j)
{
    int temp = A[i];
    A[i]=A[j];
    A[j]=temp;
}

int main()
{
    int A[] = {3,1,4,5,7,6,10,8};
    int i=0,j=1,n;
    n=sizeof(A)/sizeof(int);
    while(i<n)
    {
        while(i<n && A[i]%2 == 0)
            i+=2;
        while(j<n && A[j]%2 == 1)
            j+=2;
        if(i<n && j<n)
            Swap(A,i,j);
    }// end of while

    for(i=0;i<n;i++)
        printf(" %d",A[i]);

return 0;
}

Let me know your thoughts

Sort an Array of 0 1& 2 in one pass

 Given an array int a[] = {0, 1, 1 ,0, 2, 2, 1, 0 ,1, 2, 1,0 }
to be converted into {0, 0, 0, 0, 1, 1, 1, 1, 1 ,2 ,2 ,2}
inplace and single pass

Input :  int A[] = {2,2,2,1,1,1,0,0,0,1,2,0};
Output:  0 0 0 0 1 1 1 1 2 2 2 2

#include<stdio.h>

int main()
{
    int A[] = {2,2,2,1,1,1,0,0,0,1,2,0};
    int j,i,x,y,n,t=A[0];
    n=sizeof(A)/sizeof(A[0]);
printf("Size of array : %d\n",n);
    for(x=i=0,y=j=n-1;i<=j;)
    {
        if(t==0)
        {
            A[x]=0;
            x++;
            i++;
            t=A[i];
        }
        else if(t==2)
        {
            t=A[y];
            A[y]=2;
            y--;
            j--;
        }
        else
        {
            i++;
            t=A[i];
        }
    }

    while(x<=y)
    {
        A[x++]=1;
    }

    for(i=0;i<n;i++)
    {
        printf(" %d",A[i]);
    }
return 0;
}

Let me know your thoughts.

Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.

Explanation:

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.

Input format :

First line of the input contains T , number of test-cases.

Then follow T testcases. Each testcase has given format.

N [ representing the dimension of the matrix N X N ].

Followed by N lines , with N numbers on each line.

Ouput format :

For each test case print one line ,  number of connected component it has.

Sample Input :

4

4

0 0 1 0

1 0 1 0

0 1 0 0

1 1 1 1

4

1 0 0 1

0 0 0 0

0 1 1 0

1 0 0 1

5

1 0 0 1 1

0 0 1 0 0

0 0 0 0 0

1 1 1 1 1

0 0 0 0 0

8

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

Sample output :

1

3

3

9

Constraint :

0 < T < 6 

0 < N < 1009 

=================WORKING CODE=================

#include<stdio.h>

int count_connected_set(int A[1015][1015],int i,int j,int n)

{

    A[i][j]=2;

    if(A[i-1][j-1]==1 && i>0 && j>0 && i<=n && j<=n )     //NW

        count_connected_set(A,i-1,j-1,n);

    if(A[i-1][j]==1 && i>0 && j>0 && i<=n && j<=n)       //N

        count_connected_set(A,i-1,j,n);

    if(A[i-1][j+1]==1 && i>0 && j>0 && i<=n && j<=n)//   //NE

        count_connected_set(A,i-1,j+1,n);

    if(A[i][j-1]==1 && i>0 && j>0 && i<=n && j<=n)       //W

        count_connected_set(A,i,j-1,n);

    if(A[i][j+1]==1 && i>0 && j>0 && i<=n && j<=n)       //E

        count_connected_set(A,i,j+1,n);

    if(A[i+1][j-1]==1 && i>0 && j>0 && i<=n && j<=n)     //SW

        count_connected_set(A,i+1,j-1,n);

    if(A[i+1][j]==1 && i>0 && j>0 && i<=n && j<=n)       //S

        count_connected_set(A,i+1,j,n);

    if(A[i+1][j+1]==1 && i>0 && j>0 && i<=n && j<=n)     //SE

        count_connected_set(A,i+1,j+1,n);

return 1;

}// end of count_connected_set()

int main()

{

    int i,j,t,k,n,A[1015][1015],count;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                scanf("%d",&A[i][j]); // geting input a test case;

        count =0;

        for(i=1;i<=n;i++)

        {

            for(j=1;j<=n;j++)

                if(A[i][j]==1)

                    if(count_connected_set(A,i,j,n))

                        count++;

        }// of for

        printf("%d\n",count);

    }// end of while

return 0;

}

Let me know your thoughts.