Skip to content

Project Euler Problem 1: Analysis and Generalization

September 28, 2011

Although being an utterly simple Project Euler Problem 1 can be considered a special case of a general class of problems sharing the same approach to the solution:

  1. Select a subsequence of members of some sequence
  2. Further, select members of this subsequence sharing some common property
  3. Finally, aggregate this selection

The solution may look like a higher-order function

solve:  selector -> filter -> aggregator  -> sequence 

that, when being applied to specific function arguments produces the sought solution. Below is an attempt to define such higher-order function that would allow solve a general form of Problem 1:

let solve (selector: 'a -> bool)
          (filter: 'a -> bool)
          (aggregator: seq -> 'a)
          (sequence: seq) =
    sequence
    |> Seq.takeWhile selector
    |> Seq.filter filter
    |> aggregator

This function would allow to solve Problem 1 when being called over specific selector, filter, and aggregator:

(Seq.initInfinite id)
|> solve ((>) 1000) (fun x -> x % 3 = 0 || x % 5 = 0) (Seq.sum)
|> printfn "Problem 1 Answer: %d"

The same higher-order function can deliver solution to another alike problem: “find the product of all numbers that are multiples of 11 and are less, than 100” just by appropriate changes to arguments:

(Seq.initInfinite id) |> Seq.skip 1 // first 0 will spoil aggregation
|> solve ((>) 100) (fun x -> x % 11 = 0) (Seq.reduce (*))
|> printfn "%d"

While progressing through Project Euler tasks we will be able to see how much problems this general solution would be applicable to.

Advertisements

From → Project Euler

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: