Porównywanie tekstów — palindromy i anagramy

🎯 Po co Ci to?

„Kobyła ma mały bok". „A to kanapa pana Kota". Czytane od tyłu — to samo zdanie. Zabawa? Owszem, ale spróbuj kazać komputerowi to sprawdzić, a odkryjesz, że pod błahym pytaniem siedzi cała maszyneria: porównywanie znak po znaku, czyszczenie danych, dwa zupełnie różne pomysły na „te same litery w innej kolejności". Porównywanie tekstów to chleb powszedni informatyki — od wykrywania duplikatów w bazie, przez sprawdzanie haseł, po systemy antyplagiatowe — i dziś opanujesz jego fundamenty.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• porównywać teksty co do znaku i słownikowo — oraz wskazać, kiedy które porównanie jest właściwe;
• sprawdzić, czy tekst jest palindromem — także „po ludzku", z pominięciem spacji i wielkości liter;
• rozstrzygnąć, czy dwa wyrazy są anagramami — metodą zliczania i metodą sortowania.

🔁 Przypomnij sobie

Z 3.4: napis to sekwencja znaków, indeksy od zera, odwracanie pętlą, porządek słownikowy; z 2.5: znak = numer w tablicy (dlatego "A" < "a").

📘 Wyjaśnienie

Równość i porządek. == porównuje znak po znaku — i jest bezlitosne: "Ala" == "ala" to False, bo A (65) i a (97) to różne numery. Gdy chcesz porównywać „po ludzku", najpierw ujednolić: napis.lower() zwraca wersję pisaną małymi literami. Porządek </> znasz z 3.4 — słownikowy, po numerach znaków. To wystarczy, by teksty sortować (dział 6 zrobi z tego użytek).

Palindromy. Wersja szkolna jest jednolinijkowa — masz ją z jednostki 3.4: odwróć i porównaj. Ale prawdziwe palindromy zdaniowe („Kobyła ma mały bok") psują zabawę spacjami i wielkimi literami. Zawodowe podejście: najpierw oczyść, potem sprawdzaj:

def palindrom(tekst):
    czysty = ""
    for znak in tekst.lower():
        if znak != " ":               # zostaw tylko litery (spacje precz)
            czysty = czysty + znak
    wspak = ""
    for znak in czysty:
        wspak = znak + wspak
    return czysty == wspak

Dwie fazy — czyszczenie i test — to wzorzec ogólniejszy niż palindromy: dane wejściowe niemal nigdy nie przychodzą w postaci gotowej do algorytmu. Oczyszczanie (normalizacja) bywa połową roboty.

💭 Pomyśl: Palindrom da się też sprawdzić bez budowania odwrotności: porównuj pierwszy znak z ostatnim, drugi z przedostatnim… Zapisz warunek na indeksach: który znak porównujesz z którym i kiedy możesz przestać?

Anagramy. Dwa wyrazy są anagramami, gdy zawierają te same litery w tych samych ilościach: „karta" i „katar", „los" i „sol". Porównanie wprost nie zadziała (kolejność inna!) — potrzebny pomysł. Są dwa klasyczne.

Metoda 1: zliczanie. Policz wystąpienia każdej litery w obu wyrazach i porównaj liczniki:

def anagramy(a, b):
    if len(a) != len(b):
        return False                  # różne długości? koniec dyskusji
    for znak in "abcdefghijklmnopqrstuvwxyz":
        if a.count(znak) != b.count(znak):
            return False
    return True

(napis.count(znak) zlicza wystąpienia — to gotowa metoda napisu, taki licznik z 3.3 w jednej wywołaniu.)

Metoda 2: sortowanie. Posortuj litery obu wyrazów — anagramy dadzą identyczny wynik: „karta" → aakrt, „katar" → aakrt. W Pythonie sorted(a) == sorted(b) i po sprawie. Elegancko, prawda? Sortowanie jeszcze poznasz od podszewki (dział 6) — tu występuje w roli, którą pełni zaskakująco często: normalizatora, sprowadzającego różne układy do jednej postaci kanonicznej. Dwa obiekty są „takie same z dokładnością do kolejności" wtedy i tylko wtedy, gdy po posortowaniu są identyczne.

Która metoda lepsza? Zliczanie robi 26 przebiegów count (albo, sprytniej, jeden przebieg z tablicą liczników); sortowanie — jedno wywołanie, ale sortowanie ma swój koszt. Dla wyrazów — bez różnicy. Dla porównywania milionów dokumentów — zliczanie jednym przebiegiem wygrywa. Znów: dwa poprawne algorytmy, wybór należy do Ciebie.

🐞 Znajdź błąd

Program ma sprawdzać anagramy „po ludzku" (ignorując wielkość liter):

def anagramy(a, b):
    return sorted(a.lower()) == sorted(b.lower())

print(anagramy("Kot", "tok"))        # True — działa!
print(anagramy("rok", "kra"))        # ???

Drugi wynik będzie błędny w subtelny sposób — a właściwie... sprawdź najpierw ręcznie, czy „rok" i „kra" to anagramy, potem znajdź prawdziwy problem tej funkcji.

🌍 Powiązania

Anagramy i palindromy wyglądają na zabawę słowną, ale ich algorytmy pracują na poważnych posadach: zliczanie znaków to podstawa analizy częstości (jednostka 5.5 użyje jej do łamania szyfrów!), normalizacja przez sortowanie wykrywa duplikaty „z dokładnością do kolejności" (playlisty, składniki przepisów, przelewy), a porównywanie z czyszczeniem to codzienność każdej wyszukiwarki, która ignoruje wielkość liter i polskie ogonki.

🛠️ Teraz Ty

Bez komputera: rozstrzygnij metodą zliczania, czy anagramami są „algorytm" i „logarytm" (tak — a to spore szczęście dla tej książki). Z komputerem: napisz palindrom w wersji z indeksami (bez budowania odwrotności) i przetestuj na: „kajak", „Kobyła ma mały bok", „ab", „a", „" (pusty!). Który przypadek brzegowy wymagał zastanowienia?

📐 Definicje tej lekcji

• Normalizacja — sprowadzenie danych do postaci porównywalnej (małe litery, bez spacji) przed właściwym algorytmem.
• Palindrom — tekst równy swojemu odwróceniu (po normalizacji); test parami indeksów $i$ oraz $n-1-i$ do połowy.
• Anagramy — teksty o identycznych licznikach liter; test przez zliczanie albo przez porównanie posortowanych znaków.

📌 Najważniejsze w pigułce

• == porównuje numery znaków — „po ludzku" znaczy: najpierw znormalizuj.
• Palindrom sprawdzaj parami z dwóch końców — bez kopii, z natychmiastową ewakuacją.
• Anagramy = te same liczniki liter; sortowanie znaków to uniwersalny trik „taki sam z dokładnością do kolejności".

🎒 Zadania

1. Sprawdź ręcznie (parami indeksów), czy palindromem jest „ANAGRAM ARGANA" (po czyszczeniu: anagramargana, 13 znaków). Które pary porównasz i przy której (jeśli w ogóle) test upadnie?

2. Ułóż trzy pary wyrazów: (a) anagramy będące palindromami… żartuję — (a) anagramy, (b) wyrazy o tych samych literach, ale NIE-anagramy, (c) parę, która testuje brzeg „różne długości". Uzasadnij (b) — czym różni się „te same litery" od „anagram"?

3. Napisz funkcję wspolne_litery(a, b) zwracającą, ile rodzajów liter występuje w obu wyrazach naraz (np. „karta", „trawa" → t, r, a → 3). Wykorzystaj pomysł zliczania.

def wspolne_litery(a, b):
    ile = 0
    for znak in "abcdefghijklmnopqrstuvwxyz":
        if znak in a and znak in b:
            ile = ile + 1
    return ile

🔍 Sprawdź, czy umiesz

• Wyjaśnić, czemu "Ala" != "ala", i pokazać, jak porównywać „po ludzku".
• Sprawdzić palindrom bez budowania odwrotności — i uzasadnić „do połowy".
• Rozstrzygnąć anagramowość dwiema metodami i wskazać, kiedy która wygrywa.