Saturday, March 07, 2009
YAPES: Problem Eight

Welcome coding ninjas!1 Continuing with Yet Another Project Euler Series (YAPES™), we come upon problem eight.

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

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Being one of the earlier Project Euler problems, this is pretty trivial to solve. We’ll approach the problem by first breaking it into a set of simple steps:

  1. Transform the 1000-digit number into a list of digits.
  2. Transform the list of digits into a list of quintuplets—that is, a list containing tuples of each five consecutive elements.
  3. Transform the list of quintuplets into a list containing the product of each.
  4. Find the maximum element in the list.

Some or all of the steps above could be combined to produce a more optimal solution. However, the beauty of F#—and functional programming in general—is the ability to easily break a problem like this into a series of data transformations that run quickly enough for most situations. When a problem is broken down into simple operations, it is easier to optimize in other ways (e.g. parallelization).

The first step is to transform the 1000-digit number into a list of digits. To facilitate working with such a large number in code, we’ll represent it as a multi-line string. Like before, we’ll break the problem of converting a string into a list of digits into a set of simple steps:

  1. Transform the string into a list of chars.
  2. Because this was a multi-line string, some of the chars will be line breaks and whitespace. So, we’ll filter the list to include only the chars that represent digits.
  3. Transform the list of digit chars into a list containing the numerical value of each.

Let’s define a few library functions to to help with each step above.

module String =
  /// Takes a string and produces a list of chars.
  let toChars (s : string) =
    s.ToCharArray() |> Array.to_list

module Char =
  /// Determines whether a char represents a digit.
  let isDigit (c : char) =
    System.Char.IsDigit(c)

  /// Converts a char representing a digit into its numerical value.
  let toNumber (c : char) =
    int c - int '0'

Armed with these, we can perform the 3 steps above in a declarative fashion.

let number =
  "73167176531330624919225119674426574742355349194934
   96983520312774506326239578318016984801869478851843
   85861560789112949495459501737958331952853208805511
   12540698747158523863050715693290963295227443043557
   66896648950445244523161731856403098711121722383113
   62229893423380308135336276614282806444486645238749
   30358907296290491560440772390713810515859307960866
   70172427121883998797908792274921901699720888093776
   65727333001053367881220235421809751254540594752243
   52584907711670556013604839586446706324415722155397
   53697817977846174064955149290862569321978468622482
   83972241375657056057490261407972968652414535100474
   82166370484403199890008895243450658541227588666881
   16427171479924442928230863465674813919123162824586
   17866458359124566529476545682848912883142607690042
   24219022671055626321111109370544217506941658960408
   07198403850962455444362981230987879927244284909188
   84580156166097919133875499200524063689912560717606
   05886116467109405077541002256983155200055935729725
   71636269561882670428252483600823257530420752963450"
   |> String.toChars
   |> List.filter Char.isDigit
   |> List.map Char.toNumber

The next step is to transform the list of digits into a list of quintuplets. To achieve this, we’ll write a simple recursive function.

let rec toQuintuplets l =
  match l with
  | x1::(x2::x3::x4::x5::_ as t) -> (x1,x2,x3,x4,x5)::(toQuintuplets t)
  | _ -> []

Notice that the first pattern match above is slightly more complicated as we bind the list starting with the next element in the list to t, to make the recursion cleaner.

NeRd Note
The toQuintuplets function defined above will work well for this particular problem but will stack overflow if passed too large of a list because it is head-recursive. There are a couple of ways to make it tail-recursive and avoid blowing the stack, but the most elegant is to employ a continuation.
let toQuintuplets l =
  let rec loop l cont =
    match l with
    | x1::(x2::x3::x4::x5::_ as t) -> loop t (fun l –> cont ((x1,x2,x3,x4,x5)::l))
    | _ -> cont []

  loop l (fun x -> x)
Of course, that unnecessarily complicates this solution by turning the logic inside out!

The last function we’ll define is a small helper to produce the product of all of the values in a quintuplet.

let product (x1,x2,x3,x4,x5) = x1*x2*x3*x4*x5

All of the pieces are now in place, and the steps can be combined to solve Project Euler problem eight.

number
  |> toQuintuplets
  |> List.map product
  |> List.max

It’s that simple!

1Or pirates.

F# | Functional Programming | Project Euler
posted on Saturday, March 07, 2009 1:09:11 PM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on DotNetKicks.com
Related posts:
Empty Nothings
YAPES: Problem Ten
YAPES: Problem Nine
Dustin and Chris, Deep Fried
YAPES: Problem Seven, Part 2
Printf and Formatting Debug Output in F#
Sunday, March 08, 2009 5:51:52 AM (Pacific Standard Time, UTC-08:00)
Instead of "ToQuintuplets, I used "Seq.windowed" which does the same thing, something like:

let longNum = "731 ... 450".Replace("\n", "")
let charToNum x = int x - int '0'
let multiplyCharArray arr = arr |> Array.map charToNum |> Array.reduce_right (*)

longNum
|> Seq.to_list
|> Seq.windowed 5
|> Seq.map multiplyCharArray
|> Seq.max
Martin
Monday, March 30, 2009 8:27:20 PM (Pacific Standard Time, UTC-08:00)
Martin, once we go with using seq's instead of lists and the complexities of toQuintuplets, we can simplify even more because seq's are just a name for DotNet IEnumberable's and the original string has this interface:

let n = "73167...63450"
|> Seq.filter (System.Char.IsDigit)
|> Seq.map (fun c -> int(c) - int('0'))
|> Seq.windowed 5
|> Seq.map (Array.reduce_right (*))
|> Seq.max

Note that using IsDigit (as Dustin does) also eliminates the spaces (or tabs) which are in his original formulation of the multi-line string, that I didn't declare a separate toNumber function because this is an easily recognized method of converting characters to integers, and that I think any competent F# programmer would recognize the short form "reduce_right (*)" is just taking the product of the array window.

This solution is both elegant and efficient in that nothing gets done until the max function runs, which then passes through the string elements exactly once forming windows of only the numeric integers and checking the product of the window elements for maximum. It wouldn't be any more efficient writing this in C# and would certainly take a lot more source code. Embedding the charToNum conversion in the product function as you do, Martin, means that this conversion is done for every number as the product is formed instead of only being done once when the windowed function passes through forming the sliding windows, meaning you do the char conversion five times too many times. Seq can do this conversion without repeating because seq's automatically do memoization internally (using Seq.cache).

I really like using sequences rather than any form of recursion if it can be avoided (to Dustin ;)! The trouble with the Functional Programmer's mindset is that they first look for solutions using recursion as they are taught that unlike for imperative languages, as long as they do tail recursion there is no penalty and the code will be more concise. They then go through all kinds of hoops that make the code less readable to obtain the necessary tail recursion when it is necessary to prevent stack overflow or improve the performance of the code (see the above NeRd note). I'm glad to see that F# encourages the use of seq's, which in most cases can avoid the need for recursion, still produce very concise readable code, are likely more efficient as far as the compiler being able to optimize the code (already implemented as code loops), and avoid most of the requirements for lazy evaluations.

This is a great application for functional programming techniques and F#!
Gordon
Comments are closed.

Page rendered at Thursday, September 02, 2010 2:49:12 PM (Pacific Standard Time, UTC-08:00)

msn cams