Created
April 28, 2014 17:18
-
-
Save TimboTambo/11378320 to your computer and use it in GitHub Desktop.
Alien Language - Google Code Jam solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Alien Language - solution | |
#Google Code Jam 2009 - Qual round | |
#Problem available at http://code.google.com/codejam/contest/90101/dashboard#s=p0 | |
#By Tim Lee, 28/04/14 | |
#Input as L D N, followed by D dictionary words, N 'patterns' to decode | |
f = open('A-small-practice.in','r') | |
g = open('A-small-practice-output.txt','w') | |
L, D, N = (int(x) for x in f.readline().split()) | |
def make_dictionary(): | |
"""Creates dictionary from list in file""" | |
dictionary = [] | |
for i in range(D): | |
dictionary.append((f.readline()).rstrip('\n')) | |
return dictionary | |
def format_pattern(raw_pattern): | |
"""Turns pattern string into a more easily iterable form. | |
Removes parentheses and turns letters in between them into a | |
sub-list""" | |
pattern_formatted = [] | |
bracketed_letters = [] | |
in_brackets = False | |
for char in raw_pattern: | |
if (char != "(" and char != ")" and in_brackets != True): | |
pattern_formatted.append(char) | |
elif char == "(": | |
in_brackets = True | |
elif char == ")": | |
pattern_formatted.append(bracketed_letters) | |
bracketed_letters = [] | |
in_brackets = False | |
elif in_brackets == True: | |
bracketed_letters.append(char) | |
return pattern_formatted | |
def match_words(pattern_formatted, dictionary): | |
"""Takes the formatted pattern and dictionary and returns the number of | |
pattern configurations that match with dictionary words""" | |
matched_words = 0 | |
for word in range(D): | |
for letter in range(L): | |
match = False | |
for subletter in range(len(pattern_formatted[letter])): | |
if dictionary[word][letter] == pattern_formatted[letter][subletter]: | |
match = True | |
if match == False: | |
break | |
if match == True: | |
matched_words += 1 | |
return matched_words | |
def write_result(case, matched_words): | |
"""Writes the result in required format to file and prints to console""" | |
print("Case #" + case + ": " + matched_words) | |
g.write("Case #"+ case +": "+ matched_words + "\n") | |
DICTIONARY = make_dictionary() | |
for n in range(N): | |
#Iterates through each pattern to test for matching words | |
pattern = (f.readline()).rstrip('\n') | |
matched_words = match_words(format_pattern(pattern), DICTIONARY) | |
write_result(str(n+1), str(matched_words)) | |
f.close() | |
g.close() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment