Python ćwiczenie - kwadraty liczb

Rozwiązujemy ćwiczenie na trzy sposoby. Zobaczymy, że nieposortowane dane w listach można posortować, w drugim przykładzie nauczymy się pisać funkcje, które nie modyfikują oryginalnych tablic, nawet jeśli wewnątrz funkcji chcemy je sobie zmodyfikować – zobaczymy jak łatwo o funkcję, która niechcący modyfikuje pewne dane. Trzeci przykład nauczy nas podejścia „frequency counter”, często używanego w problemach algorytmicznych.

Ćwiczenie polega na tym, że dostajemy dwie nieposortowane listy. Jedna ma zawierać liczby, zaś druga – kwadraty tych liczb.

A zatem poniższy kod ma zwrócić prawdę:

our_func([1,2,3], [1,4,9])
#True

Mamy tutaj liczby 1,2,3 oraz ich kwadraty 1,4,9. Nasza funkcja ma zwrócić True.

Nasze liczby mogą występować w dowolnej ilości, pod warunkiem, że mamy taką samą liczbę kwadratów:

our_func([1,2,2,3], [1,4,4,9])
#True
our_func([1,2,2,3], [1,4,9])
#False

Mamy dwa razy liczbę 2 i dwa jej kwadraty 4 – funkcja zwraca True.

Ostatnią rzeczą, o której musimy pamiętać – liczby mogą być w dowolnej kolejności:

our_func([3,1,2], [4,9,1])
#True

Podejście pierwsze – pętla, sortowanie

Wiemy, że jeżeli nasze tablice nie będą równej długości, to musimy zwrócić fałsz, bo nie ma takiej opcji, aby zawierały one liczby i odpowiadające im kwadraty, jeżeli się różnią długością.

def compare_arrays(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

Teraz musimy sobie te tablice posortować, ponieważ te liczby są tam w różnych kolejnościach:

def compare_arrays(arr1, arr2):
    if len(arr1) != len(arr2):
        return False
    arr1.sort()
    arr2.sort()
    print(arr1, arr2)

compare_arrays([1,3,2], [9,4,1])
#[1, 2, 3] [1, 4, 9]

Teraz, mając posortowane tablice jednakowej długości, możemy przejść po indeksach dowolnej z tablic i sprawdzić, czy wartość pod indeksem tablicy pierwszej podniesiona do kwadratu odpowiada wartości z tablicy drugiej o tym samym indeksie:

def compare_arrays(arr1, arr2):
    if len(arr1) != len(arr2):
        return False
    arr1.sort()
    arr2.sort()
    for idx in range(len(arr1)):
        if arr1[idx] ** 2 != arr2[idx]:
            return False
    return True

print(compare_arrays([1,2,3], [1,4,9]))
#True
print(compare_arrays([1,2,3], [1,3,9]))
#False

Gotowe.

Sposób 2 – sorted, zip

Zobaczmy na dość osobliwe działanie naszej funkcji z przykładu pierwszego:

a1 = [3,1,2]
a2 = [4,9,1]

def compare_arrays(arr1, arr2):
    if len(arr1) != len(arr2):
        return False
    arr1.sort()
    arr2.sort()
    for idx in range(len(arr1)):
        if arr1[idx] ** 2 != arr2[idx]:
            return False
    return True

print(compare_arrays(a1, a2))
#True
print(a1, a2)
#[1, 2, 3] [1, 4, 9]

Wydawałoby się, że wszystko ok – funkcja dała radę dobrze porównać tablice, które nie były posortowane i znajdowały się w zmiennych a1 i b2.

Problem w tym, że te tablice zostały posortowane. I nie działo się to „wewnątrz” funkcji – zmienne a1 i b2 zostały posortowane, uległy zmianie.

Dzieje się tak, ponieważ zmienne przekazywane do funkcji są przez referencję zaś sort to metoda in-place, która modyfikuje oryginalną tablicę.

Możemy to poprawić, używając sorted oraz zip:

a1 = [3,1,2]
a2 = [4,9,1]

def compare_arrays(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    for num, square in zip(sorted(arr1), sorted(arr2)):
        if num ** 2 != square:
            return False
    return True

print(compare_arrays(a1, a2))
#True
print(a1, a2)
#[3, 1, 2] [4, 9, 1]

Funkcja sorted zwraca posortowaną kopię tablicy, zaś zip pozwala nam połączyć dwie listy o jednakowej długości w listę krotek zawierające pary elementów.

To się w naszym przykładzie dzieje, dzięki czemu nie tylko nie modyfikujemy oryginalnych list, ale też ten przykład jest w mojej ocenie bardziej czytelny.

Sposób 3 – frequency counter

Zobaczmy na taką funkcję, której użyjemy, jako funkcji pomocniczej:

def count_elements(arr):
    element_count = {}
    for element in arr:
        if element in element_count:
            element_count[element] += 1
        else:
            element_count[element] = 1
    return element_count


arr = [1, 2, 3, 4, 1, 2, 1]
print(count_elements(arr))  
# {1: 3, 2: 2, 3: 1, 4: 1}

Jak widać zlicza ona ilość wystąpień danego elementu w tablicy i pakuje to do słownika. Nie jest przesadnie trudna.

Najwyższa pora użyć tej funkcji do zliczania ilości wystąpień i sprawdzić, czy dostajemy listę, w której po lewej stronie mamy liczby, po prawej – kwadraty tych liczb, w odpowiedniej ilości.

def compare_arrays(arr1, arr2):
    counter1 = count_elements(arr1)
    counter2 = count_elements(arr2)
    for key in counter1.keys():
        if not (key**2) in counter2.keys():
            return False
        if counter2[key**2] != counter1[key]:
            return False
    return True

Nie musimy niczego sortować. Tworzymy dwa liczniki, jeden dla liczb, drugi dla kwadratów.

Przechodzimy po kluczach licznika pierwszego. Jeżeli taki klucz to np. 2, to wiemy, że licznik drugi musi zawierać klucz, który się nazywa 4, inaczej oblewa warunek – nie ma nawet jednego kwadratu liczby z pierwszej listy.

Drugi warunek, to sprawdzenie, czy kwadrat liczby i liczba występują w odpowiedniej ilości. Np. dwie liczby 3 i dwie liczby 9 w kwadratach.

A teraz cały przykład:

def count_elements(arr):
    element_count = {}
    for element in arr:
        if element in element_count:
            element_count[element] += 1
        else:
            element_count[element] = 1
    return element_count

def compare_arrays(arr1, arr2):
    counter1 = count_elements(arr1)
    counter2 = count_elements(arr2)
    for key in counter1.keys():
        if not (key**2) in counter2.keys():
            return False
        if counter2[key**2] != counter1[key]:
            return False
    return True

print(compare_arrays([1,2,3,3], [1,4,9,9]))
#True
print(compare_arrays([1,2,3,3], [1,4,9]))
#False

Jak widać wszystko działa, w dodatku użyliśmy podejścia „frequecy counter” czyli zliczania ilości wystąpień danego elementu w liście i zapisywania w słowniku.

Takie podejście jest często używane w różnego rodzaju problemach algorytmicznych i warto je znać.

Dalsza lektura

Counter w Pythonie – jak napisać funkcję count_elements, na kilka sposobów – obszerny opis
Anagram w Pythonie – bardzo podobne zadanie, w którym również możemy zastosować „frequency counter” jako jedno z podejść
Kwadraty liczb w JS – to samo zadanie co w tym artykule wykonane na 3 sposoby w języku JavaScript

Wyzwanie – napisz to w JS

Przeczytaj ten artykuł – opisuje on to samo zadanie, ale wykonane w języku JavaScript.

Odpal edytor albo kompilator online obsługujący JavaScript.

Postaraj się wziąć sposób 2 z tego artykułu i napisać go w JavaScript, bazując na artykule w JS.

Pamiętaj – funkcja sort działa w Pythonie i JS tak samo, tj. sortuje tablicę in-place, modyfikując ją, ale w JS musimy jeszcze podać callback.

Funkcja sorted w Pythonie zwraca posortowaną kopię tablicy, zaś w JS służy do tego metoda toSorted (trzeba jej podać callback).

W języku JavaScript nie mamy funkcji zip – to kolejne wyzwanie.

Wyzwanie nie jest łatwe i wymaga dobrej znajomości zarówno Pythona jak i JavaScript.

Python ćwiczenie – kwadraty liczb

Podejście pierwsze – pętla, sortowanie

Sposób 2 – sorted, zip

Sposób 3 – frequency counter

Dalsza lektura

Wyzwanie – napisz to w JS