Yeah, not fourty. I didn't get right answer until I saw this forty was recorded as 5 letters instead of 6 letters.
Anyway.
Project Euler 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.
1. http://www.mathblog.dk/project-euler-17-letters-in-the-numbers-1-1000/
2. http://blog.functionalfun.net/2008/08/project-euler-problem-17-converting.html
3. This.
First way would be using pattern of occurrence of the words. You know, word one exist in number 1 and 51 and 100 and bla bla bla. I don't really want to deal with this one.
Second way, it is by actually calculating the letters. The Words for specific numbers stored in a dictionary (I don't know what is that). Though this guy made it for more.
My way is similar, but in term of I already calculate it by hand for specific numbers. So I only add numbers according to the noOfLetter I already see first, with some more algorithm to automate the calculate for larger number. Let's see the specific number list.
num, word, noOfLetter
1, "one", 3
2, "two", 3
3, "three", 5
4, "four", 4
5, "five", 4
6, "six", 3
7, "seven", 5
8, "eight", 5
9, "nine", 4
10, "ten", 3
11, "eleven", 6
12, "twelve", 6
13, "thirteen", 8
14, "fourteen", 8
15, "fifteen", 7
16, "sixteen", 7
17, "seventeen", 9
18, "eighteen", 8
19, "nineteen", 8
20, "twenty", 6
30, "thirty, 6"
40, "forty", 5
50, "fifty", 5
60, "sixty", 5
70, "seventy", 7
80, "eighty", 6
90, "ninety", 6
100, "onehundred", 10
200, "twohundred", 10
300, "threehundred",12
400, "fourhundred",11
500, "fivehundred",11
600, "sixhundred",10
700, "Sevenhundred",12
800, "eighthundred",12
900, "ninehundred",11
1000, "onethousand",11
2, "two", 3
3, "three", 5
4, "four", 4
5, "five", 4
6, "six", 3
7, "seven", 5
8, "eight", 5
9, "nine", 4
10, "ten", 3
11, "eleven", 6
12, "twelve", 6
13, "thirteen", 8
14, "fourteen", 8
15, "fifteen", 7
16, "sixteen", 7
17, "seventeen", 9
18, "eighteen", 8
19, "nineteen", 8
20, "twenty", 6
30, "thirty, 6"
40, "forty", 5
50, "fifty", 5
60, "sixty", 5
70, "seventy", 7
80, "eighty", 6
90, "ninety", 6
100, "onehundred", 10
200, "twohundred", 10
300, "threehundred",12
400, "fourhundred",11
500, "fivehundred",11
600, "sixhundred",10
700, "Sevenhundred",12
800, "eighthundred",12
900, "ninehundred",11
1000, "onethousand",11
When I see number like 931 = "ninehundred and thirty one", I can see it can be divided by three(3) parts. So, first I calculate the number of letters for "ninehundred", then "thirty", then "one". Bear in mind, there is also "and" which only happened if the hundred don't have tens or unit. It this, I refer hundred to 100-999, tens to 10-99 and unit to 1-9. So, I am planning to make 3 different methods related to each other.
1. Unit[1-9]/noOfLetter(i)
I only need to return the specific value for each of them.
2. Tens[10-99]/noOfLetterTen(i)
For 11-19, the term is not divide-able. So we require their own noOfLetter. Then, we can set the value for 20,30,40,50,60,70,80 and 90. Why that only? Because we can re-use Unit part. So, when it is for 21, do recursive of noOfLetterTen(20) + noOfLetter(1). This, as you can see, actually "twentyone" = "twenty"+"one". But there are a need of splitting the number. I'll tell you later.
3. Hundreds[100-999]/noOfLetterHundred(i)
We need to remember that "and" only happen if there are more words after, e.g., "onehundred". So how we can divide it? I remember our modulus (%) of integer division can split numbers.
Let's test this: 1234
1234/1000=1
1234%1000=234
1234/100 =12
1234%100=34
1234/10 = 123
1234%10 = 4
So, from here, we can reduce our algorithm significantly. Bear in mind, "onehundred" can be divided into "one" and "hundred". "hundred" have noOfLetter=7. "and" have numberOfLetter=2. Something I have done to look at the pattern and create its formula.
i
|
Name
|
Return value
|
i/100
|
I%100
|
i/10
|
i%10
|
1000
|
One thousand
|
11
|
10
|
|||
100
|
One hundred
|
value(i%100)+7=3+7=10
|
1
|
0
|
||
200
|
value(i%100)+7=10
|
2
|
0
|
|||
300
|
value(i%100)+7=12
|
3
|
0
|
|||
345
|
Three hundred and forty
five
|
Value(300) + 3[and] +
value(40) + value(5)
|
3
|
45
|
4
|
5
|
400
|
value(i%100)+7=11
|
4
|
0
|
|||
500
|
value(i%100)+7=11
|
5
|
0
|
|||
600
|
value(i%100)+7=10
|
6
|
0
|
|||
700
|
value(i%100)+7=5+7=12
|
7
|
0
|
|||
800
|
value(i%100)+7=12
|
8
|
0
|
|||
900
|
value(i%100)+7=11
|
9
|
0
|
|||
1
|
One
|
3
|
||||
2
|
Two
|
3
|
||||
3
|
Three
|
5
|
||||
4
|
Four
|
4
|
||||
5
|
Five
|
4
|
||||
6
|
Six
|
3
|
||||
7
|
Seven
|
5
|
||||
8
|
Eight
|
5
|
||||
9
|
Nine
|
4
|
||||
10
|
ten
|
3
|
1
|
0
|
||
11
|
Eleven
|
6
|
1
|
1
|
||
12
|
Twelve
|
6
|
1
|
2
|
||
13
|
Thirteen
|
8
|
1
|
3
|
||
14
|
Fourteen
|
8
|
1
|
4
|
||
15
|
Fifteen
|
7
|
1
|
5
|
||
16
|
Sixteen
|
7
|
1
|
6
|
||
17
|
Seventeen
|
9
|
1
|
7
|
||
18
|
Eighteen
|
8
|
1
|
8
|
||
19
|
Nineteen
|
8
|
1
|
9
|
||
20
|
Twenty
|
6
|
2
|
0
|
||
30
|
Thirty
|
6
|
3
|
0
|
||
40
|
Forty
|
5
|
4
|
0
|
||
45
|
Fourty-five
|
Value(40)+value(5)=5+4=10
|
45
|
4
|
5
|
|
50
|
Fifty
|
5
|
5
|
0
|
||
60
|
Sixty
|
5
|
6
|
0
|
||
70
|
Seventy
|
7
|
7
|
0
|
||
80
|
Eighty
|
6
|
8
|
0
|
||
90
|
Ninety
|
6
|
9
|
0
|
||
91
|
Ninety one
|
Value(90)+value(1)=6+3=9
Value(i - i%10) +
value(i%10)
|
`
|
9
|
1
|
So, for method noOfLetterTen : noOfLetterTen(i-i%10) + noOfLetter(i%10); You see, it split by subtracting i with i%10 for the ten part and modulus i%10 for unit part. While for method noOfLetterHundred, : noOfLetter(i/100) + 7 + and + noOfLetterTen(i%100);
.
