Project Euler Problem 8: Largest Product in a Series

When I first learned to program I didn’t explore too much. I played it safe. I took things I knew how to do and I applied those to each new problem I found, no matter how well suited the solution actually was to the problem.

But, like any good technologist, I’m lazy. So if you give me a problem that (1) I know how to solve but (2) involves me doing a lot of repetitive work and (3) hints at a lazy solution, then, well, I might be lazy enough to actually learn something new. Problem 8 was like that for me. It pushed me to understand and use Python slicing better when I was starting out. It helped me not have to type so much.

As usual, spend some time with the problem if you haven’t already.

WET Code

This problem gives us a test case and tells us that the biggest product from 4 adjacent digits of our number is 5832. Let’s hammer out a quick solution to run against that test case.

Copying and pasting the 1000 digit number from the problem into Python as a string and assigning it to the variable n we can do:

biggest = 0
for i in range(996):
    product = int(n[i]) * int(n[i + 1]) * int(n[i + 2]) * int(n[i + 3])
    biggest = max(biggest, product)

print(biggest)

This… works. And, if you can tolerate it, you can fix the ranges, extend this up to n[i + 12] and it’ll solve the actual problem. But if you’re like me, and I know I am, you’re too lazy for that.

DRY-ing Our Code

Copying and pasting code is almost always a bad idea. Imagine maintaining our solution above. You come back to this code to make a change and find yourself making the same change 13 different times. God forbid you mess up a change or, gasp, miss one of the changes you needed to make.

This is the “Don’t Repeat Yourself” principle in action. Let’s tweak our solution with slicing and a loop to remove repetition.

biggest = 0
for i in range(996):
    substring = n[i:i + 4]
    product = 1
    for digit in substring:
        product *= int(digit)
    biggest = max(biggest, product)

print(biggest)

There we go! Now it’s much easier to modify this code to solve the actual problem instead of just the test case. But if you do you’ll notice that you still have to make changes in multiple places.

Science, not Magic

The solution above has two magic numbers: the 996 in the range and the 4 in our substring slice. These “magic numbers”, or unexplained numbers directly in our code, are problematic for at least two reasons.

First, why is 996 there? What does it represent? Why that number instead of another? If we have the context of the problem fresh in our head it might be obvious that it’s the number of substrings we’re going to sample. But what if you come back to this code in a month? What if someone else needs to use it?

Second, these magic numbers introduce the same kind of repetition we want to avoid by keeping our code DRY. If you change the length of the substring from 4 (our test) to 13 (the problem) you now have to change both magic numbers. And what if we made our input number n bigger? We’d have to remember to change all those magic numbers too or our solution would no longer be correct.

Let’s rewrite our solution without the magic numbers:

biggest = 0
substring_length = 4
for i in range(len(n) - substring_length):
    substring = n[i:i + substring_length]
    product = 1
    for digit in substring:
        product *= int(digit)
    biggest = max(biggest, product)

print(biggest)

This version will automatically handle any changes to the length of n. It lets us modify the length of the substring we’re looking at in one single place. And we use a nice semantic name for the number so our code is easier to read and understand.

Scrap That, Let’s Be Complex and Efficient

We’ve nicely removed the repetition from our code. The solution runs in a fraction of a second. We could stop here, and in real-life work we probably should. But there is a way to speed up the code. It’s useful to look at this solution now and stash it in our toolbox for later.

There are 996 4-digit substrings of a 1,000 digit string, and in our solutions so far we’ve been calculating each product from scratch. It turns out that repeats a lot of work and we can get away with a lazier algorithm.

Consider the first six digits of our n (73167) and the first three 4-digit substrings:

• 7316__
• _3167_
• __1671

Each substring is only a little different from the one before it. If we think of a 4-digit-wide “window” sliding from left to right we see each substring is made by chopping off the leftmost digit of the last substring and adding a new digit to the right.

The digit products of each substring are similarly related. To find the product of each new substring we take the previous substring product, divide it by the digit that’s disappearing, then multiply it by our new digit. This algorithm works no matter how “wide” the window is: if we have the product of the last substring we can calculate the next one with only two operations (a division and a multiplication).

Well, almost. We don’t want to divide by zero so we have to be careful when zero is involved. We’ll keep track of that.

Let’s code that up:

substring_length = 4

# Keep track of whether our window includes a zero.
zero_count = n[0:substring_length].count('0')

# Initialize the value of our substring product.
previous_product = 1
for digit in n[0:substring_length]:
    if digit != 0:
        previous_product *= int(digit)

biggest = 0 if zero_count > 0 else previous_product

# Slide our window across.
for j in range(len(n) - substring_length):
    
    left = int(n[j])
    right = int(n[j + substring_length])
    
    # Update our count of zeros in the window.
    zero_count = zero_count - (left == 0) + (right == 0)
    
    # Be careful of zeros.
    if left != 0:
        next_product = previous_product / left
    if right != 0:
        next_product = next_product * right
    if zero_count == 0:
        biggest = max(biggest, next_product)    
    
    previous_product = next_product

print(biggest)

Phew. That was a lot of work to save a small amount of compute. This is the kind of optimization that’s good to talk about during a coding interview but where the extra complexity of the code and difficulty to read and comprehend it isn’t worth the performance improvement. At least, not for this problem. But hey we’re doing PE for this kind of fuh, eh?