Golang solution to Project Euler #81 (min path through a matrix)

Question

Project Euler problem 81 asks:

In the 5 by 5 matrix below,

131   673 234 103 18
201   96  342 965 150
630   803 746 422 111
537   699 497 121 956
805   732 524 37  331

the minimal path sum from the top left to the bottom right, by only moving to the right and down, is

131 → 201 → 96 → 342 → 746 → 422 → 121 → 37 → 331

and is equal to 2427.

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Below is a Go solution using uniform-cost search to build a search tree. It works on the toy small problem but on the 80x80 matrix it runs out of space. Could anyone that is up for a challenge help improve this still using this solution? By the way, this is the first program of any consequence I have written in Go and I am try to learn the language.

package main

import (
    "bufio"
    "container/heap"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

var matrix [][]int = make([][]int, 0, 80)

func main() {
    f, _ := os.Open("matrix.txt")
    r := bufio.NewReader(f)
    defer f.Close()
    for {

        s, ok := r.ReadString('\n')
        if ok == io.EOF {
            break
        }
        s = strings.Trim(s, "\n")
        stringArr := strings.Split(s, ",")
        tmp := make([]int, 0)
        for i := 0; i < 80; i++ {
            v, _ := strconv.Atoi(stringArr[i])
            tmp = append(tmp, v)
        }
        matrix = append(matrix, tmp)
    }
    //fmt.Println(matrix)
    fmt.Println(uniformCostSearch(treeNode{0, 0, 4445, 0}))
}

func (node treeNode) getPriority(y, x int) int {
    return matrix[y][x]
}

type Node interface {
    // Neighbors returns a slice of vertices that are adjacent to v.
    Neighbors(v Node) []Node
}

// An treeNode is something we manage in a priority queue.
type treeNode struct {
    X        int
    Y        int
    priority int // The priority of the item in the queue.
    Index    int // The index of the item in the heap.
}

func (node treeNode) Neighbors() []*treeNode {
    tmp := []*treeNode{ //&treeNode{X: node.X - 1, Y: node.Y},
        &treeNode{X: node.X + 1, Y: node.Y},
        //&treeNode{X: node.X, Y: node.Y - 1},
        &treeNode{X: node.X, Y: node.Y + 1}}
    childNodes := make([]*treeNode, 0)
    for _, n := range tmp {
        if n.X >= 0 && n.Y >= 0 && n.X <= 80 && n.Y <= 80 {
            n.priority = node.priority + n.getPriority(n.Y, n.X)
            childNodes = append(childNodes, n)
        }
    }
    return childNodes
}

func uniformCostSearch(startNode treeNode) int {
    frontier := make(PriorityQueue, 0, 10000)
    closedSet := make([]*treeNode, 0)
    heap.Push(&frontier, &startNode)
    for frontier.Len() > 0 {
        fmt.Println(frontier.Len())
        currentNode := heap.Pop(&frontier).(*treeNode)
        if currentNode.X == 79 && currentNode.Y == 79 {
            return currentNode.priority
        } else {
            closedSet = append(closedSet, currentNode)
        }
        possibleMoves := currentNode.Neighbors()
        for _, move := range possibleMoves {
            explored := false
            for _, seen := range closedSet {
                if seen.X == move.X && seen.Y == move.Y {
                    explored = true
                    break
                }
            }
            if explored {
                continue
            }
            // check that frontier does not contain this node and 
            // if it does then compare the cost so far
            for index, node := range frontier {
                if node.X == move.X && node.Y == move.Y && move.priority < node.priority {
                    fmt.Println("removing")
                    heap.Remove(&frontier, index)
                    break
                }
            }
            heap.Push(&frontier, move)
        }
    }
    return -1
}

// A PriorityQueue implements heap.Interface and holds treeNodes.
type PriorityQueue []*treeNode

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the lowest priority so we use greater than here.
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].Index = i
    pq[j].Index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    // To simplify indexing expressions in these methods, we save a copy of the
    // slice object. We could instead write (*pq)[i].
    a := *pq
    n := len(a)
    a = a[0 : n+1]
    item := x.(*treeNode)
    item.Index = n
    a[n] = item
    *pq = a
}

func (pq *PriorityQueue) Pop() interface{} {
    a := *pq
    n := len(a)
    item := a[n-1]
    item.Index = -1 // for safety
    *pq = a[0 : n-1]
    return item
}

Answer 1

Your code could be less fragile and more idiomatic. For example,

package main

import (
    "bufio"
    "container/heap"
    "errors"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

type Matrix [][]int

type Node struct {
    x, y int
}

type Item struct {
    value    Node
    priority int
    index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    a := *pq
    n := len(a)
    item := x.(*Item)
    item.index = n
    a = append(a, item)
    *pq = a
}

func (pq *PriorityQueue) Pop() interface{} {
    a := *pq
    n := len(a)
    item := a[n-1]
    item.index = -1
    *pq = a[0 : n-1]
    return item
}

func (pq *PriorityQueue) changePriority(item *Item, priority int) {
    heap.Remove(pq, item.index)
    item.priority = priority
    heap.Push(pq, item)
}

func readMatrix() (Matrix, error) {
    var matrix Matrix
    file, err := os.Open(`matrix.txt`)
    if err != nil {
        return nil, err
    }
    defer file.Close()
    rdr := bufio.NewReader(file)
    for {
        line, err := rdr.ReadString('\n')
        if err != nil {
            if err == io.EOF && len(line) == 0 {
                break
            }
            return nil, err
        }
        var row []int
        for _, s := range strings.Split(line[:len(line)-1], ",") {
            n, err := strconv.Atoi(s)
            if err != nil {
                return nil, err
            }
            row = append(row, n)
        }
        matrix = append(matrix, row)
    }
    return matrix, nil
}

func (i Item) neighbors(matrix Matrix) []*Item {
    items := make([]*Item, 0, 2)
    x, y, p := i.value.x, i.value.y, i.priority
    if x := x + 1; x < len(matrix[y]) {
        items = append(items, &Item{value: Node{x, y}, priority: p + matrix[y][x]})
    }
    if y := y + 1; y < len(matrix) {
        items = append(items, &Item{value: Node{x, y}, priority: p + matrix[y][x]})
    }
    return items
}

func UniformCostSearch(matrix Matrix) (int, error) {
    if len(matrix) < 0 || len(matrix[0]) < 0 {
        return 0, errors.New("UniformCostSearch: invalid root")
    }
    root := Item{value: Node{0, 0}, priority: matrix[0][0]}
    if len(matrix) < 0 || len(matrix[len(matrix)-1]) < 0 {
        return 0, errors.New("UniformCostSearch: invalid goal")
    }
    goal := Node{len(matrix[len(matrix)-1]) - 1, len(matrix) - 1}
    frontier := make(PriorityQueue, 0, len(matrix)*len(matrix[len(matrix)-1]))
    heap.Push(&frontier, &root)
    explored := make(map[Node]bool)
    for {
        if len(frontier) == 0 {
            return 0, errors.New("UniformCostSearch: frontier is empty")
        }
        item := heap.Pop(&frontier).(*Item)
        if item.value == goal {
            return item.priority, nil
        }
        explored[item.value] = true
    neighbor:
        for _, n := range item.neighbors(matrix) {
            if explored[n.value] {
                continue neighbor
            }
            for _, f := range frontier {
                if f.value == n.value {
                    if f.priority > n.priority {
                        frontier.changePriority(f, n.priority)
                    }
                    continue neighbor
                }
            }
            heap.Push(&frontier, n)
        }
    }
    return 0, errors.New("UniformCostSearch: unreachable")
}

func main() {
    matrix, err := readMatrix()
    if err != nil {
        fmt.Println(err)
        os.Exit(1)
    }
    minPathSum, err := UniformCostSearch(matrix)
    if err != nil {
        fmt.Println(err)
        os.Exit(1)
    }
    fmt.Println(minPathSum)
}

Answer 2

The uniform-cost search, an algorithm based on graph theory, is unnecessarily complex for this problem. You should be able to use a dynamic programming algorithm instead, which requires just a matrix for storage.

Consider how you can reduce the problem to a base case. Let's take the 5×5 example in the question, and consider just the bottom-right 2×2 submatrix:

 121  956
  37  331

Starting at 331, the minimal path to the bottom-right is 331. Starting at 37, the minimum distance is 37 + 331 = 368, because you must go right. Starting at 956, the minimum distance is 956 + 331 = 1287, because you must go down. Starting at 121, what do you do? Since 368 < 1287, it's cheaper to go down and join the 37 → 331 path, for a distance of 489. Let's store all of that information as a matrix, where each element is the minimum distance from that element to the bottom-right corner:

 489 1287
 368  331

Expanding that matrix to 2×5 for the bottom two rows:

2222 1685  986  489 1287
2429 1624  892  368  331

Continuing all the way,

2427 2576 1903 1669 1566
2296 2095 1999 1876 1548
2852 2460 1657  911 1398
2222 1685  986  489 1287
2429 1624  892  368  331

Simply read out the answer from the top-left, which is 2427.

For an input matrix of dimensions m × n, the memory required is m × n. Each element can be filled in O(1) time ("Is it cheaper to go right or go down?") for a total running time of O(m × n). Any computer should be able to fill an 80 × 80 matrix effortlessly. (The only concern might be overflow, but it turns out that the answer fits comfortably within 31 bits.)