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)
}

• Quentin Pradet: Thanks you for this answer, but it would have been nice to explain the main changes that you did: it avoids the need to compare the two versions and trying to figure out the reasons of the changes.

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 example in the question, and consider just the bottom-right ×ばつ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 ×ばつ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.)