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

Perl & CPAN working together:

#!/usr/bin/perl

use strict;
use warnings;

use Lingua::EN::Numbers qw(num2en);

print num2en($_), "\n" for 2, 1024, 1024*1024;

C:\Temp> n.pl
two
one thousand and twenty-four
one million, forty-eight thousand, five hundred and seventy-six

Answer 2

Here's a relatively straightforward implementation in C (52 lines).

NOTE: this does not perform any bounds checking; the caller must ensure that the calling buffer is large enough.

#include <stdio.h>
#include <string.h>

const char *zero_to_nineteen[20] = {"", "One ", "Two ", "Three ", "Four ", "Five ", "Six ", "Seven ", "Eight ", "Nine ", "Ten ", "Eleven ", "Twelve ", "Thirteen ", "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ", "Eighteen ", "Nineteen "};

const char *twenty_to_ninety[8] = {"Twenty ", "Thirty ", "Forty ", "Fifty ", "Sixty ", "Seventy ", "Eighty ", "Ninety "};

const char *big_numbers[7] = {"", "Thousand ", "Million ", "Billion ", "Trillion ", "Quadrillion ", "Quintillion "};

void num_to_word(char *buf, unsigned long long num)
{
  unsigned long long power_of_1000 = 1000000000000000000ull;
  int power_index = 6;

  if(num == 0)
  {
    strcpy(buf, "Zero");
    return;
  }

  buf[0] = 0;

  while(power_of_1000 > 0)
  {
    int group = num / power_of_1000;
    if(group >= 100)
    {
      strcat(buf, zero_to_nineteen[group / 100]);
      strcat(buf, "Hundred ");
      group %= 100;
    }

    if(group >= 20)
    {
      strcat(buf, twenty_to_ninety[group / 10 - 2]);
      group %= 10;
    }

    if(group > 0)
      strcat(buf, zero_to_nineteen[group]);

    if(num >= power_of_1000)
      strcat(buf, big_numbers[power_index]);

    num %= power_of_1000;
    power_of_1000 /= 1000;
    power_index--;
  }

  buf[strlen(buf) - 1] = 0;
}

And here's a much more obfuscated version of that (682 characters). It could probably be pared down a little more if I really tried.

#include <string.h>
#define C strcat(b,
#define U unsigned long long
char*z[]={"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"},*t[]={"Twenty ","Thirty ","Forty ","Fifty ","Sixty ","Seventy ","Eighty ","Ninety "},*q[]={"","Thousand ","Million ","Billion ","Trillion ","Quadrillion ","Quintillion "};
void W(char*b,U n){U p=1000000000000000000ull;int i=6;*b=0;if(!n)strcpy(b,"Zero ");else while(p){int g=n/p;if(g>99){C z[g/100]);C " ");C "Hundred ");g%=100;}if(g>19){C t[g/10-2]);g%=10;}if(g)C z[g]),C " ");if(n>=p)C q[i]);n%=p;p/=1000;i--;}b[strlen(b)-1]=0;}

Answer 3

Perl 5.10

my %expo=(0,'',
  qw'1 thousand 2 million 3 billion 4 trillion 5 quadrillion 6 quintillion
  7 sextillion 8 septillion 9 octillion 10 nonillion 11 decillion 12 undecillion
  13 duodecillion 14 tredecillion 15 quattuordecillion 16 quindecillion
  17 sexdecillion 18 septendecillion 19 octodecillion 20 novemdecillion
  21 vigintillion'
);

my %digit=(0,'',
  qw'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 2* twenty 3* thirty 4* forty 5* fifty 6* sixty
  7* seventy 8* eighty 9* ninety'
);

sub spell_number(_){
  local($_)=@_;
  ($_,@_)=split/(?=(?:.{3})*+$)/;
  $_=0 x(3-length).$_;
  unshift@_,$_;
  my @o;
  my $c=@_;
  for(@_){
    my $o='';
    /(.)(.)(.)/;
    $o.=$1?$digit{$1}.' hundred':'';
    $o.=$2==1?
      ' '.$digit{$2.$3}
    :
      ($2?' '.$digit{"$2*"}:'').
      ($2&&$3?' ':'').
      $digit{$3}
    ;
    $o.=--$c?($o?' '.$expo{$c}.', ':''):'';
    push@o,$o;
  }
  my $o;
  $o.=$_ for@o;
  $o=~/^\s*+(.*?)(, )?$/;
  $o?$1:'zero';
}

Notes:

• This almost works on earlier Perls, it's that first split() that seems to be the main problem. As it sits now the strings take up the bulk of the characters.
• I could have shortened it, by removing the my's, and the local, as well as putting it all on one line.
• I used Number::Spell as a starting point.
• Works under strict and warnings.

Answer 4

Mmm, you might have put the bar a bit high, both on the limit (18,446,744,073,709,552,000, I don't even know how to write that!) and on the goal (the other code golfs resulted in short code, this one will be long at least for the data (words)).

Anyway, for the record, I give an well known solution (not mine!) for French, in PHP: Écriture des nombres en français. :-)

Note the ambiguity (voluntary or not) of your wording: "Submissions in any language welcome"
I first took it as "natural language", before understand you probably meant "programming language...
The algorithm is probably simpler in English (and with less regional variants...).

Answer 5

Paul Fischer and Darius: You guys have some great ideas, but I hate to see them implemented in such an overly verbose fashion. :) Just kidding, your solution is awesome, but I squeezed 14 30 more bytes out, while staying inside of 79 columns and maintaining python 3 compatibility.

So here's my 416 byte python within 79 columns: (thanks guys, I'm standing on your shoulders)

w=lambda n:_(n,["","thousand "]+p("m b tr quadr quint","illion"))[:-1]or"zero"
_=lambda n,S:n*"x"and _(n//M,S[1:])+(Z[n%M//C]+"hundred ")*(n%M//C>0)+(n%C>19
and p("twen thir fo"+R,"ty")[n%C//10-2]+Z[n%10]or Z[n%C])+S[0]*(n%M>0)
p=lambda a,b="":[i+b+" "for i in a.split()]
R="r fif six seven eigh nine"
M=1000
C=100
Z=[""]+p("one two three four five%st nine ten eleven twelve"%R[5:20])+p(
"thir fou"+R,"teen")

And the tests:

if __name__ == "__main__":
    import sys
    assert(w(0)=="zero")
    assert(w(100)=="one hundred")
    assert(w(1000000)=="one million")
    assert(w(1024)=="one thousand twenty four")
    assert(w(1048576)=="one million forty eight thousand five hundred seventy six")

Answer 6

In the D programming language

string Number(ulong i)
{
    static string[] names = [
      ""[],
      " thousand",
      " million",
      " billion",
      " trillion",
      " quadrillion",
      ];
    string ret = null;
    foreach(mult; names)
    {
       if(i%1000 != 0)
       {
           if(ret != null) ret = ret ~ ", "
           ret = Cent(i%1000) ~ mult ~ ret;
       }
       i /= 1000;
    }
    return ret;
}

string Cent(int i)
{
   static string[] v = 
        [""[], "one", "two", "three", "four", 
        "five", "six", "seven", "eight", "nine"];

   static string[] tens = 
        ["!"[], "!", "twenty", "thirty", "forty", 
        "fifty", "sixty", "seventy", "eighty", "ninety"];

   string p1, p2, p3 = "";


   if(i >= 100)
   {
      p1 = v[i/100] ~ " hundred";
      p3 = (i % 100 != 0) ? " and " : ""; //optional
   }
   else
      p1 = "";

   i %= 100;
   switch(i)
   {
       case 0, 1, 2, 3, 4, 5, 6, 7, 8, 9:
          p2 = v[i];
          break;

       case 10: p2 = "ten"; break;
       case 11: p2 = "eleven"; break;
       case 12: p2 = "twelve"; break;
       case 13: p2 = "thirteen"; break;
       case 14: p2 = "fourteen"; break;
       case 15: p2 = "fifteen"; break;
       case 16: p2 = "sixteen"; break;
       case 17: p2 = "seventeen"; break;
       case 18: p2 = "eighteen"; break;
       case 19: p2 = "nineteen"; break;

       default:
           p2 = tens[i/10] ~ "-" ~ v[i%10];
           break;

   }

   return p1 ~ p3 ~ p2;
}

import std.stdio;
void main()
{
  writef("%s\n", Number(8_000_400_213));
}

Try it out here