- write gRPC service
- find the optimal route (given an initial city and a lsit of cities to visit)
refer Makefile for more information
run server
make serverrun client
make clientIn the task, there was not any time limit for the server response & requirement for an algorithm. For this reason, I have solved the problem by creating own custom algorithm. The solution (brute force solution) considers all possible routes with a little optimization.
The time complexity is O(n!). However, as there are only 17 cities, I think it is not a big problem.
Regarding the Yandex Map & Google Map. I played around with Yandex Map API (Яндекс.Маршрутизация). It can build a route by coordinates of cities, but it did not work properly for cities of Kazakhstan. It might get a bit longer to find out the problem. For this reason, I decided to use own custom solution.
The custom algorithm is injected. If you create another solution, you can inject it into the code.
distanceMap = map[string]map[string]int{}
customCalculator := NewCalculatorCustom(distanceMap)
newServer := NewCalculationServer(&customCalculator).
├── cmd
│ ├── client
│ │ └── main.go
│ └── server
│ └── main.go
├── data
│ ├── distances.json
│ └── distances_raw.json
├── go.mod
├── go.sum
├── Makefile
├── pb
│ └── calculation.pb.go
├── proto
│ └── calculation.proto
├── README.md
├── service
│ ├── main_test.go
│ ├── calculator_custom.go
│ ├── calculator.go
│ ├── calculator_test.go
│ └── service_calculation.go
└── utils
├── load.go
├── parser.go
└── randomer
├── payload.go
└── payload_test.go
cmd - client & server files (main.go)
data - parsed distances between cities (source: https://www.della.kz/distance/)
pb - .go file(s) generated by protoc
proto - .proto file(s)
service - the main logic (custom algorithm is here)
utils - helper functions
make client
go run cmd/client/main.go
Please, visit in the next order: [усть-каменогорск павлодар кокшетау нур-султан караганда тараз туркестан уральск атырау]
The total optimal distance will be: 6410