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