Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Connect Stars by mortonfox
from typing import List, Tuple, Iterable
import math
def dist(point1, point2):
return math.hypot(point1[0] - point2[0], point1[1] - point2[1])
# Using Prim's algorithm
# https://en.wikipedia.org/wiki/Prim%27s_algorithm
def connect_stars(coords: List[Tuple[int, int]]) -> Iterable[Tuple[int, int]]:
tree = []
vertices = [{ 'index': i, 'coord': coord, 'dist': math.inf, 'edge': None } for i, coord in enumerate(coords)]
while vertices:
# Grow the tree by one by finding the edge with the lowest distance.
lowest = min(range(len(vertices)), key=lambda i: vertices[i]['dist'])
vertex = vertices.pop(lowest)
if vertex['edge']:
tree.append(vertex['edge'])
# See if the new vertex added to the tree lowers the distance to any
# vertices that are not in the tree.
# If it does, record the lower distance and associated edge.
for otherv in vertices:
newdist = dist(vertex['coord'], otherv['coord'])
if newdist < otherv['dist']:
otherv['dist'] = newdist
otherv['edge'] = (vertex['index'], otherv['index'])
return tree
if __name__ == '__main__':
print("Example:")
print(connect_stars([(1, 1), (4, 4)]))
def sort_edges(edges): return sorted(map(lambda e: tuple(sorted(e)), edges))
# These "asserts" are used for self-checking and not for an auto-testing
assert sort_edges(connect_stars([(1, 1), (4, 4)])) == [(0, 1)], '2 vertices'
assert sort_edges(connect_stars([(1, 1), (4, 1), (4, 4)])) == [(0, 1), (1, 2)], '3 vertices'
assert sort_edges(connect_stars([(6, 6), (6, 8), (8, 4), (3, 2)])) == [(0, 1), (0, 2), (0, 3)], '4 vertices'
assert sort_edges(connect_stars([(5, 4), (5, 1), (2, 6), (7, 2), (6, 9)])) == [(0, 2), (0, 3), (1, 3), (2, 4)], '5 vertices'
assert sort_edges(connect_stars([(5, 8), (5, 1), (4, 2), (7, 6), (8, 6), (2, 2)])) == [(0, 3), (1, 2), (2, 3), (2, 5), (3, 4)], '6 vertices'
assert sort_edges(connect_stars([(2, 7), (9, 9), (4, 9), (9, 6), (3, 3), (1, 6), (9, 7)])) == [(0, 2), (0, 5), (1, 2), (1, 6), (3, 6), (4, 5)], '7 vertices'
print("Coding complete? Click 'Check' to earn cool rewards!")
May 18, 2020
Comments:
