Project Euler - 17

Question

The problem states:

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.

The code that I've written is:

int getCount(map<int, int> numWords, int i)
{
    if (i <= 20) // one to twenty
        return numWords[i];
    else if (i <= 99 && i % 10 == 0) // thirty, forty, fifty etc.
        return numWords[i];
    else if (i <= 99) // thirty one, seventy eight etc.
    {
        int md = i % 10;
        return numWords[i-md] + numWords[md]; // (1) -> if its 55, then take 50; (2) -> take 5
    }
    else if (i <= 999 && i % 100 == 0) // two hundred, five hundred etc.
    {
        int md = i / 100;
        return numWords[md] + numWords[100]; // number + hundred
    }
    else if(i <= 999 && i % 10 == 0) // 340 three hundred forty
    {
        int hunsDig = (i - (i % 100)) / 100; // (340 - 40)/100 = 3
        int tens = i - hunsDig*100; // 340-300=40
        return numWords[hunsDig] + numWords[100] + numWords[0] + numWords[tens]; // three hundred and forty
    }
    else if(i <= 999) // 342
    {
        int hunsDig = (i - (i % 100)) / 100; // (342 - 42)/100 = 3
        int units = i % 10; // 342 % 10 = 2
        int tens = (i % 100) - units; // (342 % 100=42) - 2 = 40
        int tensCount = tens == 0 ? 0 : numWords[tens];

        return numWords[hunsDig] + numWords[100] + numWords[0] + tensCount + numWords[units]; // three hundred and forty two
    }
    else if(i==1000)
        return numWords[1] + numWords[1000];
}

void problem17()
{
    // make a map of all the words and corresponding word lengths
    map<int, int> numWords; 
    numWords[1] = 3; // one
    numWords[2] = 3; // two
    numWords[3] = 5; // three
    numWords[4] = 4; // four
    numWords[5] = 4; // five
    numWords[6] = 3; // six
    numWords[7] = 5; // seven
    numWords[8] = 5; // eight
    numWords[9] = 4; // nine
    numWords[10] = 3; // ten
    numWords[11] = 6; // eleven
    numWords[12] = 6; // twelve
    numWords[13] = 8; // thirteen
    numWords[14] = 8; // fourteen
    numWords[15] = 7; // fifteen
    numWords[16] = 7; // sixteen
    numWords[17] = 9; // seventeen
    numWords[18] = 8; // eighteen
    numWords[19] = 8; // nineteen
    numWords[20] = 6; // twenty
    numWords[30] = 6; // thirty
    numWords[40] = 5; // forty
    numWords[50] = 5; // fifty
    numWords[60] = 5; // sixty
    numWords[70] = 7; // seventy
    numWords[80] = 6; // eighty
    numWords[90] = 6; // ninety
    numWords[100] = 7; // hundred
    numWords[1000] = 8; // thousand
    numWords[0] = 3; // and

    int totalCount = 0; // total num of words

    for (int i=1; i <= 1000; i++)
    {
        totalCount += getCount(numWords, i);
    }
    cout << "Total number of letters required: " << totalCount;
}

However, this is not giving me the right answer. What am I doing wrong? It outputs 21088 while the answer is 21124.

Answer 1

My Python code

ones = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
        "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
tens = ["", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]

def to_words(i):
    if 0 <= i < 20:
        return ones[i]
    elif 20 <= i < 100:
        return tens[i//10]+ (ones[i%10] if(i%10!=0) else "")
    elif 100 <= i <1000:
        return ones[i//100] + "hundred" + ("and"+to_words(i%100) if(i%100!=0) else "")


s=0
for k in range(1,1000):
    s+=len(to_words(k))
print(s+11)

Answer 2

//here is a function to count letters in the word representation of a number

int countLetters(int num)
{
int count = 0;

if( num >= 1000000000 )
count += countLetters( num / 1000000000 ) + 7 + countLetters( num % 1000000000);
else if ( num >= 1000000 )
count += countLetters( num / 1000000 ) + 7 + countLetters( num % 1000000);
else if( num >= 1000 )
count += countLetters( num / 1000 ) + 8 + countLetters( num % 1000);
else if( num >= 100 )
count += countLetters( num / 100 ) + 7 + countLetters( num % 100) + (num % 100 > 0 ? 3 : 0);
else if( num >= 20 )
{
    switch( num / 10 ) 
    {
        case  2: count += 6;    break;
        case  3: count += 6;    break;
        case  4: count += 5;     break;
        case  5: count += 5;     break;
        case  6: count += 5;     break;
        case  7: count += 7;   break;
        case  8: count += 6;    break;
        case  9: count += 6;     break;
    }
    count += countLetters( num % 10 );
}
else 
{
    switch( num )
    {
        case  1: count += 3;      break;
        case  2: count += 3;      break;
        case  3: count += 5;    break;
        case  4: count += 4;     break;
        case  5: count += 4;     break;
        case  6: count += 3;      break;
        case  7: count += 5;    break;
        case  8: count += 5;    break;
        case  9: count += 4;     break;
        case 10: count += 3;      break;
        case 11: count += 6;   break;
        case 12: count += 6;   break;
        case 13: count += 8; break;
        case 14: count += 8; break;
        case 15: count += 7;  break;
        case 16: count += 7;  break;
        case 17: count += 9;break;
        case 18: count += 8; break;
        case 19: count += 8; break;      
    }
}

return count;

}

Answer 3

I think your problem is with numbers like 215. You consider it to be "two hundred and one five".

BTW, here is a correct solution in python I wrote (sorry for not doing it in C):

numWords = {1: 3, 2: 3, 3: 5, 4: 4, 5: 4, 6: 3, 7: 5, 8: 5, 9: 4, 10: 3, 11: 6, 12: 6, 13: 8, 14: 8, 15: 7, 16: 7, 17: 9, 18: 8, 19: 8, 20: 6, 30: 6, 40: 5, 50: 5, 60: 5, 70: 7, 80: 6, 90: 6, 100: 7, 1000: 8, 0: 3}
def get_count(number):
    if number==0:
        return 0
    if number > 99:
        return get_count(number / 100) + len("hundred") + ((len('and') + get_count(number % 100)) if (get_count(number % 100)) else 0)
    if number > 20:
        return numWords[(number / 10)*10] + get_count(number % 10)
    return numWords[number]
print sum(get_count(x) for x in xrange(1,1000))+len('one thousand')

You can see it much shorter than yours. The main improvement I think, is using recursive calls to the method. This would have prevented you from falling into the problem with 215, since the recursion handles the 200 and 15 separately.

Answer 4

You are not considering the tens right, i.e 111-120 211-220 etc. replace

int tensCount = 0;
if(tens==1) {tenscount = words[10+units]; units=0;}
else if(tens>1) {tenscount = words[tens]; units = words[units];}
else units = words[units];

and add units in the return