Python ćwiczenie - palindrom

Wykonujemy ćwiczenie sprawdzające, czy dany wyraz jest palindromem. Zrobimy to na klika sposobów, wykorzystując język Python.

Palindrom to taki wyraz, który zapisany od tyłu daje to samo słowo co od przodu. Najlepszym przykładem palindromu może być imię „anna” albo wyraz „kajak”.

Sprawdzenie, czy dany wyraz jest palindromem, napisanie takiej funkcji, to bardzo częste zadanie na różnych rozmowach kwalifikacyjnych bądź w ramach ćwiczenia na różnych stopniach uczenia się programowania.

Sposób 1 – odwrócenie

Napiszmy taką funkcję w Pythonie:

def is_palindrome(word):
    return word == word[::-1]

print(is_palindrome("anna"))
#True
print(is_palindrome("kajak"))
#True

To najłatwiejszy sposób na zabranie się za to zadanie. Zwracamy warunek, że nasze słowo równa się naszemu słowu zapisanemu wspak. Oczywiście, można to opisać w sposób bardziej obszerny:

def is_palindrome(word):
    if word == word[::-1]:
        return True
    else:
        return False

print(is_palindrome("anna"))
#True
print(is_palindrome("kajak"))
#True

Albo i lekko mniej obszerny:

def is_palindrome(word):
    if word == word[::-1]:
        return True
    return False

print(is_palindrome("anna"))
#True
print(is_palindrome("kajak"))
#True

W obu przypadkach sprawdzamy, czy wyraz to to samo co wyraz zapisany wspak i zwracamy prawdę a w przeciwnym wypadku fałsz. Aczkolwiek samo sprawdzenie czy wyraz i wyraz wspak to to samo już nam daje prawdę/fałsz i to zastosowaliśmy w pierwszym przykładzie. Taką funkcję można zapisać jako lambdę:

is_palindrome = lambda word: word == word[::-1]
print(is_palindrome("anna"))
#True
print(is_palindrome("kajak"))
#True

Przyjmuje słowo, zwraca wynik porównania słowa ze słowem wspak i jest albo prawda albo fałsz.

Dociekliwi mogą zauważyć, że przecież „anna” mogła zostać zapisana wielką literą i wtedy takie porównanie da nam fałsz (w każdym z prezentowanych przypadków) a przecież taki wyraz palindromem jest:

is_palindrome = lambda word: word == word[::-1]
print(is_palindrome("Anna"))
#False
print(is_palindrome("kajak"))
#True

W takim wypadku należy przed porównaniem opuścić nasz wyraz do małej litery. Niech „Anna” albo „ANNA” zostanie zamienione na „anna” i po problemie:

def is_palindrome(word):
    return word.lower() == word[::-1].lower()

print(is_palindrome("anna"))
#True
print(is_palindrome("Anna"))
#True

Możemy to zapisać inaczej, żeby zbytnio się nie powtarzać:

def is_palindrome(word):
    word = word.lower()
    return word == word[::-1]

print(is_palindrome("anna"))
#True
print(is_palindrome("Anna"))
#True

Natomiast w funkcji lambda musielibyśmy wszystko zapisać w jednej linijce, lambda nie ma wcięcia na ciało funkcji więc musi być jednolinijkowcem:

is_palindrome = lambda word : word.lower() == word[::-1].lower()

print(is_palindrome("anna"))
#True
print(is_palindrome("Anna"))
#True

Sposób 2 – pętla for, reversed, enumerate

Możemy zastosować inne podejście. Mamy coś takiego jak pętla for oraz funkcja reversed:

for letter in reversed("Hello"):
    print(letter)

Mamy coś takiego jak enumerate, które pozwala nam się dobrać do indeksu:

for idx, letter in enumerate(reversed("Hello")):
    print(idx, letter)
#0 o
#1 l
#2 l
#3 e
#4 H

A zatem połączmy to:

def is_palindrome(word):
    for idx, letter in enumerate(reversed(word)):
        if letter != word[idx]:
            return False
    return True
print(is_palindrome("anna"))
#True
print(is_palindrome("hello"))
#False

Tutaj bierzemy wyraz, np. „anna”. Następnie iterujemy po indeksie i literze tego wyrazu zapisanego wspak. I sprawdzamy czy „anna” i „anna” wspak mają takie same litery pod tym samym indeksem. Jeżeli nie – fałsz. Jeżeli tak, pętla się kończy, zwracamy prawdę.

„anna” i „anna” wspak mają takie same litery pod tymi samymi indeksami. „hello” i „olleh” nie – już pod indeksem zerowym jeden wyraz ma 'h’ zaś drugi 'o’.

Może sposób trudniejszy i wymaga nieco intelektualnego wysiłku, ale zazwyczaj po to się te ćwiczenia wymyśla, aby się trochę pobawić a nie iść na łatwiznę i pozwalać komputerowi robić wszystko za nas.

Za nas to on może co najwyżej zmniejszyć litery do małych aby „Anna” zapisana wspak i normalnie miała dokładnie to samo pod każdym indeksem:

def is_palindrome(word):
    word = word.lower()
    for idx, letter in enumerate(reversed(word)):
        if letter != word[idx]:
            return False
    return True
print(is_palindrome("anna"))
#True
print(is_palindrome("Anna"))
#True
print(is_palindrome("hello"))
#False

Sposób 3 – dwa wskaźniki

Kolejny sposób dla lubiących się bawić. Tutaj podam przykład, który wypisała mi sztuczna inteligencja poproszona o taką funkcję z metodą dwóch wskaźników, omówimy go sobie:

def is_palindrome(s):
    # Convert the string to lowercase and remove non-alphanumeric characters
    s = ''.join(char.lower() for char in s if char.isalnum())

    # Initialize two pointers, one at the beginning and one at the end of the string
    left, right = 0, len(s) - 1

    # Iterate until the pointers meet
    while left < right:
        # If characters at the pointers don't match, return False
        if s[left] != s[right]:
            return False
        # Move the pointers towards the center
        left += 1
        right -= 1

    # If the loop completes without finding a mismatch, the string is a palindrome
    return True


# Test the function
print(is_palindrome("A man, a plan, a canal, Panama"))  # True
print(is_palindrome("race a car"))  # False
print(is_palindrome("anna"))
#True
print(is_palindrome("Anna"))
#True
print(is_palindrome("hello"))
#False

Czyli tak, rzecz pierwsza – palindrom to może być nie tylko „anna” czy też „Anna” (której litery trzeba zmniejszyć do małej aby funkcja działała) ale także zdanie zawierające spacje, znaki i tak dalej.

Zatem bierzemy nasz napis i zapisujemy do niego (w pewien sposób filtrujemy) tylko te znaki, które są alfanumeryczne, w dodatku zapisujemy małą literą. Tak to wygląda:

msg = "A man, a plan, a canal, Panama"
print(''.join(char.lower() for char in msg if char.isalnum()))
#amanaplanacanalpanama

Następnie musimy utworzyć lewy i prawy wskaźnik. Wskaźnik lewy to indeks 0, wskaźnik prawy to długość (czyli funkcja len) ale -1 bo indeksuje się od zera. Proszę zobaczyć:

name = "Anna"
left = 0
right = len(name) -1
print(name[left]) #A
print(name[right]) #a

Dla ułatwienia napisałem pierwszą literę wielką, żebyśmy widzieli, co się mniej więcej dzieje. A teraz pomyślmy, jakby tu te wskaźniki przesunąć.

Aby lewy poszedł w prawo zwiększymy go o 1, zaś aby prawy poszedł w lewo – zmniejszymy go o 1. Tak to wygląda:

name = "Anna"
left = 0
right = len(name) -1
print(name[left]) #A
print(name[right]) #a
left += 1
print(name[left]) #n
right -= 1
print(name[right]) #n

Teraz potrzebna nam pętla while, która sprawdza, czy wskaźniki się nie minęły,

def is_palindrome(s):

    s = ''.join(char.lower() for char in s if char.isalnum())
    left, right = 0, len(s) - 1

    while left < right:

        if s[left] != s[right]:
            return False

        left += 1
        right -= 1

    return True


print(is_palindrome("A man, a plan, a canal, Panama"))  # True
print(is_palindrome("race a car"))  # False
print(is_palindrome("anna"))
#True
print(is_palindrome("Anna"))
#True
print(is_palindrome("hello"))
#False

Tak długo, jak lewy jest mniejszy od prawego mamy do czynienia z sytuacją, w której lewy idzie do środka i prawy idzie do środka. W przypadku „anna” najpierw lewy to 0 a prawy to 3, porównanie „a” do „a”. Potem lewy to 1 a prawy to 2, porównanie „n” do „n”. Potem lewy to 2 a prawy to 1, a to oznacza, że pora wychodzić z pętli bo już nic do porównania nam nie zostało.

I to się dzieje. Jeżeli tylko wszystkie litery z lewej i prawej były takie same nie otrzymaliśmy return False, a zatem pora zwrócić True czyli prawdę.

Tak ta funkcja działa. Częste zadanie na myślenie w sposób algorytmiczny, rozwiązywanie problemów. Oczywiście – sposób pierwszy jest jak najbardziej na miejscu, pokazuje naszą znajomość Pythona i umiejętność wykorzystania tej wiedzy do pisania łatwego i czytelnego kodu.

W tym przykładzie w zasadzie każdy sposób jest dobry a nawet można by pokusić się o stworzenie kilku nowych. Każdy sposób obrazuje naszą umiejętność rozwiązywania zadania przy użyciu wiedzy z Pythona i własnego, logicznego myślenia.

Zadanie – sposób z wykorzystaniem listy

Zróbmy sobie zatem takie zadanie, w którym ten konkretny problem mamy rozwiązać za pomocą listy. Nie używamy dwóch wskaźników, w każdym razie nie w taki sposób, nie używamy reversed ani innych sztuczek, takich jak [::-1] które listę też tam odwrócą, chcemy, aby rozwiązać to zadanie w sposób tak „listowy” jak to tylko możliwe.

Rzecz pierwsza, zamiana „anna” na listę:

name = "anna"
lst = list(name)
print(lst)
#['a', 'n', 'n', 'a']

Inny sposób, bardziej nam przydatny:

name = "anna"
lst = [letter for letter in name]
print(lst)
#['a', 'n', 'n', 'a']

Rzecz druga, zamiana wielkich liter na małe:

name = "Anna"
lst = [letter.lower() for letter in name]
print(lst)
#['a', 'n', 'n', 'a']

Rzecz trzecia, pozbycie się zbędnych spacji i innych znaków niealfanumerycznych:

name = "Anna anna"
lst = [letter.lower() for letter in name if letter.isalnum()]
print(lst)
#['a', 'n', 'n', 'a', 'a', 'n', 'n', 'a']

Rzecz piąta, jak z listy „zrzucić” ostatnią literę:

name = "Anna"
lst = [letter.lower() for letter in name if letter.isalnum()]
print(lst)
#['a', 'n', 'n', 'a']
right = lst.pop()
print(right) #a

Rzecz szósta, jak zrzucić pierwszy element:

name = "Anna"
lst = [letter.lower() for letter in name if letter.isalnum()]
print(lst)
#['a', 'n', 'n', 'a']
right = lst.pop()
print(right) #a
left = lst.pop(0)
print(left) #a
print(lst) #['n', 'n']

Rzecz nr 7, jak wypisać w pętli „a” „a” oraz „n” „n” z anny?

name = "Anna"
lst = [letter.lower() for letter in name if letter.isalnum()]
print(lst)
#['a', 'n', 'n', 'a']
while len(lst) > 0:
    print(lst.pop())
    print(lst.pop(0))

Rzecz nr 8, co zrobić z kajakiem? W przypadku wyrazu „kajak” interesuje nas „k” „k” oraz „a” „a”, „j” już nie ma z czym porównywać. A zatem ma działać i na annie („a” „a”, „n” „n”) i na kajaku („k” „k”, „a” „a”).

name = "anna"
lst = [letter.lower() for letter in name if letter.isalnum()]
print(lst)
#['a', 'n', 'n', 'a']
while len(lst) > 1:
    print(lst.pop())
    print(lst.pop(0))

name = "kajak"
lst = [letter.lower() for letter in name if letter.isalnum()]
print(lst)
#['k', 'a', 'j', 'a', 'k']
while len(lst) > 1:
    print(lst.pop())
    print(lst.pop(0))

Teraz zbieramy całość „do kupy”:

def is_palindrome(s):
    lst = [letter.lower() for letter in s if letter.isalnum()]
    while len(lst) > 1:
        left = lst.pop(0)
        right = lst.pop()
        if left != right:
            return False
    return True

print(is_palindrome("anna")) #True
print(is_palindrome("kajak")) #True
print(is_palindrome("hello")) #False

Czyli nasz s (od string, napis) zamieniamy na listę znaków tylko alfanumerycznych zapisanych do małej litery, bez spacji i znaków specjalnych.

Następnie tak długo jak długość listy jest większa niż 1 (czyli lista nie jest pusta, jak po zrzuceniu „a” „a” oraz „n” „n” z „anna” ani nie ma jednego elementu np. „j” jak kajak po zrzuceniu „k” „k” oraz „a” „a”) bierzemy sobie zmienną left, do której pakujemy zrzucony element z lewej strony listy oraz zmienną right, do której pakujemy zrzucony element z prawej strony listy.

Jeżeli te elementy nie są takie same to pora zwrócić False.

Jeżeli pętla nam się skończyła (lista jest albo pusta, albo jednoelementowa) to pora zwracać True, prawdę, bo mamy do czynienia z palindromem.

Jestem pewien, że jak człowiek pomyśli, to znajdzie jeszcze kolejne sposoby na rozwiązanie tego problemu. Natomiast wydaje mi się, że tyle wystarczy.

Python ćwiczenie – palindrom

Sposób 1 – odwrócenie

Sposób 2 – pętla for, reversed, enumerate

Sposób 3 – dwa wskaźniki

Zadanie – sposób z wykorzystaniem listy