C++

Forum

 
Number to Words Challenge

Duthomhas (13206)
Due to a recent posting (which some of you know about, but that's all I'll say about that), I thought it might be fun to see how we can convert a number into a string of words. For example:

    74315    -->    seventy four thousand three hundred and fifteen

I'm sure there already exist numerous algorithms to do this, but I haven't looked at any of them -- I'd like you to create your own versions too.

Should you accept, the Rules are:

  1) C++ only. Boost libraries are OK, so long as they don't do it for you.

  2) Pick your own target language. I did mine in English, using the Short Scale.
     http://en.wikipedia.org/wiki/Long_and_short_scales

  3) I want to see a write-up of both your algorithm and the actual code.
     (The code and generous commentary should be short enough to fit in 100-200 lines.)

There is no grading on this one, just the fun of playing with it.

Just so you know, I've already written mine, which I'll post later. My basic algorithm is a reverse string mapping, which I will also share later. (I don't want to suggest anything too detailed before you get a chance to think about it yourself.)

[edit] Remember, C is a subset of C++. But we'd like to see C++ instead of C.

[edit 2] Oh, I just found this!
http://es.wikipedia.org/wiki/Anexo:Nombres_de_los_n%C3%BAmeros_en_espa%C3%B1ol
I'm going to go play with an number->spanish words version now.

[edit 3] BTW, you don't have to handle anything more than 66 digits -- up into the vigintillions on the short scale. It gets messy after that, but magic bonus points if you do.

:O)
Last edited on
Duthomhas (13206)
BTW, if you are doing the standard English Short Scale, this is a valuable reference:
http://en.wikipedia.org/wiki/Names_of_large_numbers

[edit] Not content to play with small numbers (999×1063 or smaller), I found a really nice resource at
http://mrob.com/pub/math/largenum.html#conway-wechsler
This is, of course, wholly unnecessary (especially as it is all made-up). Fun though :O)
Last edited on
closed account (D80DSL3A)
Hi Duoas,

Here's my entry.

http://codepad.org/I1nsxPYB

If the comments within the code provide an unsatisfactory description of my algorithm please let me know and I'll describe it in more detail.


Duthomhas (13206)
Yeah! Someone liked my challenge!

No need to post elsewhere. Cut-n-paste here on the forum for all to admire. Also, make note that you used the English Short Scale to help any lurkers, if you will.

Your algorithm is similar to mine. I went least-to-most significant. And you were smarter about your powers of 1000 than I was (I just listed them in full from "thousand" to "vigintillion".)

(I got smarter when I decided to play with the Conway-Wechsler method if naming zillions, but I had to learn that method, whereas the challenge is really to use our brains to figure out how to name numbers we already know. I'm happy that I was able to calculate 101000000000 = ten trestrigintatrecentillitrestrigintatrecentilliduotrigintatrecentillion before string length/alloc errors)

Right now I'm playing with the word "and", as in "three thousand and twenty-one" and "four hundred and seventeen million".

PS, everyone. My internet is really spotty since that storm Sunday night here in South Jersey -- which is why I'm playing with this instead of fixing the FAQ.

Maybe I should make it more interesting and ask challengers to also be able to produce ordinal numbers, like "five hundred twenty-first". (That function and its tables cost me an extra forty lines.)

:O)

[edit] BTW, you forgot to consider the possibility that a thousands place may be all zeros. (I did that the first pass too...)
Last edited on
coder777 (8444)
So I did it in deutsch:[EDIT: too buggy, needs to reconsidered]
Last edited on
shadow123 (127)
Good attempt coder777! But your solution is buggy when inserting numbers bigger than ten thousand.

BTW, I consider it funny that you print the numbers in German, but the prompts are in English ;o)

Edit:
I know it's more difficult to solve this problem in german grammar.
Last edited on
coder777 (8444)
But your solution is buggy when inserting numbers bigger than ten thousand.
whoopers. I posted too early...
Duthomhas (13206)
I am actually a little surprised at the interfaces... This here is the actual code to my main program.
(Feel free to yoink it for yourselves.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
//----------------------------------------------------------------------------
int usage( const string& argv0 )
  {
  cerr <<
    "usage:\n  " << argv0 << " [OPTIONS] N\n\n"

    "Write the number N in words using the English short scale.\n"
    "N may be up to 66 digits long.\n\n"

    "options:\n"
    "  1st     Write the number as an ordinal (as in \"first\", \"second\", etc).\n"
    "  and     Write the number using the word \"and\" (as in American usage).\n"
    "  hyphen  Write the number using hyphens between tens and ones in [21,99].\n\n"

    "Options may be abbreviated by the first letter, so \"ah\" is a valid way\n"
    "to get \"and\"s and hyphens. Space between options is ignored.\n\n"

    "Options may be prefixed by one or two dashes '-' or a '/' -- they are ignored.\n";
  return 1;
  }

//----------------------------------------------------------------------------
int complain( const string& s )
  {
  cerr << "\"" << s << "\" is not an integer that I can understand.\n";
  return 1;
  }

//----------------------------------------------------------------------------
bool is_help( const string& s )
  {
  return ((s.find( "help" ) != string::npos)
      or  (s.find( '?'    ) != string::npos));
  }

//----------------------------------------------------------------------------
int main( int argc, char** argv )
  {
  vector <string> args( argv, argv + argc );
  bool is_ordinal    = false;
  bool is_use_and    = false;
  bool is_use_hyphen = false;

  switch (argc)
    {
    case 2: if (is_help(  args[ 1 ] ))
    case 1: return usage( args[ 0 ] );
    }

  for (int n = 1; n < (args.size() - 1); n++)
    {
    if (is_help( args[ n ] )) return usage( args[ 0 ] );

    is_ordinal    |= (args[ n ].find( "1st"    ) != string::npos);
    is_use_and    |= (args[ n ].find( "and"    ) != string::npos);
    is_use_hyphen |= (args[ n ].find( "hyphen" ) != string::npos);

    is_ordinal    |= (args[ n ].find( '1'      ) != string::npos);
    is_use_and    |= (args[ n ].find( 'a'      ) != string::npos);
    is_use_hyphen |= (args[ n ].find( 'h'      ) != string::npos);
    }

  string s = is_ordinal
           ? OrdinalToWords( args.back(), is_use_and, is_use_hyphen )
           : IntegerToWords( args.back(), is_use_and, is_use_hyphen );

  if (s.empty()) return complain( args.back() );

  cout << s << endl;

  return 0;
  }

Now I can use it as a standard utility.
C:\Users\Dúthomhas\Prog\IntegerToWords> dir a.exe
...
... 22,016 a.exe
...

C:\Users\Dúthomhas\Prog\IntegerToWords> a -ah 127000300015000000000000000000
one hundred twenty-seven octillion three hundred sextillion and fifteen quintillion

C:\Users\Dúthomhas\Prog\IntegerToWords>

Alas, I don't read large German numbers (I struggle with small ones), so I haven't had a chance to look at it yet besides to run it and plug some of my own test numbers into it and see what happened.

Neither of you guys take negative numbers... :-(

The Algorithm
Also, no one has yet made an actual writeup of their algorithm. Here's mine for an example. (Don't read this if you are still designing your own algorithm. Read it after, so you have your own fun!)

First, we perform a number of checks on the input string. If it is in any way invalid, the result is the empty string ("").

Next, we take note of whether or not the string begins with a '-'. If it does we remove it.

If what is left is composed entirely of zeros, we just return "zero".

Next, we pre-process the string a little:
  - Since we walk the string from least to most-significant digit, reverse it.
  - Convert all the digits ('0'..'9') to direct indices into the lookup tables by subtracting '0' from each.
  - For each ten's place digit, if it equals 1:
      - set it to zero
      - increment the (previous) one's place digit by 10.

Now for the actual lookup, where we will build our list of words. It is complicated slightly for handling hyphens, "and"s, and "hundreds".
  - For every group of three digits (taking zeros for digits past the end of the string):
      - If all three digits are zero, continue with the next iteration
      - lookup and words.append the name of 1000current_iteration
      - if not zero, lookup and words.append the name of the one's place
      - (optional) words.append "-" if both one's and ten's places are nonzero
      - if not zero, lookup and words.append the name of the ten's place
      - (optional) words.append "and" if either one's or ten's place are nonzero
      - if hundred's place is nonzero:
          - words.append "hundred"
          - lookup and words.append the name of the hundred's place using the one's table
          - (optional) words.append "and"
It is important that the word "and" only get appended into the words list one time, ever.

Now, if the last word in the list is an "and", get rid of it.

If the number is negative, words.append "negative".

Now we can convert the list of words into the output string. For each word in the list, starting with the last, append it to the result string, separating all words except "-" with spaces.

All done!

Keep posting everyone!
Catfish2 (666)
This is very rudimentary and dumb... also it's not a competitor because it violates Rule 1.

http://pastebin.com/xBRzru7s
ResidentBiscuit (4459)
Ah god. Here goes my day of work. Why did I have to read this?
closed account (D80DSL3A)
Duoas wrote:
BTW, you forgot to consider the possibility that a thousands place may be all zeros.

Doh! Didn't even cross my mind.
Here's the corrected code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string numStr;// for user entered number
    bool isNegative = false;

    // names for use in output
    string onesName[] = { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
    string teensName[] = { "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
    string tensName[] = { "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
    string illion_preName[] = { "m", "b", "tr", "quadr", "quint", "sext", "sept", "oct", "non", "dec" };
    string decillion_preName[]={ "un", "duo", "tre", "quattuor", "quin", "sex", "septen", "octo", "novem" };

    char repeat = 'n';

    do// as long as user wishes to enter number for naming
    {
        cout << "Number = "; cin >> numStr;

        // check for '-' as 1st character
        if( numStr[0] == '-' )
        {
            isNegative = true;
            numStr.erase(0,1);
        }
        else
            isNegative = false;

        // validate entry: check that all characters are digits
        bool isValid = true;
        for( unsigned int i = 0; i < numStr.size(); ++i )
            if( numStr[i] < '0' || numStr[i] > '9' )
            {
                isValid = false;
                break;
            }
        if( !isValid )
        {
            cout << "Your entry contains invalid characters." << endl;
            goto repeat;// evil but effective
        }

        // check that number of digits is not too high.
        cout << "power = " << numStr.size() - 1 << endl;
        if( numStr.size() > 66 )
        {
            cout << "The number's too damn big! Try again." << endl;
            goto repeat;
        }// validation complete

        // process the validated entry
        while( numStr.size()%3 != 0 )
            numStr = '0' + numStr;// pad the string with leading '0' until size = multiple of 3

        // print if number is negative
        if( isNegative ) cout << "negative ";

        // for each group of 3 digits from most to least significant
        for( unsigned int i = 0; i < numStr.size(); i += 3 )
        {
            // skip if all 3 digits == '0'
            if( numStr[i] == '0' && numStr[i+1] == '0' && numStr[i+2] == '0' )
                continue;

            if( numStr[i + 0] > '0' )// treat the hundreds place
                cout << onesName[ numStr[i + 0] - '0' - 1 ] << " hundred ";

            if( numStr[i + 1] == '0' || numStr[i + 1] > '1' )// treat tens and ones digits for non-teens case
            {
                if( numStr[i + 1] > '1' ) cout << tensName[ numStr[i + 1] - '0' - 2 ] << " ";
                if( numStr[i + 2] > '0' ) cout << onesName[ numStr[i + 2] - '0' - 1 ] << " ";
            }
            else// special teens case
                cout << teensName[ numStr[i + 2] - '0' ] << " ";

            // naming each factor of 1,000
            unsigned int j = ( numStr.size() - i )/3;
            if( j == 2 ) cout << "thousand ";
            else if( j > 2 )
            {

                if( j <= 12 ) cout << illion_preName[ j - 3 ];// 'xx' before "illion" cases
                else if( j <= 21 ) cout << decillion_preName[ j - 13 ] << "dec";// 'xx' before "dec" + "illion" cases
                else if( j == 22 ) cout << "vigint";// special 'xx' before "vigint" + "illion" case

                cout << "illion ";// the "illion" suffix
            }
        }

        repeat:
        cout << endl << "Repeat? (y/n): ";
        cin >> repeat;
    }while( repeat == 'y' );


    cout << endl;
    return 0;
}

EDIT: I have changed my code to a version which includes basic input validation (check for non-digit characters) and handles the negative number case.
Last edited on
coder777 (8444)
So now more elaborated (but still deutsch (as in rule 2) sorry Duoas). the other texts are still english though. Error checks but no hyphens. the worded algorithm later.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
#include <iostream>
#include <string>
#include <algorithm>

// the german names of the numbers
const std::string from_0_to_9[] = { "Null", "ein", "zwei", "drei", "vier", "fuenf", "sechs", "sieben", "acht", "neun" };
const std::string from_10_to_19[] = { "zehn", "elf", "zwoelf", "dreizehn", "vierzehn", "fuenfzehn", "sechzehn", "siebzehn", "achtzehn", "neunzehn" };
const std::string from_20_step_10[] = { "zwanzig", "dreissig", "vierzig", "fuenfzig", "sechzig", "siebzig", "achtzig", "neunzig" };
const std::string from_100[] = { "hundert", "tausend", "million", "milliarde", "billion", "billiarde", "trillion", "trilliarde",
  "quadrillion", "quadrilliarde", "quintillion", "quintilliarde", "sextillion", "sextilliarde", "septillion", "septilliarde",
  "oktillion", "oktilliarde", "nonillion", "nonilliarde", "dezillion", "dezilliarde", "undezillion", "undezilliarde", "dodezillion",
  "dodezilliarde", "tredezillion", "tredezilliarde", "quattuordezillion", "quattuordezilliarde", "quindezillion", "quindezilliarde",
  "sedezillion", "sedezilliarde", "septendezillion", "septendezilliarde", "dodevigintillion", "dodevigintilliarde", "undevigintillion",
  "undevigintilliarde", "vigintillion", "vigintilliarde", "trigintillion", "trigintilliarde", "zentillion", "zentilliarde" };

// this function makes sure that only digits are processed
// (avoids crash in case of wrongful input)
int GetValue(const std::string &num, const int offs)
{
  int result = 0;
  if(offs < num.size()) // offset must not exceed the number
    result = isdigit(num[offs]) ? // only digits are allowed
      (num[offs] - '0') : 0;
  return result;
}

// this returns the string for the 2 digits value
std::string GetBelowHundred(const std::string &num, const int offs)
{
  std::string result;

  if(offs < num.size()) // offset must not exceed the number
  {
    // gets the first digit
    const int value_from_0_to_9 = GetValue(num, offs);
    // checks if a second digit exists
    // (a single digit may have another name / null may exists)
    bool more = ((offs + 1) < num.size());
    if(more) // ok there're two digits
    {
      // gets the second digit
      const int value_from_10 = GetValue(num, offs + 1);
      if(value_from_10 > 0) // only non null are taken into account
      {
        if(1 == value_from_10) // the value is 10+
          result += from_10_to_19[value_from_0_to_9]; // the least significant digit determines the name
        else // the value is 20+
        {
          // name wise the least significant digit is placed in front!
          if(value_from_0_to_9 > 0) // only least significant digits >0 are taken into account
          {
            result += from_0_to_9[value_from_0_to_9]; // adds the name of the digit
            result += "und"; // here the connecting word 'und' is required
          }
          result += from_20_step_10[value_from_10 - 2]; // 0/1 are treated diffently hence -2
        }
      }
      else if(value_from_0_to_9 > 0) // leading digits means different treatment
      {
        result += "und"; // the connecting word 'und' is required then
        more = false; // but it's considered a single digit
      }
    }
    if(!more) // when it's a single digit it's not been treated yet
    {
      if((value_from_0_to_9 > 0) || (1 == num.size())) //the name 'null' is allowed only if there's just 1 digit
      {
        result += from_0_to_9[value_from_0_to_9]; // the name of the least signigicant digit
        if(1 == value_from_0_to_9) // with no leading digits the value one
          result += 's'; // needs 's' to be appended
      }
    }
  }
  return result;
}

// gets the name und value for hundreds
std::string GetHundred(const std::string &num, const int offs)
{
  std::string result;

  if(num.size() > (offs + 2)) // the offset is expected at the beginning of the hundred
  {
    const int value_100 = GetValue(num, offs + 2); // gets the hundred digit
    if(value_100 > 0) // if there actually is hundred
      result = from_0_to_9[value_100] + from_100[0]; // both appear: the value of hundred and the word hundred itself
  }
  return result;
}

// Removes characters from the string (all -> whether just a series or all)
int RemoveChar(std::string &str, const char ch, const bool all)
{
  int result = 0; // holds the amount of chars removed
  std::string::iterator it = str.begin(); // gets the start of the string
  while(it != str.end()) // as long as it's not at end
  {
    if(ch == (*it)) // checks if it's a char to remove
    {
      it = str.erase(it); // remove the char
      ++result; // count the chars removed
    }
    else if(all) // whether all characters should be removed
      ++it; // just continue
    else
      break; // the series ends
  }
  return result;
}

int main()
{
  std::cout << "Number to Words" << std::endl << "q - quit" << std::endl;
  bool q = false;
  while(!q)
  {
    std::string num;
    std::cout << "Enter number:" << std::endl;
    std::getline(std::cin, num);
    q = ("q" == num);
    if(q)
      ; // do nothing if quit
    else
    {
      RemoveChar(num, ' ', true); // remove all blanks
      const int minus = RemoveChar(num, '-', false); // remove and count minus
      const int zero = RemoveChar(num, '0', false); // remove leading zero
      bool is_nondigit = false;
      for(std::string::size_type i = 0; i < num.size(); ++i) // check for correctness of the number
      {
        is_nondigit = (0 == isdigit(num[i])); // check the digit
        if(is_nondigit) // whether it's invalid
          break; // stop here
      }
      if(is_nondigit)
        std::cout << "Invalid number: digits only" << std::endl;
      else
      {
        std::reverse(num.begin(), num.end()); // reverse the string for convenience
        const int size = num.size(); // get the size
        if((size > 0) and (size < (((sizeof(from_100) / sizeof(*from_100)) * 3) + 2))) // check the amount of digits
        {
          std::string result = GetHundred(num, 0) + GetBelowHundred(num, 0); // get the name of the lowes hundert
          const int size_3 = (size + 2) / 3; // this is the number of following hundreds
          for(int i = 1; i < size_3; ++i) // calculates every three digits above hundert
          {
            // gets the three names for the three digits
            result = GetHundred(num, i * 3) + GetBelowHundred(num, i * 3) + from_100[i] + result; // must be prepended!
          }
          if(1 == minus % 2) // whether a minus appeared
            std::cout << "minus "; // show minus
          std::cout << result << std::endl; // The final output
        }
        else if(num.empty() && (zero > 0)) // There's only zero
          std::cout << from_0_to_9[0] << std::endl;
        else // Invalid input
          std::cout << "Invalid number: 1 to " << ((sizeof(from_100) / sizeof(*from_100)) * 3) + 2 << " digits" << std::endl;
      }
    }
  }
  return 0;
}
Tested to a certain extent
Duthomhas (13206)
Well, I think perhaps this challenge was too easy. :-\

In any case, here's mine:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
// Copyright 2012 Michael Thomas Greer
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt
//  or copy at http://www.boost.org/LICENSE_1_0.txt )

#include <algorithm>
#include <cctype>
#include <iterator>
#include <string>
#include <vector>

#include <iostream>
#include <sstream>
using namespace std;

//--------------------------------------------------------------------------
// IntegerToWords()
//
// Convert an integer number into its name using the English Short Scale,
// up to nine hundred vigintillion in the most significant digit (that is,
// up to 66 digits total).
//
// No number may contain non-digit characters (anything but '0' through '9')
// except for an optional leading minus sign ('-') for negative integers.
//
// The result may have the word 'and' in it.
// The result may have hyphens between ones and tens digits.
//
// Returns an empty string for all invalid inputs.
//
// References:
//   http://en.wikipedia.org/wiki/Names_of_large_numbers
//   http://en.wikipedia.org/wiki/Long_and_short_scales
//

//--------------------------------------------------------------------------
string IntegerToWords(
//--------------------------------------------------------------------------
  string s,
  bool   use_and     = true,
  bool   use_hyphen  = true )
  {
  typedef vector <const char*>                     words_type;
  typedef words_type::const_reverse_iterator       words_iter;

  // Lookup tables
  const char* ones[] =
    {
    "",        "one",     "two",       "three",    "four",
    "five",    "six",     "seven",     "eight",    "nine",
    "ten",     "eleven",  "twelve",    "thirteen", "fourteen",
    "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"
    };
  const char* tens[] =
    {
               "",        "twenty",    "thirty",   "fourty",
    "fifty",   "sixty",   "seventy",   "eighty",   "ninety"
    };
  const char* powers[] =
    {
    "",
    "thousand",           "million",            "billion",
    "trillion",           "quadrillion",        "quintillion",
    "sextillion",         "septillion",         "octillion",
    "nonillion",          "decillion",          "undecillion",
    "duodecillion",       "tredecillion",       "quattuordecillion",
    "quindecillion",      "sexdecillion",       "septendecillion",
    "octodecillion",      "novemdecillion",     "vigintillion"
    };
  const char* and_word = "and";

  // Check for negative and invalid numbers. Also check for zero.
  if (s.empty()) return "";

  bool is_negative = (s[ 0 ] == '-');
  if (is_negative) s.erase( 0, 1 );
  if (s.empty()) return "";

  if ((size_t)count( s.begin(), s.end(), '0' ) == s.length()) return "zero";
  if (s.length() > 66) return "";

  // We need to preprocess the source a little.
  //
  // First, the algorithm works from least-significant to most significant
  // digit, so we need to reverse the source string to make life easier.
  //
  // Next, we convert the elements in s from characters to indices into the
  // lookup tables. The conversions from elements to indices are as follows:
  //   digit      -->  digit -= '0'
  //   tens == 1  -->  ones += 10,  tens=0
  //   tens > 2   -->  tens -= 1
  //
  reverse( s.begin(), s.end() );
  for (string::iterator c = s.begin(); c != s.end(); ++c)
    {
    if (!isdigit( *c )) return "";
    *c -= '0';
    }
  for (size_t n = 1; n < s.length(); n += 3)
    if (s[ n ])
      {
      if (s[ n ] -= 1);
      else s[ n - 1 ] += 10;
      }
  s.append( 3, '\0' );  // (Buffer enough to take elements in groups of three)

  // Here is the conversion part.
  // Lookup words in groups of three: (hundreds, tens, ones).
  //
  // Notice that the algorithm is complicated slightly
  // by handling the hyphen between numbers in [21..99],
  // and by adding the word "and" in the right spot.

  #define with( index )   v = s[ n + index ]; if (v)
  #define use( array )    vs.push_back( array[ v ] )
  #define add( literal )  vs.push_back( literal )
  #define iff( b, again ) if (b and vs.size()) b = again,

  words_type words;
  words.reserve( 130 );  
  unsigned v, power = 0;
  for (size_t n = 0; n < s.length() - 3; n += 3, power++)
    {
    words_type vs;
    with (0)                           use( ones      );
    with (1) {  iff (use_hyphen, true) add( "-"       );
                                       use( tens      );  }
                iff (use_and, false)   add( and_word  );
    with (2) {                         add( "hundred" );
                                       use( ones      );
                iff (use_and, false)   add( and_word  );  }
    if (vs.size())
      {
      if (power) words.push_back( powers[ power ] );
      words.insert( words.end(), vs.begin(), vs.end() );
      }
    }

  #undef iff
  #undef add
  #undef use
  #undef with

  // If the result is to have the word "and" in it,
  // make sure it isn't the first word (last in our current list).
  if (words.back() == and_word)
    words.resize( words.size() - 1 );

  if (is_negative) words.push_back( "negative" );

  // Now build the result string by reverse concatenating the list of words.
  // (Again, that hyphen complicates things a little bit.)
  string result( words.back() );
  for (words_iter word = words.rbegin() + 1; word != words.rend(); ++word)
    {
    if (((*word)[ 0 ] != '-') and (result[ result.length() - 1 ] != '-'))
      result.append( " " );
    result.append( *word );
    }

  return result;
  }

//----------------------------------------------------------------------------
int usage( const string& argv0 )
  {
  cerr <<
    "usage:\n  " << argv0 << " [OPTIONS] N\n\n"

    "Write the number N in words using the English short scale.\n"
    "N may be up to 66 digits long.\n\n"

    "options:\n"
    "  and     Write the number using the word \"and\", as in \"two hundred and one\".\n"
    "  hyphen  Write the number using hyphens between tens and ones in [21,99].\n\n"

    "Options may be abbreviated by the first letter, so \"ah\" is a valid way\n"
    "to get \"and\"s and hyphens. Space between options is ignored.\n\n"

    "Options may be prefixed by one or two dashes '-' or a '/'; they are ignored.\n";

  return 1;
  }

//----------------------------------------------------------------------------
int complain( const string& s )
  {
  cerr << "\"" << s << "\" is not an integer that I can understand.\n";
  return 1;
  }

//----------------------------------------------------------------------------
bool is_help( const string& s )
  {
  return ((s.find( "help" ) != string::npos)
      or  (s.find( '?'    ) != string::npos));
  }

//----------------------------------------------------------------------------
int main( int argc, char** argv )
  {
  vector <string> args( argv, argv + argc );
  bool is_use_and    = false;
  bool is_use_hyphen = false;

  switch (argc)
    {
    case 2: if (is_help(  args[ 1 ] ))
    case 1: return usage( args[ 0 ] );
    }

  for (int n = 1; n < (argc - 1); n++)
    {
    if (is_help( args[ n ] )) return usage( args[ 0 ] );
    is_use_and    |= (args[ n ].find( 'a' ) != string::npos);
    is_use_hyphen |= (args[ n ].find( 'h' ) != string::npos);
    }

  string s = IntegerToWords( args.back(), is_use_and, is_use_hyphen );

  if (s.empty()) return complain( args.back() );

  cout << s << endl;

  return 0;
  }

This is actually just the basic algorithm. I've long since extended it to be able to handle much larger numbers, using:
- Conway-Wechsler & Miakinen's extensions to the short scale
- the traditional British long scale (thousand millions)
- Peletier's (now traditional) European long scale (milliards)
- Rowlett & Saibian's "Greek" based scale
I'm still not sure I want to waste any time with Knuth's interesting scale.
(I want to play with the numbers in Spanish before I do anything else.)

Perhaps I'll post a follow-up challenge for huge numbers (above vigintillions).
Topic archived. No new replies allowed.