Amaliy loyiha - Metro marshrut qidiruvchi

# metro_malumot.py
"""Toshkent metrosi ma'lumotlari (soddalashtirilgan)."""

CHIZIQLAR = {
    "Chilonzor": {
        "rang": "qizil",
        "bekatlar": [
            "Buyuk Ipak Yo'li", "Pushkin", "Hamid Olimjon", "Amir Temur xiyoboni",
            "Mustaqillik maydoni", "Paxtakor", "Xalqlar do'stligi",
            "Chilonzor", "Novza", "Milliy bog'", "Olmazor",
        ],
    },
    "O'zbekiston": {
        "rang": "ko'k",
        "bekatlar": [
            "Beruniy", "Tinchlik", "Chorsu", "G'afur G'ulom", "Alisher Navoiy",
            "Paxtakor", "Oybek", "Toshkent", "Mashinasozlar", "Do'stlik",
        ],
    },
    "Yunusobod": {
        "rang": "yashil",
        "bekatlar": [
            "Turkiston", "Yunus Rajabiy", "Shahriston", "Bodomzor",
            "Minor", "Abdulla Qodiriy", "Yunusobod",
        ],
    },
}

# Bekatlar orasidagi o'rtacha yurish vaqti (daqiqa)
BEKAT_VAQTI = 2.5

# Chiziqni almashtirish uchun ketadigan vaqt (daqiqa)
ALMASHTIRISH_VAQTI = 5.0

# Almashtirish mumkin bo'lgan bekatlar
ALMASHTIRISH_BEKATLARI = {
    "Paxtakor": ["Chilonzor", "O'zbekiston"],
    "Alisher Navoiy": ["O'zbekiston", "Yunusobod"],
    "Amir Temur xiyoboni": ["Chilonzor", "Yunusobod"],
}

# metro_graf.py
"""Metro tarmog'ini graf sifatida quradi."""

from collections import defaultdict

from metro_malumot import (
    CHIZIQLAR, BEKAT_VAQTI, ALMASHTIRISH_VAQTI, ALMASHTIRISH_BEKATLARI,
)


class MetroGraf:
    """Metro tarmog'i - vaznli yo'naltirilmagan graf."""

    def __init__(self):
        self._qoshnilar = defaultdict(dict)
        self._bekat_chiziqlari = defaultdict(set)
        self._qur()

    def _qur(self):
        """Chiziqlar ma'lumotidan grafni yig'adi."""
        for chiziq_nomi, malumot in CHIZIQLAR.items():
            bekatlar = malumot["bekatlar"]

            for bekat in bekatlar:
                self._bekat_chiziqlari[bekat].add(chiziq_nomi)

            # Qo'shni bekatlarni bog'laymiz
            for i in range(len(bekatlar) - 1):
                joriy, keyingi = bekatlar[i], bekatlar[i + 1]
                self._qoshnilar[joriy][keyingi] = BEKAT_VAQTI
                self._qoshnilar[keyingi][joriy] = BEKAT_VAQTI

    # ---------- so'rovlar ----------

    def bekatlar(self):
        """Barcha bekatlar ro'yxati."""
        return sorted(self._bekat_chiziqlari.keys())

    def qoshnilar(self, bekat):
        return self._qoshnilar[bekat]

    def chiziqlari(self, bekat):
        """Bekat qaysi chiziqlarda joylashgan."""
        return self._bekat_chiziqlari.get(bekat, set())

    def bormi(self, bekat):
        """O(1) - xesh-jadval tufayli."""
        return bekat in self._bekat_chiziqlari

    def almashtirish_bekatimi(self, bekat):
        return len(self._bekat_chiziqlari.get(bekat, set())) > 1

    def statistika(self):
        return {
            "bekatlar": len(self._bekat_chiziqlari),
            "chiziqlar": len(CHIZIQLAR),
            "qirralar": sum(len(q) for q in self._qoshnilar.values()) // 2,
            "almashtirish": sum(1 for b in self._bekat_chiziqlari
                                if self.almashtirish_bekatimi(b)),
        }

# marshrut.py
"""Marshrut qidiruv algoritmlari."""

import heapq
from collections import deque

from metro_malumot import ALMASHTIRISH_VAQTI


def eng_tez_marshrut(graf, boshlanish, manzil):
    """Dijkstra: eng kam vaqt ketadigan marshrutni topadi. O((V+E) log V)."""
    if boshlanish == manzil:
        return [boshlanish], 0.0

    vaqtlar = {bekat: float("inf") for bekat in graf.bekatlar()}
    vaqtlar[boshlanish] = 0.0
    qayerdan = {boshlanish: None}
    tayyor = set()

    uyum = [(0.0, boshlanish)]

    while uyum:
        joriy_vaqt, joriy = heapq.heappop(uyum)

        if joriy in tayyor:
            continue
        tayyor.add(joriy)

        if joriy == manzil:
            break

        for qoshni, vazn in graf.qoshnilar(joriy).items():
            if qoshni in tayyor:
                continue

            qoshimcha = 0.0
            # Almashtirish bekatidan o'tayotgan bo'lsak, qo'shimcha vaqt
            if graf.almashtirish_bekatimi(joriy) and qayerdan.get(joriy) is not None:
                oldingi = qayerdan[joriy]
                if not (graf.chiziqlari(oldingi) & graf.chiziqlari(qoshni)):
                    qoshimcha = ALMASHTIRISH_VAQTI

            yangi_vaqt = joriy_vaqt + vazn + qoshimcha

            if yangi_vaqt < vaqtlar[qoshni]:
                vaqtlar[qoshni] = yangi_vaqt
                qayerdan[qoshni] = joriy
                heapq.heappush(uyum, (yangi_vaqt, qoshni))

    if vaqtlar[manzil] == float("inf"):
        return None, None

    return _yolni_tikla(qayerdan, manzil), vaqtlar[manzil]


def eng_kam_bekat(graf, boshlanish, manzil):
    """BFS: eng kam bekatdan o'tadigan marshrut. O(V + E)."""
    if boshlanish == manzil:
        return [boshlanish]

    korilgan = {boshlanish}
    qayerdan = {boshlanish: None}
    navbat = deque([boshlanish])

    while navbat:
        joriy = navbat.popleft()

        for qoshni in graf.qoshnilar(joriy):
            if qoshni in korilgan:
                continue

            korilgan.add(qoshni)
            qayerdan[qoshni] = joriy

            if qoshni == manzil:
                return _yolni_tikla(qayerdan, manzil)

            navbat.append(qoshni)

    return None


def _yolni_tikla(qayerdan, manzil):
    yol = []
    joriy = manzil
    while joriy is not None:
        yol.append(joriy)
        joriy = qayerdan.get(joriy)
    return yol[::-1]


def almashtirishlar(graf, yol):
    """Marshrutdagi chiziq almashtirish nuqtalarini topadi."""
    if len(yol) < 3:
        return []

    natija = []
    joriy_chiziq = None

    for i in range(len(yol) - 1):
        umumiy = graf.chiziqlari(yol[i]) & graf.chiziqlari(yol[i + 1])
        if not umumiy:
            continue

        chiziq = sorted(umumiy)[0]
        if joriy_chiziq is not None and chiziq != joriy_chiziq:
            natija.append((yol[i], joriy_chiziq, chiziq))
        joriy_chiziq = chiziq

    return natija

# qidiruv.py
"""Bekat nomini xato yozganda taklif beradi."""


def tahrirlash_masofasi(birinchi, ikkinchi):
    """Levenshtein masofasi. DP, O(n * m)."""
    birinchi, ikkinchi = birinchi.lower(), ikkinchi.lower()
    n, m = len(birinchi), len(ikkinchi)

    if n == 0:
        return m
    if m == 0:
        return n

    oldingi = list(range(m + 1))

    for i in range(1, n + 1):
        joriy = [i] + [0] * m
        for j in range(1, m + 1):
            narx = 0 if birinchi[i - 1] == ikkinchi[j - 1] else 1
            joriy[j] = min(
                oldingi[j] + 1,          # o'chirish
                joriy[j - 1] + 1,        # qo'shish
                oldingi[j - 1] + narx,   # almashtirish
            )
        oldingi = joriy

    return oldingi[m]


def takliflar(graf, kiritilgan, nechta=3):
    """Eng o'xshash bekat nomlarini qaytaradi."""
    kiritilgan_past = kiritilgan.lower().strip()
    natijalar = []

    for bekat in graf.bekatlar():
        bekat_past = bekat.lower()

        # Prefiks mos kelsa - eng yuqori prioritet
        if bekat_past.startswith(kiritilgan_past):
            ball = 0
        elif kiritilgan_past in bekat_past:
            ball = 1
        else:
            ball = 2 + tahrirlash_masofasi(kiritilgan_past, bekat_past)

        natijalar.append((ball, bekat))

    natijalar.sort()
    return [bekat for ball, bekat in natijalar[:nechta] if ball < 10]

# asosiy.py
"""Metro marshrut qidiruvchi - asosiy dastur."""

from metro_graf import MetroGraf
from marshrut import eng_tez_marshrut, eng_kam_bekat, almashtirishlar
from qidiruv import takliflar
from metro_malumot import CHIZIQLAR

KENGLIK = 58


def sarlavha(matn):
    print("=" * KENGLIK)
    print(f"{matn:^{KENGLIK}}")
    print("=" * KENGLIK)


def bekat_sora(graf, xabar):
    """To'g'ri bekat nomi kiritilgunicha so'raydi, taklif beradi."""
    while True:
        kiritilgan = input(xabar).strip()

        if not kiritilgan:
            print("  ! Bekat nomini kiriting.")
            continue

        if graf.bormi(kiritilgan):
            return kiritilgan

        mos_kelganlar = takliflar(graf, kiritilgan)
        if not mos_kelganlar:
            print(f"  ! '{kiritilgan}' topilmadi.")
            continue

        print(f"  ! '{kiritilgan}' topilmadi. Balki quyidagilardan biri?")
        for raqam, bekat in enumerate(mos_kelganlar, start=1):
            print(f"      {raqam}. {bekat}")

        tanlov = input("    Raqamni tanlang (yoki qaytadan yozing): ").strip()
        if tanlov.isdigit() and 1 <= int(tanlov) <= len(mos_kelganlar):
            return mos_kelganlar[int(tanlov) - 1]


def marshrutni_chiqar(graf, yol, vaqt=None):
    """Marshrutni chiroyli ko'rinishda chiqaradi."""
    print()
    sarlavha("MARSHRUT")

    almashtirish_nuqtalari = {b: (a, c) for b, a, c in almashtirishlar(graf, yol)}

    for raqam, bekat in enumerate(yol, start=1):
        belgi = "*" if graf.almashtirish_bekatimi(bekat) else "."
        chiziqlar = ", ".join(sorted(graf.chiziqlari(bekat)))
        print(f"  {raqam:>2}. {belgi} {bekat:<26}{chiziqlar}")

        if bekat in almashtirish_nuqtalari:
            eski, yangi = almashtirish_nuqtalari[bekat]
            print(f"        >>> '{eski}' dan '{yangi}' chizig'iga o'ting")

    print("-" * KENGLIK)
    print(f"  Bekatlar soni:     {len(yol)}")
    print(f"  O'tish joylari:    {len(almashtirish_nuqtalari)}")
    if vaqt is not None:
        print(f"  Taxminiy vaqt:     {vaqt:.0f} daqiqa")
    print("=" * KENGLIK)


def chiziqlarni_chiqar(graf):
    print()
    sarlavha("METRO CHIZIQLARI")
    for nomi, malumot in CHIZIQLAR.items():
        print(f"\n  {nomi} ({malumot['rang']}) - {len(malumot['bekatlar'])} bekat")
        for bekat in malumot["bekatlar"]:
            belgi = "*" if graf.almashtirish_bekatimi(bekat) else " "
            print(f"    {belgi} {bekat}")
    print("\n  * - o'tish bekati")
    print("=" * KENGLIK)


def statistikani_chiqar(graf):
    malumot = graf.statistika()
    print()
    sarlavha("TARMOQ STATISTIKASI")
    print(f"  {'Chiziqlar soni:':<28}{malumot['chiziqlar']:>10}")
    print(f"  {'Bekatlar soni:':<28}{malumot['bekatlar']:>10}")
    print(f"  {'Bog‘lanishlar (qirralar):':<28}{malumot['qirralar']:>10}")
    print(f"  {'O‘tish bekatlari:':<28}{malumot['almashtirish']:>10}")

    # Eng ko'p bog'lanishga ega bekatlar
    print("\n  Eng gavjum bekatlar:")
    darajalar = [(len(graf.qoshnilar(b)), b) for b in graf.bekatlar()]
    for daraja, bekat in sorted(darajalar, reverse=True)[:5]:
        print(f"    {bekat:<28}{daraja} ta yo'nalish  {'#' * daraja}")
    print("=" * KENGLIK)


def menyu():
    graf = MetroGraf()

    while True:
        print("\n" + "=" * KENGLIK)
        print(f"{'TOSHKENT METRO MARSHRUT QIDIRUVCHI':^{KENGLIK}}")
        print("=" * KENGLIK)
        print("  1 - Eng tez marshrut (Dijkstra)")
        print("  2 - Eng kam bekatli marshrut (BFS)")
        print("  3 - Ikkalasini taqqoslash")
        print("  4 - Barcha chiziqlar")
        print("  5 - Tarmoq statistikasi")
        print("  0 - Chiqish")

        tanlov = input("\nTanlovingiz: ").strip()

        if tanlov == "0":
            print("\nXayr! Yo'lingiz bexatar bo'lsin.")
            break

        if tanlov in {"1", "2", "3"}:
            boshlanish = bekat_sora(graf, "\nQayerdan: ")
            manzil = bekat_sora(graf, "Qayerga:  ")

            if tanlov == "1":
                yol, vaqt = eng_tez_marshrut(graf, boshlanish, manzil)
                if yol:
                    marshrutni_chiqar(graf, yol, vaqt)
                else:
                    print("\n  ! Marshrut topilmadi.")

            elif tanlov == "2":
                yol = eng_kam_bekat(graf, boshlanish, manzil)
                if yol:
                    marshrutni_chiqar(graf, yol)
                else:
                    print("\n  ! Marshrut topilmadi.")

            else:
                tez_yol, vaqt = eng_tez_marshrut(graf, boshlanish, manzil)
                kam_yol = eng_kam_bekat(graf, boshlanish, manzil)

                print()
                sarlavha("TAQQOSLASH")
                print(f"  {'Mezon':<24}{'Eng tez':>14}{'Eng kam bekat':>16}")
                print("-" * KENGLIK)
                print(f"  {'Bekatlar soni':<24}{len(tez_yol):>14}{len(kam_yol):>16}")
                print(f"  {'O‘tish joylari':<24}"
                      f"{len(almashtirishlar(graf, tez_yol)):>14}"
                      f"{len(almashtirishlar(graf, kam_yol)):>16}")
                print(f"  {'Vaqt (daqiqa)':<24}{vaqt:>14.0f}{'-':>16}")
                print("=" * KENGLIK)

                if tez_yol == kam_yol:
                    print("\n  Ikkala marshrut bir xil.")
                marshrutni_chiqar(graf, tez_yol, vaqt)

        elif tanlov == "4":
            chiziqlarni_chiqar(graf)
        elif tanlov == "5":
            statistikani_chiqar(graf)
        else:
            print("  ! Noto'g'ri tanlov.")


if __name__ == "__main__":
    try:
        menyu()
    except KeyboardInterrupt:
        print("\n\nDastur to'xtatildi.")

python asosiy.py