Solutions to Google Code Jam Qualification Round 2010 Africa Problems

GoogleCodeJam_Qualification_2010_Africa.txt

Below are the solutions to the three problems of the Google Code Jam Qualification Round of 2010 in Africa.

Reverse_Words.py

def unscramble(sentence):
    unscramble_sent = [] # array placeholder for unscrambled sentence
    sentence_array = sentence.split() # split sentence into array of words
    for j in range(len(sentence_array) - 1, -1, -1): # iterates backwards through indices including 0
        unscramble_sent.append(sentence_array[j]) # adds words to sentence backwards
    final_sent = ' '.join(unscramble_sent) # joins words in array to make one space separated sentence
    return final_sent    

def Reverse_Words():
    '''Reads sentences from a given input file, and writes each word in each sentence backwards onto a new output file.'''
    file = open('B-large-practice.in','r')
    written_file = open('Reverse_Words_final.txt', 'w')
    iterations = file.readline() # reads number of total iterations of lines from input file
    for i in range(0, int(iterations)):
        scrambled_sent = file.readline()
        final_unscramble_sent = unscramble(scrambled_sent) # variable holding unscrambled sentence
        written_file.write("Case #{0}: {1}\n".format(i + 1, final_unscramble_sent))
    file.close()
    written_file.close()
    
Reverse_Words()

Store_Credit.py

def two_sub_arrays(arr):
    outermost_array = [] # holds all subarrays
    sum_array = [] # holds all sums
    for i in range(0, len(arr) - 1): # first pointer always starting from 0 index omitting last index
        for j in range(1, len(arr)): # 2nd pointer starting from 1 index include last index
            if i == j: # omits duplicates of indicies
                continue
            else:
                outermost_array.append([arr[i],arr[j]]) # appends length 2 lists
    return outermost_array

def sum_subarrays(arr):
    sum_dict = {} # arrays of sums placeholder
    for number in range(0, len(arr)): # for each subarray in a larger array
        sum_dict[number] = sum(arr[number]) # adds sum of each subarray to a sum dictionary keeping track of indices
    return sum_dict
        
def Store_Credit():
  '''Reads file of inputs provided by Google, and writes the indices of the two products that add up to the amount of given store credit to a new output file.'''
    file = open('A-small-practice.in','r')
    written_file = open('Store_credit_output.txt','w')
    iterations = file.readline() # reads first line of file to determine number of iterations
    for i in range(0, int(iterations)):
        credit = file.readline() # C value
        num_items = file.readline() # Number of items in store
        items_list = file.readline().split() # list of item prices separated by their spaces
        for q in range(0,len(items_list)): # converts all string numbers to int numbers
            items_list[q] = int(items_list[q])
        doubles_list = two_sub_arrays(items_list) # list of all possible two item combinations
        total_price_dict = sum_subarrays(doubles_list) # dictionary of all combined prices and their corresponding indicies
        for index, sums in total_price_dict.items():
            if int(sums) == int(credit):
                credit_sum_list = doubles_list[index] # correct two prices that equal credit
                case_1 = items_list.index(credit_sum_list[0])
                items_list[case_1] = 0 # replaces already found cases with 0 to avoid duplicates
                case_2 = items_list.index(credit_sum_list[1])
                written_file.write("Case #{0}: {1} {2}\n".format(i + 1, case_1 + 1, case_2 + 1)) # add 1 to nullify zero base
                break # to stop duplicates
            else:
                continue
    written_file.close()
    file.close()
Store_Credit()

T9_Spelling.py

def T9_Spelling():
    '''Reads a Latin based alphabet sentence and converts each letter to its alpha-numeric equivalent and writes each interation to a file.'''
    alpha_num_dict = {'a':'2', 'b':'22', 'c':'222', 'd':'3', 'e':'33', 'f':'333', 'g':'4', 'h':'44', 'i':'444', 'j':'5', 'k':'55', 'l':'555', 'm':'6', 'n':'66', 'o':'666', 'p':'7', 'q':'77', 'r':'777', 's':'7777', 't':'8', 'u':'88', 'v':'888', 'w':'9', 'x':'99', 'y':'999', 'z':'9999', ' ':'0'}
    file = open("C-small-practice.in", "r")
    written_file = open("T9_output.txt", "w")
    iterations = int(file.readline())
    num = 0 # number of input lines being read
    while num < iterations:
        letters_array = list(file.readline())
        numeric_string = ''
        for index in range(0, len(letters_array)):
            current_string_nums = alpha_num_dict[letters_array[index]] # number string values of specified letter keys
            numeric_string += current_string_nums # concatenates to a continuous empty string
            try:
                next_string_nums = alpha_num_dict[letters_array[index + 1]]
                if current_string_nums[0] in next_string_nums:
                    numeric_string += ' '
                else:
                    continue
            except:
                break
        num += 1 # move to next line of file
        written_file.write("Case #{0}: {1}\n".format(num, numeric_string))
    written_file.close()
    file.close()
    
T9_Spelling()