#12. is_armstrong(n: int) -> bool
#Проверить, является ли число числом Армстронга
#(сумма цифр, возведённых в степень количества цифр, равна числу).
#Пример: 153 = 1³ + 5³ + 3³.
#is_armstrong(153) → True
#is_armstrong(10) → False
import math


def is_armstrong(n: int) -> bool:
    s = str(n)
    power = len(s)
    total = sum(int(digit) ** power for digit in s)
    return total == n



#№18. intersection_of_sorted(a: list, b: list) -> list
#Найти пересечение двух отсортированных списков (без дубликатов). Сложность O(n+m).
#intersection_of_sorted([1, 2, 3, 4], [2, 4, 6]) → [2, 4]
def intersection_of_sorted(a: list, b: list) -> list:
    result = []
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            if not result or a[i] != result[-1]:
                result.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return result



#№21. longest_increasing_subsequence(arr: list) -> list
#Найти самую длинную возрастающую подпоследовательность (не обязательно непрерывную).
#longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]) → [2, 3, 7, 18]
def longest_increasing_subsequence(arr: list) -> list:
    if not arr: return []
    n = len(arr)
    lengths = [1] * n
    prev = [-1] * n
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j] and lengths[i] < lengths[j] + 1:
                lengths[i] = lengths[j] + 1
                prev[i] = j

    max_idx = 0
    for i in range(1, n):
        if lengths[i] > lengths[max_idx]:
            max_idx = i

    res = []
    while max_idx != -1:
        res.append(arr[max_idx])
        max_idx = prev[max_idx]
    return res[::-1]



#№2. remove_duplicate_chars(s: str) -> str
#Удалить из строки все повторяющиеся символы, оставив только первое вхождение каждого.
#remove_duplicate_chars("abacabad") → "abcd"
def remove_duplicate_chars(s: str) -> str:
    result = ""
    for char in s:
        if char not in result:
            result += char
    return result



#№23. most_frequent_value(d: dict) -> tuple
#Найти значение, которое чаще всего встречается среди значений словаря. Вернуть (значение, частота)
#most_frequent_value({"a": 1, "b": 2, "c": 1, "d": 3}) → (1, 2)
def most_frequent_value(d: dict) -> tuple:
    values = list(d.values())

    best_val = None
    max_count = 0

    for val in values:
        count = values.count(val)

        if count > max_count:
            max_count = count
            best_val = val
    return (best_val, max_count)



#№8. gcd(a: int, b: int) -> int
#Найти наибольший общий делитель двух чисел (алгоритм Евклида).
#gcd(18, 24) → 6
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a



#№14. lcm(a: int, b: int) -> int
#Найти наименьшее общее кратное двух чисел.
#lcm(4, 6) → 12
def lcm(a: int, b: int) -> int:
    num1 = a
    num2 = b
    while b:
        a, b = b, a % b
    nod = a

    result = (num1 * num2) // nod
    return result



#№31. frequency_analysis(text: str, n: int) -> list
#Найти n самых частых слов в тексте (игнорируя знаки препинания и регистр). Вернуть список (слово, частота)
#frequency_analysis("cat dog cat bird cat dog", 2) → [("cat", 3), ("dog", 2)]
def frequency_analysis(text: str, n: int) -> list:
    for char in ".,!?;:-()":
        text = text.replace(char, "")

    words = text.lower().split()

    counts = {}
    for word in words:
        if word in counts:
            counts[word] += 1
        else:
            counts[word] = 1

    items = list(counts.items())
    items.sort(key=lambda x: x[1], reverse=True)
    return items[:n]



#№7. decode_caesar(text: str, shift: int) -> str
#Расшифровать текст, сдвинутый по шифру Цезаря на shift позиций. Только русские буквы.
#decode_caesar("гтужф", 5) → "абвгд" КАКИМ ОБРАЗОМ МЕЖДУ "Г" и  "А" СДВИГ 5!?!?!?!?
def decode_caesar(text: str, shift: int) -> str:
    alphabet = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя"
    result = ""

    text = text.lower()

    for char in text:
        if char in alphabet:
            index = alphabet.find(char)
            new_index = (index - shift) % len(alphabet)
            result += alphabet[new_index]
        else:
            result += char
    return result



#№3. is_strong_password(password: str) -> bool
#Проверить, что пароль: длина ≥8, есть хотя бы одна цифра и одна заглавная буква.
#is_strong_password("Python123") → True
#is_strong_password("python") → False
def is_strong_password(password: str) -> bool:
    if len(password) < 8:
        return False

    has_upper = False
    has_digit = False

    for char in password:
        if char.isupper():
            has_upper = True
        if char.isdigit():
            has_digit = True
    return has_upper and has_digit



#№16. remove_outliers(numbers: list, threshold: float) -> list
#Удалить выбросы: числа, отклоняющиеся от среднего более чем на threshold * стандартное_отклонение.
#remove_outliers([1, 2, 3, 100, 4, 5], 2) → [1, 2, 3, 4, 5]
def remove_outliers(numbers: list, threshold: float) -> list:
    if not numbers:
        return []

    count = len(numbers)
    mean = sum(numbers) / count

    variance_sum = 0
    for x in numbers:
        variance_sum += (x - mean) ** 2
    variance = variance_sum / count

    std_dev = variance ** 0.5

    result = []
    for x in numbers:
        deff = x - mean
        if abs(deff) <= threshold * std_dev:
            result.append(x)
    return result



# --- Главное миню ---
# без него не вайб


def get_list_input(prompt):
    return [int(x) for x in input(prompt).split()]


def main():
    while True:
        print("\n" + "=" * 30)
        print("ВЫБЕРИТЕ ФУНКЦИЮ:")
        print("1. Число Армстронга")
        print("2. Пересечение отсортированных списков")
        print("3. Самая длинная возрастающая подпоследовательность")
        print("4. Удаление дубликатов из строки")
        print("5. Частое значение в словаре")
        print("6. НОД (алгоритм Евклида)")
        print("7. НОК")
        print("8. Частотный анализ текста")
        print("9. Декодер Цезаря (RU)")
        print("10. Проверка пароля")
        print("11. Удаление выбросов")
        print("0. Выход")

        cmd = input("\nВведите номер: ")

        try:
            if cmd == '1':
                n = int(input("Введите число: "))
                print("Результат:", is_armstrong(n))

            elif cmd == '2':
                a = get_list_input("Введите 1-й список (через пробел): ")
                b = get_list_input("Введите 2-й список (через пробел): ")
                print("Результат:", intersection_of_sorted(a, b))

            elif cmd == '3':
                arr = get_list_input("Введите числа через пробел: ")
                print("Результат:", longest_increasing_subsequence(arr))

            elif cmd == '4':
                s = input("Введите строку: ")
                print("Результат:", remove_duplicate_chars(s))

            elif cmd == '5':
                print("Пример ввода: ключ:значение через пробел (a:1 b:2 c:1)")
                data = input("Введите данные: ").split()
                d = {x.split(':')[0]: int(x.split(':')[1]) for x in data}
                print("Результат:", most_frequent_value(d))

            elif cmd == '6':
                a, b = map(int, input("Введите два числа через пробел: ").split())
                print("НОД:", gcd(a, b))

            elif cmd == '7':
                a, b = map(int, input("Введите два числа через пробел: ").split())
                print("НОК:", lcm(a, b))

            elif cmd == '8':
                txt = input("Введите текст: ")
                n = int(input("Сколько слов вывести?: "))
                print("Результат:", frequency_analysis(txt, n))

            elif cmd == '9':
                txt = input("Введите зашифрованный текст: ")
                s = int(input("Сдвиг: "))
                print("Результат:", decode_caesar(txt, s))

            elif cmd == '10':
                p = input("Введите пароль: ")
                print("Надежный?:", is_strong_password(p))

            elif cmd == '11':
                nums = [float(x) for x in input("Введите числа через пробел: ").split()]
                t = float(input("Порог (threshold): "))
                print("Результат:", remove_outliers(nums, t))

            elif cmd == '0':
                print("Программа завершена.")
                break
            else:
                print("Неверный пункт меню.")

        except Exception as e:
            print(f"Ошибка при вводе данных: {e}")

        # Предложение продолжить
        choice = input("\nВернуться в меню? (д/н): ").lower()
        if choice not in ['д', 'y', 'l']:
            print("Программа завершена.")
            break


if __name__ == "__main__":
    main()