Home > OS >  Python Solution for Project Euler Question 8
Python Solution for Project Euler Question 8

Time:11-28

I am trying to solve the question about the largest product in a series from Project Euler website.

https://projecteuler.net/problem=8

I basically,

  • saved the 1000 digits as a text file
  • converted it to string
  • created an array called window that stores the values
  • this array goes through the 1000 digit array and stores the adjacent digits multiplies these digits and only keeps the maximum value.

The code works for the example answer given (for 4 numbers it actually calculates 5832). The problem is the code wrongly calculates the 13 digit answer and I can't seem to find the problem.

Here is my code

from functools import reduce
import numpy as np

# open the textfile
with open('Euler_8.txt') as file:
    lines = file.readlines()

# remove the \n from each line
mappedLines = list(map(lambda s: s.strip(), lines))

p = []

for ls in mappedLines:
    p.append(list(ls))

collapse = sum(p, [])  # collapsing of matrix

window = np.zeros(13)
size = len(window)

maxValue = 0
for a in range(len(collapse) - size - 1):
    for b in range(size):
        window[b] = collapse[a   b]

        intWin = list(map(int, window))

        mult = reduce(lambda x, y: x * y, intWin)
        if mult > maxValue:
            maxValue = mult

print(maxValue)

Could you help me find the problem ?

Thank you for your time.

CodePudding user response:

You compute intWin and mult inside the b loop, giving you a mix of old window and new window, and as a result you get a product that's sometimes too high. Instead, you should only compute intWin and mult once you've populated the current window.

But really, your code is over-complicated, and doesn't need reduce or numpy or a separate window array (especially as that array is a float array, which may or may not have enough accuracy for the calculations you perform). Your code also omits the window that includes the final digit in the input, although that happens not to matter in this case.

For example, this is a simplified (and corrected) version of your code.

with open('Euler_8.txt') as file:
    lines = file.readlines()

digits = ''.join(line.strip() for line in lines)
digits = [int(x) for x in digits]

size = 13
maxValue = 0
for a in range(len(digits) - size):
    prod = 1
    for b in range(size):
        prod *= digits[a   b]
    maxValue = max(maxValue, prod)


print(maxValue)
  • Related