3
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd probably take highest to be 0 or -1; in case the dataset contains too many zeros. \$\endgroup\$ – Russ Hyde Mar 27 at 9:52
5
\$\begingroup\$

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))
    
\$\endgroup\$
  • \$\begingroup\$ I appriciate all your suggestions,, \$\endgroup\$ – Güray Sur Apr 29 at 22:08
2
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ I appriciate all your suggestions,, \$\endgroup\$ – Güray Sur Apr 29 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.