Grind Report 17

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

*WARNING: This contains the solution!*

There are many approaches to this. I think that this is a pretty simply problem overall. My approach to this problem was fairly straightfoward. Basically I made a map that consisted of keys that represented the number and the values were the number of letters the number was made up of. Such as 7 mapped to 5 (seven). 20 -> 6 (twenty).

I did not have to include all of the numbers because there is so much overlap and I could split up the number into its different components. An example of this would be 192 one comes from 1 -> 3. 100 -> 7. 90 -> 6. 2 -> 3 and then since the number is greater than 100 and not evenly divisible by 100 we need to include the 'and' so add 3. 192 = 22

I used recursion for this since I like recursion so much :)

#include <string>
#include <iostream>
#include <map>

using std::map;
using std::string;
using std::cout;

map<int, int> dictionary;
const int MAX = 1000;

int CountLetters(int number)
{
 if (!number)
  return 0;
 if (number < 20)
  return dictionary[number];
 if (number / 1000)
  return CountLetters(number / 1000) + dictionary[1000] + CountLetters(number % 1000);
 if (number / 100)
 {
  int temp = CountLetters(number / 100);
  temp += dictionary[100];
  temp += CountLetters(number % 100);
  return  temp;
 }
 if (number / 10)
 {
  int temp = dictionary[(number / 10) * 10];
  temp += CountLetters(number % 10);
  return temp;
 }
}

int main()
{
 dictionary[0] = 3; //and
 dictionary[1] = 3; //one
 dictionary[2] = 3; //two
 dictionary[3] = 5; //three
 dictionary[4] = 4; //four
 dictionary[5] = 4; //five
 dictionary[6] = 3; //six
 dictionary[7] = 5; //seven
 dictionary[8] = 5; //eight
 dictionary[9] = 4; //nine
 dictionary[10] = 3; //ten
 dictionary[11] = 6; //eleven
 dictionary[12] = 6; //twelve
 dictionary[13] = 8; //thirteen
 dictionary[14] = 8; //fourteen
 dictionary[15] = 7; //fifteen
 dictionary[16] = 7; //sixteen
 dictionary[17] = 9; //seventeen
 dictionary[18] = 8; //eighteen
 dictionary[19] = 8; //nineteen
 dictionary[20] = 6; //twenty
 dictionary[30] = 6; //thirty
 dictionary[40] = 5; //forty
 dictionary[50] = 5; //fifty
 dictionary[60] = 5; //sixty
 dictionary[70] = 7; //seventy
 dictionary[80] = 6; //eighty
 dictionary[90] = 6; //ninety
 dictionary[100] = 7; //hundred
 dictionary[1000] = 8; //thousand


 int temp = CountLetters(201);


 int letterCount = 0;
 for (int i = 1; i <= MAX; ++i)
 {
  letterCount += CountLetters(i);
  if (i > 100 && i % 100 != 0)
   letterCount += dictionary[0];
 }

 cout << letterCount << std::endl;
}

*saved game*