22. Code Jam
By: Steve Krenzel
Previous Index Next
Alien Language

This challenge was the easiest and should have taken most people just a few minutes.

You're given a list of words that define a language, and then a list of patterns that should represent a word in that language. The catch is that the patterns have unknown characters with potential solutions in parentheses. For example, if our language had three words "bad", "dad" and "sad" and we were given a pattern "(bd)ad", either "b" or "d" could be the first letter of the desired word. There are two words in our language that match the pattern: "bad" and "dad". On the other hand if we were given the pattern "(bt)a(ds)", we'd have four potential words "bad", "bas", "tad", and "tas" but only one of them is in our language so only one possible combination matches.

The challenge was simply to count how many words in the alien language matched a given pattern. We can simply translate the patterns into regular expressions by substituting parentheses for square brackets, and then use our regular expression library to count the matches found. The code looks like:

from string import maketrans
from sys    import stdin
from re     import findall

length = int(stdin.readline().split()[1])
lang   = "".join(stdin.readline() for i in range(length))

for i, test in enumerate(stdin.readlines()):
    test = test.translate(maketrans("()", "[]"))
    print "Case #%d: %d"%(i, len(findall(test, lang)))

To try it just save the code in a file (e.g. alien.py), download sample input from the challenge site, and run "python alien.py < A-small-practice.in" at the command line.

About the author
I'm Steve Krenzel, a software engineer and co-founder of Thinkfuse. Contact me at steve@thinkfuse.com.
Previous Next