import math

# ============================================================
# USER-BASED рекомендательная система
# ============================================================

# Матрица предпочтений: ratings[товар][пользователь]
# 0 = пользователь не оценил товар

products = ['P1', 'P2', 'P3', 'P4', 'P5']
users    = ['U1', 'U2', 'U3', 'U4']

#          U1   U2   U3   U4
ratings = [
    [5,   5,   4,   5],   # P1
    [5,   5,   3,   0],   # P2
    [5,   5,   5,   5],   # P3
    [5,   0,   2,   0],   # P4
    [0,   5,   1,   0],   # P5
]

# Матрица косинусного подобия пользователей (задаётся вручную или берётся из задания 1)
# sim[i][j] — подобие между users[i] и users[j]
user_sim_raw = {
    ('U1', 'U2'): 0.9,
    ('U1', 'U3'): 0.7,
    ('U1', 'U4'): 0.0,   # U4 исключён (мало оценок — все нули кроме P1, P3)
    ('U2', 'U3'): 0.6,
    ('U2', 'U4'): 0.0,
    ('U3', 'U4'): 0.0,
}

# ============================================================
# Вспомогательные функции
# ============================================================

def dot_product(a, b):
    return sum(x * y for x, y in zip(a, b))

def norm(v):
    return math.sqrt(sum(x ** 2 for x in v))

def cosine_similarity(a, b):
    na, nb = norm(a), norm(b)
    if na == 0 or nb == 0:
        return 0.0
    return dot_product(a, b) / (na * nb)

def get_user_vector(user_idx):
    """Вектор оценок пользователя (по всем товарам)."""
    return [ratings[i][user_idx] for i in range(len(products))]

def get_item_vector(item_idx):
    """Вектор оценок товара (по всем пользователям)."""
    return ratings[item_idx]

def get_sim(u1, u2):
    """Косинусное подобие между двумя пользователями по имени."""
    if u1 == u2:
        return 1.0
    key = (u1, u2) if (u1, u2) in user_sim_raw else (u2, u1)
    return user_sim_raw.get(key, 0.0)

def avg_rating(user_idx):
    """Средняя оценка пользователя по всем товарам, которые он оценил (> 0)."""
    rated = [ratings[i][user_idx] for i in range(len(products)) if ratings[i][user_idx] > 0]
    return sum(rated) / len(rated) if rated else 0.0

def is_new_user(user_idx):
    """Новый пользователь — все оценки == 0."""
    return all(ratings[i][user_idx] == 0 for i in range(len(products)))

def best_avg_product():
    """Товар с наибольшим средним рейтингом (для новых пользователей)."""
    best_p, best_avg = None, -1
    for i, p in enumerate(products):
        rated = [ratings[i][j] for j in range(len(users)) if ratings[i][j] > 0]
        avg = sum(rated) / len(rated) if rated else 0.0
        if avg > best_avg:
            best_avg = avg
            best_p = p
    return best_p, best_avg

# ============================================================
# Формула предсказания оценки (USER-BASED):
#
#   Pr(a, i) = r̄(a) + Σ_{u∈K} (r(u,i) - r̄(u)) × cos(a,u)
#              ─────────────────────────────────────────────
#                        Σ_{u∈K} |cos(a, u)|
#
# K — пользователи, похожие на a, которые оценили товар i (> 0)
# r̄(a) — средняя оценка пользователя a
# r̄(u) — средняя оценка пользователя u
# r(u,i) — оценка пользователя u для товара i
# cos(a,u) — косинусное подобие a и u
# ============================================================

def predict(user_a_idx, item_i_idx, demo=True):
    """Предсказывает оценку пользователя a для товара i."""
    a_name = users[user_a_idx]
    i_name = products[item_i_idx]

    # K — пользователи которые оценили товар i (кроме самого a)
    K = []
    for u_idx, u_name in enumerate(users):
        if u_idx == user_a_idx:
            continue
        if ratings[item_i_idx][u_idx] > 0:
            sim = get_sim(a_name, u_name)
            if sim > 0:
                K.append(u_idx)

    if not K:
        if demo:
            print(f"    K пуст — нет похожих пользователей, оценивших {i_name}")
        return None

    r_a = avg_rating(user_a_idx)

    numerator   = 0.0
    denominator = 0.0

    if demo:
        print(f"    r̄({a_name}) = {r_a:.4f}")
        print(f"    K = {{ {', '.join(users[u] for u in K)} }}")

    for u_idx in K:
        u_name  = users[u_idx]
        r_ui    = ratings[item_i_idx][u_idx]
        r_u     = avg_rating(u_idx)
        cos_au  = get_sim(a_name, u_name)

        term    = (r_ui - r_u) * cos_au
        numerator   += term
        denominator += abs(cos_au)

        if demo:
            print(f"      u={u_name}: r({u_name},{i_name})={r_ui}, "
                  f"r̄({u_name})={r_u:.4f}, cos({a_name},{u_name})={cos_au:.4f} "
                  f"→ ({r_ui} - {r_u:.4f}) × {cos_au:.4f} = {term:.4f}")

    if denominator == 0:
        return None

    pr = r_a + numerator / denominator

    if demo:
        print(f"    Pr({a_name},{i_name}) = {r_a:.4f} + {numerator:.4f} / {denominator:.4f} = {pr:.4f}")

    return pr

# ============================================================
# Главная функция — рекомендация для каждого пользователя
# ============================================================

def recommend_for_user(user_idx, demo=True):
    a_name = users[user_idx]

    print(f"\n{'='*60}")
    print(f"  Пользователь: {a_name}")
    print(f"{'='*60}")

    # Новый пользователь?
    if is_new_user(user_idx):
        best_p, best_avg = best_avg_product()
        print(f"  Новый пользователь (все оценки = 0).")
        print(f"  Рекомендуем товар с наибольшим средним рейтингом: {best_p} (avg={best_avg:.4f})")
        return best_p

    # Товары, которые пользователь НЕ оценил
    unrated = [i for i in range(len(products)) if ratings[i][user_idx] == 0]

    if not unrated:
        print(f"  {a_name} оценил все товары — нечего рекомендовать.")
        return None

    print(f"  Неоцененные товары: {[products[i] for i in unrated]}")
    print(f"  Считаем предсказанную оценку для каждого:\n")

    predictions = {}
    for i_idx in unrated:
        i_name = products[i_idx]
        print(f"  → Pr({a_name}, {i_name}):")
        pr = predict(user_idx, i_idx, demo=demo)
        if pr is not None:
            predictions[i_name] = pr
            print(f"    Результат: {pr:.4f}")
        else:
            print(f"    Нет данных для предсказания.")
        print()

    if not predictions:
        print(f"  Не удалось предсказать оценки.")
        return None

    best = max(predictions, key=lambda x: predictions[x])
    print(f"  Все предсказания: { {k: round(v,4) for k,v in predictions.items()} }")
    print(f"  ✓ Рекомендуем {a_name}: товар {best} (Pr = {predictions[best]:.4f})")
    return best

# ============================================================
# Вывод исходных данных
# ============================================================

print("=" * 60)
print("  USER-BASED РЕКОМЕНДАТЕЛЬНАЯ СИСТЕМА")
print("=" * 60)

# Матрица предпочтений
col_w = 6
print("\n  Матрица предпочтений:")
print("  " + " " * 4 + "".join(f"{u:>{col_w}}" for u in users))
print("  " + "-" * (4 + col_w * len(users)))
for i, p in enumerate(products):
    row = f"  {p:<4}" + "".join(f"{ratings[i][j]:>{col_w}}" for j in range(len(users)))
    print(row)

# Средние оценки
print("\n  Средние оценки пользователей (по оцененным товарам):")
for j, u in enumerate(users):
    print(f"    r̄({u}) = {avg_rating(j):.4f}")

# Матрица подобия
print("\n  Матрица косинусного подобия пользователей:")
print("  " + " " * 4 + "".join(f"{u:>{col_w}}" for u in users))
print("  " + "-" * (4 + col_w * len(users)))
for i, u1 in enumerate(users):
    row = f"  {u1:<4}"
    for j, u2 in enumerate(users):
        row += f"{get_sim(u1,u2):>{col_w}.2f}"
    print(row)

# ============================================================
# Рекомендации для всех пользователей
# ============================================================
print("\n\n" + "=" * 60)
print("  РАСЧЁТ РЕКОМЕНДАЦИЙ")
print("=" * 60)

results = {}
for j in range(len(users)):
    rec = recommend_for_user(j, demo=True)
    results[users[j]] = rec

# Итог
print("\n" + "=" * 60)
print("  ИТОГОВЫЕ РЕКОМЕНДАЦИИ")
print("=" * 60)
for u, rec in results.items():
    if rec:
        print(f"  {u} → рекомендовать {rec}")
    else:
        print(f"  {u} → нечего рекомендовать")