Project Euler Problem 8

Largest Product in a Series

Project Euler presents the following Problem #8:

The four adjacent digits in the 1000-digit number that have the greatest product are $9\times9\times8\times9=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?

Product of String Digits

Before solving the larger problem at hand, let's decide how to approach the smaller task of calculating the product of all digits in a String of unknown size.

The obvious answer is to use a simple for loop that iterates over all characters and converts them to their numeric value:

1fun stringProduct(series: String): Long {
2    var product = 1L
3    for (ch in series) {
4        product *= ch - '0'
5    }
6    return product
7}

Line 1: If the length of the String is not expected to exceed thirteen characters, then the resulting product will not overflow Long, as $9^{13}$ does not exceed Long.MAX_VALUE.

This function works just fine, but let's use the tools that Kotlin gives us.

First, we'll use a built-in extension function, digitToInt() that converts a Char to its decimal equivalent.

Second, whenever a collection of elements needs to be transformed into a single element by performing the same accumulative operation repeatedly, we should consider using some sort of aggregate function, in this case either reduce() or fold() (or one of their respective variants). fold() is preferable in this case because it allows the return value to be of a different type than the elements in the collection, based on the type of the initial value passed as an argument:

1fun stringProduct(series: String): Long {
2    return series.fold(1L) { acc, ch ->
3        acc * ch.digitToInt() 
4    }
5}

There is a slight inefficiency in this function that becomes apparent when arguments that contain the character '0' are passed. Let's add a println() to see what happens when we provide "23034" as an argument:

1fun stringProduct(series: String): Long {
2    return series.fold(1L) { acc, ch ->
3        println("Product = ${acc * ch.digitToInt()}")
4        acc * ch.digitToInt() 
5    }
6}
7
8println(stringProduct("23034"))

Product = 2
Product = 6
Product = 0
Product = 0
Product = 0
0

Given that any digit multiplied by 0 would return 0 regardless of either the position of '0' in the String or what characters come after, we should probably include an early termination for this event.

The joy of Kotlin's trailing lambda expressions is that so much can be done in their temporary scope, with only the value of the final expression being implicitly returned. So, let's add a conditional block that causes a premature exit from the operation as soon as the character '0' is encountered:

1fun stringProduct(series: String): Long {
2    return series.fold(1L) { acc, ch ->
3        if (ch == '0') {
4            println("'0' encountered")
5            return 0L
6        } else {
7            println("Product = ${acc * ch.digitToInt()}")
8            acc * ch.digitToInt()
9        }
10    }
11}
12
13println(stringProduct("23034"))

Product = 2
Product = 6
'0' encountered
0

Rather than iterating indiscriminately over every character, fold() now terminates if the character '0' is found, thereby returning a value sooner. This is the final form of the helper function that will be used by our solutions (minus the print statements, of course).

1fun stringProduct(series: String): Long {
2    val product = series.fold(1L) { acc, ch ->
3        if (ch == '0') {
4            return 0L
5        } else {
6            acc * ch.digitToInt()
7        }
8    }
9    println("This will not be printed")
10    return product
11}
12
13fun main() {
14    val series = "23034"
15    println("String product of $series = ${stringProduct(series)}")
16}

String product of 23034 = 0

1fun stringProduct(series: String): Long {
2    val product = series.fold(1L) { acc, ch ->
3        if (ch == '0') {
4            return@fold 0L
5        } else {
6            acc * ch.digitToInt()
7        }
8    }
9    println("Perform some extra work")
10    return if (product == 0L) -1L else product
11}
12
13fun main() {
14    val series = "23034"
15    println("String product of $series = ${stringProduct(series)}")
16}

Perform some extra work
String product of 23034 = -1

Python Helper

As a comparison, Python also has aggregate functions, with the math module in version 3.8 introducing prod() that calculates the product of elements in an iterable. reduce() is also available if we wanted to pass a custom lambda. Neither allow the operation to be terminated early, however.

1from math import prod
2from functools import reduce
3
4def string_product(string: str) -> int:
5    return prod(map(int, string))
6    
7def string_product_custom(string: str) -> int:
8    return reduce(lambda acc, ch: (acc * int(ch)), string, 1)

Iterative Solution

To find the answer to Problem #8, we need to continuously slide across the input String and check the product of every $k$-digit substring, with $k$ being the requested number of adjacent digits.

Kotlin easily enables this with either windowed() or windowedSequence() (more about these extension functions); however, windowed() generates a List of all relevant snapshots for processing.

1fun largestSeriesProductWindowed(number: String, k: Int): Long {
2    return number.windowed(k) { series ->
3        stringProduct(series.toString()) 
4    }.maxOf { it }
5}

In the case of a thousand-digit String, with $k=13$, this means the temporary storage of 988 elements in memory when the only value of interest to us is the largest product found so far. Using a Sequence instead seems a wasted attempt at improving performance in this situation as the result of the whole processing chain will need to be ultimately requested in order to get an accurate final answer.

Sticking with a simple for loop seems the best choice for this problem. There are also certain conditions to check for that would warrant avoiding the loop entirely:

• If the provided String has only one character, it just needs to be cast.
• If $k=1$ then only the largest character needs to be found and cast.
• If $k$ is equal to the String size $n$, the helper function only needs to be called once.

1fun largestSeriesProduct(number: String, n: Int, k: Int): Long {
2    return when {
3        n == 1 -> number.toLong()
4        k == 1 -> number.maxOf { it.digitToInt() }.toLong()
5        n == k -> stringProduct(number)
6        else -> {
7            var largest = 0L
8            for (i in 0..n - k) {
9                largest = maxOf(largest, stringProduct(number.substring(i, i + k)))
10            }
11            largest
12        }
13    }
14}

Recursive Solution

For curiosity's sake, let's tweak our solution to make it recursive, since the problem could be approached by performing the same operation on an increasingly smaller input String. The base cases will remain unchanged, but the final branch of the when block will differ:

1fun largestSeriesProductRecursive(number: String, n: Int, k: Int): Long {
2    return when {
3        n == 1 -> number.toLong()
4        k == 1 -> number.maxOf { it.digitToInt() }.toLong()
5        n == k -> stringProduct(number)
6        else -> {
7            maxOf(
8                // first substring with k-adjacent digits
9                stringProduct(number.take(k)),
10                // provided string minus the first digit
11                largestSeriesProductRecursive(number.drop(1), n - 1, k)
12            )
13        }
14    }
15}

Here are the average speeds for the two solutions over 100 iterations (using the original thousand-digit string), with the iterative solution outperforming the recursive one regardless of the size of $k$:

Visit the following links to see the Kotlin and Python source code and test suites in their respective repositories:

• Kotlin source: solution tests
• Python source: solution tests

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️🔎🎞️🐍