Hi!
I am new to Go and has been using PHP for a while. I have a work-related problem where I need to find the shortest way between coordinates. So I found a code in PHP that I could use, up to 9 nodes before it took too long to calculate the distances.
Another guy gave me Go code that could solve my problem, but I don’t really know how to use it.
I need the .csv file as a 2d matrix and help to get the argument passed into the code so I can just create the .csv file with PHP and use the algorithm.
I also don’t get the Visual Studio Code, does it compile Go code or is it like PHP? Because when I press F5 (start debugging) it doesn’t bring me any result with this code. Is it because the code doesn’t run properly or do I handle Visual Studio Code wrong?
package main
import (
"bytes"
"encoding/csv"
"fmt"
"io"
"log"
"math/bits"
"math/rand"
"os"
"runtime"
"strconv"
"strings"
"time"
)
const MaxInt = int(^uint(0) >> 1)
// IntSet
type IntSet struct {
Storage uint
}
func (vs IntSet) Contains(value int) bool {
return (vs.Storage & (1 << uint(value))) != 0
}
func (vs IntSet) Count() int {
return bits.OnesCount(vs.Storage)
}
func (vs *IntSet) Insert(value int) {
vs.Storage |= 1 << uint(value)
}
func (vs *IntSet) Remove(value int) {
vs.Storage &= ^(1 << uint(value))
}
func (vs IntSet) Value() int {
return int(vs.Storage >> 1)
}
func (vs IntSet) Iter() []int {
n := vs.Count()
v := make([]int, n)
for c, i := 0, 0; c < n; i++ {
if vs.Contains(i) {
v[c] = i
c++
}
}
return v
}
func (vs IntSet) String() string {
buf := bytes.Buffer{}
buf.WriteString("{")
delim := ""
for c, i := 0, 0; c < vs.Count(); i++ {
if vs.Contains(i) {
buf.WriteString(fmt.Sprintf("%s%v", delim, i))
delim = ","
c++
}
}
buf.WriteString("}")
return buf.String()
}
// Combinations 'k' integers from a serie '1..n'
type Combs []IntSet
func combWithLen(n, k, first int, vs IntSet, acc Combs) Combs {
if k > vs.Count() {
for x := first; x <= n; x++ {
s := vs
s.Insert(x)
acc = combWithLen(n, k, x+1, s, acc)
}
} else {
acc = append(acc, vs)
}
return acc
}
func Comb(n, k int) Combs {
return combWithLen(n, k, 1, IntSet{}, Combs{})
}
// Held Karp
type Path struct {
Cost int
From int
}
func minPath(paths []Path) Path {
m := paths[0]
for i := 1; i < len(paths); i++ {
if m.Cost > paths[i].Cost {
m = paths[i]
}
}
return m
}
func pathFromTo(from, to int, c [][]Path, dists CostMatrix, prev IntSet) Path {
p := Path{}
p.Cost = c[prev.Value()][from-1].Cost + dists[from][to]
p.From = from
return p
}
func reverse(a []int) []int {
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
return a
}
// CostMatrix
type CostMatrix [][]int
func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) {
maxWorkers := runtime.NumCPU()
workers := 0
done := make(chan bool)
for _, visited := range Comb(edges, subsetSz) {
if workers == maxWorkers {
<-done
} else {
workers += 1
}
go func(vs IntSet) {
subset := vs.Iter()
// Find the lowest cost to get to this subset
for _, k := range subset {
prev := vs
prev.Remove(k)
res := []Path{}
for _, m := range subset {
if m != k {
res = append(res, pathFromTo(m, k, c, dists, prev))
}
}
if len(res) > 0 {
c[vs.Value()][k-1] = minPath(res)
}
}
done <- true
}(visited)
}
// Wait for all workers to finish
for ; workers > 0; workers -= 1 {
<-done
}
}
func (dists CostMatrix) ShortestPath() (int, []int) {
n := len(dists)
c := make([][]Path, 1<<uint(n-1))
for i := 0; i < len(c); i++ {
c[i] = make([]Path, n-1)
}
// Add paths from start to first steps
for k := 1; k < n; k++ {
c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0}
}
for s := 2; s < n; s++ {
dists.CalcCostToSubsets(c, n-1, s)
}
visited := IntSet{}
for k := 1; k < n; k++ {
visited.Insert(k)
}
// Add path back to start and calculate optimal cost
res := []Path{}
for k := 1; k < n; k++ {
res = append(res, pathFromTo(k, 0, c, dists, visited))
}
p := minPath(res)
cost := p.Cost
// Backtrack to find path
steps := make([]int, n+1)
for i := 1; i < n; i++ {
steps[i] = p.From
from := p.From
p = c[visited.Value()][p.From-1]
visited.Remove(from)
}
return cost, reverse(steps)
}
func (c CostMatrix) MaxDigitWidth() (width int) {
for row := 0; row < len(c); row++ {
for col := 0; col < len(c[row]); col++ {
w := 0
for d := c[row][col]; d > 0; d /= 10 {
w += 1
}
if width < w {
width = w
}
}
}
return
}
func (c CostMatrix) String() string {
fmtstr := fmt.Sprintf("%%%vv", c.MaxDigitWidth())
buf := bytes.Buffer{}
for row := 0; row < len(c); row++ {
if row == 0 {
buf.WriteString("{\n")
}
buf.WriteString(" { ")
for col := 0; col < len(c[row]); col++ {
buf.WriteString(fmt.Sprintf(fmtstr, c[row][col]))
if col != len(c[row])-1 {
buf.WriteString(", ")
}
}
buf.WriteString(" },\n")
if row == len(c)-1 {
buf.WriteString("}")
} else {
}
}
return buf.String()
}
func Abs(n int) int {
if n < 0 {
return -n
}
return n
}
func Max(a, b int) int {
if a < b {
return b
}
return a
}
type Location struct {
shelf int
level int
}
func cost(from, to Location) int {
dx := Abs(from.shelf - to.shelf)
dy := Abs(from.level-to.level) * 2
return Max(dx, dy)
}
func zeroMatrix(dim int) CostMatrix {
var c CostMatrix = make([][]int, dim)
for i := range c {
c[i] = make([]int, dim)
}
return c
}
func genMatrix(nodes, depth, height int) CostMatrix {
rand.Seed(time.Now().UnixNano())
c := zeroMatrix(nodes)
l := make([]Location, nodes)
for i := range l {
l[i] = Location{rand.Intn(depth), rand.Intn(height)}
}
for row := 0; row < nodes; row++ {
for col := row + 1; col < nodes; col++ {
c[row][col] = cost(l[row], l[col])
c[col][row] = c[row][col]
}
}
return c
}
func readMatrix(r io.Reader) CostMatrix {
cr := csv.NewReader(r)
rec, err := cr.ReadAll()
if err != nil {
log.Fatalln(err)
}
M := zeroMatrix(len(rec))
for row, line := range rec {
for col, str := range line {
v, err := strconv.ParseInt(strings.TrimSpace(str), 10, 32)
if err != nil {
log.Fatalln(err)
}
M[row][col] = int(v)
}
}
return M
}
func GetCostMatrix() CostMatrix {
if len(os.Args) == 1 {
return readMatrix(os.Stdin)
}
arg := os.Args[1]
if strings.HasSuffix(arg, ".csv") {
file, err := os.Open(arg)
if err != nil {
log.Fatalln(err)
}
return readMatrix(file)
}
dim, err := strconv.ParseInt(arg, 10, 32)
if err != nil {
log.Fatalln(err)
}
return genMatrix(int(dim), 50, 9)
}
// Program entrypoint
func main() {
c := GetCostMatrix()
fmt.Println(c)
fmt.Println(c.ShortestPath())
}