Ståle's weblog

Problem 8 in project Euler is:

Find the greatest product of five consecutive digits in the 1000-digit number.

The first step is just to copy and paste the big block off numbers into a new file. I preserved line breaks and everything in my file, and called it Euler008-data.txt.

Since I day to day program in Python, and have been pretty happy with how Python handles file reading, I wanted to compare the Scala code for this to the equivalent Python code. I first present the Python solution for extracting the number into 1 long string:

1

digit = "".join(open("Euler008-data.txt").read().split())

Pretty short one-liner. I first open the file and read the entire content, giving me a single big string with linebreaks. I then use the default split method which splits on whitespace to create an array of strings, one for each line. Then finally that list is joined with nothing between the numbers. The result is one big number of strings.

Next I need a method for calculating the product of the digits in a string, I will use this method on each segment of 5 numbers in the digit string:

1
2
3
4

def prodDigits(n):
    prod = 1
    for d in n: prod *= int(d)
    return prod

Her it’s just a matter of iterating over the characters in the string, converting each to an int and multiplying them together.

Finally we need to test each subset of 5 digits. I include here the complete program for finding the solution.

1
2
3
4
5
6
7
8
9
10

if __name__ == "__main__":
    def prodDigits(n):
        prod = 1
        for d in n: prod *= int(d)
        return prod
    digit = "".join(open("Euler008-data.txt").read().split())
    maxval = 0
    for n in xrange(0,len(digit)-5):
        maxval = max(maxval, prodDigits(digit[n:n+5]))
    print maxval

Now for the Scala solution. I import and use the scala.io.Source.fromFile method for extracting the data from the file. The fromFile returns a list of characters, for the content off a file. To convert this into one big digit string, I just filter out all the newlines, then turn the list into a string with mkString:

1

val digit = fromFile("Euler008-data.txt") filter (_!='\n') mkString

Next we need the method for converting a string to the product of its digits. To do that, I map the string from a list of chars to a list of ints, by substracting ’0′ from each value, then I fold that list using the multiply operator:

1

def prodDigits(n:String) = (1 /: (n map (_-'0'))) (_*_)

Thanks to Scalas functional nature, this is a much shorter function than the same in Python. I add an extra step in scala, where I convert the digit string into a list of parts, each beeing 1 subset of 5 strings from the digit string:

1

val parts = for (n <- 0 until digit.length-5) yield digit.substring(n,n+5)

The final step is to map all the parts into products, then find the max value, here is the complete program:

1
2
3
4
5
6
7
8
9
10
11

import scala.io.Source.fromFile
 
object Euler008 extends Application {
    def prodDigits(n:String) = (1 /: (n map (_-'0'))) (_*_)
 
    val digit = fromFile("Euler008-data.txt") filter (_!='\n') mkString
    val parts = for (n <- 0 until digit.length-5) yield digit.substring(n,n+5)
 
    val max = parts map prodDigits reduceLeft((a,b) => if (a>b) a else b)
    println(max)
}

I think Scala is great for simple file handling (there are other methods to turn files into a list of strings as well), and the product method gets pretty small thanks to functional programming. The actual runtime is faster for the Python program though. Partly because of the JavaVM startup overhead, and also because I didn’t create a list of substrings in Python, which is an extra 995 object creations.