3

数時間前にこの質問を投稿しましたが、削除したと思います! 本当に申し訳ありません... 私は Project Euler Problem 17 に取り組んでいます。

もっと明白な解決策は他にもありますが、学習演習として、再帰を使用して解決することを意図して問題に取り組みました。また、コードの特定の部分が後で他のコンテキストで使用できるようになることも期待していました。問題の説明自体は、なじみのないもののために、コードの上部にある docstring にあります。

問題のコードは次のとおりです。

"""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.
"""

import collections
import re


SMALLS =       [(0,     "zero"),
                (1,     "one"),
                (2,     "two"),
                (3,     "three"),
                (4,     "four"),
                (5,     "five"),
                (6,     "six"),
                (7,     "seven"),
                (8,     "eight"),
                (9,     "nine"),
                (10,    "ten"),
                (11,    "eleven"),
                (12,    "twelve"),
                (13,    "thirteen"),
                (14,    "fourteen"),
                (15,    "fifteen"),
                (16,    "sixteen"),
                (17,    "seventeen"),
                (18,    "eighteen"),
                (19,    "nineteen")]

MULTS_OF_TEN = [(20,    "twenty"),
                (30,    "thirty"),
                (40,    "forty"),
                (50,    "fifty"),
                (60,    "sixty"),
                (70,    "seventy"),
                (80,    "eighty"),
                (90,    "ninety")]

HUNDRED =      [(100,   "hundred")]

BIGS =         [(1000,  "thousand"),
                (10**6, "million"),
                (10**9, "billion")]

# other bigs: trillion, quadrillion, quintillion, sextillion, septillion, octillion, nonillion, decillion,
#             undecillion, duodecillion, tredecillion, quattuordecillion, quindecillion, sexdecillion,
#             septendecillion, octodecillion, novemdecillion, vigintillion

SMALLS = collections.OrderedDict(reversed(SMALLS))
MULTS_OF_TEN = collections.OrderedDict(reversed(MULTS_OF_TEN))
HUNDRED = collections.OrderedDict(reversed(HUNDRED))
BIGS = collections.OrderedDict(reversed(BIGS))


def int_to_words(num, follows_hundreds=False):
    """Retuns the text-equivelent of num, using recursion for distinct
    pieces.
    """
    def do_chunk(n,
                 num_text_map,
                 include_quotient=True,
                 is_hundreds=False):

        for x in num_text_map:
            quotient = n // x
            remainder = n % x

            if n == x: return num_text_map[x]

            if quotient and remainder:
                quotient_text = (int_to_words(quotient) + " " + num_text_map[x]) \
                                if include_quotient else \
                                (num_text_map[x])
                remainder_text = int_to_words(remainder, follows_hundreds=True) \
                                if is_hundreds else \
                                int_to_words(remainder)
                return quotient_text + " " + remainder_text

            elif quotient:
                quotient_text = (int_to_words(quotient) + " " + num_text_map[x]) \
                                if include_quotient else \
                                (num_text_map[x])
                return quotient_text

        return False

    result = do_chunk(num, BIGS)
    if result: return result

    result = do_chunk(num, HUNDRED, is_hundreds=True)
    if result: return result

    result = do_chunk(num, MULTS_OF_TEN, include_quotient=False)
    if result and follows_hundreds: return "and " + result
    if result: return result

    result = do_chunk(num, SMALLS)
    if result and follows_hundreds: return "and " + result
    if result: return result

def count_letters(string):
    looking_for = "[a-z]"
    instances = re.findall(looking_for, string)
    return len(instances)

def tally_letters(start, end):
    total_letters = 0
    for i in range(start, end + 1):
        total_letters += count_letters(int_to_words(i))
    return total_letters

そして、これが予想される解と比較したプログラムの出力です。

>>> answer = tally_letters(1, 1000)
>>> assert answer == 21124
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    assert answer == 21124
AssertionError
>>> answer
1: 21118

私が 6 の差で外れていることに困惑しています。事前に助けてくれてありがとう。

4

1 に答える 1

7

誰かが私に 9 個の風船をくれて、さらに 1 個くれたら、私は 10 個の風船を持っていたと思います。一方、99 個の風船を持っていて、もう 1 個受け取った場合は、「I have one million balloons」ではなく、「I have one million balloons」と言います。

>>> int_to_words(10)
'ten'
>>> int_to_words(100)
'hundred'
>>> int_to_words(1000)
'thousand'

len("one")*2 == 6.

于 2012-08-28T04:13:06.557 に答える