Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Connect Stars by Moff
from typing import List, Tuple, Iterable
from dataclasses import dataclass
import math
@dataclass
class Point:
x: float
y: float
def dist_to(self, other):
return math.hypot(self.x - other.x, self.y - other.y)
@dataclass
class Edge:
dist: float
v1: int
v2: int
def connect_stars(coords: List[Tuple[int, int]]) -> Iterable[Tuple[int, int]]:
points = [Point(*r) for r in coords]
visited = set()
edges = []
mst = []
def visit(v1):
if v1 not in visited:
visited.add(v1)
for v2, p2 in enumerate(points):
if v2 not in visited:
edges.append(Edge(points[v1].dist_to(p2), v1, v2))
visit(0)
while len(mst) < len(coords) - 1:
edges.sort(key=lambda x: x.dist)
edge = edges.pop(0)
if edge.v1 in visited and edge.v2 in visited:
continue
mst.append((edge.v1, edge.v2))
visit(edge.v1)
visit(edge.v2)
return mst
Dec. 20, 2021
Comments:
