#!/usr/bin/env python
'''
Generates simple arithmetic questions
'''
import random
import sys
import optparse
import doctest
import math
from itertools import izip

addition_difficulties = {
    'digit_zero' : 1,   # any digit added to zero
    'even_even'  : 2,   # sum of even digits
    'odd_odd'    : 2,   # sum of odd digits 
    'even_odd'   : 3,   # sum of even and odd digits
    'carry'      : 2    # difficulty of carry (for remembering and then adding)
}

subtraction_difficulties = {
    'digit_zero' : 1,    # difference of zero and any digit
    'same_digits': 1,    # difference of same values digits
    'even_even'  : 2,    # difference of even digits
    'odd_odd'    : 2,    # difference of odd digits
    'even_odd'   : 3,    # difference of even and odd digits
    'borrow'     : 2,    # doing a borrow
    'twodigit_digit' : 4 # difference of two-digit number and digit
}

multiplication_difficulties = {
    'carry'  : 1,   # carry operation, summation difficulty is seperate
    'offset' : 1,
}

division_difficulties = {
    # long division
    'use_digit'       : 1,  # brinding down digit from dividend
    'multiple_lookup' : 1,  # looking up precomputed multiple of divisor
    'quotient_update' : 1,  # updating quotient with digit or period
}

def is_even(digit):
    return digit % 2 == 0

def is_odd(digit):
    return digit % 2 != 0

def compute_addition_difficulty(*numbers):
    '''
    Generates a difficulty number and sum for given
    list of numbers for the addition operation
    *args - integers
    returns: (sum, difficulty)

    >>> compute_addition_difficulty(0, 0)
    (0, 1)

    >>> compute_addition_difficulty(0, 1)
    (1, 1)

    >>> compute_addition_difficulty(1, 1)
    (2, 2)

    >>> compute_addition_difficulty(1, 2)
    (3, 3)

    >>> compute_addition_difficulty(2, 2)
    (4, 2)

    >>> compute_addition_difficulty(19, 9)
    (28, 5)

    >>> compute_addition_difficulty(99999, 12345)
    (112344, 22)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 0, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    num1 = str(num1)
    num2 = str(num2)

    max_length = max([len(num1), len(num2)])
    num1 = num1.rjust(max_length, '0')
    num2 = num2.rjust(max_length, '0')

    difficulty = 0
    carry = 0
    r = reversed
    ad = addition_difficulties
    sum = []

    for index, (d1, d2) in enumerate( izip( r(num1), r(num2) ) ):
        d1 = int(d1)
        d2 = int(d2)

        d1_is_even = is_even(d1)
        d2_is_even = is_even(d2)
        
        if not d1 or not d2: difficulty += ad['digit_zero']
        elif d1_is_even and d2_is_even: difficulty += ad['even_even']
        elif not d1_is_even and not d2_is_even: difficulty += ad['odd_odd']
        elif d1_is_even != d2_is_even: difficulty += ad['even_odd']
    
        dsum = d1 + d2 + carry

        if dsum > 9:
            carry = 1
            difficulty += ad['carry']
        else:
            carry = 0
        
        sum.append( str(dsum % 10) )

    if carry:
        sum.append( str(carry) )

    sum.reverse()
    sum = ''.join(sum)
    sum = int (sum)

    numbers = [sum] + numbers[2:]

    sum, sub_difficulty = compute_addition_difficulty(*numbers)

    difficulty += sub_difficulty

    return sum, difficulty

def do_borrow(num, index):
    if index == len(num)-1: raise Exception('cannot perform borrow')

    num_borrows = 1
    next_digit = int(num[index+1])
    
    if next_digit > 0:
        num[index+1] = str(next_digit-1)

    else:
        num[index+1] = str(9)
        num_borrows += do_borrow(num, index+1)

    return num_borrows

def compute_subtraction_difficulty(*numbers):
    '''
    Generates a difficulty number and result for given
    list of numbers for the subtraction operation
    *args (tuple) - integers
    returns: (difference, difficulty)

    >>> compute_subtraction_difficulty(0,0)
    (0, 1)
    
    >>> compute_subtraction_difficulty(1,0)
    (1, 1)
    
    >>> compute_subtraction_difficulty(1,1)
    (0, 1)
    
    >>> compute_subtraction_difficulty(2,1)
    (1, 3)
    
    >>> compute_subtraction_difficulty(4,2)
    (2, 2)
    
    >>> compute_subtraction_difficulty(4,3)
    (1, 3)
    
    >>> compute_subtraction_difficulty(100,1)
    (99, 10)

    >>> compute_subtraction_difficulty(5000007,9)
    (4999998, 22)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 0, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    if num1 < num2: num1, num2 = num2, num1

    num1 = str(num1)
    num2 = str(num2)

    max_length = max([len(num1), len(num2)])
    num1 = list(num1.rjust(max_length, '0'))
    num2 = list(num2.rjust(max_length, '0'))

    difficulty = 0
    borrow = 0
    sd = subtraction_difficulties
    difference = []
    num1.reverse()
    num2.reverse()

    for index, (d1, d2) in enumerate( izip( num1, num2 ) ):
        d1 = int(d1)
        d2 = int(d2)

        d1_is_even = is_even(d1)
        d2_is_even = is_even(d2)

        if d1 > d2:
            if not d1 or not d2: difficulty += sd['digit_zero']
            elif d1_is_even and d2_is_even: difficulty += sd['even_even']
            elif not d1_is_even and not d1_is_even: difficulty += sd['odd_odd']
            elif d1_is_even != d2_is_even: difficulty += sd['even_odd']
            ddiff = d1 - d2

        elif d1 < d2:
            num_borrows = do_borrow(num1, index)
            difficulty += sd['borrow']*num_borrows
            ddiff = 10 + d1 - d2
            difficulty += sd['twodigit_digit']

        elif d1 == d2:
            difficulty += sd['same_digits']
            ddiff = 0

        difference.append( str(ddiff) )

    difference.reverse()
    difference = ''.join(difference)
    difference = int (difference)

    numbers = [difference] + numbers[2:]

    difference, sub_difficulty = compute_subtraction_difficulty(*numbers)

    difficulty += sub_difficulty

    return difference, difficulty

def get_single_digit_multiplication_difficulty(d1, d2):
    '''
    Max value of multiplication of two digits is 81 (9*9).
    Difficulty of d1*d2 increases as the resulting value
    of the multiplication increases. thereby 9*9=81 is most difficult
    and 0*0 is least difficult.

    We will represent this difficult with value from 1-4 (inclusive)

    Note that the difficulty will be incremented by 1 for presence
    of odd digit in the operands (except for 1 and 5 because it is arguably
    easier to multiply)
    
    >>> get_single_digit_multiplication_difficulty(0, 1)
    (0, 1)
    >>> get_single_digit_multiplication_difficulty(1, 1)
    (1, 1)
    >>> get_single_digit_multiplication_difficulty(2, 5)
    (10, 1)
    >>> get_single_digit_multiplication_difficulty(2, 7)
    (14, 2)
    >>> get_single_digit_multiplication_difficulty(2, 6)
    (12, 1)
    >>> get_single_digit_multiplication_difficulty(8, 9)
    (72, 5)
    >>> get_single_digit_multiplication_difficulty(8, 8)
    (64, 4)
    '''

    if not d1 or not d2: return 0, 1 

    res = d1 * d2
    difficulty = math.ceil((4/81.) * res)

    # odd numbers are harder to multiply except 1 and 5
    if d1 not in [1,5] and d2 not in [1,5] and (is_odd(d1) or is_odd(d2)):
        difficulty += 1

    return res, int(difficulty)

def compute_simple_multiplication_difficulty(num, digit):
    '''
    >>> compute_simple_multiplication_difficulty(1, 0)
    (0, 1)
    >>> compute_simple_multiplication_difficulty(1, 1)
    (1, 1)
    >>> compute_simple_multiplication_difficulty(2, 1)
    (2, 1)
    >>> compute_simple_multiplication_difficulty(10, 1)
    (10, 2)
    >>> compute_simple_multiplication_difficulty(15, 1)
    (15, 2)
    >>> compute_simple_multiplication_difficulty(15, 5)
    (75, 7)
    >>> compute_simple_multiplication_difficulty(999, 7)
    (6993, 25)
    '''
    num = str(num)

    result = []
    md = multiplication_difficulties
    carry = 0
    difficulty = 0

    for index, d in enumerate(reversed(num)):
        d = int(d)
        res, s_diff = get_single_digit_multiplication_difficulty(d, digit)
        difficulty += s_diff

        if (carry):
            res, carry_sum_difficulty = compute_addition_difficulty(res, carry)
            difficulty += carry_sum_difficulty + md['carry']

        carry = res/10
        result_digit = int(str(res)[-1:])
        result.append( str(result_digit) )

    if carry:
        result.append( str(carry) )

    result.reverse()
    result = ''.join(result)
    result = int(result)

    return result, difficulty

def compute_multiplication_difficulty(*numbers):
    '''
    Generates a difficulty number and result for given
    list of numbers for the multiplication operation
    *args (tuple) - integers
    returns: (product, difficulty)

    >>> compute_multiplication_difficulty(0,0)
    (0, 1)
    >>> compute_multiplication_difficulty(1,0)
    (0, 1)
    >>> compute_multiplication_difficulty(1,1)
    (1, 1)
    >>> compute_multiplication_difficulty(2,1)
    (2, 1)
    >>> compute_multiplication_difficulty(5,1)
    (5, 1)
    >>> compute_multiplication_difficulty(5,2)
    (10, 1)
    >>> compute_multiplication_difficulty(17,2)
    (34, 7)
    >>> compute_multiplication_difficulty(17,29)
    (493, 20)
    >>> compute_multiplication_difficulty(17,29,3)
    (1479, 31)
    >>> compute_multiplication_difficulty(1776,29,3)
    (154512, 77)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 1, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    if num1 < num2: num1, num2 = num2, num1

    num2 = str(num2)

    difficulty = 0
    borrow = 0
    md = multiplication_difficulties
    m_numbers = []

    for index, d in enumerate(reversed(num2)):

        d = int(d)
        
        m_number, m_diff = compute_simple_multiplication_difficulty(num1, d)
        difficulty += m_diff

        if index:
            m_number = int(m_number * math.pow(10, index))
            difficulty += md['offset']
        
        m_numbers.append(m_number)
    
    m_numbers_sum, m_numbers_diff = compute_addition_difficulty(*m_numbers)
    difficulty += m_numbers_diff

    numbers = [m_numbers_sum] + numbers[2:]
    product, m_diff = compute_multiplication_difficulty(*numbers)

    difficulty += m_diff

    return product, difficulty

def compute_multiples_difficulty(num, n):
    '''
    Generates difficulty number for computing
    nth multiple of num.
    @num (int)
    @n (int)
    returns: multiple, difficulty

    >>> compute_multiples_difficulty(10,5)
    (50, 14)
    >>> compute_multiples_difficulty(7,9)
    (63, 39)
    >>> compute_multiples_difficulty(1,5)
    (5, 10)
    >>> compute_multiples_difficulty(0,6)
    (0, 5)
    >>> compute_multiples_difficulty(99,3)
    (297, 18)
    '''

    numbers = [num] * n
    multiple, difficulty = compute_addition_difficulty(*numbers)
    return multiple, difficulty

def compute_multiple_less_than_number_difficulty(num, max_num):
    '''
    Generates the difficulty of computing the greatest multiple of num
    less than max_num
    @num (int)
    @max_num (int)
    returns: multiple, difficulty
    '''
    multiple = max_num - (max_num % num)
    n = multiple / num

    multiple, difficulty = compute_multiples_difficulty(num, n)
    return multiple, difficulty

def compute_division_difficulty(dividend, divisor, precision):
    '''
    Generates a difficulty number, quotient and remainder
    for dividend / divisor
    @precision (int) -- max required number of digits after decimal point in quotient
    returns: (quotient, remainder, difficulty)

    >>> compute_division_difficulty(54, 5, 0)
    (10.0, 4, 6)
    >>> compute_division_difficulty(50, 5, 0)
    (10.0, 0, 6)
    >>> compute_division_difficulty(575, 6, 0)
    (95.0, 5, 60)
    >>> compute_division_difficulty(575, 6, 1)
    (95.829999999999998, 20, 112)
    >>> compute_division_difficulty(6, 9, 1)
    (0.66000000000000003, 60, 50)
    >>> compute_division_difficulty(410, 2, 1)
    (205.0, 0, 54)
    '''

    if not divisor: raise Exception('Division by Zero')
    if not dividend: return 0, 0, 1

    dividend = str(dividend)
    divisor  = str(divisor)

    difficulty = 0
    previous_multiples_difficulty = 0
    precision_reached = 0
    decimal_point_used = 0
    dd = division_difficulties
    num = []
    quotient = []

    num = dividend[0]
    difficulty += dd['use_digit']
    index = 0

    #print 'divisor = %s, dividend = %s' % (divisor, dividend)

    while 1:
        #print 'loop start, num=%s' % (num)
        q_digit = int(num) / int(divisor)

        multiple, multiple_difficulty = compute_multiples_difficulty(int(divisor), q_digit)
        difficulty += int(math.fabs(multiple_difficulty - previous_multiples_difficulty))
        if previous_multiples_difficulty: difficulty += dd['multiple_lookup']
        previous_multiples_difficulty = max(multiple_difficulty, previous_multiples_difficulty)

        quotient.append( str(q_digit) )
        difficulty += dd['quotient_update']

        if decimal_point_used:
            precision_reached += 1

        #print 'quotient = %s' % (quotient)

        num, sub_difficulty = compute_subtraction_difficulty(int(num), multiple)
        difficulty += sub_difficulty
        num = str(num)
        
        #print 'num = %s' % (num)

        index += 1

        if index == len(dividend):
            if precision == 0: break
            quotient.append('.')
            difficulty += dd['quotient_update']
            decimal_point_used = 1
            #print 'quotient = %s' % (quotient)

        if not decimal_point_used:
            num += dividend[index]
        else:
            num += '0'
        
        difficulty += dd['use_digit']

        if (len(num) == 1 and not int(num)) or precision_reached >= precision + 1:
            break
        
        #print 'num = %s' % (num)
        #raw_input('end loop\n')

    remainder = int(num)
    quotient = float(''.join(quotient))

    return quotient, remainder, difficulty

def main():
    doctest.testmod()

if __name__ == '__main__':
    main()