Saturday, May 29, 2010

Problem 28: What is the sum of the numbers on the diagonals in a 1001 by 1001 number spiral?

Another pleasant one where by writing down the first few terms of the sequence (by dimension) of sequences (corners in a dimension), it was easy to spot a recursive pattern based on the last element of the previous sequence.  The neatest part is how apt recursive sequence expressions are for capturing this algorithm.  For interest, I show my first-pass solution followed by a refactored version.

let problem28a =
    let diags upperdim =
        let rec diags dim prev =
            seq { let prev = (dim-1) + prev
                  yield prev
                  let prev = (dim-1) + prev
                  yield prev
                  let prev = (dim-1) + prev
                  yield prev
                  let prev = (dim-1) + prev
                  yield prev
                  if dim <> upperdim then 
                    yield! diags (dim+2) prev }
        diags 3 1
    (diags 1001 |> Seq.sum) + 1 //add center 1
                
let problem28b =
    let diags upperdim =
        let rec diags dim prev =
            seq { let next i = i*(dim-1) + prev
                  yield! {1..4} |> Seq.map next
                  if dim <> upperdim then 
                    yield! diags (dim+2) (next 4) }
        diags 3 1
    (diags 1001 |> Seq.sum) + 1 //add center 1

The next two versions use an infinite sequence which includes the center 1.  The later of the two takes advantage of the fact that it’s easy to count how many terms we need to sum.

let problem28c =
    let diags =
        let rec diags dim prev =
            seq { let next i = (dim, i*(dim-1) + prev)
                  yield! {1..4} |> Seq.map next
                  yield! diags (dim+2) (next 4 |> snd) }
        seq { yield (1,1) ; yield! diags 3 1 }
    diags |> Seq.takeWhile(fun (dim,_)  -> dim <= 1001) |> Seq.sumBy snd
    
let problem28d =
    let diags =
        let rec diags dim prev =
            seq { let next i = i*(dim-1) + prev
                  yield! {1..4} |> Seq.map next
                  yield! diags (dim+2) (next 4) }
        seq { yield 1 ; yield! diags 3 1 }
    diags |> Seq.take((4*500)+1) |> Seq.sum

No comments:

Post a Comment