My answer in Clojure: https://gist.github.com/3730531

### DeWitt Clinton

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

"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

12 comments

Interesting, I'll give it a whack Sunday night

Usually I use python but thought i'd give javascript a go: (spoiler alert) http://pastebin.com/EeGua55c

Travis Owens

+

3

4

3

4

3

must... not... click... other's... code....

DeWitt Clinton

+

1

2

1

2

1

+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.

+Robert King Shouldn't that be Math.min?

yeah, that code I wrote was intended to find the maximum path

Mark Lentczner

+

1

2

1

2

1

Haskell version: https://gist.github.com/3731333

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.

Robert King

+

1

2

1

2

1

7 lines in python (although I tried to make it cryptic) http://pastebin.com/uTBEhVr7

Matthias Ernst

+

1

2

1

2

1

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.

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.

+Matthias Ernst On the plus side, the Go code above is probably the most readable of them all, imo.

Add a comment...