10,000桁の数字の隣接する13桁の最大値を見つける

Question

私のコードに何が問題なのか分かりません（Project Eulerの問題8）。私は下の10,000桁の数字の13桁の数字の最大積を見つけたいと思っています。私は間違った答えを得ています。

my_list = list('7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450') 

for i in range(1000): 
    my_list[i] = int(my_list[i]) 

previous_product = 1 
for x in range(13): 
    previous_product *= my_list[x] 
current_product = previous_product*my_list[13]/my_list[0] 

for i in range(1, 987): 
    if current_product > previous_product: 
    maximum_product = current_product 
    previous_product = current_product 
    if my_list[i]==0: 
    current_product = 1 
    for x in range(13): 
     current_product *= my_list[i+x+1] 
    else: 
    current_product = previous_product*my_list[i+x+1]/my_list[i] 

print(maximum_product) 

編集：解決済み！ maximum_productは間違って定義されていました...最近の "現在の製品"の値は、必ずしも最大の製品ではなく、以前の製品よりも大きくなります。

正しい、スーパーではない、効率的なコードはいえ：あなたのアプローチが動作しない理由を

my_list = list('7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450') 

for i in range(1000): 
    my_list[i] = int(my_list[i]) 

previous_product = 1 
for x in range(13): 
    previous_product *= my_list[x] 
current_product = previous_product*my_list[13]/my_list[0] 

large_products = [] 

for i in range(1, 987): 
    if current_product > previous_product: 
    large_products.append(current_product) 
    previous_product = current_product 
    if my_list[i]==0: 
    current_product = 1 
    for x in range(13): 
     current_product *= my_list[i+x+1] 
    else: 
    current_product = previous_product*my_list[i+x+1]/my_list[i] 

print(max(large_products)) 

Answer 1

私がチェックしていませんが、あなたは簡単にこの問題を解決することができます場合は

import operator 
from functools import reduce 

my_int_list = [int(char) for char in my_list] 

max(map(lambda *x: reduce(operator.mul, x), 
     my_int_list[0:], 
     my_int_list[1:], 
     my_int_list[2:], 
     my_int_list[3:], 
     my_int_list[4:], 
     my_int_list[5:], 
     my_int_list[6:], 
     my_int_list[7:], 
     my_int_list[8:], 
     my_int_list[9:], 
     my_int_list[10:], 
     my_int_list[11:], 
     my_int_list[12:])) 

これは、ダイレクトスライスの代わりにitertools.isliceを[idx:]で使用することができます。

Answer 2

あなたの現在のコードは、間違った計画 に基づいているか、少なくとも私が完全に理解していない計画に基づいているように思われます。アルゴリズムについて考えてみると、別の方法があります。

7316717とします。そして我々は隣接する3桁の数字の を探しています。この問題は次のように解決できます。私は 各ステップの結果をハードコーディングしていますが、Python コードを書いて各部分を計算できるはずです。

• すべての隣接3桁のシーケンスを探す：

  seqs = [731, 316, 167, 671, 717] 
  

• は、自社製品を計算します。

  products = [21, 18, 42, 42, 49] 
  

• は、彼らの最大値を検索します。

  answer = max(products) 
  

Answer 3

私はあなたのコードをチェックしていないとどのようにそれが動作しません。

しかし、あなたの問題を簡単に解決するには、入力データから13の隣接数を持つすべての可能なスライスを生成し、その要素の積を見つけてそれらの最大積を見つけます。ここで

はそれを行うための方法です：

data = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450' 

def product(a): 
    prod = 1 
    for k in a: 
     prod *= int(k) 
    return prod 

def max_adjacent_number(data, suit=13): 
    return max(product(data[k:k+suit]) for k in range(len(data)) if '0' not in data[k:k+suit]) 


from time import time 
start = time() 
val = max_adjacent_number(data) 
elapsed = time() - start 
print("Solution: {0} \telapsed: {1:.5f}ms".format(val, elapsed*1000)) 

出力：ここ

# Best time 
Solution: 23514624000 elapsed: 1.31226ms 

Answer 4

があなたのスライディングウィンドウのアイデアの実装である、それだけで何のゼロを含まない文字列に適用されるように修正します上記sで

def max_product(s,k): 
    s = [int(d) for d in s] 
    p = 1 
    for d in s[:k]: 
     p *= d 
    m = p 
    for i,d in enumerate(s[k:]): 
     p *= d 
     p //= s[i] 
     if p > m: m = p 
    return p 

はのLEAにおける長さの非ゼロ数字の文字列でありますt k（問題でk = 13）。k連続桁の最大積を返します。繊細さは列挙の仕方にあります。 s[k:]にenumerateを使用すると、iというインデックスが0から始まります。これは、そのループを最初に通過する際に削除する要素とまったく同じです。

chunks = [s for s in data.split('0') if len(s) >= 13] 

24は、このような塊がある：

にはゼロを含まず、少なくとも13桁の長さのチャンクに

data = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450' 

まずスプリットにこれを適用します。

print(max(max_product(s,13) for s in chunks)) 

確かにこの質問はおそらく、[コードレビュー]（HTTPSに属し23514624000