Project Euler 017

017

1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

今回はちょっと面倒な問題です。
->次の問題

Project Euler目標

効率的なアルゴリズムを考える
可読性もできるだけ保つ。そのために関数化もする
関数は汎用性をもたせ、問題の条件以外でも動くようにする

考え方

せっかくなので1000以上の数についても作れるようにしてみようとしました。
また、関数の中でリストがstrでもintでも動くようにしてみました(特に意味もなく難度が上がりました)。

・1~99について
1~19については厳密な規則性がなさそうなので全てリストに入れ、20未満か以上かで条件分岐し、20以上ではn // 10で10の位を取得、n % 10で1の位を取得して組み合わせています。
・1~999について
100以上であればn // 100で100の位を取得し'hundred'を追加。さらに10以下の位があるようであれば'and'を追加。
その後、上の方法で1~99の文字列を取得し追加
・1000以上
thousand, million, billion, ...と10³ごとに単位が上がっていくので、
1234567であれば10³ごとに1 234 567に分けて、1~999の方法でそれぞれの1 234 567を文字に変換、それぞれの後ろに単位の英語[million, thousand]及び'and'をつける
かなり煩雑な処理になっていますが、処理を上の3つの段階に分けて関数化しています。

コード

euler017.py

from math import log10


one_to_nineteen_list = ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten',
                        'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen',
                        'nineteen']
twenty_to_ninety_list = ['', '', 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']
hundred_to_quintillion_list = ['hundred', 'thousand', 'million', 'billion', 'trillion', 'quadrillion', 'quintillion']
and_word = 'and'
space = ' '
hyphen = '-'


# Falseでは変換した文字列を返す。Trueでは文字列の合計をintで返す
if True:
    one_to_nineteen_list = [len(s) for s in one_to_nineteen_list]
    twenty_to_ninety_list = [len(s) for s in twenty_to_ninety_list]
    hundred_to_quintillion_list = [len(s) for s in hundred_to_quintillion_list]
    and_word = 3
    space = 0
    hyphen = 0


def main():
    answer = 0
    for i in range(1, 1001):
        answer += num_to_word(i)
    print(answer)


def num_to_word(n: int) -> str:
    """数字を英語に変換する関数
    hundred_to_quintillion_listを増やせば大きな桁まで対応可能
    Args:
        n: 自然数
    Returns:
        str: 英語を返す。リストがintになっていれば文字数を返す
    """
    digit = int(log10(n) / 3)  # 10^3ごとに単位が変わるので単位の変わるlog(n)/3をdigitとして利用
    result = __num_to_word_1_999(n % 1000)  # 百の位以下をresultに代入
    for i in range(1, digit + 1):  # 単位が変わるごとに繰り返す
        three_digits = 10 ** (i * 3)
        three_digits = (n // three_digits) % 1000  # 10^3ごとに3桁の数字を取得
        if three_digits != 0:
            if result:
                result = space + and_word + space + result  # 前の数字があればandを挿入。本来はカンマらしい
            #  3桁の数字とその桁(10^3ごと)をresultに追加
            result = __num_to_word_1_999(three_digits) + space + hundred_to_quintillion_list[i] + result
    return result


def __num_to_word_1_999(n: int) -> str:
    """数字を英語に変換するprivate関数
    1~999まで対応
    Args:
        n: 1~999までの自然数
    Returns:
        str: 英語を返す。リストがintになっていれば文字数を返す
    """
    result = one_to_nineteen_list[n // 100]  #100の位をone~nineをresultに代入、なければ空
    if n >= 100:  # 100以上ならresultにhundredを追加
        result = result + space + hundred_to_quintillion_list[0]
    if n % 100 != 0: # 十と一の位が0でない場合
        if result:  # かつresultが空でなければandを追加
            result = result + space + and_word + space
        result = result + __num_to_word_1_99(n % 100)  # 十と一の位を追加
    return result


def __num_to_word_1_99(n: int) -> str:
    """数字を英語に変換するprivate関数
    1~99まで対応
    Args:
        n: 1~99までの自然数
    Returns:
        str: 英語を返す。リストがintになっていれば文字数を返す
    """
    if n < 20:  # 20未満なら
        return one_to_nineteen_list[n]  # one~nineteenを返す
    elif n % 10 == 0:  # 一の位が0twenty~ninetyを返す
        return twenty_to_ninety_list[n // 10]
    # 20より大きくかつ1の位が0でない場合、組み合わせで返す
    return twenty_to_ninety_list[n // 10] + hyphen + one_to_nineteen_list[n % 10]


if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaにて実行
結果 21124 0.0009174346923828125 sec
文字列を出力するようにもできます。
str型のリストを使用した場合(if TrueをFalseに変更)、

num_to_word(9999999)
# -> nine million and nine hundred and ninety-nine thousand and nine hundred and ninety-nine

ただ、作ってから調べたのですが、正しくはnine million, nine hundred and ninety-nine thousand, のようにカンマ区切りのようですので要修正です…