Euler Project - 17

Question

The task indicates:

If numbers from 1 to 5 are written in words: one, two, three, four, five, that is, 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all numbers from 1 to 1000 (one thousand) inclusive were written in words, how many letters will 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. Use of "and" when recording numbers in compliance with British use.

Code I wrote:

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 does not give me the correct answer. What am I doing wrong? It outputs 21088, while the answer is 21124.

Answer 1

You do not consider dozens of right, that is, 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 to return

Answer 2

I think your problem is related to numbers like 215. You think this is two hundred and five.

By the way, here is the correct python solution I wrote (sorry for not doing this 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, in my opinion, is the use of recursive method calls. This would prevent you from falling into trouble with 215, since recursion processes 200 and 15 separately.

Answer 3

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 4

// here is a function for counting letters in the representation of the word 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; 

}