Below is a Go solution to the problem 81 in project euler 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. 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
}
