Project Euler 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, ...と103ごとに単位が上がっていくので、
1234567であれば103ごとに1 234 567に分けて、1~999の方法でそれぞれの1 234 567を文字に変換、それぞれの後ろに単位の英語[million, thousand]及び'and'をつける
かなり煩雑な処理になっていますが、処理を上の3つの段階に分けて関数化しています。
コード
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, のようにカンマ区切りのようですので要修正です…