HP CodeWars 2016 Problem 21: Astro-Navigation¶
http://www.hpcodewars.org/past/cw19/problems/CodeWars2016NAProblemSetFinal.pdf
The following code is modified from the solution posted at hpcodewars.org¶
In [1]:
from heapq import heapify, heappop, heappush
In [2]:
def dist(a, b):
return (((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 + (a[2] - b[2]) ** 2)**0.5)
def process(line):
(name, classs, mag, x, y, z) = line.split()
return name, float(x), float(y), float(z)
In [3]:
# Hardcoded test data set
_catalog_count = 10
_catalog = ["Sol G2V 4.83 0 0 0",
"Alpha-Centauri G2V+K1V+M5.5V 4.06 -1.641 -1.372 -3.833",
"Luhman-16 L8+T1 14.2 -3.751 1.195 -5.285",
"Sirius A1V+DA2 1.43 -1.611 8.078 -2.471",
"Epsilon-Eridani K2V 6.18 6.201 8.296 -1.724",
"Groombridge-34 M1+M3 10.32 8.329 0.67 8.074",
"Epsilon-Indi K4V+T1+T6 6.89 5.66 -3.157 -9.897",
"Tau-Ceti G8V 5.68 10.283 5.021 -3.267",
"Teegarden's-star M6 17.22 8.719 8.202 3.633",
"Kapteyn's-Star M1 10.87 1.89 8.834 -9.039"]
_trip_count = 3
_trips = ["Sol Alpha-Centauri 5",
"Teegarden's-star Sirius 5",
"Groombridge-34 Alpha-Centauri 9"]
In [4]:
data = {}
for line in _catalog:
(name, x, y, z) = process(line)
data[name] = (x, y, z)
print(data)
In [5]:
starDists = {}
for n in data: # calculate all distances once.
lengths={}
for n2 in data:
lengths[n2] = dist(data[n], data[n2])
starDists[n] = lengths
# print(starDists)
In [6]:
def journey(line, data):
(s, e, d) = line.split()
d = int(d)
print("JOURNEY from {} to {}, max jump: {} LY".format(s, e, d))
print("STRAIGHT LINE DISTANCE: {:.2f} LY".format(dist(data[s], data[e])))
queue = [(0.0, tuple([s]))]
heapify(queue)
shortestpath = None
shortestdist = None
shortPathToStar={}
for n in data:
shortPathToStar[n]=20000
while queue:
(basedist, basepath) = heappop(queue)
if (shortestdist is not None) and (basedist > shortestdist):
continue
if basepath[-1] == e:
shortestpath = basepath
shortestdist = basedist
continue
for n in data:
if n in basepath:
continue
thisdist = starDists[basepath[-1]][n]
# Don't travel if too far, or we found a shorter distance to n before
if ((thisdist < d) and (basedist+thisdist < shortPathToStar[n])):
heappush(queue,(basedist + thisdist, basepath + tuple([n])))
shortPathToStar[n] = basedist + thisdist
if shortestpath is None:
print("No route from {} to {}".format(s, e))
return
p = shortestpath
print("number of jumps: {}".format(len(p) - 1))
for i in range(len(p) - 1):
print("{} to {}; {:.2f} LY".format(p[i], p[i + 1], dist(data[p[i]], data[p[i + 1]])))
print("Total Distance: {:.2f} LY".format(shortestdist))
In [7]:
for line in _trips:
journey(line, data)
print("")
