Project Euler 16〜20,67をpythonで解く

Problem 16

問題（英語）

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?
「 https://projecteuler.net/problem=16 」

問題（日本語）

215 = 32768 であり, 各位の数字の和は 3 + 2 + 7 + 6 + 8 = 26 となる.

同様にして, 21000 の各位の数字の和を求めよ.

注: Problem 20 も各位の数字の和に関する問題です。解いていない方は解いてみてください。
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2016 」

コード

num = 2 ** 1000
tot = 0
for i in str(num):
    tot += int(i)
print(tot)

num = 2 ** 1000

tot = 0

for i in str(num):

tot += int(i)

print(tot)

考え方

いきなりどうした？というぐらい簡単な問題。

str型をイテレータとして使っている例。

strはイテレータ

str型はイテレータなので、for分で回せる。

s = 'あいうえお'
for i in s:
    print(i)

s = 'あいうえお'

for i in s:

print(i)

実行結果:

あ
い
う
え
お

あ

い

う

え

お

これを使えば各桁を足すのも簡単に書ける。

もっと短く書ける

5行で書けて満足していたら実は一行で書けるらしい。

print(sum(map(int, str(2 ** 1000))))

1	print(sum(map(int, str(2 ** 1000))))

参考「 https://qiita.com/hoxo_m/items/a552d1098f4fdcb7e6ce 」

これもやってることは全く同じ。

for文でtot（total,合計）に足していくのは、（for文の内容が簡単なら）map関数+sum関数でスマートに書けるのか。

これを記事にするまで忘れていた。

Problem 17

問題（英語）

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.
「 https://projecteuler.net/problem=17 」

問題（日本語）

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" を使用するのは英国の慣習.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2017 」

コード

#0,one,two,three,four,five,six,seven,eight,nine
length0_9 = [0,3,3,5,4,4,3,5,5,4]

#ten,eleven,twelve,thirteen,fourteen,fifteen,sixteen,seventeen,eighteen,nineteen
length10_19 = [3,6,6,8,8,7,7,9,8,8]

#0,ten,twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety
length_ty = [0,3,6,6,5,5,5,7,6,6]

hundred = 7
_and = 3
one_thousand = 11

#n = 1〜1000
def letters(n):
    if 0 < n < 10:
        return length0_9[n]
    if 10 <= n < 20:
        digit1 = int(str(n)[-1])
        return length10_19[digit1]
    if 20 <= n < 100:
        digit1 = int(str(n)[-1])
        digit10 = int(str(n)[-2])
        return length_ty[digit10] + length0_9[digit1]
    if 100 <= n < 1000:
        digit1 = int(str(n)[-1])
        digit10 = int(str(n)[-2])
        digit100 = int(str(n)[-3])
        if n % 100 == 0:
            return length0_9[digit100] + hundred
        elif digit10 == 1:
            return length0_9[digit100] + hundred + _and + length10_19[digit1]
        else:
            return length0_9[digit100] + hundred + _and + length_ty[digit10] + length0_9[digit1]
    if n == 1000:
        return one_thousand
#size = 5
size = 1000
tot = 0
for i in range(size):
    tot += letters(i+1)
print(tot)

#0,one,two,three,four,five,six,seven,eight,nine

length0_9 = [0,3,3,5,4,4,3,5,5,4]

#ten,eleven,twelve,thirteen,fourteen,fifteen,sixteen,seventeen,eighteen,nineteen

length10_19 = [3,6,6,8,8,7,7,9,8,8]

#0,ten,twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety

length_ty = [0,3,6,6,5,5,5,7,6,6]

hundred = 7

_and = 3

one_thousand = 11

#n = 1〜1000

def letters(n):

if 0 < n < 10:

return length0_9[n]

if 10 <= n < 20:

digit1 = int(str(n)[-1])

return length10_19[digit1]

if 20 <= n < 100:

digit1 = int(str(n)[-1])

digit10 = int(str(n)[-2])

return length_ty[digit10] + length0_9[digit1]

if 100 <= n < 1000:

digit1 = int(str(n)[-1])

digit10 = int(str(n)[-2])

digit100 = int(str(n)[-3])

if n % 100 == 0:

return length0_9[digit100] + hundred

elif digit10 == 1:

return length0_9[digit100] + hundred + _and + length10_19[digit1]

else:

return length0_9[digit100] + hundred + _and + length_ty[digit10] + length0_9[digit1]

if n == 1000:

return one_thousand

#size = 5

size = 1000

tot = 0

for i in range(size):

tot += letters(i+1)

print(tot)

考え方

なかなか骨の折れる問題。

丁寧にコードを読んで貰えば、理解してもらえるはず。

重複する部分はリスト化、場合分けで計算

例えば、40~49の文字数を数える時、

forty

forty-one

forty-two

・・・

forty-nine

必要な情報はfortyの文字数と、one,two,・・・,nineの文字数である。

同様に50~59の場合、必要な情報はfiftyの文字数と、one,two,・・・,nineの文字数である。

このように必要な情報は重複するので、あらかじめリスト化して、それぞれの文字数を足してやればいい。

意外と複雑

面倒なのが、10~19で、これらの数え方は少し特殊。

例えば11は

ten-one

ではなく、

eleven

なので、他の2桁の数字と同様の方法では文字数を求められない。

よって場合分けしなくてはならず、少し面倒。

桁の取り出し方

以下のように桁を取り出した。

digit1 = int(str(n)[-1])
digit10 = int(str(n)[-2])
digit100 = int(str(n)[-3])

digit1 = int(str(n)[-1])

digit10 = int(str(n)[-2])

digit100 = int(str(n)[-3])

n桁目の数はstr型にして[-n]とスライスすることで取り出せる。

%10などと書いてもいいが、個人的にはこちらの方が直感的で好き。

変数の名前の付け方

hundred = 7
_and = 3
one_thousand = 11

hundred = 7

_and = 3

one_thousand = 11

などはその変数名の文字数を入れた変数だが、このように表現することで、

return length0_9[digit100] + hundred + _and + length_ty[digit10] + length0_9[digit1]

1	return length0_9[digit100] + hundred + _and + length_ty[digit10] + length0_9[digit1]

上のコードなどが文字そのままの意味で分かりやすいのでお気に入りポイントである。

辞書型の方が分かりやすいかも

この辺から正解した後に、ググって他の方の解答を見るようにした。

その中に辞書型を使ったコードがあり見やすいと感じた。

自分で数えない

僕はone,two,three...などと書いた後に自分で数えてしまったが、len関数で数えさせた方が良かったと反省。

自分の手間は少しでも省くのがいいプログラマーのはず。

Problem 18

問題（英語）

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
「 https://projecteuler.net/problem=18 」

問題（日本語）

以下の三角形の頂点から下の行の隣接する数字を通って下まで移動するとき, その数値の和の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23.

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2018 」

コード

#下から上に
height = 15
data = """
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""[1:-1]

#str
l_data = data.split('\n')
for i in range(height):
    #int
    l_data[i] = list(map(int,l_data[i].split(' ')))

#l_data = [[75],[95,64],...,]

for row in range(height):
    if row == 0:
        continue
    for index in range(height-row):
        l_data[height-row-1][index] += max(l_data[height-row][index],l_data[height-row][index+1])
result = l_data[0][0]
print(result) #1074

#下から上に

height = 15

data = """

95 64

17 47 82

18 35 87 10

20 04 82 47 65

19 01 23 75 03 34

88 02 77 73 07 63 67

99 65 04 28 06 16 70 92

41 41 26 56 83 40 80 70 33

41 48 72 33 47 32 37 16 94 29

53 71 44 65 25 43 91 52 97 51 14

70 11 33 28 77 73 17 78 39 68 17 57

91 71 52 38 17 14 91 43 58 50 27 29 48

63 66 04 68 89 53 67 30 73 16 69 87 40 31

04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

"""[1:-1]

#str

l_data = data.split('\n')

for i in range(height):

#int

l_data[i] = list(map(int,l_data[i].split(' ')))

#l_data = [[75],[95,64],...,]

for row in range(height):

if row == 0:

continue

for index in range(height-row):

l_data[height-row-1][index] += max(l_data[height-row][index],l_data[height-row][index+1])

result = l_data[0][0]

print(result) #1074

考え方

数学的な工夫が必要な問題。

まず、4行の例で見てみる。

下から上に最少となる経路を探す。

7 4

2 4 6

8 5 9 3

最初に3行目に注目する。

左の2に行くには8と5の2通りのルートがあるが、今回探すのは最大の経路なので、必要な情報は8だけである。

よって、2+8=10と2を上書きする。

同様に他の3行目の数字を更新すると、次のようになる。

3
7 4
10 13 15

7 4

10 13 15

すると、3行のピラミッド問題に置き換わる。

同様に計算すると、

3
20 19

20 19

最後に

23

確かに答えの23が求まった。

このやり方の面白いところは最大値は求まるが最大の経路は求まらないということである。

問われているのは最大値のみなので問題ない。

行が増えてもやり方は変わらない。

データの扱い方

相変わらず便利なsplitメソッドで解決。

まず、改行（'\n'）でリスト化して、それをさらに半角スペース（' '）で二次元リスト化する。

l_data = data.split('\n')
for i in range(height):
    l_data[i] = list(map(int,l_data[i].split(' ')))

l_data = data.split('\n')

for i in range(height):

l_data[i] = list(map(int,l_data[i].split(' ')))

改めて見るとfor文が必要ないように感じたので書き直してみたら1行で書けたが読みづらくなった。

l_data = list(map(lambda s:list(map(int,s.split(' '))),data.split('\n')))

1	l_data = list(map(lambda s:list(map(int,s.split(' '))),data.split('\n')))

読みやすさは大事なので、for文の方が良さそう。

height

高さ(height)を自分で数えてしまったが、

height = len(l_data)

1	height = len(l_data)

とすべきだった。

problem67もほぼ同じ問題なので、先に解いた。

Problem 67

問題（英語）

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
「 https://projecteuler.net/problem=67 」

問題（日本語）

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23

100列の三角形を含んでいる15Kのテキストファイル triangle.txt (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.

注：これは, Problem 18のずっと難しいバージョンです.
全部で299 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません！
あなたが毎秒1兆本の(1012)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう.
解決するための効率的なアルゴリズムがあります. ;o)
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2067 」

コード

自明&長いので省略。

考え方

Problem18とほぼ同じ。

変えるのは、heightを15から100にすることと、

height = 100

1	height = 100

dataに入れる文字列を100行verに入れ替えるだけである。

Problem 19

問題（英語）

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.

Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.

A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
「 https://projecteuler.net/problem=19 」

問題（日本語）

次の情報が与えられている.

1900年1月1日は月曜日である.

9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.

2月は28日まであるが, うるう年のときは29日である.

うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.

20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか?
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2019 」

コード

days_par_month = {1:31,2:28,3:31,4:30,5:31,6:30,7:31,8:31,9:30,10:31,11:30,12:31}
leap_days_par_month = {1:31,2:27,3:31,4:30,5:31,6:30,7:31,8:31,9:30,10:31,11:30,12:31}
Months_par_year = 12
Years_par_century = 100
Days_par_year = 365
#不要
Leap_days_par_year = 364

#1900年1月1日（月）(=1)から数える日数、
#1901年1月1日から数え始めたいので、デフォルトで365日（1900年はうるう年ではない）を代入。
day_tot = Days_par_year
#不要だけどメモ
date = {0:'日',1:'月',2:'火',3:'水',4:'木',5:'金',6:'土'}
first_Sun_count = 0

for year in range(Years_par_century):
    for month in range(Months_par_year):
        if (day_tot + 1) % 7 == 0:
            first_Sun_count += 1
        if (year + 1) % 4 == 0:
            day_tot += leap_days_par_month[month + 1]
        else:
            day_tot += days_par_month[month + 1]
print(first_Sun_count)

days_par_month = {1:31,2:28,3:31,4:30,5:31,6:30,7:31,8:31,9:30,10:31,11:30,12:31}

leap_days_par_month = {1:31,2:27,3:31,4:30,5:31,6:30,7:31,8:31,9:30,10:31,11:30,12:31}

Months_par_year = 12

Years_par_century = 100

Days_par_year = 365

#不要

Leap_days_par_year = 364

#1900年1月1日（月）(=1)から数える日数、

#1901年1月1日から数え始めたいので、デフォルトで365日（1900年はうるう年ではない）を代入。

day_tot = Days_par_year

#不要だけどメモ

date = {0:'日',1:'月',2:'火',3:'水',4:'木',5:'金',6:'土'}

first_Sun_count = 0

for year in range(Years_par_century):

for month in range(Months_par_year):

if (day_tot + 1) % 7 == 0:

first_Sun_count += 1

if (year + 1) % 4 == 0:

day_tot += leap_days_par_month[month + 1]

else:

day_tot += days_par_month[month + 1]

print(first_Sun_count)

考え方

Problem17同様、骨の折れる問題。

国語力も必要。

main

日曜日を「0」として、曜日を7で割った余り（mod7）を求めて0になるかで曜日判定を行う。

20世紀（1901年1月1日から2000年12月31日）の全ての年、月をfor文で回して月の初めの曜日判定を行う。

次の月にいく前に、その月の日数（6月なら30日,7月なら31日,閏年の2月なら27日）をdateに足す。

Problem17の時に辞書型を使った方のコードが読みやすかったので、月の日数のデータは辞書型を使用した（いい感じ）。

+1が見づらい

色々な都合で+1をしているのが見づらいと感じた。

for year in range(Years_par_century):
    for month in range(Months_par_year):
        if (year + 1) % 4 == 0:
            day_tot += leap_days_par_month[month + 1]

for year in range(Years_par_century):

for month in range(Months_par_year):

if (year + 1) % 4 == 0:

day_tot += leap_days_par_month[month + 1]

これは、例えばmonth（for文の変数）が0から始まるが、それを1月と捉えて後で+1しているからである。

以下のように書き直した方が見やすいかも。

for year in range(1,Years_par_century + 1):
    for month in range(1,Months_par_year + 1):
        if (year) % 4 == 0:
            day_tot += leap_days_par_month[month]

for year in range(1,Years_par_century + 1):

for month in range(1,Months_par_year + 1):

if (year) % 4 == 0:

day_tot += leap_days_par_month[month]

この方が変数に本来入れたい値が入るので読みやすい。

考えることが多くて読みづらい

僕のコードはなんというか数学的な考えがないと読みづらいコードになってしまっている。

この記事のコードなどは関数をうまく導入することで直感的に読めるコードになっている。

「 https://qiita.com/cof/items/44b380466e560de99e25 」

関数や状況にあった型をうまく使って直感的に読みやすいコードを書けるよう心掛けたい。

Problem 20

問題（英語）

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!
「 https://projecteuler.net/problem=20 」

問題（日本語）

n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.

例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる.
この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.

では, 100! の各位の数字の和を求めよ.

注: Problem 16 も各位の数字の和に関する問題です。解いていない方は解いてみてください。
「 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2020 」

コード

import math

num = math.factorial(100)
ans = sum(map(int,str(num)))
print(ans)

import math

num = math.factorial(100)

ans = sum(map(int,str(num)))

print(ans)

考え方

Problem16と同じ癒し枠。

この頃はsum関数+map関数を覚えてたんだな...。

以上！

段々とpythonの書き方が分かってきた感じじゃな。

次の記事↓

Project Euler 21〜25をpythonで解く