СНЗ - Системи за препорака испитна

'''Во променливата songs_ratings дадени се оценки на 300 корисници за 19 песни. Оцените се во ранг од 0 до 10.
Податочното множество треба да се исфилтрира, така што ќе се отстранат корисниците кои најдобрата песна ја оцениле
со оцена помала од просечната оцената на песната. Просечната оцена на дадена песна се пресметува како вредноста на
сумата на оцените од корисниците, поделена со бројот на корисници кои оставиле оцена за дадената песна. Најдобрата
песна е песната која што има најголема просечна оцена.

Потребно е да се направи препорака на песни за нов корисник test_user_id. За овој корисник оцените за песните се
читаат од стандарден влез во променливата test_user_ratings. Потоа, потребно е да се направи препорака на 5 песни
преку препорака од корисници (user-based) со Евклидово растојание, препорака од корисници (user-based) со Пирсонова
корелација и препорака од песни (item-based). На стандарден излез да се испечатат песните кои се препорачуваат со
сите три начини на препорака (сортирани по растечки алфанумерички редослед), заедно со нивната просечна оцена, како
и вредностите за препорака од сите три методи. Доколку нема препорачани песни на стандарден излез треба да се испечати
'Nema preporachani pesni'



Sample input
129
1: 0, 2: 5, 3: 0, 4: 1, 5: 2, 6: 5, 7: 4, 8: 4, 9: 2
Sample output
Preporacani pesni:
Pesna 11, prosecna ocena: 5.82, preporaka so evklidovo rastojanie: 6.183104258859523, preporaka so pirsonova korelacija: 6.246043501983225, preporaka preku pesni: 0.6361729114217167
Pesna 12, prosecna ocena: 5.92, preporaka so evklidovo rastojanie: 6.46977823184295, preporaka so pirsonova korelacija: 6.370226152101855, preporaka preku pesni: 0.568420986600022'''


from math import sqrt


def sim_distance(prefs, person1, person2):
    """
    Враќа мерка за сличност базирана на растојание помеѓу person1 и person2
    :param prefs: речник со оцени од корисници
    :param person1: име на корисник1
    :param person2: име на корисник2
    :return: сличност помеѓу корисник1 и корисник2
    """
    # Се прави листа на заеднички предмети
    si = {}
    for item in prefs[person1]:
        if item in prefs[person2]:
            si[item] = 1
    # Ако немаат заеднички рејтинзи, врати 0
    if len(si) == 0:
        return 0
    # Собери ги квадратите на сите разлики
    sum_of_squares = sum([pow(prefs[person1][item] - prefs[person2][item], 2)
                          for item in prefs[person1] if item in prefs[person2]])
    return 1 / (1 + sqrt(sum_of_squares))


def sim_pearson(prefs, p1, p2):
    """
    Го враќа коефициентот на Пирсонова корелација помеѓу p1 и p2 (личност1 и личност 2).
    Вредностите се помеѓу -1 и 1
    :param prefs: речник со оцени од корисници
    :param p1: име на корисник1
    :param p2: име на корисник2
    :return: сличност помеѓу корисник1 и корисник2
    """
    # Се креира речник во кој ќе се чуваат предметите кои се оценети од двајцата
    # Во речникот ни се важни само клучевите за да ги чуваме имињата на филмовите
    # кои се заеднички, а вредностите не ни се важни
    si = {}
    for item in prefs[p1]:
        if item in prefs[p2]:
            si[item] = 1

    # Се пресметува бројот на предмети оценети од двајцата
    n = len(si)

    # Ако немаат заеднички предмети, врати корелација 0
    if n == 0:
        return 0

    # Собери ги сите оцени за секоја личност посебно
    sum1 = sum([prefs[p1][it] for it in si])
    sum2 = sum([prefs[p2][it] for it in si])
    # Собери ги квадратите од сите оцени за секоја личност посебно
    sum1Sq = sum([pow(prefs[p1][it], 2) for it in si])
    sum2Sq = sum([pow(prefs[p2][it], 2) for it in si])
    # Собери ги производите од оцените на двете личности
    pSum = sum([prefs[p1][it] * prefs[p2][it] for it in si])

    # Пресметај го коефициентот на корелација
    num = pSum - (sum1 * sum2 / n)
    den = sqrt((sum1Sq - pow(sum1, 2) / n) * (sum2Sq - pow(sum2, 2) / n))
    if den == 0:
        return 0
    r = num / den
    return r


def top_matches(prefs, person, n=5, similarity=sim_pearson):
    """
    Ги враќа најсличните n корисници за даден корисник.
    :param prefs: речник со оцени од корисници
    :param person: име на корисник
    :param n: број на слични корисници
    :param similarity: метрика за сличност
    :return: листа со најслични n корисници
    """
    scores = [(similarity(prefs, person, other), other)
              for other in prefs if other != person]
    # Се сортира листата во растечки редослед
    scores.sort()
    # Се превртува за најсличните (со најголема вредност) да бидат први
    scores.reverse()
    return scores[0:n]


def get_recommendations(prefs, person, similarity=sim_pearson):
    """
    Ги враќа препораките за даден корисник со користење на тежински просек
    со оцените од другите корисници
    :param prefs: речник со оцени од корисници
    :param person: име на корисник
    :param similarity: метрика за сличност
    :return: препораки за даден корисник
    """
    totals = {}
    simSums = {}
    for other in prefs:
        # За да не се споредува со самиот себе
        if other == person:
            continue
        sim = similarity(prefs, person, other)
        # не се земаат предвид резултати <= 0
        if sim <= 0:
            continue
        for item in prefs[other]:
            # за тековниот корисник ги земаме само филмовите што ги нема гледано
            if item not in prefs[person] or prefs[person][item] == 0:
                # Similarity * Score
                totals.setdefault(item, 0)
                totals[item] += prefs[other][item] * sim

                # Сума на сличности
                simSums.setdefault(item, 0)
                simSums[item] += sim

    # Креирање на нормализирана листа со рејтинзи
    rankings = [(total / simSums[item], item) for item, total in totals.items()]

    # Сортирање на листата во растечки редослед. Превртување на листата за најголемите вредности да бидат први
    rankings.sort(reverse=True)

    return rankings


def get_recommendations_item_based(inverted_prefs, person):
    """
    Ги враќа препораките за даден корисник со користење на тежински просек
    со оцените од предметите
    :param inverted_prefs: инвертиран речник со оцени од корисници, item-based
    :param person: име на корисник
    :return: препораки за даден корисник
    """
    similarity_per_item = {}
    person_items = [item for item, values in inverted_prefs.items() if person in values.keys()]
    for item in person_items:
        similar_items = top_matches(inverted_prefs, item, n=None)
        my_rating = inverted_prefs[item][person]
        for similarity, item in similar_items:
            if person in inverted_prefs[item] or similarity <= 0:
                continue
            similarity_per_item.setdefault(item, [])
            similarity_per_item[item].append(similarity * my_rating)

    # Креирање на нормализирана листа со рејтинзи
    similarity_per_item_avg = [(sum(similarity_per_item[item]) / len(similarity_per_item[item]), item) for item in
                               similarity_per_item]
    similarity_per_item_avg.sort(reverse=True)

    return similarity_per_item_avg


def transform_prefs(prefs):
    """
    Ги трансформира рејтинзите така што клучеви ќе бидат филмовите,
    а вредност ќе биде листа со рејтинзи од секој корисник
    :param prefs: речник со оцени од корисници
    :return: инвертиран речник со оцени од корисници
    """
    result = {}
    for person in prefs:
        for item in prefs[person]:
            result.setdefault(item, {})
            # Замени ги местата на корисникот и предметот
'__main__':
    test_user_id = int(input())
    test_user_ratings = {int(x.split(': ')[0]): int(x.split(': ')[1]) for x in input().split(', ')}

    inverted = transform_prefs(songs_ratings)                          # najprvo kje go prevrtime setot za polesno da dojdeme do najdobrata prosecna pesna
    maks = sum(inverted[1].values()) / len(inverted[1].values())       # na pocetokot inicijalno maks go postavuvame na prosecnata ocena na prvata pesna
    best_song = None                                                    # tuka kje ja zacuvame pesnata so najdobra prosecna ocena
    avg_songs_ratings = {}                                              # vo ovoj recnik kje gi cuvame prosecnite oceni na sekoja pesna bidejki ni treba toa vo printot
    for song in inverted.keys():                                           # iterirame pesna po pesna
        avg = sum(inverted[song].values()) / len(inverted[song].values())   # naogjame prosecna ocena na pesnata
        avg_songs_ratings[song] = round(avg, 2)                            # ja zapisuvame soodvetno vo recnikot so prosecni oceni za sekoja pesna posebno
        if avg > maks:                                                     # proveruvame dali taa pesna do sega ima najgolema prosecna ocena
            maks = avg                                                     # ja zacuvuvame taa vrednost
            best_song = song                                               # ja zacuvuvame i pesnata koja do togas ja ima najdobrata prosecna ocena

    for user in list(songs_ratings.keys()):                                # sega gi izminuvame site korisnici
        if songs_ratings[user][best_song] < maks:                          # proveruvame koj od korisnicite pesnata so najdobra prosecna ocena ja ocenile so ocena pomala od taa vrednost
            songs_ratings.pop(user)                                       # gi otstranuvame takvite korisnici

    songs_ratings[test_user_id] = test_user_ratings                          # go dodavame noviot korisnik soodvetno so ocenkite koi toj gi dal za site pesni
    inverted = transform_prefs(songs_ratings)                                # go prevrtuvame setot povtorno po dodavanjeto, ova ni treba za da napravime item_based preporaka

    rec_e = get_recommendations(songs_ratings, test_user_id, sim_distance)    # user_based preporaka so ekvildovo rastojanie
    rec_p = get_recommendations(songs_ratings, test_user_id, sim_pearson)    # user_based preporaka so pirsonova korelacija
    rec_i = get_recommendations_item_based(inverted, test_user_id)            # item_based preporaka

    songs_e = {tup[1] for tup in rec_e}                                       # id na sekoja pesna od torkite na sekoja preporaka go zemame i stavame vo set
    songs_p = {tup[1] for tup in rec_p}                                       # ova go pravime bidejki so pomosh na set lesno kje dojdeme do zaednickite preporaki
    songs_i = {tup[1] for tup in rec_i}                                         # odnosno do pesnite koi gi ima vo trite poraki so pomosh na intersection

    set1 = songs_e.intersection(songs_p)                                      # presekot na onie so ekvildovo rastojanie i onie so pirsonova korelacija t.e zaednickite koi gi ima vo dvete preporaki
    common_songs = set1.intersection(songs_i)                               # na rezultatot od toj presek mu pravime nov presek so onie koi se vo item_based preporakata i gi dobivame pesnite koi se zaednicki za site tri preporaki

    rec_e = [tup for tup in rec_e if tup[1] in common_songs]
    rec_p = [tup for tup in rec_p if tup[1] in common_songs]                # vo samite preporaki gi ostavame samo torkite koi sodrzat id na pesna koe se naogja vo site tri preporaki t.e e zaednicka za site preporaki
    rec_i = [tup for tup in rec_i if tup[1] in common_songs]

    rec_e.sort(key=lambda x: x[1])
    rec_p.sort(key=lambda x: x[1])                                         # gi sortirame preporakite "alfanumericki" t.e vo rastecki redosled po id na pesna
    rec_i.sort(key=lambda x: x[1])

    if len(common_songs) == 0:                                          # dokolku nemalo takvi pesni koi se preporacani so site tri preporaki naednas smetame deka nema preporacani pesni
        print("Nema preporachani pesni")
    else:
        print("Preporacani pesni:")
        i = 0
        while True:
            if i == len(rec_e) or i == 5:                               # dokolku sme ispecatile 5 preporacani pesni ili pak sme dostignale maksimum kolku sto imalo zaednicki preporacani (dokolku bile pomalku od 5) togash zavrsuvame so pecatenje
                break                                                   # moze da proveruvame so dolzinata na bilo koja preporaka bidejki sekako sekoja od niv ima ist broj torki vnatre t.e onolku kolku sto bile zaednicki pesni vo site tri preporaki

            print(f"Pesna {rec_e[i][1]}, prosecna ocena: {avg_songs_ratings[rec_e[i][1]]}, preporaka so evklidovo rastojanie: "
                  f"{rec_e[i][0]}, preporaka so pirsonova korelacija: {rec_p[i][0]}, preporaka preku pesni: {rec_i[i][0]}")
            i += 1