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 D=str N=str 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.
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 🙂