Our code from GCJ 2014 Round 1C Problem A

jun_GCJ_2014_1C_PartElf.py

import math

FILE_NAME = "1C_ProbA_PartElf_small.in"
OUTPUT = "1C_ProbA_PartElf_small.out"

def load_file():
    '''
    String -> ListOfInt
    Open a newline delimited text file and do the following
    manipulations:
    (1) Remove all '\n' chars and insert each line into a list
    (2) Convert split strings into lists to create a list of
        sublists
    (3) Convert each string element in each sublist into a list
        of chars
    (4) Cast each char element in each sublist into an int

    '''
    in_file = open(FILE_NAME, 'r', 0)
    line_list = list(in_file)
    in_file.close()
    # remove all newline chars from the string blob
    line_list = [i.strip('\n') for i in line_list]
    # split blob into lines and put lines into a list
    line_list = [line_list[i].split() for i in range(len(line_list))]
    # split P/Q fractions into sublists containing ['P', 'Q']
    line_list = [line_list[i][0].split('/') for i in range(len(line_list))]
    # cast all list elements to type int
    line_list = [map(int, line_list[i]) for i in range(len(line_list))]
    return line_list


def num_cases(list_file):
    '''
    ListOf Natural -> Natural
    Given a list of lines containing Naturals, return a Natural
    denoting the number of cases to consider.
    **NOTE**: this function mutates the input list!

    >>> num_cases([[5], [1, 2], [3, 4], [1, 4], [2, 23], [123, 31488]])
    5
    '''
    ncases = list_file.pop(0)[0]
    return ncases

def next_case(list_file):
    '''
    ListOf Natural -> ListOf Natural
    Given a list of lines containing sublists of ints, return the
    next case where a case is defined as a line of form
    [a, b]
    where a and b are natural nums.

    **NOTE**: this function mutates the input list!

    >>> next_case([[1, 2], [3, 4], [1, 4], [2, 23], [123, 31488]])
    [1, 2]
    '''
    nextc = list_file.pop(0)
    return nextc


def calculate_num_gens(list_PQ):
    '''
    ListOf Natural -> Int
    Given a list of the form [a, b] where a and b are both natural nums,
    return the minimum num of generations ago that there was a 1/1 Elf
    in Vida's family

    >>> calculate_num_gens([1, 2])
    1

    >>> calculate_num_gens([3, 4])
    1

    >>> calculate_num_gens([1, 4])
    2

    >>> calculate_num_gens([2, 23])
    impossible

    >>> calculate_num_gens([123, 31488])
    8
    '''
    P = float(list_PQ[0])
    Q = float(list_PQ[1])
    ngens = 0

    if not (Q % 2) == 0:
        return 'impossible'
    else:
        math.ceil(abs(math.log((P/Q), 2)))
        return int(ngens)


def write_out(outfile):
    '''
    -> File
    Calls helper functions and writes output to outfile
    '''

    output_file = open(outfile, 'w')
    input_list = load_file()
    copy_input = input_list
    ans = 0
    case_cnt = 1

    for i in range(num_cases(copy_input)):
        ans = calculate_num_gens(next_case(copy_input))
        output_file.write(
            'Case #' + str(case_cnt) + ': ' + str(ans) + '\n')
        case_cnt += 1
    output_file.close()

## MAIN PROGRAM ##
write_out(OUTPUT)

if __name__ == "__main__":
    import doctest
    doctest.testmod()