W nauce programowania przychodzi moment, gdy pisanie prostych rzeczy z poradników wydaje się być stratą czasu. Chcemy napisać coś konkretnego, co da nam wartość, a może będzie dobrym elementem do dodania w CV. Ale gdy już mamy pomysł, przychodzi pewien problem. Od czego zacząć?
Pierwszą myślą jest, czego użyć, jakiej biblioteki, jakiego frameworku. Zaczynamy rozglądać się za odpowiedziami na pytania, które nie pomogą nam zacząć rozwiązywać nasz problem. Przy próbie implementacji, należy w pierwszej kolejności zastanowić się nad elementami, od których możemy zacząć, i przesuwać decyzje jak najdalej się da. Omówmy sobie rozbicie takiego skomplikowanego problemu.
Problem
Po pierwsze znajdźmy problem, który będziemy chcieli rozwiązać. Może się do tego przydać, chociażby poniższa grafika, krążąca po internecie, z pomysłami na to, co zaimplementować. Jeden z użytkowników wykop.pl, któremu chciałem pomóc, zdecydował się na implementacje mrówki Langtona.
Jeżeli chcesz skorzystać z powyższego zbioru, ale nie wiesz, na co się zdecydować, skorzystaj z tej strony https://thinkbreak.github.io/programming-challenges/, która wylosuje Ci zadanie.
Mrówka Langtona
Jest to prosty automat komórkowy. W dużym skrócie mamy mrówkę, która porusza się po planszy. Jeżeli stanie na białym polu, zmienia jego kolor i idzie na pole po jej prawej. W przeciwnym wypadku także zmienia kolor, ale idzie na pole po jej lewej. Brzmi dość prosto? Poniżej animacja, ukazująca pierwsze 200 kroków.
Jeżeli problem jest już dla nas zrozumiały, rozbijmy go na kroki:
Plansza
Nasza mrówka przemieszcza się po planszy. Przyjmijmy wstępnie, że będzie to plansza 11 na 11 pól. Pozycja startowa mrówki to środek planszy, czyli pole (5,5). Mamy dwa typy pól - białe oraz czarne. Dla ułatwienia reprezentujmy je za pomocą cyfr - 0 dla białych, 1 dla czarnych
A więc musimy stworzyć przestrzeń 2D, po której przemieszczać będzie się mrówka. Ponieważ nie chcemy używać zewnętrznych bibliotek na typ etapie, wykonamy ją za pomocą listy list. Plansza na początku jest pusta, a jej pola są białe, dlatego wszystkie pola w naszej tablicy będą wypełnione zerami. Dodatkowo wyznaczamy zmienne x oraz y aby przechowywać pole, na którym znajduje się mrówka.
from pprint import pprint
def create_board(size):
return [[0 for _ in range(size)] for _ in range(size)]
size = 11
board = create_board(size)
x, y = size // 2, size // 2
pprint(board)
print(x, y)[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] 5 5
Jak widać, udało nam się wykonać prostą tablicę zer. Aby odczytać odpowiednie pole, użyjemy board[y][x], ponieważ pierwsza pozycja definiuje nam wiersze, a druga kolumny. Dodatkowo korzystamy ze wbudowanej biblioteki pprint, aby wygodnie podglądać, jak wygląda nasza tablica.
Pierwszy krok
Gdy mamy plansze możemy dokonać pierwszego kroku! Ponieważ mrówka startuje na białej planszy, w pierwszej kolejności zmienimy kolor pola na czarny, i przejdziemy na pole po naszej prawej.
Najpierw musimy zmienić wartość pola, na którym stoimy, z 0 na 1. Następnie zmieniamy wartość y. Ponieważ, nasza mrówka idzie w górę, to y się zmniejszy o jeden. Aby udowodnić nasz ruch, na końcu dodamy sobie 8 jako reprezentacje mrówki.
board[y][x] = 1 y -= 1 board[y][x] = 8 pprint(board) print(x, y)
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] 5 4
Udało się! Nasza mrówka zrobiła już pierwszy krok! Dodatkowo widzimy, że zmiana wartości zmiennych przebiegła pomyślnie wedle naszych oczekiwań.
Kolejne kroki
Pierwszy krok był celnie wymierzony. Jednak nie chcemy wpisywać każdego kolejnego kroku ręcznie. Kolejne kroki są dość istotne, ponieważ pierwsze cztery kroki utworzą czarny kwadrat, a kolejny spowoduje pierwszą zmianę pola z koloru czarnego na biały.
Czwarty krok 
Piąty krok 
Szósty krok
Musimy zdefiniować sobie kilku pomocników, aby te ruchy działy się automatycznie na bazie tego, jaki jest stan pola, na którym stoimy. Potrzebujemy zdefiniować obrót mrówki oraz jej kierunek.
Obrót mrówki
Najpierw zdefiniujmy zmienną, która będzie definiować, w którą stronę obróci się mrówka. Zrobimy to za pomocą prostej logiki:
direction = "L" if board[y][x] else "R" print(direction)
R
Nasza zmienna będzie teraz zwracać nam informacje o tym, jak obróci się mrówka po zmianie barwy pola, na którym stoi. Zwróćmy jeszcze na zapis, który pojawia się w pierwszej linii. Zapis ten jest jednolinijkową reprezentacją poniższego kodu. Tak jak przy list comprehension oszczędzamy miejsce i mamy możliwość wykonania pewnej czynności logicznej bezpośrednio przy wywołaniu funkcji.
if board[y][x]:
direction = "L"
else:
direction = "R"Kierunek mrówki
Wiemy już, gdzie pójdzie nasza mrówka, ale jak to zaprezentować na planszy? Musimy zdefiniować zmienną, która określać będzie kierunek, w którym obrócona jest nasza mrówka. Aby sobie ułatwić pisanie zasad ruchu, w pierwszej kolejności przypiszemy sobie kierunki świata, aby zobrazować to na planszy.
board[y - 1][x] = "N" board[y][x + 1] = "E" board[y + 1][x] = "S" board[y][x - 1] = "W" pprint(board)
[['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', 'N', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', 'W', '0', 'E', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', 'S', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0']]
Ponieważ nasza mrówka jest ustawiona, na przykładowym obrazku, na zachód, to jej koordynaty następnego kroku wynoszą (0,-1). Oznacza to, że wartość 0 zostałaby dodana do zmiennej y, a wartość -1 do zmiennej x. Zatem zdefiniujmy sobie zmienną coordinates.
coordinates = (0,-1)
Ponieważ zdefiniowaliśmy sobie już zapis obrotu, oraz przesunięcie naszej mrówki, musimy zapisać teraz, jak powinna przesunąć się mrówka, jeżeli jest skierowana na pole (0,-1) i ma obrócić się w prawo. Jednym ze sposobów byłoby stworzenie drzewa ifów, jednak ja wolę tutaj wykorzystać słowniki. Nasze przesunięcie to tupla, a ze względu, iż tupla jest niemutowalna, to możemy jej użyć jako klucza w słowniku.
coord_moves = {
"R": {(0, -1): (-1, 0), (-1, 0): (0, 1), (0, 1): (1, 0), (1, 0): (0, -1)},
"L": {(0, -1): (1, 0), (1, 0): (0, 1), (0, 1): (-1, 0), (-1, 0): (0, -1)},
}
print(coord_moves[direction][coordinates])(-1, 0)
Teraz gdy będziemy chcieli otrzymać pozycje nowego pola, na które trafi mrówka, wystarczy, że odczytamy to ze słownika. Na powyższym przykładzie widać, iż dla naszej pozycji oraz obrotu zostało zwrócone poprawne przesunięcie w tablicy.
Pętla
Skoro udało nam się zdefiniować logikę, która będzie odpowiednio zmieniać pole, wybierać obrót i się na niego przemieszczać, musimy teraz spiąć to w całość. Użyjemy do tego pętli, aby zrobić pierwsze 6 kroków oraz z reprodukować kroki z animacji. Więc po kolei:
- Odczytaj pole, na którym jest mrówka
- Odczytaj obrót na podstawie pola
- Odczytaj przesunięcie na podstawie tego, w jakim kierunku aktualnie obrócona jest mrówka.
- Zmień barwę pola
- Przesuń mrówkę, poprzez aktualizacje jej pozycji za pomocą wcześniej odczytanego przesunięcia
coordinates = (0, -1)
for _ in range(6):
field = board[y][x]
direction = "L" if field else "R"
coordinates = coord_moves[direction][coordinates]
board[y][x] = 0 if field else 1
y, x = y + coordinates[0], x + coordinates[1]
pprint(board)[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Wynik nie powinien zaskakiwać. Widać, iż otrzymaliśmy ten sam kształt, jak na ilustracji. Nasz algorytm powinien działać poprawnie.
200 kroków
Według przykładowej animacji, plansza po 200 krokach powinna wyglądać jak poniżej:
Jeżeli logika, którą zaimplementowaliśmy, była poprawna dla sześciu kroków, to powinna także bez trudu poradzić sobie z większą ilością kroków. Po zmianie ilości kroków w pętli otrzymaliśmy poniższy wynik:
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0], [0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0], [0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Pewnie nie uwierzysz, że jest to poprawne rozwiązanie. Aby lepiej to z wizualizować, zamieńmy cyfry 0 na puste pola, oraz 1 na pełny blok.
for row in board:
for field in row:
print(f"[{'█' if field else ' '}]", end="")
print()[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][█][█][ ][ ][ ] [ ][ ][ ][█][█][█][█][█][█][ ][ ] [ ][ ][█][ ][█][ ][ ][█][ ][█][ ] [ ][█][ ][ ][█][ ][█][ ][ ][█][ ] [ ][█][ ][ ][█][█][ ][█][ ][█][ ] [ ][█][ ][ ][█][ ][ ][█][ ][█][ ] [ ][█][ ][█][█][█][ ][█][█][ ][ ] [ ][ ][█][█][█][█][█][ ][█][ ][ ] [ ][ ][ ][█][█][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
Teraz już nikt nie powinien mieć złudzeń, że jest to poprawne rozwiązanie!
Graficzny interfejs
Ponieważ wyświetlenie większej ilości kroków może być problematyczne w terminalu, dodajmy do naszego kodu graficzny interfejs. Aby korzystać wciąż ze wbudowanych elementów, użyjemy biblioteki tkinter. Po stworzeniu okna oraz przestrzeni roboczej, dla każdego pola w tabeli będziemy dodawać odpowiednio pokolorowany kwadrat.
import tkinter
root = tkinter.Tk()
window_size = 400
canvas = tkinter.Canvas(root, width=window_size, height=window_size)
canvas.pack()
s = window_size / size
for y, row in enumerate(board):
for x, field in enumerate(row):
canvas.create_rectangle(
s * x,
s * y,
s + (s * x),
s + (s * y),
fill="white" if field == 0 else "black",
)
root.bind()
root.mainloop()
W kilku krokach wykonaliśmy prosty graficzny interfejs. Mając go, możemy przejść do ostatniego kroku.
11_000 kroków
Mrówka Langtona jest ciekawa, ponieważ w okolicy jedenasty tysięcy kroków zaczyna tworzyć autostradę w nieskończoność. Niestety nie zmieścilibyśmy takiego obrazu w tablicy 11 na 11 pól, a na dodatek wyświetlenie wyniku nie byłoby wygodne w terminalu.
Aby wygenerować powyższe, zmieniłem rozmiar tablicy, tworząc tablicę o rozmiarach 100 na 100 pól. Dodatkowo zmieniłem ilość pętli do 11_000 kroków. Wynik działania kodu można zobaczyć poniżej:
Ostateczny kod, wymagany do uruchomienia powyższego przykładu prezentuje się tak:
import tkinter
coord_moves = {
"R": {(0, -1): (-1, 0), (-1, 0): (0, 1), (0, 1): (1, 0), (1, 0): (0, -1)},
"L": {(0, -1): (1, 0), (1, 0): (0, 1), (0, 1): (-1, 0), (-1, 0): (0, -1)},
}
def create_board(size):
return [[0 for _ in range(size)] for _ in range(size)]
size = 100
board = create_board(size)
x, y = size // 2, size // 2
coordinates = (0, -1)
for _ in range(11000):
field = board[y][x]
direction = "L" if field else "R"
board[y][x] = 0 if field else 1
coordinates = coord_moves[direction][coordinates]
y, x = y + coordinates[0], x + coordinates[1]
root = tkinter.Tk()
window_size = 400
canvas = tkinter.Canvas(root, width=window_size, height=window_size)
canvas.pack()
s = window_size / size
for y, row in enumerate(board):
for x, field in enumerate(row):
color = "white" if field == 0 else "black"
canvas.create_rectangle(
s * x, s * y, s + (s * x), s + (s * y), fill=color, outline=color
)
root.mainloop()Na pierwszy rzut oka skomplikowany problem udało się zaimplementować w 48 liniach kodu, bez instalacji zewnętrznych bibliotek. Jest to też ciekawy przykład, ponieważ nie raz zdarzyło mi się dostać zadanie, które na pierwszy rzut oka wyglądało na bardzo skomplikowane. Rozbijając problem na mniejsze elementy, pozbyliśmy się blokad myślowych, a na dodatek po każdym bloku mieliśmy działający kod, który robił coś konkretnego i przybliżał nas do efektu końcowego.
Kolejnym razem wrócimy do naszego kodu, aby zrobić refactor oraz rozbudować algorytm o dodatkowe kolory pól, oraz dodatkowe mrówki 🔥
