Project Euler #8 in Python

There were several issues.

1. You were printing product not biggest. Make sure to print the right variable!

2. You were iterating through the length of the entire string when you should really just iterate in the range [0..len(num) - 4) so that you don't get an IndexError when you do your product calculation.

3. You were incrementing your i variable wrong. You want to increment it by 1 each turn so just do i += 1 or i = i + 1. The code i += i + 1 is equivalent to i = i + i + 1. I don't think you wanted to double i on every iteration of your while loop. :)

4. Sequences are 0-indexed in Python. This means when you are iterating through a set of indices, the first element is always at seq[0] and the elements continue until seq[n-1]. Therefore you should start your i variable at 0, not 1!

5. You were not measuring your time correctly. You want to have your start time be assigned to before all your code executes so that you can correctly measure elapsed time.

Here is your fixed code:

'''
Find the greatest product of five consecutive digits in the 1000-digit number
'''

import time
start = time.time()

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

biggest = 0
i = 0
while i < len(num) - 4:
    one = int(num[i]) 
    two = int(num[i+1])  
    thr = int(num[i+2]) 
    fou = int(num[i+3])
    fiv = int(num[i+4])
    product = one*two*thr*fou*fiv
    if product > biggest:
        biggest = product
    i = i + 1 
print(biggest)

elapsed = (time.time() - start)
print("This code took: " + str(elapsed) + " seconds")

Your problem is here:

i += i+1

You are walking through the list too fast. You should do this:

i += 1

I would write the code like this:

import operator

# Return the product of all the digits in `series` converted to integers
def numprod(series):
    # Convert the series of digits into a list of integers
    digits = [int(c) for c in series]

    # This applies the multiplication operator to all the digits,
    # starting with 1
    return reduce(operator.__mul__, digits, 1)

# Produce every string of length 5
# This uses a generator but could just as easily use a list comprehension:
# numiter = [num[i : i + SERIES_SIZE] for i in range(len(num) - SERIES_SIZE + 1)]
SERIES_SIZE = 5
numiter = (num[i : i + SERIES_SIZE] for i in range(len(num) - SERIES_SIZE + 1))

# Calculate all the products
allnumprods = [numprod(series) for series in numiter]

# Find the maximum of all the products
print max(allnumprods)

A simpler way to calculate the product is this:

def numprod(series):
    product = 1
    for c in series:
        product *= int(c)
    return product

One can also use functional programing to simplify the problem considerably:

def foo():
    max_product = 0
    num = "string of input number"
    for e,n in enumerate(num):
        product = reduce((lambda x,y: x*y),map(int,(num[e:e+13])))
        if product > max_product: 
            max_product = product
    return max_product

give it a try!

The issue is here:

i += i+1

You are doubling i every time and adding 1 to it. So if i is 1, you make it 3. If it's 3, you make it 7. If it's 7, you make it 15, and so on. But this means your index is missing a lot of places, isn't it!

It is causing you to skip many positions in the number. You want to use:

i += 1

This just means add 1 to i.

Or you could do:

i = i+1

This means, set i equal to i+1.

import string
numbers=list()
fo=open("C:/python34/libs/maths2.txt","r+")
for eachline in fo:
    for char in eachline:
        if char.isdigit():
            A=char
            numbers.append(int(A))

print(numbers)
list1=list()
for i in range(0,len(numbers)-4):
    x=numbers[i]*numbers[i+1]*numbers[i+2]*numbers[i+3]*numbers[i+4]
    list1.append([x])
print(list1)
print(max(list1))

again this is not optimized but it works for 13 digits

import time
start_time = time.time()
num = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450"
i = 0
j = 0
k = 0
while i < len(num) - 13:
    one = int(num[i])
    two = int(num[i + 1])
    three = int(num[i + 2])
    four = int(num[i + 3])
    five = int(num[i + 4])
    six = int(num[i + 5])
    seven = int(num[i + 6])
    eight = int(num[i + 7])
    nine = int(num[i + 8])
    ten = int(num[i + 9])
    eleven = int(num[i + 10])
    twoelve = int(num[i + 11])
    thirteen = int(num[i + 12])
    j = one * two * three * four * five * six * seven * eight * nine * ten * eleven * twoelve * thirteen
    i = i + 1
    if k < j:
        k = j
print(k)
print(time.time() - start_time," seconds")

# 8 Largest product in a series

from functools import reduce

the_num = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

the_num_lst = []
for n in the_num:
    the_num_lst.append(int(n))

x = 0
y = reduce((lambda a, b: a * b), the_num_lst[x:x + 13])
while x < 1000 - 13:
    x += 1
    z = reduce((lambda a, b: a * b), the_num_lst[x:x + 13])
    if z > y:
        y = z
print(y)

My solution

s = '''7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'''


t = list(s)
#len(t) = 1000
#t[::-1] = t[999]

r = []
q = 0
while q <= 999:
    w = int(t[q])
    r.append(w)
    q += 1

a = 0
b = 1
c = 2
d = 3
e = 4
f = 5
g = 6
h = 7
i = 8
j = 9
k = 10
l = 11
m = 12

y = []

while m<=999:
    n = r[a]*r[b]*r[c]*r[d]*r[e]*r[f]*r[g]*r[h]*r[i]*r[j]*r[k]*r[l]*r[m]
    y.append(n)
    a += 1
    b += 1
    c += 1
    d+= 1
    e+= 1
    f+= 1
    g+= 1
    h+= 1
    i+= 1
    j+= 1
    l+= 1
    k+= 1
    m+= 1
    if m >= 1000:
        break

print(y)
print(max(y))

One-liner:

from functools import reduce
def max_prod(x):
    return max([reduce(lambda x, y: int(x) * int(y), (x[i:i+5])) for i in range(len(x)-5)])

The solutions on here iterate over the series and iterate over a window (sub-series) in each iteration, which make them very slow for large window sizes.

The solution below computes the product in each iteration by using the product from the previous iteration, so there's no need to re-compute most of it (saves a loop over each window). To do that, it uses deque from the built-in collections module to keep a running window that allows to drop elements from each window efficiently.

The basic idea is, in each iteration, divide the product from the previous iteration by the first number used in its computation and multiply it by the number in the current iteration - similar to moving the window one slot to the right.

The main difficulty is that any number multiplied by 0 is 0, so once 0 enters a window, the product of the remaining numbers are lost. To recover that, two separate products are kept in each iteration: prod (which is the true running product) and after_zero (which is the product of non-zero numbers after a 0), and after_zero is assigned back to prod once the window doesn't contain a zero anymore.

from collections import deque

def compute_window(new_digit, prod, no_zero_prod, window, old_digit=1):

    # compute product for this window
    prod = prod // old_digit * new_digit
    # if the new digit is zero, restart everything (because 0*number=0)
    if new_digit == 0:
        window, prod, no_zero_prod = deque(), 0, 1
    else:
        window.append(new_digit)
        no_zero_prod = no_zero_prod // old_digit * new_digit

    return prod, no_zero_prod, window


def greatest_product(num, window_size):

    # initialize variable
    running_window = deque()
    prod = after_zero = 1

    # calculate the initial product
    for d in num[: window_size]:
        prod, after_zero, running_window = compute_window(int(d), prod, after_zero, running_window)
    # max value to beat
    max_so_far = prod

    for d in num[window_size :]:

        # in each iteration, if the window is full, pop the element that was first entered
        current_window_size = len(running_window)
        prev = running_window.popleft() if current_window_size == window_size else 1

        # if a single element is missing from window, assign the after_zero value to prod
        # (which allows us to use it for this round's product computation)
        if current_window_size == window_size - 1:
            prod = after_zero

        # computations for this iteration
        prod, after_zero, running_window = compute_window(int(d), prod, after_zero, running_window, prev)

        # update max_so_far
        if prod > max_so_far:
            max_so_far = prod

    return max_so_far

If num is an integer instead of a string, the following works in a very similar way; only, it starts from the end by iteratively dividing the integer by 10 to get the individual digits; so instead of moving the window to the right, it moves it to the left in each iteration.

def greatest_product(num, window_size):

    n = num
    prod = after_zero = 1
    max_so_far = -1
    running_window = deque()

    while n:

        n, r = divmod(n, 10)
        current_window_size = len(running_window)
        prev = running_window.popleft() if current_window_size == window_size else 1

        if current_window_size == window_size - 1:
            prod = after_zero

        prod, after_zero, running_window = compute_window(r, prod, after_zero, running_window, prev)

        # update max_so_far
        if prod > max_so_far:
            max_so_far = prod

    return max_so_far

Output:

print(greatest_product(num, 13))
# 23514624000

To optimize the code, I think it is better to split the string by "0". Then find the product if the string length is greater than the adjacent number.

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

no_of_adjacent = 13

def find_greatest_product(num, adj):
    greatest = 1
    for i in range(adj):
        greatest *= int(num[i])
    
    prv_temp = greatest    
    for i in range(adj, len(num)):
        temp = (prv_temp // int(num[i-adj])) * int(num[i])
        prv_temp = temp
        
        if (temp > greatest):
            greatest = temp
    
    return greatest


fractions = number.split("0")
greatest_product = 1

for frac in fractions:
    if len(frac) >= no_of_adjacent:
        temp = find_greatest_product(frac, no_of_adjacent)
        if temp > greatest_product:
            greatest_product = temp

print(greatest_product)