def euclidean(a, b):
    '''returns the euclidean distance between two pixel RGB values.'''

    r = (a[0] - b[0]) * (a[0] - b[0])
    g = (a[1] - b[1]) * (a[1] - b[1])
    b = (a[2] - b[2]) * (a[2] - b[2])

    return math.sqrt(r + g + b)

def kmeans(source_colors, k):
    '''takes a list of source colors as tuples and returns a kmeans generated color palette'''

    kmeans = {}

    for i in range(k):
        r = random.choice(source_colors)
        kmeans[r] = []

    while True:
        for color in source_colors:
            distances = {}
            for mean in kmeans:
                distances[mean] = euclidean(color, mean)

            mdist = min(distances.values())

            for key, val in distances.items():
                if val == mdist:
                    kmeans[key].append(color)

        new_kmeans = {}

        for mean, colors in kmeans.items():
            r, g, b = 0, 0, 0
            for i in colors:
                r += i[0]
                g += i[1]
                b += i[2]

            r = r // len(colors)
            g = g // len(colors)
            b = b // len(colors)

            new_kmeans[(r, g, b)] = []

        if kmeans.keys() == new_kmeans.keys():
            break
        else:
            kmeans = new_kmeans

    palette = list(kmeans.keys())

    return palette