Simplify an "if" condition

Question

Soo... I'm trying to solver Problem n. 8 in Project Euler's site (https://projecteuler.info/problem=8) and I was wondering if there is a cleaner way to write this if condition

n="7316717653..." # there are 1000 digits 
(https://projecteuler.info/problem=8)
Max=0
s=[int(s) for s in n]
for i in range(len(s)-3):
    if s[i]*s[i+1]*s[i+2]*s[i+2] > Max:
            Max=s[i]*s[i+1]*s[i+2]*s[i+3]
print(Max)

# In particular
if s[i]*s[i+1]*s[i+2]*s[i+2] > Max:
            Max=s[i]*s[i+1]*s[i+2]*s[i+3]

How could I write this better (I must write it also as if s[i]*s[i+1]*s[i+2]*s[i+2]*s[i+3]...*s[i+13] so it would be nice to find a better way.. Thank you in advance!

Edit: I wrote the post very badly... sorry.

I meant:

Can i write if s[i]*s[i+1]*s[i+2]*s[i+3]*s[i+4]*s[i+5]*s[i+6]*s[i+7]*s[i+8]*s[i+9]*s[i+10]*s[i+11]*s[i+12]*s[i+13] > Max:

or as suggested (better, thank you)

Max=max(Max,s[i]*s[i+1]*s[i+2]*s[i+3]*s[i+4]*s[i+5]*s[i+6]*s[i+7]*s[i+8]*s[i+9]*s[i+10]*s[i+11]*s[i+12]*s[i+13])

In a better way? Like with an automated way of doing s[i+n] 13 or whatever times. Sorry for my bad english.

Edit 2: You answered when I was editing, thank to all of you!

Answer 1

You could use functools.reduce to calculate the product:

from functools import reduce
from operator import mul

reduce(mul, [2, 3, 4])  # calculates 2 * 3 * 4
# 24

Your code would be, with 13 digits multiplied, as asked at the end of your question:

from functools import reduce
from operator import mul

n = "7316717653..." # there are 1000 digits 
s = [int(s) for s in n]

maxi = max(reduce(mul, s[i:i+13]) for i in range(len(s)-13))

print(maxi)

---

Edit

Though compact to write, this is not really efficient, especially when the length of the sequence of digits multiplied together gets longer.

A more efficient idea is to view our product as built of numbers in a sliding window. When the window moves one digit to the right, the product gets divided by the number that just got out on the left, and multiplied by the one entering on the right.

This way, we only need to get two numbers and perform two operations on each step, whatever the length of the sequence.

def findmax(seq, k=13):
    p = reduce(mul, seq[:k])
    maxi = p
    for i in range(k, len(seq)):
        p = p * seq[i] // seq[i-k]
        if p > maxi:
            maxi = p
    return maxi

Some crude timing shows that it is already more than 2 x faster for sequences of length 2, more than 5 times faster for length 13.

Answer 2

You can solve this using the numpy python library. It handles numerical data more efficiently when compared to lists or strings.

For example, you could solve this by using:

import numpy as np
#n = "7316717653..." # there are 1000 digits
n = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'

n_as_nparray = np.array([int(character) for character in n])
every_thirteen_char = np.array([n_as_nparray[i:i+13] for i in range(len(n)-13)])

You will have an array with shape = (987,13).

Then, your maximum product will be:

>>> every_thirteen_char.prod(axis=1).max()
23514624000

And the sequence is found using:

>>> every_thirteen_char[every_thirteen_char.prod(axis=1).argmax()]
array([5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5])

Answer 3

Simply use the max function directly, no need for a if statement.

Max = max(Max, s[i]*s[i+1]*s[i+2]*s[i+3])

For the cumulative product, you may resort to a library like numpy, which has vectorized (i.e. really fast) functions cumprod and prod . For example,

import numpy as np

>>> np.cumprod([1,2,3,4,5])
array([  1,   2,   6,  24, 120])

and

>>> np.prod([1,2,3,4,5])
120

Of course, replace dummy [1,2,3,4,5] for s which the corresponding slice (e.g. s[:13])

Answer 4

If you're asking how to simplify s[i]*s[i+1]*s[i+2]*s[i+2], you could use a product function along with list slices. I got the definition from What's the function like sum() but for multiplication? product()?

from functools import reduce # Valid in Python 2.6+, required in Python 3
import operator

def product(sequence):
    reduce(operator.mul, sequence, 1)

n="7316717653..." # there are 1000 digits 
(https://projecteuler.info/problem=8)
s=[int(s) for s in n]
highest = s[0]
for i in range(1, len(s)-3):
    highest = max(highest, product(s[i:i+4]))
print(highest)

However, if you're looking for performance optimizations, this isn't the way to do it. This is O(n*m), where m is the length of the subsequences being multiplied, but you can take advantage of the fact that when you go to the next slice, you divide the current product by the element you're going past, and multiplying by the element you're adding, to get an O(n) algorithm.

highest = product(s[0:4])
for i in range(len(s)-5):
    highest = max(highest, highest/s[i]*s[i+4]))
print(highest)

OOPS, this second method doesn't work if there are any 0 digits. Dealing with that will complicate it significantly.

Answer 5

Although not as pretty as the simple solution provided by @Thierry, this solution is significantly faster (about 5x). Because the inclusion of zero makes the product zero, I split the text on this character. After getting the product for the first 13 characters using reduce, I then update this product by the ratio of the new number to the one dropping off. The product is always tested against the global max.

big_number = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
n = 13
global_max = 0
for chunk in big_number.split('0'):
    if len(chunk) < n:
        continue
    product = reduce(lambda x, y: x * int(y), chunk[:n], 1)  # Product of first `n` integers in `chunk`.
    global_max = max(global_max, product)
    for i in range(n, len(chunk)):
        product *= (int(chunk[i]) / int(chunk[i - n]))  # Rolling product of window size `n`.
        if product > global_max:
            global_max = product
>>> int(global_max)
23514624000

Timings

%%timeit -n 1000  # Code above.
# 437 µs ± 76.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%%timeit -n 1000
s = [int(s) for s in big_number]
maxi = max(reduce(mul, s[i:(i + 13)]) for i in range(len(s) - 13))
# 2.46 ms ± 916 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# Using numpy.
%%timeit -n 1000
n_as_nparray = np.array([int(character) for character in big_number])
every_thirteen_char = np.array([n_as_nparray[i:(i + 13)] for i in range(len(big_number) - 13)])
every_thirteen_char.prod(axis=1).max()
# 2.81 ms ± 418 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# Using pandas with a rolling window.
%%timeit -n 100
s = pd.Series([int(c) for c in big_number])
s.rolling(window=13, min_periods=1).apply(np.prod, raw=True).max().astype(int)
# 8.06 ms ± 830 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 6

The if-condition-shortener you're looking for is a mix of functools.reduce and operator.mul and a string slice:

m = functools.reduce(operator.mul, s[i:i+13])
if m > Max:
    Max = m

Don't forget to import functools and operator