Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Connect Stars by freeman_lex
from itertools import product
def connect_stars(coords):
free = coords[:]
con = [free.pop(0)]
dist = lambda a: (a[0][0]-a[1][0])**2 + (a[0][1]-a[1][1])**2
while free:
new, existed = min(product(free, con), key=dist)
con.append(new)
free.remove(new)
yield coords.index(new), coords.index(existed)
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 9, 2023
Comments:
