Project Euler Problem 17 Solution: Convert numbers to words

Project Euler Problem 17 Statement

Give a number, 0 ≤ N ≤ 10¹², write out the equivalent value in English. This differs substantially from the original Project Euler problem by adapting it to the HackerRank requirements.

Solution

The intrinsic data

We create several lists to define all the English words that are required to spell any value less than one quintillion (10¹⁸). Lists ones and tens are permuted using the itertools.product function to generate the decades and compound numbers between 20 and 99. The words for the numbers 1 through 19 are then prepended to this list and stored in the units list. The intention was to have a one–to–one relationship with the index of the unit list and the corresponding number in written form.

You can extend the maximum value by simply adding other magnitudes to the thousands list.

The recursive function for hundreds

No matter how big the number is, it can be expressed by translating each 3–digit magnitude to a hundred designation (0–999) and then appending the appropriate magnitude (thousand’s) name to the end. For example, consider the number 194,382,426,112 expressed in English:

One Hundred Four Billion Three Hundred Eighty–Two Million Four Hundred Twenty–Six Thousand One Hundred Twelve

This pattern in large numbers allows us to create a recursive function (which could easily be replaced by a loop) to call upon itself until all the 3–digit magnitudes are processed. The q[] list will accumulate the word groups for each magnitude. Because we start with the lowest magnitude and work upwards, the list is joined in reverse order to place the larger magnitudes first.

Here is a flow chart to better explain the logic used to solve this problem:

Flowchart showing the logic used to solve Project Euler 17

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 17

HackerRank Project Euler 17 has us represent compound numbers with a space other than a hyphen. That is the only change required to solve their version of this problem.

Python Source Code

import itertools
ones = ['', 'One','Two','Three','Four','Five','Six','Seven','Eight','Nine']
teens = ['Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']
tens = ['Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']
units = ones + teens + list(map(lambda n: n[0]+("-"+n[1] if n[1] else ''), itertools.product(tens,ones)))
thousands = ['','Thousand','Million','Billion','Trillion','Quadrillion']
def n2words(n, z=0, q=[]):
    if n==0: return ' '.join(q[::-1])
    n,r = divmod(n, 1000)
    if r>0:
        h,u = divmod(r, 100)
        words = (ones[h]+' Hundred ' if h>0 else '') + units[u] + " " + thousands[z]
        q.append(words)
    return n2words(n, z+1, q)
n = int(input("Enter a number to spell out? "))
print ('Zero' if n==0 else n2words(n))

Last Word

Other thousands groups: Quintillion 10¹⁸, Sextillion 10²¹, Septillion 10²⁴, Octillion 10²⁷, and even more here.