Statement

The statement for this problem can be found in the Google CodeJam 2009 page, or click this link

Solution

The solution is not complex but it has a tricky thing.

The first thing to do is to populate a set of words which will be the dictionary containing the D words of the Alien Language.

Then the tricky part comes, how to process the sequence of characters that might conform a word. There are basically two choices:

• Try each possible combination and see which of those match a valid word.
• For each valid word see if the characters received can conform it.

Both of the choices lead to a right answer but time plays a crucial part in the competence and if you choose the wrong one the program will never end, not at least in a reasonable amount of time.

Let's analyze the solutions:

• If we try each possible combination based on the characters received it can lead to process $27^{15}$ combinations for the large set which is 2954312706550833698643. Forget about processing that in 8 minutes. And that's only for one test case! If the number of cases is the highest your program may end up trying to process $27^{15} * 500$ which is even more!
• If we try to match each valid word to the characters received we will have to try 5000 words per each case. That gives as a $500 * 5000 = 2500000$ combinations to process which is definitively not much.

So once decided the approach to take, how to implement it? What I did is to process each sequence of characters received and generate a list consisting of L sets, each containing the possible characters in that position. After parsing the case it was a piece of cake, for each word I determined the character at each position was in the set of characters at that position in the sequence, if for all characters that happened then the word was possible.

The python source code (GCJ2009-Q-A.py):

words = set()
 
if __name__ == '__main__':
    L, D, N = map(int, input().split())
    for i in range(D):
        words.add(input())
    for i in range(1, N+1):
        characters = input()
        characters_set = []
        s = set()
        flag = True
        for c in characters:
            if c == '(':
                flag = False
            elif c == ')':
                flag = True
            else:
                s.add(c)
            if flag:
                characters_set.append(s)
                s = set()
        result = 0
        for word in words:
            t = True
            for k in range(L):
                if word[k] not in characters_set[k]:
                    t = False
                    break
            if t:
                result += 1
        print("Case #{0}: {1}".format(i, result))