2
\$\begingroup\$

Is there any room for improvement? Your feedback would be helpful.

Problem Statement: The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832. Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

import operator    
number = """\
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?


def partition(n):
    """returns a list of n series"""
    list_of_nums = list(number)
    all_partitions = []
    while len(list_of_nums) != 0:
        count = 0
        temp = ''
        while count <= n - 1:
            try:
                temp += list_of_nums[count]
                count += 1
            except IndexError:
                return all_partitions
        all_partitions.append(temp)
        if len(list_of_nums) != 0:
            del list_of_nums[0]
    return all_partitions


def get_max(all_partitions):
    """returns the maximum product of n series"""
    part_sum = []
    for num in all_partitions:
        tot = 1
        for digit in num:
            tot *= int(digit)
        if tot != 0:
            part_sum.append((num, tot))
    return sorted(part_sum, key=operator.itemgetter(1), reverse=True)[0] 
    [1]


if __name__ == '__main__':
    # Sanity check: sequence of length (4)
    partitions1 = partition(4)
    print(get_max(partitions1))
    print()

    # Result: sequence of length (13)
    partitions2 = partition(13)
    print(get_max(partitions2))
\$\endgroup\$
2
\$\begingroup\$

Some suggestions:

  • number and n could be parameters to this script. That way the whole thing would be reusable.
  • You can use list comprehensions to partition your string:

    >>> def partition(digits: str, length: int) -> List[str]:
    ...     return [digits[index:index + length] for index in range(len(digits) - length + 1)]
    ... 
    >>> partition("12345", 3)
    ['123', '234', '345']
    
  • Multiplying N random digits is going to be slower than checking whether any of the digits are zero. So your first pass could be to exclude any partitions which contain zero. If there are no partitions left afterwards the max is zero, and you've done no multiplications at all.

    >>> partitions = partition("7316717653133062491", 13)
    >>> nontrivial_partitions = [partition for partition in partitions if "0" not in partition]
    >>> nontrivial_partitions
    ['7316717653133']
    
  • An optimization on the above is to immediately discard the next N - 1 digits as soon as you encounter a zero when generating partitions, since all of those partitions are also going to multiply to zero. Make sure you check for any zeros within those numbers as well to keep skipping.
  • It looks like you have a newline at the end of number.
\$\endgroup\$

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.