Project Euler Problem 8

Find the largest product of any 13 digit number within a larger number.

Solution

Our first step is to get the input into a single string. We can copy and paste it using the handy heredoc library, and then use a regular expression to remove anything that is not a digit (only the first line of the input is included in the solution because its length is not relevant).

inputStr := heredoc.Doc(`
	73167176531330624919225119674426574742355349194934
	`)

// Remove anything that is not a digit from the input
re := regexp.MustCompile(`[^0-9]*`)
inputStr = re.ReplaceAllString(inputStr, "")

Our regular expression is: [^0-9]*, which breaks down to:

Match anything in the character class 0-9, i.e. digits
Use ^ to invert the character class, i.e. match anything which is not a digit
Use * to match zero or more instances of the character class

Combined with ReplaceAllString, this removes any characters which are not digits (technically it replaces them with the empty string, but that achieves the same result).

We then need to get the 13 digit substrings of the digits-only input, using a moving window:

// With s[m:n], n is exclusive so can be equal to len(s)
for s := 0; s+DIGIT_COUNT <= len(inputStr); s++ {
    digits := inputStr[s : s+DIGIT_COUNT]
}

Normally we would compare using < len(s), however because the end of the substring expression is exclusive (i.e. it is not included in the substring), we use <= len(s).

For each substring, we calculate the product and check whether it is larger than the largest product we have found so far:

currentProduct := 1

for d := range digits {
    digit, _ := strconv.Atoi(string(digits[d]))
    currentProduct *= digit
}

if currentProduct > largestProduct {
    largestProduct = currentProduct
}

Note that we have to convert digits[d] to a string before using it in strconv.Atoi, because digits[d] will be a byte rather than a string. This could produce unexpected results if digits contained multi-byte characters, but we know that it does not as we have created the input. We couldn’t get away with this in a program that took input from a user, unless we performed some validation to ensure that it only contained digits.

The full program is therefore:

package main

import (
	"fmt"
	"regexp"
	"strconv"

	"github.com/MakeNowJust/heredoc"
)

func main() {
	const DIGIT_COUNT = 13

	inputStr := heredoc.Doc(`
	73167176531330624919225119674426574742355349194934
	`)

	// Remove anything that is not a digit from the input
	re := regexp.MustCompile(`[^0-9]*`)
	inputStr = re.ReplaceAllString(inputStr, "")

	largestProduct := 0

	// With s[m:n], n is exclusive so can be equal to len(s)
	for s := 0; s+DIGIT_COUNT <= len(inputStr); s++ {
		digits := inputStr[s : s+DIGIT_COUNT]
		currentProduct := 1

		for d := range digits {
			digit, _ := strconv.Atoi(string(digits[d]))
			currentProduct *= digit
		}

		if currentProduct > largestProduct {
			largestProduct = currentProduct
		}
	}

	fmt.Println(largestProduct)
}

Optimisations

The solution above takes 0.18s to execute on my machine, so is not worth optimising. What if we had a longer series of n digits (e.g. n = 50) - could there be scope for optimisation? Calculating the product of a series of numbers involves a lot of multiplication instructions, which can be expensive.

Don’t calculate product if any digit is zero: Anything multiplied by zero is zero, so if the current window of digits contains a zero there is no point in calculating its product. However, this is only an optimisation if strings.Contains(digits, "0") is quicker than multiplying n digits. Alternatively, we could halt the calculation if the product becomes zero at any point.

Only take account of the changed digits: The only digits that change on each step are the first digit (removed) and the last digit (added). For example, if the current substring of digits is 12345 and the next digit is 6, then the new substring will be 23456. Instead of calculating the new product as 2*3*4*5*6, we could instead divide the previous product by the removed digit (1) and multiply it by the added digit (6). This would achieve the same result, and would save n-1 multiplications at the cost of a division and a multiplication. Divisions are one of the most expensive operations, however the greater the value of n, the more likely it is that one division would be faster than n-2 multiplications.