こんにちは。
今回は「Project Euler」の第11問から第20問まで解いてみます。
以下ネタバレになるので、嫌だという方は先に解いてみてください。
目次
- Problem 11 -Largest product in a grid-
- Problem 12 -Highly divisible triangular number-
- Problem 13 -Large sum-
- Problem 14 -Longest Collatz sequence-
- Problem 15 -Lattice paths-
- Problem 16 -Power digit sum-
- Problem 17 -Number letter counts-
- Problem 18 -Maximum path sum I-
- Problem 19 -Counting Sundays-
- Problem 20 -Factorial digit sum-
Problem 11 -Largest product in a grid-
以下の20×20のグリッドで、斜めに並んだ4個の数を赤色で示した。 これらの積は26 × 63 × 78 × 14 = 1788696となる。 同じ方向（縦、横、斜め）に並んだ4個の数の積の最大値は何か。
まずはグリッドを扱いやすい形に変えます。
自分は二次元の配列にしました。
num = [] num += input().split() grid = [] for i in range(0, 20*20-20+1, 20): grid.append(num[i:i+20]) print(grid)
与えられた数字たちをinput()で受け取って、20個ずつで区切ってgridに入れていきます。
続いて、本題の積の最大値を求めるコードを書いていきます。
l = ~~~ #グリッドを入れた二次元配列 n = 4 ans = 0 for i in range(20-n): for j in range(20): product = 1 for k in range(n): product *= int(l[i+k][j]) ans = max(ans, product) for i in range(20): for j in range(20-n): product = 1 for k in range(n): product *= int(l[i][j+k]) ans = max(ans, product) for i in range(20-n): for j in range(20-n): product = 1 for k in range(n): product *= int(l[i+k][j+k]) ans = max(ans, product) for i in range(20-n): for j in range(n, 20): product = 1 for k in range(n): product *= int(l[i+k][j-k]) ans = max(ans, product) print(ans)
発想はProblem 8と同じです。
縦、横、斜め（2種類）の4つの方向で考えるので、for文のブロックも4つできています。
実行すると70600674と出力され、これを提出すると正解でした。
Problem 12 -Highly divisible triangular number-
三角数は自然数を足すことで計算される。 7番目の三角数であれば、1 + 2 + 3 + 4 + 5 + 6 + 7 = 28となる。 初めの10個は1 3 6 10 15 21 28 36 45 55である。 初めの7個について約数を並べると、 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 となり、28は5個以上の約数を持つ最初の三角数であることがわかる。 500個以上の約数を持つ最初の三角数は何か。
まずは三角数を計算するプログラムをつくります。
n = 10 triangles = [] for i in range(1, n+1): tri = 0 for j in range(1, i+1): tri += j triangles.append(tri) print(triangles)
iを1からnまで変えていく中で、jを1からiまで繰り返してtriに足していき、足し終えたらtrianglesに入れます。
n = 10では[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]と出力されました。
続いて、約数を計算します。
divisors_list = {}
for i in triangles:
divisors = []
for j in range(2, i+1):
if i % j == 0:
divisors.append(j)
divisors_list[i] = divisors
print(divisors_list)
trianglesの各要素について、jを2からiまで変えてiを割ったときの余りで0になったときはそのjをiの約数として配列divisorに入れていきます。
1つのiに対して計算が終わったら配列divisorを辞書divisors_listに入れます。
n = 10では{1: [], 3: [3], 6: [2, 3, 6], 10: [2, 5, 10], 15: [3, 5, 15], 21: [3, 7, 21], 28: [2, 4, 7, 14, 28], 36: [2, 3, 4, 6, 9, 12, 18, 36], 45: [3, 5, 9, 15, 45], 55: [5, 11, 55]}と出力されました。
（後のことを考えて、1は約数から除きました。）
最後に約数の個数を数えます。
いろいろいじったので形が大分変わっていますが、やっていることはだいたい同じです。
n = 0 tri = 0 while True: tri += n divisors = [] for i in range(2, tri+1): if tri % i == 0: divisors.append(i) n += 1 if len(divisors) >= 5: print(tri) break print(divisors)
これまではnを定数として与えていましたが、while Trueの無限ループの中で1ずつ増やしていきます。
breakする条件をif len(divisors) >= 5とすると、tri = 28、divisors = [2, 4, 7, 14, 28]と出力されました。
しかし、if len(divisors) >= 500とするといつまで経っても答えが出ない。
待てば解けるのだとは思いますが改良することにします。
for i in range(2, tri+1)の部分で計算が増えてしまっている感じがするので、エラトステネスの篩のときのようにfor i in range(2, int(tri**0.5)+1)として変えてみます。
n = 0 tri = 0 while True: tri += n divisors = [] for i in range(1, int(tri**0.5)+1): if tri % i == 0: divisors.append(i) if i != tri // i: divisors.append(tri//i) divisors.sort() n += 1 if len(divisors)-1 >= 5: print(tri) break print(divisors)
ウラムの螺旋のときに説明したように、nの約数を知りたければその平方根まで繰り返せば良いということを使っています。
if tri % i == 0で約数iを探すとともに、tri // iも約数であることがわかるのでそれもdivisorsに入れます。
（if i != tri // iで同じ約数が2回カウントされてしまうことを防いでいます。）
処理の関係上、divisorsの出力に1も含まれるようにしたので、breakの条件はif len(divisors)-1 >= 5といった形になります。
これでif len(divisors)-1 >= 5とすると正しい答えが出力されたのでif len(divisors)-1 >= 500にしてみると、少し時間はかかりましたがtriとして76576500が出力されました。
これを提出すると正解でした。
Problem 13 -Large sum-
（数列は長すぎたので途中で切りました。）
以下の50桁の数100個について、それらの和の初めの10桁を出力せよ。
まずは数列を配列に入れます。
num = list(map(int, input().split())) print(num)
そして各要素の和をとり、初めの10桁を出力します。
num = ~~~ #数列 sum = 0 for i in num: sum += i ans = str(sum)[0:10] print(ans)
数（int）でも文字列（str）に変えてしまえば、配列のようにインデックスを使って任意の値がとれます。
なので、str(sum)でsumを文字列にして、[0:10]で初めの10桁を取り出します。
実行すると5537376230と出力され、これを提出すると正解でした。
Problem 14 -Longest Collatz sequence-
正の整数に対して以下のような反復的な操作が定義される。 n → n/2 (nが偶数) n → 3n + 1 (nが奇数) これを13に適用すると、以下のようになる。 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 この操作によって10個の数を経て13から1になる。 これはまだ証明されていないが、全ての数について1で終わると考えられている（コラッツの問題）。 100万より小さい数から始めたとき、最も長く続くものはどれか。 （操作中に100万を超えても問題ない。）
まずはコラッツの問題を実装します。
def collatz(n): collatz = [n] while n > 1: if n % 2 == 0: n = n // 2 elif n % 2 == 1: n = 3*n + 1 collatz.append(n) return collatz print(collatz(13))
定義そのままです。
collatz(13)を出力すると[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]となりました。
では、100万より小さい数について適用して、長く続くものを探してみます。
def collatz(n): collatz_list = [n] while n > 1: if n % 2 == 0: n = n // 2 elif n % 2 == 1: n = 3*n + 1 collatz_list.append(n) return collatz_list n = 1000000 max_chain = 0 max_start = 0 for i in range(1, n): length = len(collatz(i)) previous = max_chain max_chain = max(max_chain, length) if max_chain != previous: max_start = i print(max_start)
1からn-1までの間collatz()にあてはめて、返された配列の長さlengthについてmax_chainと比較して大きいほうをmax_chainにするという操作を行います。
もしmax_chainが更新されたら（if max_chain != previous）、そのときのiをmax_startに入れておきます。
全てについて終わったら、max_startを出力して答えとします。
n = 1000000とすると837799と出力され、これを提出すると正解でした。
ちなみにそのときの長さ（len(collatz(837799))）は525でした。
コラッツの問題は再帰的な話なので、メモ化して計算時間を短くする努力をしてみても良いかと思います。
Problem 15 -Lattice paths-
2×2のマスの左上から始めて、右か下にのみ動くことができるとすると、左下まで行くのに6つの経路が考えられる。 20×20ではいくつの経路が考えられるか。
似たような問題を高校数学でやったような気がします。
ということで、数学Aの教科書を引っ張り出してきて一旦復習します。
今回のような条件であれば最短距離で行ったときの経路の数ということになり、教科書に同じような例題がありました。
2×2であれば右右下下の4回の移動でゴールまで行けるため、この組み合わせの個数を考えれば経路の総数がわかります。
総当たり的に考えれば、
右右下下 右下右下 右下下右 下右右下 下右下右 下下右右
の6通りになりますが、20×20では総当たりは難しいです。
数学的には、4つある空欄に右2つを入れていくと考えてその組み合わせを計算すれば、残りの下2つは空いたところに入れれば良いので組み合わせの総数がわかりそうです。
空欄は4つあるのでそこから1つ目の右を入れる場所を選ぶと4通りあります。
2つ目の右は、空欄の1つは先程の右で埋まっているので3か所から選んで3通りです。
これらの積をとって$4 \times 3 = 12$通りとなりそうですが、2つの右は区別できないので右の並べ方$2!$通り分で割ってやる必要があります。
結局、$\displaystyle \frac{4 \times 3}{2!} = 6$通りとなります。
同様に考えれば、プログラムを書くまでも無く答えが出ます。
40個の空欄に20個の右と20個の下を並べるので、
$$ \displaystyle \frac{40 \times 39 \times ... \times 22 \times 21}{20!} = 137846528820 $$
というわけで137846528820と答えが出て、提出すると正解でした。
Problem 16 -Power digit sum-
2^15 = 32768であり、各桁の数の和は3 + 2 + 7 + 6 + 8 = 26となる。 2^1000の各桁の数の和はいくつか。
単純に計算していけば良さそうです。
n = 15 num = 1 for i in range(n): num *= 2 s = 0 for i in str(num): s += int(i) print(s)
n = 15とすると、num = 32768、s = 26となったので合っているとし、n = 1000としました。
結果s = 1366となり、これを提出すると正解でした。
ちなみにnum = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376でした。
Problem 17 -Number letter counts-
1から5の数を英語で書くとone two three four fiveとなり、この文字数の和は3 + 3 + 5 + 4 + 4 = 19となる。
もし1から1000までの数を英語で書いたとき、いくつの文字が使われるか。
注:スペースやハイフンは数えない。
例えば、342 (three hundred and forty-two)は23文字であり、115 (one hundred and fifteen)は20文字である。
数字を書くときの"and"の使い方はイギリス英語に従うとする。
数字を入れたら英語にして返す関数をつくってみます。
def numberEN(n): list_num = [i for i in str(n)] list_num_rev = [i for i in reversed(list_num)] for i in range(3): list_num_rev.append('0') list_num_EN = [] one = {1: "one", 2: "two", 3: "three", 4: "four", 5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine"} teen = {0: "ten", 1: "eleven", 2: "twelve", 3: "thirteen", 4: "fourteen", 5: "fifteen", 6: "sixteen", 7: "seventeen", 8: "eighteen", 9: "nineteen",} ty = {2: "twenty", 3: "thirty", 4: "forty", 5: "fifty", 6: "sixty", 7: "seventy", 8: "eighty", 9: "ninety"} #1000 if list_num_rev[3] == '1': list_num_EN.append("one") list_num_EN.append("thousand") #100 for i in range(1,10): if int(list_num_rev[2]) == i: list_num_EN.append(one[i]) list_num_EN.append("hundred") if (list_num_rev[2] != '0' or list_num_rev[3] != '0') and (list_num_rev[0] != '0' or list_num_rev[1] != '0'): list_num_EN.append("and") #10 if list_num_rev[1] == '1': for i in range(10): if int(list_num_rev[0]) == i: list_num_EN.append(teen[i]) elif list_num_rev[1] != '1': for i in range(2, 10): if int(list_num_rev[1]) == i: list_num_EN.append(ty[i]) #1 for i in range(1, 10): if int(list_num_rev[0]) == i and int(list_num_rev[1]) != 1: list_num_EN.append(one[i]) return list_num_EN num = 123 print(numberEN(num))
引数nについて、それを1文字ずつに分けて逆向きに配列に入れます。
そして、千の位が1ならone hundred、それ以外なら百の位、十の位、一の位の順に英語をあてはめていってlist_num_ENにつくられた英語を返します。
例えばnum = 123なら['one', 'hundred', 'and', 'twenty', 'three']を返します。
では、文字数を数えて足していきます。
（以下のコードでは、numberEN()の定義は長いので省いてあります。）
def numberEN(n): ~~~ n = 1000 count = 0 for i in range(1, n+1): for j in numberEN(i): for k in j: count += 1 print(count)
単純に全ての単語について文字数を数えているだけです。
n = 5では19と出力されたので合っているとし、n = 1000とすると21124と出力されました。
これを提出すると正解でした。
Problem 18 -Maximum path sum I-
以下の三角形の一番上から始めてひとつ下の行の隣接した数字に移っていくことを繰り返す。 通った数字の和の最大値は3 + 7 + 4 + 9 = 23となる。 以下の三角形について上から下までの数字の和の最大値を求めよ。 経路は全部で16384個しかないため全ての経路を試せば解くことができる。 しかし、Problem 67では100行の三角形について同様の問題を解かせる。 これはごり押しでは解けないため、工夫が必要だ！ ;o
まずは三角形の各行を配列に入れます。
t = input().split() n = int(input()) tri = [] for i in range(1, n+1): tri.append(t[:i]) del t[:i] print(tri)
三角形の各数字と行の数を入力すると、配列tに各数字が入ります。
この手前i個を配列triに入れ、その部分はtから消します。
これを行の数だけ繰り返し、二次元配列として三角形の各行の数を入れた配列triをつくります。
問題文にある4行（n = 4）の三角形を入力するとtri = [['3'], ['7', '4'], ['2', '4', '6'], ['8', '5', '9', '3']]となりました。
とりあえずは総当たり的に求めてみることにしました。
tri = [['3'], ['7', '4'], ['2', '4', '6'], ['8', '5', '9', '3']] n = 4 route = [[0,0,0,0],[0,0,0,1],[0,0,1,1],[0,0,1,2],[0,1,1,1],[0,1,1,2],[0,1,2,2],[0,1,2,3]] ans = 0 i = 0 route_max = 0 while i < 2**(n-1): s = 0 for j in range(n): s += int(tri[j][route[i][j]]) previous = ans ans = max(ans, s) if ans != previous: route_max = route[i] i += 1 print(ans) print(route_max)
小さい方の三角形だと経路全通りを入れた配列routeが全て書き出せるので一旦そうしておきました。
そして経路の個数だけ、経路上の数を足していってansを最大値に更新していく、という処理を繰り返すことで答えを得ようとしました。
n = 4つまり小さい三角形ではans = 23となったのでうまくいったとし、どうにかして経路全通りrouteを一般化できれば良さそうです。
ここは組み合わせの規則性やら配列のコピー方法やらでいろいろ苦戦しましたが、なんとかできました。
def makeAllRoute(n): route = [[0]] for i in range(n-1): new = [] for j in range(len(route)): new = route[j][:] for k in range(len(new)): new[k] += 1 route.extend([new]) for i in range(len(route)): route[i].insert(0, 0) return route n = 4 print(makeAllRoute(n))
1行の三角形の場合の経路全部[[0]]から始めて、徐々に2行、3行、…とn行まで増やしていきます。
多分もう使わないので、興味があれば解読してみてください。
n = 4では[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 2], [0, 1, 1, 1], [0, 1, 1, 2], [0, 1, 2, 2], [0, 1, 2, 3]]と出力されたので合っているとしました。
それでは、大きい方の三角形について解いていきます。
まずは三角形の数字を行毎に配列に入れるコードに入力して…
t = input().split() n = 15 tri = [] for i in range(1, n+1): tri.append(t[:i]) del t[:i] print(tri)
出たものをtriとして先程つくった全経路を試すコードに入れ、routeの部分をmakeAllRoute()による計算に置き換えます。
tri = ~~~ #三角形の数字が入った二次元配列 n = 15 def makeAllRoute(n): route = [[0]] for i in range(n-1): new = [] for j in range(len(route)): new = route[j][:] for k in range(len(new)): new[k] += 1 route.extend([new]) for i in range(len(route)): route[i].insert(0, 0) return route route = makeAllRoute(n) ans = 0 i = 0 route_max = 0 while i < 2**(n-1): s = 0 for j in range(n): s += int(tri[j][route[i][j]]) previous = ans ans = max(ans, s) if ans != previous: route_max = route[i] i += 1 print(ans) print(route_max)
結果、ans = 1074と出力され、これを提出すると正解でした。
ちなみにその経路はroute_max = [0, 1, 2, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 9]でした。
makeAllRoute()をつくっているときに、できなかったことにして答えを見ようかと思って検索してしまった過去の自分のせいで、Problem 67のネタバレ（？）的なことになってしまいました。
（そこまで行けるかはわかりませんが。）
一応、知識として頭の片隅の方に入れておきます。
（たまにありますよね、問題は上からだけど解くときは下からやると楽みたいな、発想の転換が必要なやつ。）
Problem 19 -Counting Sundays-
以下の情報が与えられる。 1900年1月1日は月曜日だった。 4、6、9、11月は30日、それ以外は31日ある。 ただし2月は28日で、閏年では29日になる。 閏年は4の倍数の年が該当するが、400の倍数でない限り該当しない。 20世紀（1901年1月1日から2000年12月31日まで）には、日曜日が月の初めに来るときは何回あるか。
曜日の計算といえば「ツェラーの公式」。
全ての月の1日に対して適用して、そのうちの日曜日の数を数えればできそうです。
また、問題文の閏年の条件が不十分な気がするので、Wikipedaから引っ張ってきました。
西暦年が4で割り切れる年は (原則として) 閏年。
ただし、西暦年が100で割り切れる年は (原則として) 平年。
ただし、西暦年が400で割り切れる年は必ず閏年。
まずはツェラーの公式を実装してみます。
といったものの、そのままツェラーの公式ではないと思うので関数名はcalcDay()としています。
def calcDay(y, m, d): #閏年の判断 def isLeap(y): if y % 4 == 0: if y % 100 == 0: l = False if y % 400 == 0: l = True else: l = True else: l = False return l days_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} sum_day = 0 #y-1年までの日数を数える for i in range(y-1900): for j in range(1, 13): if isLeap(1900+i) == True: if j == 2: sum_day += 29 elif j != 2: sum_day += days_month[j] elif isLeap(1900+i) == False: sum_day += days_month[j] #y年のm-1月までの日数を数える for i in range(1, m): if isLeap(y) == True: if i == 2: sum_day += 29 elif i != 2: sum_day += days_month[i] elif isLeap(y) == False: sum_day += days_month[i] #残ったd日分を足す sum_day += d #曜日の計算 days_week = {1: '月', 2: '火', 3: '水', 4: '木', 5: '金', 6: '土', 0: '日'} day_week = sum_day % 7 return days_week[day_week] year = 1900 month = 1 date = 1 print(calcDay(year, month, date))
1900年1月1日は月、2022年5月3日（記事編集時）は火と出力されたので合っているとしました。
そして、各月の1日を適用して日だったらカウンターを増やす、という方法で数えます。
def calcDay(y, m, d): ~~~ year = 2000 month = 12 date = 31 count = 0 for y in range(year-1900): for m in range(1, 13): if calcDay(1900+y, m, 1) == '日': count += 1 print(1900+y, m, 1) for m in range(1, month): if calcDay(year, m, 1) == '日': count += 1 print(year, m, 1) print(count)
このままでは1900年の分も入ってしまうので、出力から1900年の分（1900 4 1と1900 7 1）は除いて、結局171となりました。
これを提出すると正解でした。
Problem 20 -Factorial digit sum-
n!はn × (n − 1) × ... × 3 × 2 × 1を意味する。 例えば、10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800である。 そして各桁の和は3 + 6 + 2 + 8 + 8 + 0 + 0 = 27となる。 100!の和を求めよ。
単純に計算すれば解けそうです。
n = 100 f = 1 for i in range(1, n+1): f *= i s = 0 for i in str(f): s += int(i) print(s)
階乗を計算して、各桁の和をとっただけです。
（前の問題との落差がすごい…）
n = 100ではs = 648となり、これを提出すると正解でした。
以上、Project Eulerの問題を解いてみました。
Problem 100までならこのような形で答えを載せても良いらしいので、できるところまでやってみようかと思っています。
