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

"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

View 6 previous comments

- yeah, that code I wrote was intended to find the maximum pathSep 16, 2012
- Haskell version: https://gist.github.com/3731333Sep 16, 2012
- 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.Sep 16, 2012
- 7 lines in python (although I tried to make it cryptic) http://pastebin.com/uTBEhVr7Sep 16, 2012
- 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.Sep 16, 2012 - +Matthias Ernst On the plus side, the Go code above is probably the most readable of them all, imo.Sep 16, 2012