{"id":614,"date":"2008-12-08T12:23:37","date_gmt":"2008-12-08T11:23:37","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/12\/08\/project-euler-in-fsharp-problem-53\/"},"modified":"2009-01-13T09:01:17","modified_gmt":"2009-01-13T08:01:17","slug":"project-euler-in-fsharp-problem-53","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/12\/08\/project-euler-in-fsharp-problem-53\/","title":{"rendered":"Project Euler in F# – Problem 53 – Dynamic Programming"},"content":{"rendered":"

Claudio Cherubino (from fsharp.it\/<\/a>) posted his solution<\/a> to Euler Project – problem 53<\/a>. As I dealed a lot with Dynamic Programming<\/a> in the recent time, I tried to solve the problem with a dynamic program in F#.<\/p>\n

<\/strong><\/p>\n

Project Euler – Problem 53:<\/a><\/p>\n

How many values of C(n<\/em>,k<\/em>), for 1 \u2264 n<\/em> \u2264 100, exceed one-million?<\/p>\n

Remark: C(n,k) are the binomial coefficients.<\/p><\/blockquote>\n

As it turned out, this is not that complicated if one knows the recursive function for the binomial coefficients (see Wikipedia<\/a>):<\/p>\n

\"Recursive with \"Recursive<\/p>\n

This is easily transformed into a F# program:<\/p>\n

let <\/span>binomials = Array2.create 101 101 1I\r\nlet <\/span>answer = ref 0\r\nfor <\/span>n in <\/span>[1..100] do\r\n  for <\/span>k in <\/span>[1..n - 1] do\r\n    <\/span>binomials.[n, k] <- binomials.[n - 1,k] + binomials.[n - 1,k - 1]\r\n    if <\/span>binomials.[n, k] > 1000000I then\r\n      <\/span>answer := !answer + 1\r\n\r\n!answer |> printf \"Answer: %A\"<\/span><\/pre>\n
Claudio’s program took 1315ms on my computer. The dynamic program needs only 63ms. But we can still do better if we use the symmetry of Pascal’s triangle<\/a>.<\/p>\n
\"Symmetry<\/p>\n
This leads to an algorithm, which calculates only half of the binomial coefficients.<\/p>\n
let <\/span>binomials = Array2.create 101 101 1I\r\nlet <\/span>answer = ref 0\r\nfor <\/span>n in <\/span>[1..100] do\r\n  for <\/span>k in <\/span>[1..n\/2] do\r\n    let <\/span>b = binomials.[n - 1,k] + binomials.[n - 1,k - 1]\r\n    binomials.[n, k] <- b\r\n    binomials.[n, n - k] <- b\r\n    if <\/span>b > 1000000I then\r\n      if <\/span>k = n-k then\r\n        <\/span>answer := !answer + 1\r\n      else\r\n        <\/span>answer := !answer + 2<\/pre>\n
!answer |> printf \"Answer: %A\"<\/span><\/pre>\n
This version needs only 45ms – but we are not ready. I mentioned Pascal’s triangle and its symmetry. But we can use another property. We don’t have to calculate the complete row, if we exceed 100000. All values behind this threshold have to be greater.<\/p>\n
let <\/span>binomials = Array2.create 101 101 1I\r\nlet <\/span>answer = ref 0\r\nfor <\/span>n in <\/span>[1..100] do\r\n  let <\/span>threshold_reached = ref false\r\n  let <\/span>c = ref 0\r\n  for <\/span>k in <\/span>[1..n\/2] do\r\n    if <\/span>not !threshold_reached then\r\n      let <\/span>b = binomials.[n - 1,k] + binomials.[n - 1,k - 1]\r\n      binomials.[n, k] <- b\r\n      binomials.[n, n - k] <- b\r\n      if <\/span>b > 1000000I then\r\n        <\/span>threshold_reached := true\r\n      else\r\n        <\/span>c := !c + 1\r\n\r\n  if <\/span>!threshold_reached then\r\n    <\/span>answer := !answer + (n - 1) - (2 * !c)<\/pre>\n
!answer |> printf \"Answer: %A\"<\/span><\/pre>\n
This final version took only 29 ms.<\/p>\n
In the next posting<\/a> I will show a version using memoization.<\/p>\n","protected":false},"excerpt":{"rendered":"
Claudio Cherubino (from fsharp.it\/) posted his solution to Euler Project – problem 53. As I dealed a lot with Dynamic Programming in the recent time, I tried to solve the problem with a dynamic program in F#. Project Euler – Problem 53: How many values of C(n,k), for 1 \u2264 n \u2264 100, exceed one-million? […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[23,448,10],"tags":[488,485,664,487,486],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/614"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=614"}],"version-history":[{"count":6,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/614\/revisions"}],"predecessor-version":[{"id":661,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/614\/revisions\/661"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=614"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=614"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=614"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}