Akcja Rekrutacja Python 28

Zadanie

Mamy taką oto listę: lista = [1 ,2, 0, 0, 5, 0, 1]

Naszym zadaniem jest sprawienie by wszystkie zera znalazły się po prawej stronie.

Zatem nasza lista będzie wyglądać tak: lista = [1 ,2, 5, 1, 0, 0, 0]

Zanim zaczniemy

Zanim skoczymy w wir rozwiązań warto by zastanowić się nad jedną sprawą. Nasz problem można rozwiązać na dwa sposoby. Pytanie jakie należałoby tu zadać to ”Czy możemy modyfikować podaną listę” ? Lista jest kolekcją typu ”mutable”, a zatem można ją modyfikować na przykład poprzez usuwanie elementów. Zupełnie innym podejściem jest stworzenie na podstawie danej kolekcji zupełnie nowej listy już pozbawionej pewnych wartości. Postaram się przedstawić obydwa podejścia do naszego zadania.

Runda pierwsza

W tym zadaniu tworzymy nową listę.

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    nowa_lista = []
    counter = 0
    for x in lista:
        if x is not 0:
            nowa_lista.append(x) # dodajemy elementy z listy pomijając zera
        else:
            counter += 1 # zliczamy ilość zer

    for _ in range(counter):
        nowa_lista.append(0) # dodajemy zera na koniec
    return nowa_lista

print(zera_na_prawo(lista))

Output:

[1, 2, 5, 1, 0, 0, 0]

Aby sprostać wymaganiom zmuszeni zostaliśmy do użycia aż dwóch pętli. W pierwszej dodajemy do naszej nowej listy wszystkie elementy z wzorcowej listy pilnując by odfiltrować zera. Jednocześnie zliczamy ilość wstąpień zer.

Wiedza o ilości zer w naszej liście przyda nam się w kolejnej pętli. Jej zadaniem jest dodanie odpowiedniej ilości zer na koniec nowej kolekcji.

Runda druga

Pewnie zastanawiasz się czy da rade rozwiązać nasze zadnie używając list składanych. Spróbujmy!

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    return [
        x for x in lista if x is not 0 # lista bez zer
    ] + [0 for x in range(lista.count(0))]# dodajemy zera na koniec

print(zera_na_prawo(lista))

Output:

[1, 2, 5, 1, 0, 0, 0]

Aby osiągnąć pożądany efekt trzeba było użyć aż dwóch list składanych połączonych ze sobą. Pierwsza lista składana zajmuję się usunięciem wszystkich zer z wnętrza naszej listy. Natomiast druga dodaje nasze zera na koniec. Kluczem do sukcesu było tu użycie metody ”count” by policzyć ilość zer w naszej liście.

Runda trzecia

Tym razem zamiast tworzyć nowa listę zmodyfikujemy tą którą już mamy.

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    for _ in range(lista.count(0)):
        lista.append(lista.pop(lista.index(0)))

zera_na_prawo(lista)
print(lista)

Output:

[1, 2, 5, 1, 0, 0, 0]

Nie martw się zaraz rozpiszemy to tak by wszytko było jasne.

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    for _ in range(lista.count(0)):
        index_na_ktorym_jest_zero = lista.index(0)
        pobrane_zero = lista.pop(index_na_ktorym_jest_zero)
        lista.append(pobrane_zero)

zera_na_prawo(lista)
print(lista)

Mam nadzieję, że teraz jest to troszkę jaśniejsze. W pierwszym ruchu sprawdzamy na, którym indeksie znajduje się pierwsze od lewej zero. Następnie wykorzystujemy ten indeks by przy pomocy metody ”pop” pobrać interesujący nas element. Metoda „pop” robi dwie rzeczy. Pobiera wskazany element z listy oraz usuwa go z niej. Jedyne co nam pozostaje to dodać pobrane metodą ”pop” zero na koniec naszej listy. W tym celu posłużymy się metodą ”append”. Powyższą operację należy powtórzyć tyle razy ile zer było początkowo w naszej kolekcji.

Powyższy kod można troszeczkę uprościć

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    for _ in range(lista.count(0)):
        lista.remove(0)
        lista.append(0)

zera_na_prawo(lista)
print(lista)

Output:

[1, 2, 5, 1, 0, 0, 0]

Metoda ”remove” usuwa pierwsze napotkane zero z listy. Następnie metodą ”append” dajemy zero na koniec kolekcji. Operacje powtarzamy tyle razy ile było początkowo zer w naszym kontenerze.

Runda 4 i ostatnia

Co jakby spróbować posortować naszą listę:

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    lista.sort(reverse=True)

zera_na_prawo(lista)
print(lista)

Output:

[5, 2, 1, 1, 0, 0, 0]

Udało się zera są po prawej stronie. Nie chwileczkę nie do końca. Niestety funkcja ”sort” poprzestawiała nam również inne elementy w naszej liście. Podsumowując odwrotne sortowanie powiodło się lecz posortowało wszystkie elementy a nie tylko zera.

Jak posortować tylko zera

A tak 🙂

lista = [1 ,2, 0, 0, 5, 0, 1]

def funkcja_sortujaca(element_listy):
    if element_listy == 0:
        return 1
    else:
        return 0

def zera_na_prawo(lista):
    lista.sort(key=funkcja_sortujaca)

zera_na_prawo(lista)
print(lista)

Output:

[1, 2, 5, 1, 0, 0, 0]

Funkcja ”sort” potrafi jako parametr ”key” przyjąć funkcję, którą możemy dowolnie sterować procesem sortowania naszej kolekcji. W naszym przypadku wszystkim zerom przyporządkowaliśmy liczbę jeden. Pozostałe elementy naszej kolekcji dostały liczbę zero. Zatem wszystkie elementy którym dopowiada liczba jeden (czyli nasze zera) posortują się na prawo, a cała reszta na lewo.

Można by troszkę skrócić nasze rozwiązanie rezygnując z przypisywania zer i jedynek na rzecz przypisywania wartości ”True” i ”False”. Podczas sortowania wszystkie wartości ”True” znajdą się po prawej stronie, a wszystkie ”False” po lewej.

lista = [1 ,2, 0, 0, 5, 0, 1]

def funkcja_sortujaca(element_listy):
    return element_listy is 0

def zera_na_prawo(lista):
    lista.sort(key=funkcja_sortujaca)

zera_na_prawo(lista)
print(lista)

Output:

[1, 2, 5, 1, 0, 0, 0]

Jak widzisz nasza funkcja sortująca ma teraz zaledwie jedną linię. Zwraca ona ”True” dla wszystkich zer oraz ”False” dla wszystkiego co nie jest zerem. Z uwagi, że nasza funkcja jest tak niewielka z powodzeniem możemy zastąpić ją funkcją lambda:

lista = [1 ,2, 0, 0, 5, 0, 1]

def zera_na_prawo(lista):
    lista.sort(key=lambda element_listy: element_listy is 0)

zera_na_prawo(lista)
print(lista)

Output:

[1, 2, 5, 1, 0, 0, 0]

Tyle na dziś 🙂 Trzymajcie się.