Project Euler 008を解いてみる。「数字列中の最大の積」

Project Euler 008

008

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.

->次の問題

考え方

全ての計算結果を求めて最大値を出す以外の方法は思いつきませんでした。
1000個の数字から連続する13個の数字を選ぶ場合、乗算した結果は1000 - 13 + 1 = 988個あります。
988回ループさせて計算してもいいですが、forループを減らすために以下の考え方でやってみました。
例10桁の数字から5個の連続する数字を選ぶ場合 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 5 6 7 8 9 10 ↓ ↓ ↓ ↓ ↓ ↓ 120 720 2520 6720 15120
・数列を1つずつずらし、5この数列を作成
・縦方向に並んだ数字で乗算
この方法であればループ回数は[選ぶ数字の数]回でよくなります。
下のコードでは、1で初期化したresult配列を作成し、1000桁配列を1つずつ左にずらしながら乗算しています。

コード

euler008.py

import numpy as np

numbers = '\
73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450'


def main():
    n = 13 # 何個連続する数字を取り出すか
    num_arr = np.array([int(i) for i in numbers])  # 上の数列はstr型なので1つずつint型に変換してndarrayに入れる
    result_arr_size = num_arr.size - n + 1  # 13個取り出す組み合わせは[全体の長さ - 13 + 1]、今回は988
    result_arr = np.ones(result_arr_size)  # 乗算した答えを格納する要素が1で初期化された配列、要素数は988
    # num_arr配列全体を1つずつずらしながら13回result_arrに乗算していく
    # ->result_arrの各要素に13個の要素を乗算した結果(988個)が格納される
    for i in range(n):
        result_arr = result_arr * num_arr[i:result_arr_size + i]
    print(np.max(result_arr))  # result_arrの中から最大の数値を取得


if __name__ == '__main__':
    main()

結果 23514624000.0 main処理時間: 0.0004661083221435547 sec.

2次元配列を利用して、一気に縦の列を計算することもできます。

test = np.arange(1,11)
test_2x = np.tile(test, (5, 1))
print(test_2x)
for i in range(5):
    test_2x[i] = np.roll(test_2x[i],-i)
print(test_2x[:,:])
result = np.prod(test_2x[:,:-5], axis=0)
print(result)

[[ 1 2 3 4 5 6 7 8 9 10] [ 1 2 3 4 5 6 7 8 9 10] [ 1 2 3 4 5 6 7 8 9 10] [ 1 2 3 4 5 6 7 8 9 10] [ 1 2 3 4 5 6 7 8 9 10]] ↓ [[ 1 2 3 4 5 6 7 8 9 10] [ 2 3 4 5 6 7 8 9 10 1] [ 3 4 5 6 7 8 9 10 1 2] [ 4 5 6 7 8 9 10 1 2 3] [ 5 6 7 8 9 10 1 2 3 4]] result: [ 120 720 2520 6720 15120]
ただ、配列をずらす部分でforループを使ってしまっているので高速化はできませんでした…