Thursday, September 5, 2013

How to Solve Triangle Minimal Path in Go

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.
assert
f(  [[1]
    [2 4]
   [5 1 4]
  [2 3 4 5]] ) == 7 ; 1+2+1+3

assert
f(    [[3]
      [2 4]
     [1 9 3]
    [9 9 2 4]
   [4 6 6 7 8]
  [5 7 3 5 1 4]] ) == 20 ; 3+4+3+2+7+1
This is an iterative solution in Go.
package main

import (
    "fmt"
)

func min(m map[int][]int) int {
    r := m[0][0]
    for _, v := range m {
        for _, v1 := range v {
            if r > v1 {
                r = v1
            }
        }
    }
    return r
}

func triangleMinPath(input [][]int) int {
    result := map[int][]int{}
    result[0] = input[0]
    for i := 1; i < len(input); i++ {
        result = minPath(input[i], result)
    }
    return min(result)
}

func minPath(input []int, accu map[int][]int) map[int][]int {
    result := map[int][]int{}
    for i := 0; i < len(input); i++ {
        for j := 0; j < len(accu[i]); j++ {
            if _, ok := result[i]; !ok {
                result[i] = []int{}
            }
            result[i] = append(result[i], input[i]+accu[i][j])
            if _, ok := result[i+1]; !ok {
                result[i+1] = []int{}
            }
            result[i+1] = append(result[i+1], input[i+1]+accu[i][j])
        }
    }
    return result
}

func main() {
    fmt.Println(triangleMinPath([][]int{{1}, {2, 4}, {5, 1, 4}, {2, 3, 4, 5}})) // 7
    fmt.Println(triangleMinPath([][]int{{3}, {2, 4}, {1, 9, 3}, {9, 9, 2, 4}, {4, 6, 6, 7, 8}, {5, 7, 3, 5, 1, 4}})) // 20
    fmt.Println(triangleMinPath([][]int{{3}})) // 3
    fmt.Println(triangleMinPath([][]int{{3}, {1, 2}})) // 4
}