Monday, April 13, 2009

Euler Problem 11 in F#

Just finished cleaning this, and I believe this to be my best work of F# to date.

This is my answer to Euler Problem 11.


let multiply sq =
let rec multiply sq x =
match sq with
[] -> x
_ -> multiply (List.tl sq) (x * (List.hd sq))
multiply sq 1

let getNS sq x y z =
Seq.nth x sq > Seq.nth (y + z)

let getEW sq x y z =
Seq.nth (x + z) sq > Seq.nth y

let getNWSE sq x y z =
Seq.nth (x + z) sq > Seq.nth (y + z)

let getNESW sq x y z =
Seq.nth (x + z) sq > Seq.nth (y - z)

let products sq length f minX maxX minY maxY =
let xAxis = [minX .. maxX]
let yAxis = [minY .. maxY]
let lengths = [0 .. length - 1]
let mapParameters s1 f = Seq.map (fun x -> f x) s1
mapParameters xAxis (f sq)
> Seq.map_concat (mapParameters yAxis)
> Seq.map (mapParameters lengths)
> Seq.map (fun x -> Seq.to_list x > multiply)

let f = products sequence 4

let ns = f getNS 0 19 0 16
let ew = f getEW 0 16 0 19
let nwse = f getNWSE 0 16 0 16
let nesw = f getNESW 0 16 3 16

let max = [ ns; ew; nwse; nesw ]
> Seq.concat
> Seq.max


Here's a brief description of what I've done.

First, the value "sequence" is of the type seq<#seq<int>>. It contains a sequence, which itself contains a sequence of every item in every row. The outer sequence is the row, where the inner sequence is the column. To create this, I literally copied the block of text from the Euler site, and pasted it into my program as a string. I then used the following code to convert it to this structure:


let sequence = 
let split (separator:string) (s:string) =
s.Split([| separator |], StringSplitOptions.None)
let sr = new StringReader(valuesfromwebsite)
sr.ReadToEnd()
|> split Environment.NewLine
|> Seq.map (split " ")
|> Seq.map (Seq.map (Int32.Parse))


multiply - Returns the product of every item in the int list passed in.
getNS, getEW, getNWSE and getNESW - Returns a sequence containing z values from sq starting at the coordinate x, y, and moving in the direction specified by the method name (NS is "north-south", while "getNESW" is "northeast-southwest", etc).
products - Returns a sequence of integer values which are the products of executing multiply returned from the specified function (f), across the entire grid (sq) starting and ending at the specified grid coordinates, within minX, maxX, minY and maxY.
f - A partially closed method specifying the first to arguments of "products"
ns, ew, nwse, nesw - The results of calling the get* methods on the grid.
max - The maximum value from ns, ew, nwse, and nesw.

I believe this proves that F# can be most succinct in many ways than C#. Here's the C# version on Bill Wagner's blog as a comparison.