Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
prim solution in 3rd party category for Connect Stars by kazuki.h
from typing import List, Tuple, Iterable
import numpy as np
from numpy import linalg as la
def connect_stars(coords: List[Tuple[int, int]]) -> Iterable[Tuple[int, int]]:
coords = [np.array(p) for p in coords]
n = len(coords)
table_weight = {i: la.norm(coords[0] - coords[i]) for i in range(1, n)}
table_pre = {i: 0 for i in range(1, n)}
result = []
while table_weight != {}:
p = min(table_weight, key = table_weight.get)
result.append((table_pre[p], p))
del table_weight[p]
q = coords[p]
for r in table_weight:
array_r = coords[r]
if table_weight[r] > la.norm(q - array_r):
table_weight[r] = la.norm(q - array_r)
table_pre[r] = p
return result
May 20, 2020
Comments:
