Solution: Alien Language (Google Code Jam 2009 Qualification Round Problem A)

al.py

import string, sys
import re

"""
ab = {"a":1,"b":2,"c":3,"d":4,"e":5,
	  "f":6,"g":7,"h":8,"i":9,"j":10,
	  "k":11,"l":12,"m":13,"n":14,"o":15,
	  "p":16,"q":17,"r":18,"s":19,"t":20,
	  "u":21,"v":22,"w":23,"x":24,"y":25,"z":26}
"""
# alphabet map
ab = {}
i = 1
for c0 in string.ascii_lowercase:
	ab[c0] = i
	i += 1

# files
fin = file(sys.argv[1])
fout = open(sys.argv[2], 'w')
lines = fin.readlines()
[l,d,n] = lines[0].split()
print l, d, n
def trunc(s0):
	return s0.rsplit('\n')[0]
words = map(trunc, lines[1:int(d)+1])
patterns = map(trunc, lines[int(d)+1:])

# bitmaps
# slow for the large cases (5000 words, 500 patterns)
# can be improved with some sort of spatial indexing
# so we dont have to loop over entire alphabet ;)

# regex
def regex(s0):
	s1 = s0.replace('(', '[')
	s2 = s1.replace(')', ']')
	return s2
regexes = map(regex, patterns)
for i in range(len(regexes)):
	count = 0
	for j in range(len(words)):
		match = re.match(regexes[i], words[j])
		# print match
		if match is not None:
			count += 1
	fout.write("Case #%d: %d\n" % ((i + 1), count))