num2words.py

# TIPS:
# Please write high level pseudocode approach before writing actual code.
# Use meaningful variables, comments and indent your code.
# Your code should compile, run and produce the correct output.
# Write some tests
# You are totally free to use search engines and stackoverflow.
# Talk about O(n) CPU and memory requirements. Best case and worst case.
# Talk about what things you'll still need to do for your code to be production ready at the end.

num2words_map = {
    0: 'zero',
    1: 'one',
    2: 'two',
    3: 'three',
    4: 'four',
    5: 'five',
    6: 'six',
    7: 'seven',
    8: 'eight',
    9: 'nine',
    10: 'ten',
    11: 'eleven',
    12: 'twelve',
    13: 'thirteen',
    14: 'fourteen',
    15: 'fifteen',
    16: 'sixteen',
    17: 'seventeen',
    18: 'eighteen',
    19: 'nineteen',
    20: 'twenty',
    30: 'thirty',
    40: 'fourty',
    50: 'fifty',
    60: 'sixety',
    70: 'seventy',
    80: 'eighty',
    90: 'ninety',
    100: 'hundred',
    int(1e3): 'thousand',
    int(1e6): 'million',
    int(1e9): 'billion',
    int(1e12): 'trillion',
    int(1e15): 'quadrillion',
    int(1e18): 'quintillion',
}


def num2words(num):
    '''
    Converts an integer into spoken words.
    Numbers can be as large as a trillion
    
    e.g num2words(1234567890)
    
    one billion
    two hundred thirty four million
    five hundred sixty seven thousand
    eight hundred ninety
    
    '''

    # TODO complete me
    return list(str(num))


def testNum2Words(num):
    print(num)
    try:
        print(num2words(num))
    except Exception as e:
        print(e)
    print()
    


if __name__ == '__main__':
    testNum2Words(1)

#### SOLN ####


def num2words(num):
    if not isinstance(num, int):
        raise ValueError('num must be an int')

    if num < 0:
        raise ValueError('%d must be a positive integer' % num)

    # Zero is a special case
    if num == 0:
        return num2words_map[num]

    # Increase scale from one, thousand, million ... until bigger than num
    cur_scale = 1
    while cur_scale <= num:
        cur_scale *= 1000

    result = []
    remainder = num

    # Keep on spliting number into (hundreds * 100 + tens * 10 + ones) * scale + remainder, until no remainder
    # Output pattern is repeating e.g xyz billion, xyz million, xyz thousand, xyz (last xyz has no suffix)
    while remainder > 0:
        # Quotient will be maximum of 999 since scale will always be multiple of 1000
        cur_scale = int(cur_scale / 1000)  # divmod supports floats but we only want to deal with ints
        v0_999, remainder = divmod(remainder, int(cur_scale))
        hundreds, v0_99 = divmod(v0_999, 100)
        tens, ones = divmod(v0_99, 10)
        words = []

        # Skip early if v0_999 == 0. e.g 2*1e6 is simply 'one million', not 'one million, zero thousand'
        if v0_999 == 0:
            continue

        # Hundred suffix. e.g 200 = two + 'hundred'
        if hundreds:
            words.append(num2words_map[hundreds])
            words.append(num2words_map[100])

        if tens == 0:  # Output single digit word
            words.append(num2words_map[ones])
        elif tens == 1:  # 11-19 (teens) is special case (when tens == 1), one word
            words.append(num2words_map[tens * 10 + ones])
        else:  # Two words e.g twenty + two
            words.append(num2words_map[tens * 10])
            words.append(num2words_map[ones])

        # billion, million, thousand. No output when scale == 1
        if cur_scale > 1:
            words.append(num2words_map[cur_scale])

        result.append(' '.join(words))

    # Join with comma and new line so line is not too long
    return ',\n'.join(result)

if __name__ == '__main__':
    testNum2Words(0)
    testNum2Words(1)
    testNum2Words(15)
    testNum2Words(99)
    testNum2Words(199)
    testNum2Words(1000)
    testNum2Words(1000000)
    testNum2Words(123456)
    testNum2Words(2 ** 64) # very large number max

    # Bad input
    testNum2Words(-1)
    testNum2Words('asdf')
    testNum2Words(None)