Annettuna on soittolista, jossa jokaista laulua vastaa tietty kokonaisluku. Tehtäväsi on selvittää, montako osalistaa soittolistassa on, joissa ei esiinny kahta samaa laulua.
Esimerkiksi listan [1,2,1,3] osalistat ovat [1], [2], [1], [3], [1,2], [2,1], [1,3], [1,2,1], [2,1,3] ja [1,2,1,3]. Esimerkiksi osalista [1,3] kelpaa, koska se sisältää kerran laulut 1 ja 3. Osalista [1,2,1] ei kelpaa, koska se sisältää kahdesti laulun 1.
Haluttu vastaus listalle [1,2,1,3] on 8, koska kelvolliset osalistat ovat [1], [2], [1], [3], [1,2], [2,1], [1,3] ja [2,1,3]. Tässä osalista [1] lasketaan mukaan kahdesti, koska soittolistassa on kahdesti tällainen osalista.
Toteuta tiedostoon playlist.py funktio count_parts, jolle annetaan parametrina soittolistan sisältö. Funktion tulee palauttaa haluttujen osalistojen määrä.
Funktion tulee toimia tehokkaasti suurillakin listoilla. Tehtäväpohjan kahdessa viimeisessä testissä listat ovat suuria ja funktion tulee palauttaa vastaus niissäkin tapauksissa välittömästi.
def count_parts(songs):
# TODO
if __name__ == "__main__":
print(count_parts([1, 1, 1, 1])) # 4
print(count_parts([1, 2, 3, 4])) # 10
print(count_parts([1, 2, 1, 2])) # 7
print(count_parts([1, 2, 1, 3])) # 8
print(count_parts([1, 1, 2, 1])) # 6
songs = [1, 2] * 10**5
print(count_parts(songs)) # 399999
songs = list(range(1, 10**5 + 1)) * 2
print(count_parts(songs)) # 15000050000