Project Euler Solution 17
Problem Statement#
How many letters would be needed to write all the numbers in words from 1 to 1000?
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.
Solution#
When I saw this problem, first I wanted to find a solution to write all numbers in words from 1 to1000. So I decided to write a program that writes numbers in words to a file and then to count the letters in words leaving spaces and hyphen. Let us see how to do this:
Create a dictionary that contains numbers in words from 1 to 20, 30, 40, 50, 60, 70, 80, 90, 100 and 1000. My dictionary is nothing but a set of switch case statements that puts the corresponding word into a file.
For numbers from 1 to 19 get the words directly from dictionary. Here comes the interesting part for numbers greater than 19.
For numbers greater than 20, find number mod 10. If number mod 10 =0, it means that the number is a multiple of 10 (ie., 20, 30, 40, etc.,). So directly get the word from the dictionary. If number mod 10 not equal to zero, it means that the number may be between 20 and 30 or 30and 40 or etc,.
For example if the number is 36, then the word that we need is Thirty-One. But “Thirty” and “Six” two different words in the dictionary.
- (36/10) * 10 = 30. Now it’s easy to get the word “Thirty” from dictionary.
- 36 mod 10 = 6. Now we can get the word "Six"
Similarly for numbers greater than 100, say for example 325. The word that we needed is “Three Hundred and Twenty Five. Let us see how to get this:
- 325 divided by 100 gives 3.
- "Hundred" is common for all numbers greater than 100 ,so get it directly from dictionary.
- "and" is given directly from the program. (See program below.)
- This step is similar to what we have done for numbers greater than 20 and less than 100. (25/10) * 10 = 20 and then 25 mod 10 = 5.
After writing numbers in words from one to thousand, just calculate the string length to get the number of letters used.
Implementation#
#include <stdio.h>#include <string.h>
using namespace std;
int Numbers_inWords(int num);int Convert_Num_to_Words();FILE * fp;
int main(){ FILE * f_read; int sum = 0; int i, word_length; Convert_Num_to_Words(); char word[50]; f_read = fopen("numbersinwords.txt", "rt"); while (fscanf(f_read, "%s", word) == 1) { word_length = strlen(word); i = 0; while (i < word_length) { if (word[i] == '-') { word_length--; break; } i++; } sum = sum + word_length; } fclose(f_read); printf("%d\n", sum); return 0;}
int Convert_Num_to_Words(){ int num, i; fp = fopen("numbersinwords.txt", "w"); for (i = 1; i <= 1000; i++) { if (i == 1000) { Numbers_inWords(i / 1000); fputs(" ", fp); Numbers_inWords(i); continue; } if (i < 20) { Numbers_inWords(i); fputs("\n", fp); continue; } if (i > 19 && i < 100) { if ((i % 10) == 0) { Numbers_inWords(i); fputs("\n", fp); continue; } else { Numbers_inWords((i / 10) *10); fputs("-", fp); Numbers_inWords(i % 10); fputs("\n", fp); continue; } } if (i >= 100 && i < 1000) { if (i % 100 == 0) { Numbers_inWords(i / 100); fputs(" ", fp); Numbers_inWords(100); fputs("\n", fp); continue; } else { Numbers_inWords(i / 100); fputs(" ", fp); Numbers_inWords(100); fputs(" and", fp); num = i % 100; if (num < 20) { fputs(" ", fp); Numbers_inWords(num); fputs("\n", fp); continue; } if (num > 19 && num < 100) { if ((num % 10) == 0) { fputs(" ", fp); Numbers_inWords(num); fputs("\n", fp); continue; } else { fputs(" ", fp); Numbers_inWords((num / 10) *10); fputs("-", fp); Numbers_inWords(num % 10); fputs("\n", fp); continue; } } } } } fclose(fp); return 0;}
int Numbers_inWords(int num){ char No_in_words[10]; switch (num) { case 1: fputs("One", fp); break; case 2: fputs("Two", fp); break; case 3: fputs("Three", fp); break; case 4: fputs("Four", fp); break; case 5: fputs("Five", fp); break; case 6: fputs("Six", fp); break; case 7: fputs("Seven", fp); break; case 8: fputs("Eight", fp); break; case 9: fputs("Nine", fp); break; case 10: fputs("Ten", fp); break; case 11: fputs("Eleven", fp); break; case 12: fputs("Twelve", fp); break; case 13: fputs("Thirteen", fp); break; case 14: fputs("Fourteen", fp); break; case 15: fputs("Fifteen", fp); break; case 16: fputs("Sixteen", fp); break; case 17: fputs("Seventeen", fp); break; case 18: fputs("Eighteen", fp); break; case 19: fputs("Nineteen", fp); break; case 20: fputs("Twenty", fp); break; case 30: fputs("Thirty", fp); break; case 40: fputs("Forty", fp); break; case 50: fputs("Fifty", fp); break; case 60: fputs("Sixty", fp); break; case 70: fputs("Seventy", fp); break; case 80: fputs("Eighty", fp); break; case 90: fputs("Ninety", fp); break; case 100: fputs("Hundred", fp); break; case 1000: fputs("Thousand", fp); break; } return 0;}Sample Output#
