Python Implementation of Problem 17

View source code here on GitHub!

Problem Solution

Project Euler Problem 17

I feel like there is a better way to recurse this problem, but I could not think of one at the time

Problem:

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.

python.src.p0017.to_string(n: int) → str
python.src.p0017.main() → int
 1"""
 2Project Euler Problem 17
 3
 4I feel like there is a better way to recurse this problem, but I could not
 5think of one at the time
 6
 7Problem:
 8
 9If the numbers 1 to 5 are written out in words: one, two, three, four, five,
10then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
11
12If all the numbers from 1 to 1000 (one thousand) inclusive were written out in
13words, how many letters would be used?
14
15NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
16forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20
17letters. The use of "and" when writing out numbers is in compliance with
18British usage.
19"""
20
21
22def to_string(n: int) -> str:
23    if n >= 1000:
24        return "{} thousand".format(to_string(n // 1000 % 100))
25    elif n >= 100:
26        hundreds = "{} hundred".format(to_string(n // 100 % 10))
27        if n % 100:
28            return "{} and {}".format(hundreds, to_string(n % 100))
29        return hundreds
30    elif n >= 20:
31        tens = {
32            2: "twenty",
33            3: "thirty",
34            4: "forty",
35            5: "fifty",
36            6: "sixty",
37            7: "seventy",
38            8: "eighty",
39            9: "ninety"
40        }[n // 10]
41        if n % 10:
42            return "{}-{}".format(tens, to_string(n % 10))
43        return tens
44    elif n > 12:
45        prefix = {
46            13: "thir",
47            14: "four",
48            15: "fif",
49            16: "six",
50            17: "seven",
51            18: "eigh",
52            19: "nine"
53        }
54        return "{}teen".format(prefix[n])
55    else:
56        return {
57            0: "zero",
58            1: "one",
59            2: "two",
60            3: "three",
61            4: "four",
62            5: "five",
63            6: "six",
64            7: "seven",
65            8: "eight",
66            9: "nine",
67            10: "ten",
68            11: "eleven",
69            12: "twelve"
70        }[n]
71
72
73def main() -> int:
74    answer = 0
75    for x in range(1, 1001):
76        string = to_string(x)
77        answer += len(string.replace(" ", "").replace("-", ""))
78    return answer

Tags: word-problem, combinatorics