Thursday, September 3, 2009

Google Code Jam 2009

This was the first time I registered for Google Code Jam. Researching about this great event I came to know that it gives way to free use of languages. Google allows its participants to code in any language they wish to. Starting from c, c++, java, batch files to php, perl, brainf*ck and all.

It was the qualification round in which I scratched my 'hairless' head throughout the day. The round consisted of three questions. One had to submit an output file of solution of test cases. Each question consisted of two test cases small and large. 4 minutes of time was given to a participant to upload his source code file and the output file in small test cases. Time was increased to 8 mins in case of large test cases. It was necessary to solve at least one small test case and one large test case of any question to qualify for next round. I was able to solve a small one.. :)

The question I solved was called "Alien Language". One can easily 'google' the whole question. I m giving the source code which I submitted :

using namespace std;
int change(string strConvert)
{
int intReturn;
intReturn = atoi(strConvert.c_str());
return(intReturn);
}

void main()
{
ifstream myfile("g1.txt");
ofstream opens("g2.txt");
string line;
int cases=0;
char words[800][800],letters[800][800],answers[800][800];
int L,D,N,r=0,c=0,f=0,m;
getline(myfile,line,' ');
L=change(line);
getline(myfile,line,' ');
D=change(line);
getline(myfile,line,'\n');
N=change(line);
for(long int i=0;i++)
{
getline(myfile,line,'\n');
for(int j=0;j++)
{
words[i][j]=line[j];
}
words[i][L]='\0';
}
for(int q=0;q++)
{
cases=0;
r=0;
getline(myfile,line,'\n');
f=0;
m=line.size();
while(f!=m)
{
if(line[f]=='(')
{
while(line[f]!=')')
{
f++;
if(line[f]!=')')
{
letters[r][c]=line[f];
c++;
}
}
letters[r][c]=NULL;
f++;
r++;
c=0;
}
else
{
letters[r][c++]=line[f];
letters[r][c]=NULL;
r++;
c=0;
f++;
}
}
for(long int s=0;s++)
{
f=0;
for(long int k=0;k+)
{
for(long int a=0;a++)
{
if(words[s][k]==letters[k][a])
{
f++;
break;
}
}
}
if(f==L)
cases++;
}
opens<<"Case #"<<<": "<<<"\n";
}
getch();
}

Explanation of code:
What I did in the program is that I took each word of language into a double dimension array called 'words'. Each test case was then bifercated into letters in another double dimension array called 'letters'. The first letter in words was then regularly checked in the different letters of each test case. The moment it matched the loop got broken with an increment of a flag called 'f'. The moment flag became equal to length of word it was sure that the given combination exists, hence, the case variable gets incremented which is ultimately our answer and gets written in the output file.
The only problem that came with this solution was during the execution of large test case. It would have been easily implemented through vectors but lack of time compelled me to quit upon it. Actually, due to continuous memory allocation sometimes due to large datasets, the values get written on read only part of memory which generates errors.

So, I settled with a 10 point mark.. BTW my first experience with Google Code Jam was awesome..!!
* * * * *

No comments:

Post a Comment