# 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?
#
# A very interesting question.
#
# Pre-processing to tokenize the number with '0' as the
# delimiter and discarding strings with length < 13
# will speed this up considerably.
#
# Code optimizations were made to ensure this script
# has good performance for the general case.
MIN_SUBSTRING_LENGTH = 13
THOUSAND_DIGIT_NUMBER = '73167176531330624919225119674426574742355349194934' \
                        '96983520312774506326239578318016984801869478851843' \
                        '85861560789112949495459501737958331952853208805511' \
                        '12540698747158523863050715693290963295227443043557' \
                        '66896648950445244523161731856403098711121722383113' \
                        '62229893423380308135336276614282806444486645238749' \
                        '30358907296290491560440772390713810515859307960866' \
                        '70172427121883998797908792274921901699720888093776' \
                        '65727333001053367881220235421809751254540594752243' \
                        '52584907711670556013604839586446706324415722155397' \
                        '53697817977846174064955149290862569321978468622482' \
                        '83972241375657056057490261407972968652414535100474' \
                        '82166370484403199890008895243450658541227588666881' \
                        '16427171479924442928230863465674813919123162824586' \
                        '17866458359124566529476545682848912883142607690042' \
                        '24219022671055626321111109370544217506941658960408' \
                        '07198403850962455444362981230987879927244284909188' \
                        '84580156166097919133875499200524063689912560717606' \
                        '05886116467109405077541002256983155200055935729725' \
                        '71636269561882670428252483600823257530420752963450'


def run():
    # Split the number by '0' since any sequence of digits
    # containing 0 will have a product of 0
    split_num = THOUSAND_DIGIT_NUMBER.split('0')

    # List to hold tokens longer than 12 digits
    processed_num = []
    for token in split_num:
        if len(token) >= MIN_SUBSTRING_LENGTH:
            processed_num.append(token)

    # Multiply consecutive digits together
    max_product = 0
    max_string = ""
    for token in processed_num:
        current = 1
        for i in range(MIN_SUBSTRING_LENGTH):
            current *= int(token[i])

        if max_product < current:
            max_product = current
            max_string = token[0:MIN_SUBSTRING_LENGTH]

        # Divide by leading digit and multiply by trailing digit
        # to reduce arithmetic overhead
        for j in range(MIN_SUBSTRING_LENGTH, len(token)):
            current //= int(token[j - MIN_SUBSTRING_LENGTH])
            current *= int(token[j])
            if max_product < current:
                max_product = current
                max_string = token[j - MIN_SUBSTRING_LENGTH + 1:j + MIN_SUBSTRING_LENGTH + 1]

    print("Highest-valued chain is {0} with product {1}".format(max_string, max_product))

# Sample Output:
# Highest-valued chain is 5576689664895 with product 23514624000
#
# Total running time for Problem8.py is 0.0006465749488128165 seconds
