A sample problem to solve

I will use as a problem for the purpose the slightly amended version of Problem 8 of Project Euler (https://projecteuler.net/problem=8):

The four adjacent digits (9989) being highlighted in the 1000-digit numbers that have the greatest product are as following: 
9 x 9 x 8 x 9 = 5832. 
 
73167176531330624919225119674426574742355349194934 
96983520312774506326239578318016984801869478851843 
85861560789112949495459501737958331952853208805511 
12540698747158523863050715693290963295227443043557 
66896648950445244523161731856403098711121722383113 
62229893423380308135336276614282806444486645238749 
30358907296290491560440772390713810515859307960866 
70172427121883998797908792274921901699720888093776 
65727333001053367881220235421809751254540594752243 
52584907711670556013604839586446706324415722155397 
53697817977846174064955149290862569321978468622482 
83972241375657056057490261407972968652414535100474 
82166370484403199890008895243450658541227588666881 
16427171479924442928230863465674813919123162824586 
17866458359124566529476545682848912883142607690042 
24219022671055626321111109370544217506941658960408 
07198403850962455444362981230987879927244284909188 
84580156166097919133875499200524063689912560717606 
05886116467109405077541002256983155200055935729725 
71636269561882670428252483600823257530420752963450 
 
Find the five adjacent digits in the same 1000-digit number that has the greatest product. What is the value of this product? 

An imperative monolithic solution

Let me begin by approaching the solution in a straightforward monolithic imperative manner: convert the 1000-character string representing the number into a character array, and then convert it into a cycle across all 996 groups of the five adjacent digits, calculating the digit product of each group and maintaining the current maximum. The final value of the current maximum will be the solution; it's that simple.

In order to remove the input number from the way, let's put it into a separate source code file, HugeNumber.fs, pulled to the solution scripts with the F# #load directive. The F# source file HugeNumber.fs is shown as follows:

[<AutoOpen>] 
module HugeNumber 
let hugeNumber = 
    "73167176531330624919225119674426574742355349194934\ 
    96983520312774506326239578318016984801869478851843\ 
    85861560789112949495459501737958331952853208805511\ 
    12540698747158523863050715693290963295227443043557\ 
    66896648950445244523161731856403098711121722383113\ 
    62229893423380308135336276614282806444486645238749\ 
    30358907296290491560440772390713810515859307960866\ 
    70172427121883998797908792274921901699720888093776\ 
    65727333001053367881220235421809751254540594752243\ 
    52584907711670556013604839586446706324415722155397\ 
    53697817977846174064955149290862569321978468622482\ 
    83972241375657056057490261407972968652414535100474\ 
    82166370484403199890008895243450658541227588666881\ 
    16427171479924442928230863465674813919123162824586\ 
    17866458359124566529476545682848912883142607690042\ 
    24219022671055626321111109370544217506941658960408\ 
    07198403850962455444362981230987879927244284909188\ 
    84580156166097919133875499200524063689912560717606\ 
    05886116467109405077541002256983155200055935729725\ 
 71636269561882670428252483600823257530420752963450" 

This file is going to be used by all variants of the problem solutions.

Then, F# script Ch1_1.fsx implementing an imperative solution will look as follows:

// Imperative monolithic solution a-la C/C++ 
#load "HugeNumber.fs" 
let number = hugeNumber.ToCharArray() 
let mutable maxProduct = 0 
let charZero = int('0') 
for i in 0..995 do 
  let mutable currentProduct = 1 
for j in 0..4 do 
  currentProduct <- currentProduct * (int(number.[i + j]) -      charZero) 
if maxProduct < currentProduct then 
  maxProduct <- currentProduct 
printfn "%s %d" "Imperative solution:" maxProduct 

The line #load "HugeNumber.fs" brings a string value HugeNumber.hugeNumber from the external code file HugeNumber.fs into the scope of this script.

The next line, let number = hugeNumber.ToCharArray() converts this string value into an array of 1000 individual characters, each representing a single digit.

The next line, let mutable maxProduct = 0 introduces a mutable int value used to carry the running tally of a maximal product of five adjacent digits.

The following line let charZero = int('0') is just a helper value used for converting a character code of a digit into an actual int value in the range of 0 to 9. It represents integer 48 indeed, not 0 as some of you may expect. But given char values of decimal digits '0' to '9' all have adjacent values after being converted to int, the simple subtraction of charZero from the result of converting a char digit x into an int will yield exactly x as an integer. More details on this matter will be given as we proceed further in this chapter.

The following seven lines of F# code are the gist of implementation:

for i in 0..995 do 
  let mutable currentProduct = 1 
for j in 0..4 do 
  currentProduct <- currentProduct * (int(number.[i + j]) -     charZero) 
if maxProduct < currentProduct then 
  maxProduct <- currentProduct 

This part of the script performs the following actions:

• The outer numerical for loop traverses the number array from the leftmost to the rightmost chunk of the five adjacent character digits, keeping the sequential number of the chunk (0,1,2,...,955) in the counter value i.
• The binding let mutable currentProduct = 1 provides a mutable placeholder for the product of the current chunk's digits.
• The inner numerical for loop traverses a subarray of length 5, calculating currentProduct by multiplying the intermediary result by the int value of each digit having sequential number j using the expression (int(number.[i + j]) - charZero). For example, if a current digit is 5, then int('5') - int('0') = 5.
• An if statement closing the outer loop ensures that maxProduct always contains the maximal product of already traversed chunks; hence, when the loop completes iterating, maxProduct contains the sought value.

Finally, the line printfn "%s %d" "Imperative solution:" maxProduct outputs the final result to the system console.

Running the script in its entirety with F# Interactive (FSI) yields the following solution:

Running an imperative solution script in F# Interactive

There are a few points that I would like to accentuate prior to covering other approaches to solving the problem as follows:

• The solution represents detailed "how-to" instructions
• The solution has been expressed in terms of low-level computer notions, such as statements, loops, and global values
• Values change along the execution, representing the changing state
• The solution code does not look structured, it just flows

An object-oriented solution

Now let me turn to the object-oriented manner of solving the same problem. It is typical for this kind of approach to hide implementation details inside instances of custom classes and manipulate them with the help of their own methods. I will use for this purpose the F# type feature representing the concept of the .NET object type also known as class (https://docs.microsoft.com/en-us/dotnet/articles/fsharp/language-reference/classes). An object-oriented solution to the problem is present in the following code (script Ch1_2.fsx):

// Object-oriented solution a-la C# with Iterator pattern 
#load "HugeNumber.fs" 
 
open System 
open System.Collections.Generic 
 
type OfDigits(digits: char[]) = 
    let mutable product = 1 
    do 
        if digits.Length > 9 then // (9 ** 10) > Int32.MaxValue 
            raise <| ArgumentOutOfRangeException 
              ("Constrained to max 9 digit numbers") 
        let charZero = int '0' in 
        for d in digits do 
            product <- product * ((int d) - charZero) 
        member this.Product 
            with get() = product 
 
type SequenceOfDigits(digits: string, itemLen: int) = 
    let collection: OfDigits[] = 
       Array.zeroCreate(digits.Length -itemLen + 1) 
    do 
      for i in 0 .. digits.Length - itemLen do 
        collection.[i] <- OfDigits(digits.[i..
           (i+itemLen-1)].ToCharArray()) 
    member this.GetEnumerator() = 
        (collection :> IEnumerable<OfDigits>).GetEnumerator() 
 
let mutable maxProduct = 1 
for item in SequenceOfDigits(hugeNumber,5) do 
    maxProduct <- max maxProduct item.Product 
 
printfn "%s %d" "Object-oriented solution:" maxProduct 

This solution is going to manipulate the objects of two classes. The first class named OfDigits represents the entity of the digit sequence, the product of which is the subject of our interest. An instance of OfDigits can be created from an array of a certain size of char elements carrying digits used as an argument to the OfDigits type constructor OfDigits(digits: char[]).

Upon its creation, each instance is associated with the product field representing the product of its digits. There is a reason for it not being possible to initialize product at once: in order to be representable as a positive integer value, the product can be constituted of nine digits or fewer (because the product of 10 or more 9 would exceed the maximum 32-bit int value 2147483647). In order to validate this, product is kept mutable and initially gets a value of 1 as given in the following line:

let mutable product = 1 

Then, after the length validity check, the OfDigits constructor provides the genuine value to the field by performing the calculation:

let charZero = int '0' in 
for d in digits do 
  product <- product * ((int d) - charZero) 

This value can be accessed via the instance property, Product as shown in the following line:

member this.Product with get() = product 

The another class required to implement the object-oriented solution represents the entity taking a string of digits of arbitrary length and represents it as a generic collection of type OfDigits, allowing enumeration in order to traverse it and find a member with the maximum Product property.

For this purpose, the class named SequenceOfDigits has been equipped with a constructor parameterized by the digits string carrying the input number's digits and the itemLen length of individual OfDigits instance arguments. During the SequenceOfDigits instance construction, all OfDigits instances are created as elements of the collection field array. The GetEnumerator() instance method allows you to enumerate this array by upcasting to the System.Collections.Generic.IEnumerable<OfDigits> interface type and delegating the call to the GetEnumerator() method of the latter in the following instance method definition:

member this.GetEnumerator() =  (collection :> IEnumerable<OfDigits>).GetEnumerator() 

Having the preceding two classes at your disposal makes composing the solution of the original problem rather simple: you construct a SequenceOfDigits instance of five digit OfDigits elements off hugeNumber and traverse it with the help of the for...in cycle, maintaining the maximum product tally similarly to the imperative solution as shown in the following code:

let mutable maxProduct = 1 
for item in SequenceOfDigits(hugeNumber,5)
  do  maxProduct <- max maxProduct item.Product 

In the end, place the result on the system console. Running the script in its entirety with F# FSI yields the result of object-oriented solution as shown in the following screenshot:

Running object-oriented solution script in F# Interactive

For those of you familiar with the object-oriented manner of approaching problem solutions, you may anticipate that the second solution rather differs from the first one:

• It is distinctively structured, with the segregation of definitions of pertinent classes from the usage of these classes
• Classes hide details of implementation, allowing usage only through exposed properties and methods
• The solution follows one of the well-known design patterns, namely the iterator pattern
• The amount of effort required for scaffolding substantially exceeds the effort required for the solution per se

A functional solution

Finally, let me turn to the solution manner that this book targets, namely, functional. Let's think of it as a series of data transformations. Let's look at it in a backward direction, from the sought solution back to the input string of digits as follows:

• The sought solution is the result of the max aggregate function application to the sequence of all products of five digit sequences.
• The sequence of all five digit sequences products is the result of the function application that maps each five digit sequence instance from the sequence of such sequences to the reduce of five digit sequence digits to their product.
• The sequence of all five digit sequences can be produced from the sequence of all initial digits by applying the F# core library windowing function Seq.windowed<'T> to the latter. In other words, this means taking a copy sequence of the first five digits from the left-hand side, placing this sequence in the output, shifting to the right of the source sequence by one digit, taking the first five digit copy and putting them after the first group in the output, shifting to the right by one digit of the source again, taking the first five digits, and so on, until there is no more possibility of taking the first five digits from the source. The output sequence of sequences is the sought function application result.
• Finally, the sequence of all initial digits is simply the initial string split by single digits, each converted into correspondent int from 0 to 9.

Each preceding step describes what transformation I want to apply to the single input argument in order to get the single result. Each next step takes the result of the previous step and treats it as its own input.

Let me show you how I usually derive the working code from the data transformation sketch similar to the preceding one with the help of the Read-Evaluate-Print-Loop (REPL) mode provided by FSI and the shrinking task dimension. The process of sequential progress toward the solution is shown in Fig.1.3, where I gradually start adding transformation steps to reproduce the data transformation process sketched earlier for a string consisting of just 10 digits "0918273645" by following these steps:

1. The input string is piped forward with the F# operator of the same name pipe-forward |> as the second argument of Seq.map string. The result is the sequence of 10 strings, each representing a single digit.
2. The result of step 1 is piped forward with |> as the second argument of Seq.map int. Now, the result is also the sequence, but it is a sequence of 10 int numbers, each representing the single digit.
3. The result of step 2 is piped forward with |> as the second argument of Seq.windowed 5. The result is the sequence of six arrays, each representing five sequentially taken digits of the result of step 2, each time shifting the beginning of the sequence to the right by one position.
4. The result of step 3 is piped forward with |> as the second argument of Seq.map (Seq.reduce (*)). The first argument is the higher-order function Seq.reduce converting its argument, which is an array of five numbers to the product of these numbers with the help of the multiplication operator ( * ). The result of this transformation step is just six numbers, each representing the product of the elements of the corresponding digit array.
5. The result of step 5 is piped into the Seq.max aggregate function, which produces the sought maximal product that equals 2520(7 * 3 * 6 * 4 * 5)w:

The incremental process of getting to the smaller problem solution with REPL

Now, after becoming pretty confident that the thought-out solution is good, I can combine the preceding steps 1 to 5 with just another F# function composition operator >>, which just glues the result of the function to the left as an argument of the function to the right into a very compact F# script provided in the file Ch1_3.fsx as follows:

#load "HugeNumber.fs" 
hugeNumber |> (Seq.map (string >> int) >> Seq.windowed 5 
>> Seq.map (Seq.reduce (*)) >> Seq.max 
>> printfn "%s %d" "Functional solution:") 

The only difference between the preceding complete problem solution code and the smaller problem solution that I was running through a few REPL steps is the input value dimension. The final code uses the same 1000 digit hugeNumber taken from the source file HugeNumber.fs in the same manner as the imperative and object-oriented solutions did previously.

Running the script in its entirety with FSI yields the functional solution result shown in the following figure:

Running the functional solution script in F# Interactive

The code quality achieved by the functional solution, despite somewhat lengthy accompanying comments, is quite outstanding:

• It does not utilize even a single value carrying an intermediate state
• It contains just one arithmetic multiplication operator absolutely needed for product calculation
• It is extremely succinct
• It almost literally reflects the original "what to do" considerations
• It uses solely half a dozen core F# library functions combined in a certain way, and we may strongly believe that the implementations of these functions are error-free and performant

The preceding bullet points reflect pretty much all the properties typical for an idiomatic functional solution of a small-scale problem. Now I'm going to decipher these properties one by one.