Code Golf: Number to Words

Question

The code golf series seem to be fairly popular. I ran across some code that converts a number to its word representation. Some examples would be (powers of 2 for programming fun):

• 2 -> Two
• 1024 -> One Thousand Twenty Four
• 1048576 -> One Million Forty Eight Thousand Five Hundred Seventy Six

The algorithm my co-worker came up was almost two hundred lines long. Seems like there would be a more concise way to do it.

Current guidelines:

• Submissions in any programming language welcome (I apologize to PhiLho for the initial lack of clarity on this one)
• Max input of 2^64 (see following link for words, thanks mmeyers)
• Short scale with English output preferred, but any algorithm is welcome. Just comment along with the programming language as to the method used.

Answer 1

A T-SQL (SQL Server 2005) function, including test cases:

if exists (select 1 from sys.objects where object_id = object_id(N'dbo.fnGetNumberString'))
    drop function fnGetNumberString
go

/*
Tests:
declare @tests table ( testValue bigint )
insert into @tests select -43213 union select -5 union select 0 union select 2 union select 15 union select 33 union select 100 union select 456 union select 1024 union select 10343 union select 12345678901234 union select -3434343434343

select testValue, dbo.fnGetNumberString(testValue) as textValue
from @tests
*/

create function dbo.fnGetNumberString
(
    @value bigint
)
returns nvarchar(1024)
as
begin
    if @value = 0 return 'zero' -- lets me avoid special-casing this later

    declare @isNegative bit
    set @isNegative = 0

    if @value < 0
        select @isNegative = 1, @value = @value * -1

    declare @groupNames table ( groupOrder int, groupName nvarchar(15) )
    insert into @groupNames select 1, '' union select 2, 'thousand' union select 3, 'million' union select 4, 'billion' union select 5, 'trillion' union select 6, 'quadrillion' union select 7, 'quintillion' union select 8, 'sextillion'

    declare @digitNames table ( digit tinyint, digitName nvarchar(10) )
    insert into @digitNames select 0, '' union select 1, 'one' union select 2, 'two' union select 3, 'three' union select 4, 'four' union select 5, 'five' union select 6, 'six' union select 7, 'seven' union select 8, 'eight' union select 9, 'nine' union select 10, 'ten' union select 11, 'eleven' union select 12, 'twelve' union select 13, 'thirteen' union select 14, 'fourteen' union select 15, 'fifteen' union select 16, 'sixteen' union select 17, 'seventeen' union select 18, 'eighteen' union select 19, 'nineteen'

    declare @tensGroups table ( digit tinyint, groupName nvarchar(10) )
    insert into @tensGroups select 2, 'twenty' union select 3, 'thirty' union select 4, 'forty' union select 5, 'fifty' union select 6, 'sixty' union select 7, 'seventy' union select 8, 'eighty' union select 9, 'ninety'

    declare @groups table ( groupOrder int identity, groupValue int )

    declare @convertedValue varchar(50)

    while @value > 0
    begin
        insert into @groups (groupValue) select @value % 1000

        set @value = @value / 1000
    end

    declare @returnValue nvarchar(1024)
    set @returnValue = ''

    if @isNegative = 1 set @returnValue = 'negative'

    select @returnValue = @returnValue +
        case when len(h.digitName) > 0 then ' ' + h.digitName + ' hundred' else '' end +
        case when len(isnull(t.groupName, '')) > 0 then ' ' + t.groupName + case when len(isnull(o.digitName, '')) > 0 then '-' else '' end + isnull(o.digitName, '') else case when len(isnull(o.digitName, '')) > 0 then ' ' + o.digitName else '' end end +
        case when len(n.groupName) > 0 then ' ' + n.groupName else '' end
    from @groups g
        join @groupNames n on n.groupOrder = g.groupOrder
        join @digitNames h on h.digit = (g.groupValue / 100)
        left join @tensGroups t on t.digit = ((g.groupValue % 100) / 10)
        left join @digitNames o on o.digit = case when (g.groupValue % 100) < 20 then g.groupValue % 100 else g.groupValue % 10 end
    order by g.groupOrder desc

    return @returnValue
end
go

Answer 2

I can't find the file now, but this was an Intro to Programming problem (late in the term) where I went to school. We had to be able to turn a float into a valid written number for use on a check.

After the assignment was completed the professor showed some C++ code that solved the problem using only concepts we'd already covered. It ran just 43 lines, and was well-documented.

Answer 3

Does anyone plan on adding the appropriate commas and 'and' any time soon? Or hyphenating twenty-one through ninety-nine? Not much point otherwise, IMHO :)

'Nine Hundred Ninety Nine Thousand Nine Hundred Ninety Nine'

vs

'Nine hundred and ninety-nine thousand, nine hundred and ninety-nine'

(And no, mine doesn't work. Yet.)

Answer 4

Is this cheating?

perl -MNumber::Spell -e 'print spell_number(2);'

Answer 5

Here's a Scala solution. I'm not happy about trying to make it look short -- I sacrificed a bit of readability :(

object NumSpeller {
  val digits = Array("","one","two","three","four","five","six","seven","eight","nine")
  val teens = Array("ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen")
  val tens = Array("", "ten", "twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety")
  val thousands = Array("", "thousand", "million", "billion", "trillion", "quadrillion", "quintillion")

  def spellGroup(num:Int) = {
    val (v3, v2, v1) = ((num / 100) % 10, (num / 10) % 10, num % 10)
    val hs = v3 match { case 0 => ""; case d => digits(d) + " hundred " }
    val ts = v2 match {
      case 0 => digits(v1)
      case 1 => teens(v1)
      case _ => v3 match { case 0 => tens(v2); case _ => tens(v2) + "-" + digits(v1) }
    }
    hs + ts
  }

  def numberGroups(num:Long) = {
    def _numberGroups(num:Long, factor:Int):List[(Double,Int)] = factor match {
      case 0 => List((num % 1000,0))
      case _ => ((num / Math.pow(1000, factor)) % 1000, factor) :: _numberGroups(num, factor - 1)
    }
    val ints = _numberGroups(num, 6) map (x => (x._1.asInstanceOf[Int],x._2))
    ints dropWhile (x => x._1 == 0.0)
  }

  def spell(num:Long) = num match { case 0 => "zero"; case _ => (numberGroups(num) map { x => spellGroup(x._1) + " " + thousands(x._2) + " " }).mkString.trim  }
}

Usage is:

NumSpeller.spell(458582)

Answer 6

Python, 446 bytes. All lines under 80 columns, dammit. This is Paul Fisher's solution with coding tweaks on almost every line, down from his 488-byte version; he's since squeezed out several more bytes, and I concede. Go vote for his answer!

g=lambda n:["zero"," ".join(w(n,0))][n>0]
w=lambda n,l:w(n//m,l+1)+[e,z[n%m//100]+["hundred"]][n%m//100>0]+\
(p("twen thir fo"+r,"ty")[n%100//10-2]+z[n%10]if n%100>19 else z[n%100])+\
[e,k[l]][n%m>0]if n else e
p=lambda a,b:[[i+b]for i in a.split()]
e=[];r="r fif six seven eigh nine";m=1000
k=[e,["thousand"]]+p("m b tr quadr quint","illion")
z=[e]+p("one two three four five six seven eight nine ten eleven twelve","")+\
p("thir fou"+r,"teen")

The history has gotten complicated. I started with the unobfuscated code below, which supports negative numbers and range-checking, plus dashes in some numbers for better English:

>>> n2w(2**20)
'one million forty-eight thousand five hundred seventy-six'

def n2w(n):
    if n < 0:  return 'minus ' + n2w(-n)
    if n < 10: return W('zero one two three four five six seven eight nine')[n]
    if n < 20: return W('ten eleven twelve',
                        'thir four fif six seven eigh nine',
                        'teen')[n-10]
    if n < 100: 
        tens = W('', 'twen thir for fif six seven eigh nine', 'ty')[n//10-2]
        return abut(tens, '-', n2w(n % 10))
    if n < 1000:
        return combine(n, 100, 'hundred')
    for i, word in enumerate(W('thousand', 'm b tr quadr quint', 'illion')):
        if n < 10**(3*(i+2)):
            return combine(n, 10**(3*(i+1)), word)
    assert False

def W(b, s='', suff=''): return b.split() + [s1 + suff for s1 in s.split()]
def combine(n, m, term): return abut(n2w(n // m) + ' ' + term, ' ', n2w(n % m))
def abut(w10, sep, w1):  return w10 if w1 == 'zero' else w10 + sep + w1

Then I squeezed it to about 540 bytes via obfuscation (new to me), and Paul Fisher found a shorter algorithm (dropping the dashes) along with some marvelously horrible Python coding tricks. I stole the coding tricks to get down to 508 (which still did not win). I tried restarting fresh with a new algorithm, which was unable to beat Fisher's. Finally here's the tweak of his code. Respect!

The obfuscated code has been tested against the clean code, which was checked by eyeball on a bunch of cases.