Poniżej rozwiązanie do naszego trzeciego wyzwania

Sprytne potęgowanie

To zadanie nie wymaga większego komentarza, gdy już widzimy rozwiązanie. Rozwiązujemy je tak, jak to zwykle bywa przy takich problemach: najpierw sprawdzamy przypadki szczególne. W tym wypadku jest to sprawdzenie, czy wykładnik nie jest równy 0 lub 1 (przypominamy, że liczba podniesiona do potęgi zerowej jest równa 1). Następnie obliczamy “połowę” potęgi. Aby wykonać tzw. dzielenie całkowitoliczbowe, czyli takie, które, upraszczając, zwróci wynik zaokrąglony do dołu do liczby całkowitej, używamy //. Warto zaznaczyć, że niepoprawne byłoby zapisanie w stylu: potega_wydajnie(podstawa, wykladnik//2)*potega_wydajnie(podstawa, wykladnik//2). Wtedy zmusilibyśmy procesor do wykonania dwa razy tej samej funkcji i zamiast potęgowania sprytnego, mielibyśmy najzwyklejsze potęgowanie z pełną liczbą mnożeń. Dlatego musimy wynik działania tej funkcji przypisać do zmiennej i dopiero pracując na niej, obliczyć jej kwadrat. Ostatecznie sprawdzamy, czy wykładnik był parzysty (czy reszta z dzielenia przez dwa jest równa zero) i w zależności od tego domnażamy jeszcze raz podstawę lub nie.

def potega_wydajnie(podstawa, wykladnik):
    if wykladnik == 1:
        return podstawa
    if wykladnik == 0:
        return 1
    polowa = potega_wydajnie(podstawa, wykladnik//2)
    if wykladnik % 2 == 0:
        return polowa*polowa
    else:
        return polowa*polowa*podstawa

Palindromy

To zadanie można próbować rozwiązywać na dwa sposoby: bardziej w stylu innych języków programowania lub bardziej w stylu Pythona. Rozwiązanie, co do którego mamy pewność, że zadziałałoby w innych językach programowania, wygląda następująco:

def czyPalindrom(napis):
    n = len(napis)
    for i in range(len(napis)//2):
        if napis[i] != napis[n-i-1]:
            return False
    return True

Używamy pętli for, która przechodzi po połowie liter napisu wejściowego. Następnie dla każdej litery obliczamy pozycję odpowiadającej jej litery leżącej w drugiej połowie napisu. Porównujemy je, i jeśli nie są one sobie równe, wiemy, że napis nie ma szans być palindromem. Zaznaczmy, że w przeciwnym wypadku, gdy litery są sobie równe, nie możemy jeszcze zwrócić prawdy, gdyż być może kolejna para liter okaże się sobie nierówna. Możemy to zrobić dopiero po przejrzeniu wszystkich par liter, czyli za pętlą.

Możemy spróbować rozwiązać to zadanie inaczej:

def czyPalindrom2(napis):
    return napis == napis[::-1]

Po prostu tworzymy nowy napis, który ma odwrócone wszystkie litery (napis[::-1]). Następnie porównujemy oryginalny napis z odwróconym. Pozostaje odpowiedzieć na pytanie, które rozwiązanie jest lepsze. Odpowiedź brzmi: to zależy. Rozwiązanie drugie, choć bardzo kuszące, może okazać się zgubne, gdy napis będzie naprawdę bardzo długi. Wtedy tworzymy jego kopię (o odwróconej kolejności liter), która zajmuje drugie tyle miejsca w pamięci. Może się okazać, że pamięć nam się zwyczajnie skończy. Co jednak, gdy pamięci mamy pod dostatkiem? Czy któreś rozwiązanie jest szybsze? Okazuje się, że tu znowu zależy. Gdy mamy do czynienia z palindromem i trzeba przejść po wszystkich znakach napisu, rozwiązanie czyPalindrom2() będzie szybsze, gdyż operacja porównywania napisów zaimplementowana w Pythonie będzie szybsza, niż nasze własne chodzenie po kolejnych literach pętlą for. Nawet narzut na tworzenie odwróconego napisu nie zmieni wyniku. W naszych testach czyPalindrom2() był 100 razy wolniejszy niż czyPalindrom(). Jednak gdy nie mamy do czynienia z palindromem i możemy to rozstrzygnąć na podstawie pierwszej i ostatniej litery, to czyPalindrom() jest górą. Nie mamy tu narzutu na tworzenie nowego napisu, ale już po pierwszym porównaniu zwracamy wynik. Wtedy to czyPalindrom() jest 100 razy szybszy od czyPalindrom2().

Anagramy

To zadanie jest lubiane na testach rekrutacyjnych, gdyż można je rozwiązać na całkiem wiele sposobów. Najważniejszą obserwacją jest to, że liczba poszczególnych liter w jednym napisie musi się zgadzać z liczbą poszczególnych liter w drugim.

Najbardziej naiwna implementacja polegałaby na tym, że dla każdej litery z pierwszego napisu szukalibyśmy w pętli takiej samej litery w napisie drugim. Gdy dla każdego znaku znajdziemy odpowiednią parę, rozstrzygamy, że dwa napisy są anagramami. To rozwiązanie jednak rodzi wiele problemów: co, gdy mamy więcej, niż jeden taki sam znak w pierwszym napisie? Czy nie przydarzy nam się go dopasować do tego samego znaku w drugim napisie? Można oczywiście ratować się listą wartości logicznych, gdzie będziemy zapisywać, które znaki już wykorzystaliśmy. Jednak komplikuje to implementację, a czas wykonania i tak będzie daleki od optymalnego.

Drugim popularnym rozwiązaniem, na jaki wpadają starający się o pracę, jest posortowanie obu napisów alfabetycznie (mądrzej: leksykograficznie), a następnie sprawdzenie, czy są one takie same. Jest to bardzo eleganckie rozwiązanie, zwłaszcza z punktu widzenia matematyki: wprowadzamy pewną postać kanoniczną dla napisu (czyli posortowaną alfabetycznie), następnie oba napisy sprowadzamy do tej postaci kanonicznej, by sprawdzić, czy jest ona taka sama. Jednak z punktu widzenia złożoności obliczeniowej to nadal nie jest najlepsze rozwiązanie.

My przedstawimy następujące podejście: policzymy, ile razy występują poszczególne znaki w obu napisach, a następnie porównamy, czy te liczności się pokrywają. W tym celu użyjemy poznanej w wyzwaniu 3 struktury danych: słownik. Kluczem będzie dany znak, a stowarzyszoną wartością liczba jego wystąpień w napisie. W rozwiązaniu sprawdzamy, czy już napotkaliśmy dany znak. Jeśli tak, to tylko zwiększamy jego wartość o 1. W przeciwnym wypadku dopiero wprowadzamy nową parę klucz-wartość, przyporządkowując liczbę wystąpień równą jeden. Całe szczęście porównanie dwóch słowników jest już zaimplementowane w Pythonie:

def czyAnagram(napis1, napis2):
    n = len(napis1)
    if n != len(napis2):
        return False
    slownik1 = dict()
    slownik2 = dict()
    for i in range(n):
        if napis1[i] in slownik1:
            slownik1[napis1[i]] += 1
        else:
            slownik1[napis1[i]] = 1
        if napis2[i] in slownik2:
            slownik2[napis2[i]] += 1
        else:
            slownik2[napis2[i]] = 1
    return slownik1 == slownik2

Moda

To zadanie jest dość podobne do poprzedniego. Także będziemy zliczać liczbę wystąpień poszczególnych wartości, jednak gdy już to zrobimy, musimy znaleźć największą liczbę wystąpień. W tym celu przejdziemy po wszystkich parach klucz-wartość (metoda items()), znajdziemy największą stowarzyszoną wartość, a następnie zwrócimy odpowiadający jej klucz.

def moda(lista):
    zliczenia = dict()
    for i in range(len(lista)):
        if lista[i] in zliczenia:
            zliczenia[lista[i]] += 1
        else:
            zliczenia[lista[i]] = 1
    maks = -1
    liczba_maks = -1
    for (co, ile) in zliczenia.items():
        if ile > maks:
            liczba_maks = co
            maks = ile
    return liczba_maks

Test rozwiązań

Na zakończenie przykładowa funkcja main(), która testuje poszczególne rozwiązania:

def main():
    print("2^10 = " + str(potega_wydajnie(2, 10)))
    print("czyPalindrom(kajak) = " + str(czyPalindrom("kajak")))
    print("czyPalindrom(kobyla) = " + str(czyPalindrom("kobyla")))
    print("czyPalindrom2(kajak) = " + str(czyPalindrom2("kajak")))
    print("czyPalindrom2(kobyla) = " + str(czyPalindrom2("kobyla")))
    print("czyAnagram(kajak, jaakk) = " + str(czyAnagram("kajak", "jaakk")))
    print("czyAnagram(kobyla, boczek) = " + str(czyAnagram("kobyla", "boczek")))
    print("moda([1,6,4,7,2,8,6,7,6]) = " + str(moda([1,6,4,7,2,8,6,7,6])))


if __name__ == "__main__":
    main()