Project Euler — Problem 8 Solution

Problem

Find the great­est prod­uct of five con­sec­u­tive dig­its in the 1000-dig­it num­ber.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Solution

open System.IO

let numbers =
    File.ReadAllLines(@"C:\TEMP\euler8.txt")
    |> Seq.concat
    |> Seq.map (fun c -> int32(c.ToString()))

let CalcProduct numbers = numbers |> Seq.fold (fun acc n -> acc * n) 1

let maxProduct =
    numbers
    |> Seq.windowed(5)
    |> Seq.map (fun n -> CalcProduct n)
    |> Seq.max

To get the 1000 dig­its into the pro­gram, I copied and past­ed the dig­its into a text file and saved it to C:\TEMP\euler8.txt.

Here you see an exam­ple of how you can use the File.ReadAllLines sta­t­ic method to read the con­tents of a text into a string array in F#. How­ev­er, a string array doesn’t real­ly help us here, so I used the Seq.concat func­tion to merge them into a char array because map­ping each char into the inte­ger it rep­re­sents.

Two things to note here:

1) why does Seq.concat return a char array as opposed to a string?

Because a string can be treat­ed as a char[] in the same way that a Dictionary<T, V> can be treat­ed as an IEnumerable<KeyValuePair<T, V> > and iter­at­ed as such when passed into a method which takes a IEnumerable<KeyValuePair<T, V> > as argu­ment.

Look­ing at the sig­na­ture of the Seq.concat func­tion, it takes a seq<‘T list> (a sequence of lists of T, i.e. IEnumerable<IEnumerable<T> >) as argu­ment and there­fore the string[] is inter­pret­ed as IEnumerable<IEnumerable<char> > and con­cate­nat­ed into IEnumerable<char>.

The same is applied to all the List/Array/Seq func­tions when used on a string.

2) why is ToString() need­ed when cast­ing a char to int32?

Because int32(char) will give you the uni­code val­ue of that char! For exam­ple,

int32('c') // this is legal and returns 99
int32("c") // this is illegal
int32('1') // this returns 49
int32("1") // this returns 1

Mov­ing on, the next line defines a helper func­tion which takes a list of num­bers and mul­ti­ply them togeth­er, i.e [x; y; z] => x * y * z. I have done this with the Seq.fold func­tion which applies a func­tion to each ele­ment of the list whilst keep­ing an accu­mu­la­tor through­out, sim­i­lar to the Enumerable.Aggregate method in Linq. In this par­tic­u­lar case, the accu­mu­la­tor starts off at 1, and iter­a­tive­ly mul­ti­plied by the ele­ments in the list:

let CalcProduct numbers = numbers |> Seq.fold (fun acc n -> acc * n) 1

It’s worth not­ing that this func­tion will return 1 if used on an emp­ty array which is not the cor­rect behav­iour, but for the pur­pose of solv­ing the prob­lem at hand it can be safe­ly assumed that this will nev­er hap­pen.

Final­ly, in the last part of the solu­tion, you will notice yet anoth­er new func­tion Seq.windowed, which iter­ates through the ele­ments in the list yield­ing a slid­ing win­dows of 5 ele­ments:

numbers |> Seq.windowed(5);;

val it : seq<int32 &#91;&#93;> =
seq
  [[|7; 3; 1; 6; 7|]; [|3; 1; 6; 7; 1|]; [|1; 6; 7; 1; 7|];
   [|6; 7; 1; 7; 6|]; ...]

I then cal­cu­late the prod­uct for each of the 5 dig­it arrays and find the great­est prod­uct:

    |> Seq.map (fun n -> CalcProduct n)
    |> Seq.max