Traveling salesman in go

salesman.go

package main

import (
	"bufio"
	"fmt"
	"math"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"time"
)

type Location struct {
	X  float64
	Y  float64
	ID int
}

func NewLocation(id int, x, y string) Location {
	xi, _ := strconv.Atoi(x)
	yi, _ := strconv.Atoi(y)
	return Location{ID: id, X: float64(xi), Y: float64(yi)}
}

func readLines(path string) ([]Location, error) {
	file, err := os.Open(path)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	locations := []Location{}
	scanner := bufio.NewScanner(file)
	id := 0
	for scanner.Scan() {
		coordinates := strings.Split(scanner.Text(), " ")
		locations = append(locations, NewLocation(id, coordinates[0], coordinates[1]))
		id++
	}
	return locations, scanner.Err()
}

func distance(source, dest Location) int {
	return int(math.Sqrt(math.Pow(source.X-dest.X, 2) + math.Pow(source.Y-dest.Y, 2)))
}

func totalDistance(locations []Location) int {
	total := 0
	source := locations[0]
	for _, dest := range locations[1:] {
		total += distance(source, dest)
		source = dest
	}
	return total
}

func optimize(locations []Location) ([]Location, int) {
	bound := len(locations)
	first, second := rand.Intn(bound), rand.Intn(bound)
	if first > second {
		first, second = second, first
	}

	firstEl := locations[first]
	secondEl := locations[second]

	swapped := []Location{}
	for idx, el := range locations {
		if idx == first {
			swapped = append(swapped, secondEl)
		} else if idx == second {
			swapped = append(swapped, firstEl)
		} else {
			swapped = append(swapped, el)
		}
	}

	bestDistance, newDistance := totalDistance(locations), totalDistance(swapped)
	if newDistance < bestDistance {
		locations = swapped
		bestDistance = newDistance
	}
	return locations, bestDistance
}

func optimizeForXSeconds(locations []Location, seconds int) []Location {
  rand.Seed(time.Now().UnixNano())
	timeChan := time.NewTimer(time.Second * time.Duration(seconds)).C
	dist, newDist, noprogress := 0, 0, 0

	for {
		select {
		case <-timeChan:
			return locations
		default:
			locations, newDist = optimize(locations)
		}

		if dist == newDist {
			noprogress++
			if noprogress > 10000 {
				return locations
			}
		} else {
			noprogress = 0
			dist = newDist
		}
	}
	return locations
}

func main() {
	if len(os.Args) != 2 {
		fmt.Println("Usage:", os.Args[0], "path/to/file")
		return
	}
	locations, _ := readLines(os.Args[1])
	locations = append(locations, locations[0])

	final := optimizeForXSeconds(locations, 1)

	fmt.Println("RESULTS")
	fmt.Println(totalDistance(final))
	fmt.Println(final)
}

test.txt

  0   0
689 291
801 724
388 143
143 832
485 484
627 231
610 311
549 990
220  28
 66 496
693 988
597 372
753 222
885 639
897 594
482 635
379 490
923 781
352 867
834 713
133 344
835 949
667 695
956 850
535 170
583 406