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

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")
defer f.Close()
for {

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
}


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

var matrix Matrix
file, err := os.Open(matrix.txt)
if err != nil {
return nil, err
}
defer file.Close()
for {
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 {
return 0, errors.New("UniformCostSearch: invalid root")
}
root := Item{value: Node{0, 0}, priority: matrix}
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() {
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)
}

• 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. – Quentin Pradet Feb 12 '13 at 8:44

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