Shared publicly  - 
 
A fun programming problem from 4clojure:

"Write a function which calculates the sum of the minimal path through a triangle. The triangle is represented as a collection of vectors. The path should start at the top of the triangle and move to an adjacent number on the next row until the bottom of the triangle is reached."

  (= 7 (__  '([1]
          [2 4]
         [5 1 4]
        [2 3 4 5]))) ; 1->2->1->3

Note that this effectively the same as Project Euler #67 [2], and can be answered efficiently in any language, though it took me a bit of head scratching before getting it.

My own answer linked in the comments (don't click unless you want a spoiler). Feel free to discuss your ideas and techniques below.

[1] http://www.4clojure.com/problem/79
[2] http://projecteuler.net/problem=67
6
Robert King's profile photoMatthias Ernst's profile photoJohn A. Tamplin's profile photoMark Lentczner's profile photo
12 comments
 
Interesting, I'll give it a whack Sunday night
 
must... not... click... other's... code....
 
+Robert King Right on.  I took the same approach.  Interesting to see the difference in how that algorithm is implemented in a functional/immutable vs. an imperative/mutable language.
 
yeah, that code I wrote was intended to find the maximum path
 
That's great, thanks, +Mark Lentczner!  Was hoping someone would write a Haskell implementation of that, as I suspected it would be the most succinct of them all. Didn't let me down at all.
 
Go: http://play.golang.org/p/l_2LYRAgLe:

func MinCost(triangle [][]float64) float64 {
  levels := len(triangle)
  best := make([]float64, levels+1)
  for i := range triangle {
    for j, value := range triangle[levels-i-1] {
      best[j] = math.Min(best[j], best[j+1]) + value
    }
  }
  return best[0]
}

IMHO succinctness in Go suffers from it being rather imperative (e.g. to copy a slice, you have to allocate, copy, use allocated. And there's no if-else/?: expression.). And it being non-generic you can't even create things like CopyOf or Reverse once and for all -- or even Min which is why I resorted to float64 here.
Add a comment...