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