Category Archives: GCJ

Solving GCJ 2009 Qualifying Round’s Question

Feeling bored at office, I thought of surfing the web to look for any upcoming programming contests and I came across Google Code Jam 2010. Registrations are already open and contest is going to begin soon.

So, I looked at the Practice section to do some time pass and came across the question Alien Language. It was good to get back to do something productive and so I did, creating pseudo-code in roughly 30 minutes.

while in.eof
 read line
 split line on spaces into string of 3 blocks..
 L=str[0]
 D=str[1]
 N=str[2]
 break
end

counter=1
while in.eof || counter <= D
 read line
 write line to file #1
end

while in.eof || counter <= N
 read line
 write line to file #2
end

i=1
while f2.eof || i <= N
 case[i-1] = 0
 read line and store into pattern..
 while f1.eof
   read line and store into word..
   if pattern matches word then
     ++case[i-1];
 end
end

Well, the following source code doesn’t look similar to the pseudo-code I wrote above. However, as I no longer code in C/C++/Java and getting used to writing shell-scripts in office irregularly. I thought of doing this with shell-scripting and within 15 minutes, I was ready to test the code.

#!/bin/ksh
# Script Name: gcj09qr_solveq1.ksh
# --- GCJ 2009 QR --- Alien Language

L=
D=
N=

while read line
do
   L=`echo $line | cut -d' ' -f1`
   D=`echo $line | cut -d' ' -f2`
   N=`echo $line | cut -d' ' -f3`
   break
done < $1

#File 1
cat $1 | tail -`expr $(cat $1|wc -l) - 1` | head -$D >  gcjq1_f1.out

Well, as you can see I used a formula to extract the D lines, where each line has 1 word exactly of L characters. I created this formula few weeks back in one of my blog entries.

#File 2
sed 's/(/[/g; s/)/]/g' < $1 | tail -$N >   gcjq1_f2.out

I=1
while read line
do
  echo "Case #$I: $(grep "$line"  gcjq1_f1.out|wc -l)"
  I=`expr $I + 1`
done <  gcjq1_f2.out

This is the way, I thought of solving the case. I tested the code with Small and Large Input case, it worked as expected.

gcj09qr_solveq1.ksh input_file.extn

I guess that could be one of the smallest solution for that question. If I code this in Java, I am sure it will take many more lines to reflect the steps in pseudo-code.

Looking forward to participate in the contest this year. Well, solving this question was a good head start :)