3
\$\begingroup\$

Project Euler Problem 8

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 first solution seems to perform comparably to those found in the related question, though I don't know how it fares in the time complexity department.

pe8.py:

#!/usr/bin/env python3

input_digits = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
adjacent_number = 13
greatest_product = 0

blocks_without_zeroes = tuple(filter(None, input_digits.split('0')))
for block in blocks_without_zeroes:
    for shift in range(len(block) - adjacent_number + 1): 
        product = 1 
        for i in range(adjacent_number):
            product *= int(block[i + shift])
        if product > greatest_product:
            greatest_product = product

print(greatest_product)

I've cheated a bit on the benchmark by not defining any function, and indeed running it through cProfile shows that I've only used 92 function calls. But then it becomes difficult to do unit testing, so I've upped the program a bit and now it has functions, unit tests and can read command line arguments.

euler8.py:

#!/usr/bin/env python3.6

import argparse
import random


def is_digit(string):
    if not string.isdigit():
        raise argparse.ArgumentTypeError("{} is not comprised of digits".format(string))
    return string


def adjacent_digits_with_greatest_product(input_digits, adjacent_number):
    """It is the end user's responsibility to guard against illegal input
    that is not a combination of a string of digits and a whole number.
    """
    adjacent_digits = ''
    greatest_product = int(adjacent_number == 0)
    blocks_without_zeroes = tuple(filter(None, input_digits.split('0')))
    for block in blocks_without_zeroes:
        for shift in range(len(block) - adjacent_number + 1):
            product = 1
            for i in range(adjacent_number):
                product *= int(block[i + shift])
            if product > greatest_product:
                adjacent_digits = block[shift:shift + adjacent_number]
                greatest_product = product
    if not adjacent_digits:
        adjacent_digits = input_digits[:adjacent_number].zfill(adjacent_number)
    return (adjacent_digits, greatest_product)


if __name__ == '__main__':

    parser = argparse.ArgumentParser(description="Project Euler Problem 8")
    parser.add_argument('-n', '--number', nargs=1, type=is_digit, default=[''.join(random.choices('0123456789', k=1000))])
    parser.add_argument('--adjacent', nargs=1, type=is_digit, default=[13])
    args = parser.parse_args()

    input_digits = vars(args)['number'].pop()
    adjacent_number = int(vars(args)['adjacent'].pop())
    adjacent_digits, greatest_product = adjacent_digits_with_greatest_product(input_digits, adjacent_number)

    print("Q: Find the", adjacent_number, "adjacent digits in", input_digits, "that have the greatest product.")
    print("A:", ' × '.join(adjacent_digits), "=", str(greatest_product))

test_euler8.py:

#!/usr/bin/env python3.6

import unittest
from euler8 import adjacent_digits_with_greatest_product as adgp

class TestAdjacentDigitsWithGreatestProduct(unittest.TestCase):

    def test_ordinary_inputs(self):
        self.assertEqual(adgp('91935150686511566951', 4), ('5669', 5 * 6 * 6 * 9))

    def test_input_digits_all_zeroes(self):
        self.assertEqual(adgp('0' * 7, 3), ('0' * 3, 0))

    def test_input_digits_all_ones(self):
        self.assertEqual(adgp('1' * 7, 4), ('1' * 4, 1))

    def test_adjacent_number_greater_than_input_digit_length(self):
        self.assertEqual(adgp('23050', 7), ('0023050', 0))

    def test_adjacent_number_equals_zero(self):
        self.assertEqual(adgp('747', 0), ('', 1))

    def test_nil_zero(self):
        self.assertEqual(adgp('0', 0), ('', 1))

if __name__ == '__main__':
    unittest.main()

I have little experience with writing unit tests, so I will be glad to receive some input on this. Otherwise, clean code, performance, and anything else you want to throw at me!

\$\endgroup\$
0
\$\begingroup\$

I basically took the same approach as the OP of the related question and implemented both a naive search, which is shown in the question, and an improved search, as shown below:

def adjacent_digits_with_greatest_product(input_digits, adjacent_number):
    """It is the end user's responsibility to guard against illegal input
    that is not a combination of a string of digits and a whole number.
    """
    adjacent_digits = input_digits[:adjacent_number].zfill(adjacent_number)
    greatest_product = int(adjacent_number == 0)
    blocks_without_zeroes = tuple(filter(None, input_digits.split('0')))
    for block in blocks_without_zeroes:
        if len(block) >= adjacent_number:
            product = 1
            for i in range(adjacent_number):
                product *= int(block[i])
            for shift in range(-1, len(block) - adjacent_number):
                if shift >= 0:
                    product = product // int(block[shift]) * int(block[shift + adjacent_number])
                if product > greatest_product:
                    adjacent_digits = block[shift + 1:shift + adjacent_number + 1]
                    greatest_product = product
    return (adjacent_digits, greatest_product)

I run the following code to compare the performance of my naive and improved solutions as well as the accepted answer in the other question:

#!/usr/bin/env python3.6

from functools import reduce


def prod(list):
    return reduce(lambda x, y: int(x) * int(y), list)


def get_indexes(num_list):
    for index, item in enumerate(num_list):
        if item == 0:
            yield index


def get_slices(num_list):
    start = 0
    stop = 0
    for item in get_indexes(num_list):
        start, stop = stop, item
        yield start + 1, stop
    yield stop + 1, len(num_list)


def filter_slices(num_list, length):
    for start, stop in get_slices(num_list):
        if stop - start > length:
            yield start, stop


def get_products(num_list, length):
    product = float(prod(num_list[0:length]))
    yield product
    for index in range(length, len(num_list)):
        product *= num_list[index] / num_list[index - length]
        yield product


def slice_string_search(num_list, length):
    num_list = [int(i) for i in num_list]
    return int(max(
        max(get_products(num_list[start: stop], length))
        for start, stop in filter_slices(num_list, length)
    ))


if __name__ == '__main__':

    import cProfile
    import random
    import euler8naive
    import euler8


    n = ''.join(random.choices('0123456789', k=100000))
    for a in range(1, 21):
        print("a =", a)
        cProfile.run("euler8naive.adjacent_digits_with_greatest_product(n, a)")
        cProfile.run("euler8.adjacent_digits_with_greatest_product(n, a)")
        cProfile.run("slice_string_search(n, a)")

I'm on Windows, so I run it in PowerShell:

python .\test.py | where { $_ | select-string -pattern "(a =)|(seconds)" }

which outputs

a = 1
         9050 function calls in 0.053 seconds
         18096 function calls in 0.052 seconds
         166169 function calls (158023 primitive calls) in 0.073 seconds
a = 2
         9050 function calls in 0.069 seconds
         17197 function calls in 0.048 seconds
         158753 function calls (151431 primitive calls) in 0.071 seconds
a = 3
         9050 function calls in 0.079 seconds
         16373 function calls in 0.045 seconds
         151133 function calls (144573 primitive calls) in 0.069 seconds
a = 4
         9050 function calls in 0.088 seconds
         15611 function calls in 0.047 seconds
         143862 function calls (137963 primitive calls) in 0.069 seconds
a = 5
         9050 function calls in 0.096 seconds
         14950 function calls in 0.041 seconds
         136746 function calls (131440 primitive calls) in 0.066 seconds
a = 6
         9050 function calls in 0.101 seconds
         14357 function calls in 0.039 seconds
         129687 function calls (124924 primitive calls) in 0.065 seconds
a = 7
         9050 function calls in 0.104 seconds
         13814 function calls in 0.045 seconds
         122967 function calls (118684 primitive calls) in 0.063 seconds
a = 8
         9050 function calls in 0.105 seconds
         13334 function calls in 0.034 seconds
         116502 function calls (112650 primitive calls) in 0.062 seconds
a = 9
         9050 function calls in 0.106 seconds
         12903 function calls in 0.031 seconds
         110534 function calls (107055 primitive calls) in 0.059 seconds
a = 10
         9050 function calls in 0.105 seconds
         12530 function calls in 0.039 seconds
         104244 function calls (101135 primitive calls) in 0.058 seconds
a = 11
         9050 function calls in 0.101 seconds
         12160 function calls in 0.027 seconds
         98124 function calls (95355 primitive calls) in 0.055 seconds
a = 12
         9050 function calls in 0.099 seconds
         11820 function calls in 0.025 seconds
         92785 function calls (90297 primitive calls) in 0.053 seconds
a = 13
         9050 function calls in 0.096 seconds
         11539 function calls in 0.032 seconds
         88345 function calls (86079 primitive calls) in 0.052 seconds
a = 14
         9050 function calls in 0.093 seconds
         11317 function calls in 0.023 seconds
         83179 function calls (81159 primitive calls) in 0.050 seconds
a = 15
         9050 function calls in 0.091 seconds
         11071 function calls in 0.021 seconds
         78779 function calls (76959 primitive calls) in 0.050 seconds
a = 16
         9050 function calls in 0.086 seconds
         10871 function calls in 0.025 seconds
         74524 function calls (72889 primitive calls) in 0.049 seconds
a = 17
         9050 function calls in 0.083 seconds
         10686 function calls in 0.018 seconds
         71164 function calls (69669 primitive calls) in 0.047 seconds
a = 18
         9050 function calls in 0.079 seconds
         10546 function calls in 0.017 seconds
         67889 function calls (66525 primitive calls) in 0.046 seconds
a = 19
         9050 function calls in 0.077 seconds
         10415 function calls in 0.017 seconds
         64379 function calls (63150 primitive calls) in 0.053 seconds
a = 20
         9050 function calls in 0.075 seconds
         10280 function calls in 0.015 seconds
         61139 function calls (60030 primitive calls) in 0.043 seconds

A 2–5 times speedup for typical cases. Not bad.

\$\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.