Project Euler Problem 8 - Largest product in a series

Question

I am new to python3 and tried to solve the task in a very basic way. Please critique my code. I appriciate any suggestions for improvement.

Here is the question:

The four adjacent digits in the 1000-digit number that have the greatest product are 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

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

My Code:

s = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
listem = []
listem2 = []
highest = 1
pp = 13
sonuc = 1
for i in range(1001 - pp + 1): 
 listem.append(s[i: i+pp])
 for digit in listem[i]:
 listem2.append(digit)
 listem2 = [int(k) for k in listem2]
 for q in listem2:
 sonuc *= q
 if highest < sonuc:
 highest = sonuc
 sonuc = 1
 listem2 = []
print(highest)

• Russ Hyde: I'd probably take highest to be 0 or -1; in case the dataset contains too many zeros.

Answer 1

The easiest (but not computationally most efficient) way to solve this challenge is to use a brute-force algorithm, like you did. However you can write it a lot more succinctly when using more of the tools available in the Python standard library.

• Use a generator expression to get all slices:

  s = "..."
  n = 13
  slices = (s[i:i+n] for i in range(len(s) - n))
  next(slices)
  # '7316717653133'
  

• map this string to an iterable of integers:

  slices = (s[i:i+n] for i in range(len(s) - n))
  list(map(int, next(slices)))
  # [7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3]
  

• Use functools.reduce and operator.mul to get the product of this iterable:

  from functools import reduce
  from operator import mul
  slices = (s[i:i+n] for i in range(len(s) - n))
  reduce(mul, map(int, next(slices)))
  # 5000940
  

• Use max to...get the maximum of those:

  slices = (s[i:i+n] for i in range(len(s) - n))
  max(reduce(mul, map(int, slice)) for slice in slices)
  

• Finally, wrap the code in functions and the calling code in a if __name__ == "__main__": guard:

  from functools import reduce
  from operator import mul
  def prod(x):
   return reduce(mul, x)
  def maximum_product(s, n):
   return max(prod(map(int, s[i:i+n])) for i in range(len(s) - n))
  if __name__ == "__main__":
   s = "..."
   n = 13
   print(max_product(s, n))
  

• Güray Sur: I appriciate all your suggestions,,

Answer 2

Essentially your algorithm

• partitions a string of integers into integer-sublists of a fixed size

• iterates over each sublist of integers

• computes the product for each sublist

• then updates the maximum-possible-product if the most recent product is larger

That's a perfectly logical way to solve the problem.

But there are some algorithmic gains to be had (which I won't code up for you, because you'll gain more from writing it up yourself).

In essence, each time I take the product of 5 integers, I have to do 4 multiplications. So if I wanted to compute the product of the first, and the second, 5 integers in the string 624919..., that is, the product of (6,2,4,9,1) and (2,4,9,1,9), is there a more efficient way to do it than to compute the products independently?

It turns out there is. First I compute the product (2,4,9,1), then to get the first answer I multiply this by 6, and to get the second I multiply it by 1. Doing the products independently requires 8 multiplications; doing the products with info about the overlaps requires 5 multiplications.

Think about how you could use a "sliding window" approach to more efficiently calculate the 13-mer products. Be careful of the zeros.

From a code-review point of view:

• 1) Separate parsing the input data from processing that data

  • int_string = '12345....'
  • int_list = [int(x) for x in int_string]

• 2) Wrap your algorithm in a function (list[int], int) -> int; and call it

  • def largest_p_product(ints, p): ... <copy in your code> ...
  • result = largest_p_product(int_list, 13)
  • print(result)

• 3) Consider what might happen with inappropriate data

  • what if the list[int] is shorter than pp
  • what if the input string contains non-digit characters?
  • what if the list[int] is all zero?

• Güray Sur: I appriciate all your suggestions,,