|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 17: Number Letter Counts |
|
3
|
|
|
============================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem17 |
|
6
|
|
|
:synopsis: My solution to problem #17. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem17.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
If the numbers :math:`1` to :math:`5` are written out in words: one, two, three, four, five, then there are |
|
|
|
|
|
|
15
|
|
|
:math:`3 + 3 + 5 + 4 + 4 = 19` letters used in total. |
|
16
|
|
|
|
|
17
|
|
|
If all the numbers from :math:`1` to :math:`1000` (one thousand) inclusive were written out in words, how many letters |
|
|
|
|
|
|
18
|
|
|
would be used? |
|
19
|
|
|
|
|
20
|
|
|
.. note:: do not count spaces or hyphens. For example, :math:`342` (three hundred and forty-two) contains :math:`23` |
|
|
|
|
|
|
21
|
|
|
letters and :math:`115` (one hundred and fifteen) contains :math:`20` letters. The use of "and" when writing |
|
|
|
|
|
|
22
|
|
|
out numbers is in compliance with British usage. |
|
23
|
|
|
|
|
24
|
|
|
Solution Discussion |
|
25
|
|
|
################### |
|
26
|
|
|
|
|
27
|
|
|
Use the rules of English to construct the string representing the numbers from :math:`1` to :math:`1000`, remove |
|
|
|
|
|
|
28
|
|
|
characters not to be counted, then calculate the total length of that string. |
|
29
|
|
|
|
|
30
|
|
|
Solution Implementation |
|
31
|
|
|
####################### |
|
32
|
|
|
|
|
33
|
|
|
.. literalinclude:: ../../solutions/problem17.py |
|
34
|
|
|
:language: python |
|
35
|
|
|
:lines: 39- |
|
36
|
|
|
""" |
|
37
|
|
|
|
|
38
|
|
|
|
|
39
|
|
|
def number_to_english(n: int) -> str: |
|
|
|
|
|
|
40
|
|
|
""" Translate an integer into words form |
|
41
|
|
|
|
|
42
|
|
|
:param n: the integer to translate |
|
43
|
|
|
:return: the English phrasing of :math:`n` |
|
44
|
|
|
|
|
45
|
|
|
>>> number_to_english(127) |
|
46
|
|
|
'one hundred and twenty-seven' |
|
47
|
|
|
""" |
|
48
|
|
|
|
|
49
|
|
|
ones = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", |
|
|
|
|
|
|
50
|
|
|
"thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"] |
|
51
|
|
|
tens = [None, None, "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"] |
|
|
|
|
|
|
52
|
|
|
if 0 <= n < 20: |
|
53
|
|
|
return ones[n] |
|
54
|
|
|
elif 20 <= n <= 90 and n % 10 == 0: |
|
55
|
|
|
return tens[n // 10] |
|
56
|
|
|
elif 20 < n < 100: |
|
57
|
|
|
return tens[n // 10] + "-" + ones[n % 10] |
|
58
|
|
|
elif 100 <= n <= 900 and n % 100 == 0: |
|
59
|
|
|
return ones[n // 100] + " hundred" |
|
60
|
|
|
elif 100 < n < 1000: |
|
61
|
|
|
return ones[n // 100] + " hundred and " + number_to_english(n % 100) |
|
62
|
|
|
elif 1000 < n < 10000: |
|
63
|
|
|
pass |
|
64
|
|
|
elif n == 1000: |
|
65
|
|
|
return "one thousand" |
|
66
|
|
|
else: |
|
67
|
|
|
raise ValueError("unexpected input") |
|
68
|
|
|
|
|
69
|
|
|
|
|
70
|
|
|
def solve(): |
|
71
|
|
|
""" Compute the answer to Project Euler's problem #17 """ |
|
72
|
|
|
target = 1000 |
|
73
|
|
|
answer = 0 |
|
74
|
|
|
for i in range(target): |
|
75
|
|
|
words = number_to_english(i + 1).replace(" ", "").replace("-", "") |
|
76
|
|
|
answer += len(words) |
|
77
|
|
|
return answer |
|
78
|
|
|
|
|
79
|
|
|
|
|
80
|
|
|
expected_answer = 21124 |
|
|
|
|
|
|
81
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.