Project Euler in F#: Problem 14

The following iterative sequence is defined for the set of positive integers:

n_i = n_{i-1}/2 (n even)
n_i = 3n_{i-1} + 1 (n odd)

Which starting number, under one million, produces the longest chain?

module Problem14 =
    let (|Even|Odd|) n =
        if n % 2L = 0L then Even
        else Odd

    let nextCollatz n =
        match n with
        | 1L -> 1L
        | Even -> n/2L
        | Odd -> (3L*n) + 1L

    let collatz =
        let cache = new System.Collections.Generic.Dictionary<_,_>()
        let rec cachedCollatz n =
            match cache.TryGetValue(n),n with
            | (true,v),_ -> v
            | (_),1L ->  1
            | _ -> let v = 1 + cachedCollatz (nextCollatz n)
                   cache.Add(n,v)
                   v
        fun n -> cachedCollatz n

    let ans = {1L..1000000L} |> Seq.map (fun n -> (n,collatz n)) |> Seq.maxBy snd |> fst

The obvious brute-force solution is actually fast enough, but this problem just screams DP / memoization, and I wanted to see how memoizing something in F# would work, so I played around with memoization for this problem.

Additionally, I (pointlessly) used an active pattern here, because I’d just read about them in Programming F# and wanted to see how they work. I could definitely see how active patterns would be helpful for more complicated problems; it seems weird to me that there’s a limit of seven cases for an active pattern, though.

Advertisements
Project Euler in F#: Problem 14

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