Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Connect Stars by pokosasa
from typing import List, Tuple, Iterable
from heapq import heappop, heappush
def connect_stars(coords: List[Tuple[int, int]]) -> Iterable[Tuple[int, int]]:
N, INF = len(coords), float("inf")
costs = [[abs((x1-x2)+(y1-y2)*1j) for x1,y1 in coords] for x2,y2 in coords]
united = {0}
min_costs = [INF]*N
min_costs[0] = 0
res = []
que = []
for pos in range(1, N):
heappush(que, (costs[0][pos], (0, pos)))
while que:
_, (pos1, pos2) = heappop(que)
if pos2 in united:
continue
united.add(pos2)
res.append(tuple(sorted((pos1, pos2))))
for pos3, cost in enumerate(costs[pos2]):
if pos3 == pos2:
continue
if cost < min_costs[pos3]:
min_costs[pos3] = cost
heappush(que, (cost, (pos2, pos3)))
res=sorted(res)
return res
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 17, 2020
Comments:
