Ugly Numbers

uglynumbers.py

'''
Credits: This challenge has appeared in a google competition before.
Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes (2, 3, 5 or 7). Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note that 0 is ugly. Also note that negative numbers can also be ugly: -14 and -39 are examples of such numbers.

One day on your free time, you are gazing at a string of digits, something like:

123456
You are amused by how many possibilities there are if you are allowed to insert plus or minus signs between the digits. For example you can make: 
1 + 234 - 5 + 6 = 236
which is ugly. Or

123 + 4 - 56 = 71
which is not ugly. 

It is easy to count the number of different ways you can play with the digits: Between each two adjacent digits you may choose put a plus sign, a minus sign, or nothing. Therefore, if you start with D digits there are 3^(D-1) expressions you can make. Note that it is fine to have leading zeros for a number. If the string is '01023', then '01023', '0+1-02+3' and '01-023' are legal expressions. 

Your task is simple: Among the 3^(D-1) expressions, count how many of them evaluate to an ugly number.

INPUT SAMPLE:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will be a single line containing a non-empty string of decimal digits. The string in each test case will be non-empty and will contain only characters '0' through '9'. Each string is no more than 13 characters long. E.g.

1
9
011
12345
OUTPUT SAMPLE:

Print out the number of expressions that evaluate to an ugly number for each test case, each one on a new line. E.g.

0
1
6
64
'''


def exponent_iterate(base, size):
    '''
    This function returns the generator that iterates
    through all the possiblities of combinations of list
    elements. yield None when iteration finishes.

    base: the max value for each element
    len: the length of iterated list
    return: yield a list length of len, the result of 
           each iteration
    '''
    if size == 0:
        yield None

    list = [0 for i in range(size)]
    while True:
        for i in range(size):
            yield list

            list[0] += 1
            for j in range(size):
                if list[j] >= base:
                    if j == size - 1:
                        yield None
                    else:
                        list[j] = 0
                        list[j + 1] += 1
                else:
                    break


def make_int(digits):
    '''
    turn list of digits into corresponding integer
    e.g. [1,2,3] -> 123
    
    digits: input of list of digits
    return: integer
    '''
    val = 0
    for i in digits:
        val = val * 10 + i

    return val


def make_expr(digits, operators):
    '''
    Make the expression.

    digits: list of digits
    operators: list of operators

    return: a list of operands and operators
    '''
    size = len(digits)
    expr = []

    index = 0
    
    for i in range(size - 1):
        # no operator
        op = operators[i]
        if op == 0:
            pass
            
        # minus operator
        elif op == 1:
            num = digits[index : i + 1]
            expr.append(make_int(num))
            expr.append('-')
            index = i + 1

        # plus operator
        elif op == 2:
            num = digits[index : i + 1]
            expr.append(make_int(num))
            expr.append('+')
            index = i + 1

    if index != size:
        expr.append(make_int(digits[index: size]))

    return expr
    

def iter_expr(digits):
    '''
    Generates all possible expression combinations of digits 
    and operators, return a generator of list of strings. 

    digits: input the list of digits
    '''
    size = len(digits)
    expo = exponent_iterate(3, size - 1)

    if size == 1:
        yield make_expr(digits, [])

    for i in expo:
        # iterate through all possible expression combination
        if i != None:
            yield make_expr(digits, i)
        else:
            break


def eval_expr(expr):
    '''
    Eval the expr.

    expr: the list of integers and operators to eval
    retrn: the eval
    '''
    stack = []
    val = expr[0]

    i = 1
    while (i < len(expr) - 1):
        if expr[i] == '+':
            val = val + expr[i + 1]
        elif expr[i] == '-':
            val = val - expr[i + 1]
        i += 2
        
    return val


def is_ugly(num):
    '''
    Input a num, determine if it's ugly

    num: input the number
    return: bool, if ugly or not
    '''
    absnum = abs(num)
    return any ([num % i == 0 for i in [2, 3, 5, 7]])



def main():
    import sys
    test_cases = open(sys.argv[1], 'r')


    for test in test_cases:
        digits = list(map(int, list(test.strip('\n'))))
    
        iter = iter_expr(digits)
        sum = 0
    
        for i in iter:
            if is_ugly(eval_expr(i)):
                sum += 1
    
    
        print(sum)
    
    test_cases.close()

main()