Google Code Jam Qualification Round 2009 Problem A. Alien Language

First time using Python sets.

	import sys
	# return a list of all tokens from a case
	# e.g. abc(abc)b(ab) returns [a,b,c,abc,b,ab]
	def getTokens(case):
	tokens = []
	token1 = case.split(")")
	for t in token1:
	t2 = t.split("(")
	for c in t2[0]:
	tokens.append(c)
	if len(t2) > 1:
	tokens.append(t2[1])
	return tokens
	# return all dictionary entries that has
	# that token at that position
	# e.g. getEntries(0,"ab") returns all entries
	# that has either a or b at pos 0
	# returns a set so no overlap/duplicate entry
	def getEntries(pos,token):
	result = set([])
	for c in token:
	if (pos,c) in sets:
	result |= sets[(pos,c)]
	return result
	L,D,N = sys.stdin.readline().strip().split()
	L = int(L)
	D = int(D)
	N = int(N)
	# initialize map of characters to dictionary entry
	# dictionary[(position, letter)] = set of all dictionary entries
	# that has that letter at that position
	sets = {}
	for d in xrange(D):
	entry = sys.stdin.readline().strip()
	l = 0
	for c in entry:
	if (l,c) in sets:
	sets[(l,c)].add(entry)
	else:
	sets[(l,c)] = set([entry])
	l += 1
	for n in xrange(N):
	# 1. read case, split into tokens
	# 2. for each position/token get all entries that has that token at position
	# 3. then get the entries common to all tokens/is present at every position
	case = sys.stdin.readline().strip()
	tokens = getTokens(case)
	possible = getEntries(0,tokens[0])
	for l in xrange(1,L):
	possible &= getEntries(l, tokens[l])
	print "".join(["Case #",str(n+1),": ",str(len(possible))])

view raw gistfile1.txt hosted with ❤ by GitHub