Friday, September 4, 2009

Alien Language

Alien Language Problem from CodeJam 2009, I solved this one pretty quickly but ran out of time on the other two (time meaning, I wanted to sleep since I work 36ish hours a week and go to school 11 credits)

If you don't want to see the solution (in perl) don't look at my code, but here it is I'll explain it below.

Quick overview of the problem:
The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.
My solution:

while (chomp($read_line = <>))
{
@settings = split(/\s/, $read_line);
for ($i = 0; $i < $settings[1]; $i++)
{
chomp($item = <>);
push(@items, $item);
}
for ($i = 0; $i < $settings[2]; $i++)
{
chomp($testCase = <>);
$counter = 0;
foreach $word (@items)
{
$testCase =~ s/\(/\[/g;
$testCase =~ s/\)/\]/g;
if ($word =~ m/$testCase/i)
{
$counter++;
}
}
$caseNumber = $i + 1;
print "Case #$caseNumber: $counter\n";
}
}

Basically we grab the first line, and look for the 3 numbers, grab the second one to determine the number of lines we drop down for our test cases, then the 3rd number to grab the actual tests, then we just make it a regular expression, worked pretty quick, I know at least on the large dataset I had over 3:41 remaining, (maybe more) from when I downloaded it, to when I completed the upload. Worked pretty quick