Zadania z programowania

Zadania z programowania, było: Programowanie obiektowe

Oryginalnie ten spis zadań dotyczył przedmiotu "Programowanie Obiektowe", przy którym prowadziłem ćwiczenia laboratoryjne. Wymyśliłem wtedy szereg zadań dla studentów, aby mogli ćwiczyć swoje opanowanie języka programowania, jakim była wtedy Java. Po paru latach doszedłem do wniosku, że zadania tego typu nadają się także do nauczania innych języków (nie tylko obiektówki), i rozbudowałem tę stronę, aby opis zadań był nieco pełniejszy. Niektóre zadania są trywialne lub już rozwiązane, jeżeli użyje się odpowiedniego języka programowania (np. niektóre języki w naturalny sposób implementują swoimi własnymi mechanizmami takie rzeczy jak ułamki zwykłe - Ruby, lub operacje na liczbach zespolonych - Go). Napisanie samodzielne takich rozwiązań zawsze może być ciekawym ćwiczeniem, które pozwoli lepiej poznać język, który często z samego początku nie jest łatwy do nauczenia się.

Poprzednie wprowadzenie do tej strony (zmieniłem w dni 20221113): Ten przedmiot ma na celu zapoznanie studentów z programowaniem obiektowym, a więc z całą terminologią i technologiami powiązanymi. Językiem wykładowym jest Java, i na ćwiczeniach w pracowni taki język poznajemy. W celu lepszego opanowania języka, sugerowane jest wykonanie poniższych zadań.

Obecne założenie jest takie, że możesz wykonać te zadania w języku, którego akurat się uczysz .

Numery PESEL

Numer PESEL to najczęściej unikalna dla jednostki ludzkiej zarejestrowanej w naszym kraju sekwencja cyfr, powiązana z jej datą urodzenia. Szczegóły na temat znaczenia poszczególnych cyfr można odnaleźć na stronie rządowej poświęconej wyjaśnieniu czym ten numer jest: PESEL - numer identyfikacyjny .

Celem do osiągnięcia w tym zadaniu jest sprawdzenie i wypisanie wszystkich numerów PESEL na podstawie jakiegoś numeru PESEL podanego wcześniej (w opcjach CLI lub wczytanego), które mają jedną środkową cyfrę (lub więcej) zmienioną w taki sposób, że jest ona o 1 większa lub mniejsza od oryginalnej. Suma kontrolna na końcu pozostaje niezmieniona w tak zmodyfikowanym numerze PESEL, a wtedy będzie to numer nieprawidłowy lub - co jest celem sprawdzenia - być może jest po takiej zmianie prawidłowy. Program powinien generować numery z wprowadzoną w kolejnych pozycjach zmianą cyfry, a następnie sprawdzać, czy nowy numer jest nadal poprawny. Można wypisać wszystkie sprawdzane numery i ich status. Warto zaobserwować w tym zadaniu czy suma kontrolna się zgadza, jeżeli dwie cyfry PESEL przestawi się miejscami, lub gdy jedną się zwiększy a drugą zwiększy, itp. Takie testy warto przeprowadzić w celu obserwacji stabilności numeru oraz w celu odkrycia jakie są zalety obliczania sumy kontrolnej. Zadanie to można także zmodyfikować i napisać program, który na podstawie daty urodzenia będzie generował losowy, prawidłowy PESEL (czyli taki, który będzie miał odpowiednią sumę kontrolną).

Analiza pliku tekstowego

Należy napisać niewielki program, który wczyta podany plik tekstowy i wyświetli na ekranie jego statystykę, np. liczbę znaków, liczbę wierszy, wiek pliku w dniach lub godzinach, sekundach, itp. Odpowiednie informacje, które ma podawać program można rozszerzyć, np. można wyświetlać sumę kontrolną lub statystkę znaków, itp. Nazwę pliku powinno się podawać podczas uruchomienia jako argument wywołania programu. Bardziej zaawansowane osoby mogą pokusić się o próbę wykrycia w jakim języku jest napisany plik tekstowy - czy jest to język naturalny, lub jakiś język programowania. Niektóre charakterystyczne słowa mogą dostarczać istotnych podpowiedzi co do rodzaju pliku.

Ułamki zwykłe

Należy napisać program, który będzie wykonywał działania na ułamkach zwykłych, czyli takich, które posiadają całkowity licznik i całkowity mianownik. Należy zaimplementować podstawowe operacje na takich ułamkach, takie co najmniej jak mnożenie, dzielenie, dodawanie i odejmowanie. Ułamek reprezentowany przez dwie liczby powinien być możliwy do wyświetlenia w postaci np. dwóch liczb z ukośną kreską dzielenia, lub na żądanie w postaci np. ułamka dziesiętnego. Należy zadbać o obsługę przypadku, gdy mianownik takiego ułamka ustawiony zostanie na zero. Zależnie od języka można zdefiniować swoje własne struktury danych, które będą wspierały taki rodzaj danych; można to zrobić nawet w przypadku, gdy język sam z siebie wspiera działania na ułamkach zwykłych (np. Ruby ma wbudowaną obsługę typu Reciprocal). W językach, które pozwalają na definiowanie operatorów (lub ich przeciążanie) można napisać bardzo zgrabne biblioteki do działań na takich ułamkach, i potem w programie działania takie mogłyby wyglądać jak działania na zwykłych liczbach. Pewnym rozszerzeniem tego zadania może być napisanie operacji dotyczących działań na liczbach zespolonych, tensorach lub kwaternionach.

Wektory w przestrzeni 3d

Stwórz klasę lub bibliotekę danego języka programowania, która obsługuje punkt w przestrzeni 3-wymiarowej. W klasie powinny być pola takie jak x, y, z odpowiedniego typu liczbowego (całkowitego lub zmiennoprzecinkowego) lub tablica z trzema elementami takiego typu. Elementy te, to współrzędne w przestrzeni 3D, i mogą reprezentować położenie jakiegoś punktu, lub być współrzędnymi jakiegoś wektora. Klasa lub biblioteka tego typu powinna umożliwiać przesuwanie wektora, mnożenie wektorów skalarne i wektorowe, oraz różne przydatne operacje, np. konwersję na system biegunowy, transformacje takie jak obrót lub rzutowanie, skalowanie, itp. Od Twojej pomysłowości i zaangażowania zależy co zaimplementujesz. Taką klasę będzie potem można wykorzystać do stworzenia małego programu animującego na ekranie obiekty trójwymiarowe, jeżeli odnajdziesz sposób na wyświetlanie graficznych prymitywów w stylu linii lub obszarów.

Bryły w przestrzeni 3d

Idąc dalej tropem z poprzedniego zadania, możesz zaprogramować dodatkowe klasy, które będą korzystały z Twojej klasy podstawowej do obsługi punktu, i rozszerzą jej możliwości o obsługę kształtów w przestrzeni 3d. Oczywiście, jeżeli w Twoich eksperymentach współrzędna 'z' będzie zawsze równa zero, otrzymasz po prostu działania dla przestrzeni 2d. Możesz zaimplementować obsługę podstawowych brył platońskich, np. czworościanu, sześcianu, dwunastościanu, itp. Takie bryły (i ogólnie bryły tego typu) podlegają podobnym transformacjom co punkty z których się składają. Pamiętaj o tym, że taka bryła powinna posiadać dodatkowy punkt, który możesz traktować jako jej środek geometryczny. W zależności od tego, czy wszystkie Twoje punkty będą miały taką samą masę, czy nie - punkt ten może być barycentrum. Implementacja zależnie od języka może zostać tak przygotowana, że wykorzystasz całe mechanizmy obiektowe dziedziczenia lub kompozycji, w których dany język programowania jest najmocniejszy, np. w Go będzie to kompozycja z komponentów, w Rubym lub w Javie - klasyczne rozwiązania obiektowe z klasami, a w C pozostaną Ci do dyspozycji tylko struktury z ewentualnymi funkcjami. Temat ten jest niesamowicie bogaty w możliwości, i budując bardziej skomplikowane hierarchie obiektów możesz nawet zaimplementować jakiś niewielki system okien lub innych elementów graficznych, których wykorzystanie będzie miało sens użytkowy.

Spalanie lasu

To stare i bardzo ciekawe zadanie, które pamiętam jeszcze z czasu swoich studiów (czyli z lat '90). Należy opracować program, symulujący spalanie lasu trafionego piorunem. W programie zasadniczo należy zaimplementować obszar w którym mogą rosnąć drzewa - w losowych miejscach. Często używa się do tego tablicy dwuwymiarowej, ale możesz też rozważyć inne modele danych. W takiej tablicy drzewo, które rośnie w lesie jest reprezentowane przez jakąś informację (najprostsza z nich to jakaś liczba, np. 1). Trafienie w taką tablicę jest losowe, wystarczy wygenerować dwie współrzędne i sprawdzić co w nich się znajduje. Jeżeli trafione zostanie drzewo, to zaczyna się palić, natomiast jeżeli trafiono pole puste, nic się nie dzieje. Drzewo, które się pali, zapala drzewa, które z nim sąsiadują bokami lub narożnikami. Możesz zdecydować samodzielnie jaki dokładny model spalania lasu będziesz implementować. Sąsiedztwo określamy analizując sąsiednie elementy tablicy. Program powinien wypalić cały obszar lasu w którym rosną sąsiadujące ze sobą drzewa. Następnie należy określić, jaki procent całego lasu został spalony. W oryginalnej wersji zadania należało dodatkowo obliczyć (metodą wielokrotnych prób losowych) jaki procent powierzchni lasu powinien być optymalny ze względu na maksymalizację zalesienia i minimalizację strat wynikających z pożarów. Zadanie to można napisać na różne sposoby, i zależnie od przyjętych założeń, wyniki będą się nieco różnić. Na podstawie uzyskanych symulacji spalania można wygenerować bardzo ciekawie wyglądające wykresy. Interpretacja wyników nie zawsze jest łatwa. Można także dodać dodatkowe czynniki do zadania, zwiększające liczbę stopni swobody systemu: np. dodać wpływ wiatru, wprowadzić zróżnicowany wiek drzew i ich odporność na spalanie, lub zmienić kształt lasu (czy kwadratowy las pali się dokładnie tak samo jak wąski las prostokątny, przy dużej liczbie prób?). Zadanie to można przedstawić graficznie - rysując las przed i po spaleniu, i można to zrobić nawet bardzo prosto w terminalu, ale bardziej zaawansowani mogą narysować las graficznie. Należy pamiętać, że każda dodatkowa idea i pomysł dodane do tego zadania zwykle bardzo je komplikują, i prześledzenie wpływu wszystkich zależności staje się często bardzo trudne lub wręcz niemożliwe. Przykładowo, jeżeli mamy losowe podpalenie drzewa w jakimś miejscu, to zależność, którą badamy jest jednowymiarowa. Jeżeli jednak dodamy kierunek wiatru, to wszystko co badaliśmy, staje się nagle dwuwymiarowe, ponieważ nie tylko badamy jak spalał się lat, ale też dochodzi do tego cała pula różnych kierunków wiatru oraz jego siły. Dodanie kolejnego parametru, takiego jak np. wilgotność, dodaje kolejny wymiar do przestrzeni danych, którą trzeba zbadać, zatem należy rozważnie rozbudowywać to zadanie, aby potem nie okazało się, że obliczenia które musimy wykonać są tak gigantyczne, że przekroczą możliwości czasowe komputera i czas trwania semestru. Moja rada: najlepiej ograniczyć się do podstawowej wersji zadania i dodać do niego jeden dosłownie dodatkowy parametr.

Analiza statystyczna

To zadanie pochodzi z rzeczywistej pracy naukowej, i zostało "wycięte" z kontekstu aby nie zaciemniać obrazu. Wyobraź sobie, że masz bardzo długi wektor liczb, które strumieniem wczytujesz do swojego programu. Liczby te mają wartości od 0 do 255 i tak naprawdę określają jasność pewnego elementu obrazu. Twoim zadaniem jest napisać program, który wczytując te liczby, policzy dla nich średnią arytmetyczną, odchylenie standardowe oraz wariancję, ale w pewien szczególny sposób - ruchomo, w "oknie". Chodzi o to, że program nie zaczyna liczyć od razu, a dopiero po wczytaniu pierwszych N liczb, np. po pierwszych 10 liczbach zacznie dopiero liczyć. Po wczytaniu wyliczana jest statystyka dla tych dziesięciu liczb, i program wczytuje następną liczbę. Wtedy kolejny raz program liczy statystykę dla ostatnich dziesięciu wczytanych liczb. I tak aż do końca danych. Koniec danych może być sygnalizowany jakimś słowem, np. "ENDOFDATA" lub wartością, która w zbiorze liczb na pewno nie występuje (np. gdy wczytujemy liczby naturalne, wczytanie wartości ujemnej będzie oznaczało koniec danych). Wyniki w postaci średniej, odchylenia standardowego oraz wariancji powinny być wypisane w kolejnych wierszach w formacie "%12.4f%12.4f%12.4f". Można także sporządzić wykresy z takiego przetworzenia danych i zaobserwować ich wygładzanie, tym silniejsze, im szersze jest okno, w którym liczymy średnie. Bardziej zaawansowane rozwinięcia tego zadania mogłyby prowadzić taki proces dla danych 2D - czyli wczytywanych w postaci macierzy, lub wprost z rysunku (poszczególne piksele obrazu można i należy traktować jak liczby). W przypadku danych 2D średnią lub inne operacje liczy się korzystając z małego obszaru w kształcie kwadratu, który "przeciąga" się przez wszystkie punkty danych. Jest to nic innego jak zwykła konwolucja, operacja stosowana powszechnie przy analizie danych w pewnych działach grafiki komputerowej. Zależnie od operatora który będziemy "przeciągać" po danych, możemy uzyskać wyostrzenie, zmiękczenie lub inne efekty dotyczące wartości, a w przypadku obrazków można to zaobserwować po ich wyświetleniu.

Mrowisko

To zadanie jest inspirowane obserwacjami przyrody, a konkretnie kolonii mrówek. Należy napisać symulator, w którym obszarem badań będzie prostokątny obszar o wymiarach XY, w którym poruszać się losowo (o jedno pole w każdym kierunku) będą mrówki. Mrówka jest obiektem, który zmienia losowo swoje współrzędne w np. dwuwymiarowej tablicy. Oprócz mrówek w przestrzeni danych znajdują się także losowo umieszczone obiekty, które mogą być np. igłami sosnowymi lub listkami. Każdy taki obiekt leży początkowo w losowej pozycji i zajmuje jedno całe pole. Mrówka po wejściu na pole, w którym znajduje się taki obiekt, podnosi go, i kontynuuje marsz losowy niosąc ten obiekt. W chwili gdy mrówka napotka kolejny taki leżący obiekt (listek lub igłę - zależnie co wybierzesz jako swój model), upuszcza ten, który do tej pory nosiła i odchodzi pozostawiając go na polu obok znalezionego obiektu. Prawidłowo napisana symulacja powinna pokazać jak powstają mrowiska z losowo znajdowanych i przemieszczanych elementów. W tym programie kryją się ciekawe niespodzianki algorytmiczne, i będzie trzeba podejmować decyzje dotyczące różnych sytuacji, np. co się może stać gdy mrówka z listkiem napotka mrówkę bez listka? Może nic, a może sobie ten listek przekażą... Decydujesz sam, tworząc w ten sposób modyfikacje tego zadania. Jeżeli taki program napisać dobrze, to potem bardzo ekscytujące jest obserwowanie jak zachowuje się cały układ. Wyniki są nieraz trudne do przewidzenia. Możesz zdefiniować inne reguły - np. dodać dla mrówek pokarm, lub zmiany ich energii, prędkości lub zachowania. Listki mogą być karaluchami, które chcą uciec mrówkom. Może mrówki mogłyby zostawiać ślad feromonowy (tak jak to robią w naturze) pozwalający im wrócić do miejsca, gdzie znalazły pożywienie? I tak dalej. Pamiętaj, że układ symulowany w tym zadaniu powinien być logicznie "szczelny", to znaczy - że jeżeli dodasz jakieś dodatkowe byty lub zachowania, to napisać całość symulacji trzeba tak, aby nie dochodziło do sytuacji niezdefiniowanych. Co się stanie gdy mrówka nie będzie mogła się poruszyć, bo będzie otoczona listkami? Czy mrówki mogą wchodzić na to samo pole? Mam nadzieję, że już rozumiesz jakie mogą się tutaj kryć wyzwania. Jest to jeden z najciekawszych programów w tym zbiorze, i naprawdę przynajmniej raz w życiu warto napisać taki system. Może nawet niech to nie będę mrówki - mogą być lisy i króliki. Zależnie od tego, jak głęboko wejdziesz w temat, możesz odkryć cały bogaty świat matematycznych abstrakcji - bifurkacje, hipotezę Collatza, fraktale, chaos deterministyczny... Zachęcam - tutaj naprawdę ciężko dojść do końca możliwości.

Programowanie interfejsów użytkownika w Swing/AWT

To zadanie dotyczy języka Java, ale w przypadku innych języków możesz wybrać inny zestaw bibliotek wspomagających programowanie okien. Jest ich sporo, a najbardziej znane (np. QT, GTK lub WxWidgets są bardzo rozbudowane). Wybierz dowolny spośród powyższych programów, i zaimplementuj dla niego system okienkowy w którym ten program będzie działał. W przypadku Javy, wykorzystaj klasy JFrame i różne elementy interfejsu takie jak JButton, JLabel i inne. Zależnie od Twojej inwencji, możesz stworzyć duży program z bardzo złożonym interfejsem, lub proste okno, wykonujące niewiele akcji. Uwaga: Gdy zaczniesz tworzyć okna graficzne, aplikacje pracujące wyłącznie w trybie tekstowym mogą stracić dla Ciebie urok!

Gra w zgadywanie

Oryginalnie wymyśliłem to zadanie na potrzeby programowania w Go, ale świetnie się to sprawdziło również na zajęciach z programowania w językach skryptowych, takich jak Ruby. Trudność zadania jest zmienna i zależy od poziomu zadania na którym się je wykonało. Samo zadanie podzielone na kilka poziomów trudności. Oto jego treść, i dokładniejszy opis:

Napisz program, którego zadaniem jest przeprowadzić grę z człowiekiem, w zgadywanie wylosowanej przez komputer liczby. Zadanie można zrobić prosto, lub w sposób bardzo rozbudowany. Warianty, a właściwie "poziomy" przedstawione są poniżej. Oto poziomy realizacji tego zadania:

Silne i słabe liczby

Zadanie to polega na obliczeniu dwóch liczb zależnych od Twojego imienia i nazwiska, które dość prosto możesz jednoznacznie wyznaczyć. Trzeba jednak wykonać sporo obliczeń na liczbach naprawdę astronomicznie wielkich. Jak się zatem do tego zabrać?

Wersja TLDR: Wygeneruj swój nick z 3 liter imienia i 3 liter nazwiska, następnie zamień go na ASCII i znajdź taką liczbę, której silnia zawiera w sobie wszystkie wartości numeryczne kodów ASCII z Twojego nicku. Będzie to Silna Liczba. Następnie wyznacz wartość 30 elementu Ciągu Fibonacciego, i oblicz liczbę wywołań każdego argumentu podczas tych obliczeń. Znajdź liczbę wywołań najbardziej zbliżoną do Silnej Liczby. Słaba liczba to argument dla którego wykonuje się ta liczba wywołań. Jeżeli nie rozumiesz o co chodzi, przeczytaj wersję długą.

Wersja długa: Potrzebujesz wygenerować swój "nick", który tworzysz biorąc 3 litery swojego imienia, i 3 litery nazwiska. Tworzy się wtedy ciąg znaków, w moim przypadku jest to "PioArł". Jeżeli taki ciąg znaków zawiera polskie znaki, możesz je uprościć zastępując je znakami ASCII (czyli 'ą' zamieniasz na 'a', 'ł' na 'l', i tak dalej). Następnie zamieniasz ten napis na jego odpowiednik pisany małymi literami - otrzymując "pioarl". Taki napis w kolejnym kroku przedstawiasz za pomocą kodów bajtowych, w tym przypadku będą to zwykłe liczby o wartościach: 112, 105, 111, 97, 114, 108. Gdy już masz rozkład ASCII swojego nicka, obliczaj po kolei wartości funkcji silnia(n), gdzie n będzie rosło do jakiejś wartości. Do jakiej? To właśnie masz ustalić. Otrzymasz w trakcie zwiększania n różne duże liczby (np. Silnia(22) jest równa 1124000727777607680000, więc sporo). W tych liczbach poszukaj ciągów znaków, które odpowiadają Twoim kodom ASCII, czyli kod ASCII litery p równy 112 znajduje się w tej liczbie (bo zaczyna się ona od 112, a silnia(21) tego kodu nie zawiera). W zadaniu trzeba znaleźć taką wartość n dla której funkcja silnia zwróci dużą liczbę zawierającą w sobie wszystkie wystąpienia kodów znaków ASCII z Twojego nicka. Sprawdź: nick "piar" ma silnię spełniającą warunki zawierania liczb 112, 105, 97, 114 równą 191! a jeżeli wydłużyć ten nick zgodnie z warunkami zadania do "pioarl" to wtedy wartość n rośnie do 298!

Tak obliczona wartość to oczywiście bardzo duża liczba. Wartość n jest zatem Twoją Silną Liczbą, wynoszącą dla mnie 298. Oblicz teraz wartość swojej Słabej Liczby. Aby to zrobić, należy wyliczyć rekurencyjnie wartość Ciągu Fibonacciego (tak, to ten gdzie F(n) = F(n-1)+F(n-2)) dla liczby 30. W takim obliczeniu, funkcja rekurencyjna oblicza wartość dla Fib(29) oraz dla Fib(28). Ale funkcja Fib(29) także wylicza wartość Fib(28). Jak wiesz, rekurencyjna postać funkcji Fib będzie wielokrotnie obliczać wartości dla takich samych parametrów, i wykona tym więcej obliczeń, im mniejszy jest ten parametr. Wypisz zatem wszystkie liczby wywołań dla wartości 0, 1, 2, 3 i kolejnych, aż do 30. Zauważysz, że liczba wywołań spada (dla przykładu: wartość 30 jest wywołana tylko raz, wartość 29 jest wywołana raz, ale wartość 28 jest wywołana 2 razy, argument 27 jest obliczany 3 razy, i tak dalej, dla zera funkcja wywołuje się 514229 razy). Gdy popatrzysz na wyniki, możesz znaleźć przedział w którym leży Twoja Słaba Liczba. Jest to taka liczba, dla której liczba wywołań jest najbliższa Twojej Silnej Liczbie. Wystarczy wypisać wartości od 0 do 30, a potem obok wartości wywołań tego argumentu funkcji Fib aby to zobaczyć. Jeżeli moja Silna Liczba wynosiła 298, to jest to najbliższe wartości 18, ponieważ funkcja Fib wywołuje podczas obliczania Fib(30) dokładnie 233 razy (a dla Fib(30) liczba 17 wywołuje się już 377 razy, więc jest bardziej odległa od Silnej Liczby). Jeżeli nadal nie rozumiesz o co chodzi, zapytaj Wykładowcę. To zadanie to tylko prosta w sumie zabawa liczbami. Zachęcam tutaj do refleksji na temat Kosmicznie Wielkich Liczb. Możesz w opracowaniu obliczyć ILE czasu musiałbyś czekać, aż Twoja rekurencyjna funkcja Fib obliczy swoją wartość dla Twojej Silnej Liczby, czyli ile by trwało obliczenie – w moim przypadku – Fib(298), rekurencyjnie. Zastanów się nad tym i odnieś ten czas do wieku np. trwania znanego nam Wszechświata. Rozważania na ten temat w opracowaniu są mile widziane! Jeżeli chcesz spróbować swoich sił w obliczaniu naprawdę wielkich liczb, zapoznaj się z Funkcją Ackermanna, która, gdy jest napisana podobnie jak Fib – rekurencyjnie – wykonuje o wiele więcej pracy niż bardzo niewydajna funkcja Fib, która i tak przecież wykonuje nieprawdopodobnie wielką ilość pracy. Jednak w porównaniu z Funkcją Ackermanna, to, co robi funkcja Fib – znika – tak bardzo ilość pracy wykonywanej przez funkcję Ackermanna przewyższa to wszystko, co możemy sobie wyobrazić. Spróbuj oszacować chociaż w przybliżeniu, ile razy dłużej trwałoby obliczenie wartości funkcji Ackermanna dla argumentów takich jak (Twoja SIlna Liczba, Twoja Słaba Liczba). Uwaga: jeżeli wymiękniesz podczas tego opracowania, nie przejmuj się, ja WIEM, że tego ludzkość nie potrafi policzyć. Ale może coś wykombinujesz? :)

Life wg. Johna Conway'a

Gra w życie to przykład symulacji, który jest grą 0-osobową, bo gracza w niej nie ma, jest on biernym obserwatorem. Pochodzi z roku 1975, autorem jest John Horton Conway, genialny matematyk, który wynalazł wiele wspaniałych rzeczy (np. - niezwykły zbiór liczb Nadrzeczywistych, gdzie można wyliczyć ściśle takie dziwne wartości jak 1/∞ lub pierwiastek z nieskończoności! Niestety zmarł w roku 2020 na Covid 🙁). Ale wracając do gry o nazwie Life – chodzi o symulację zachowania się kolonii automatów komórkowych na planszy prostokątnej. Każde pole o wartości 0 jest puste. Pole o wartości 1 zawiera znajdujący się na nim organizm. Conway zdefiniował dwie proste reguły rządzące się zachowaniem tych automatów: jedna dotyczy przeżywalności, druga umieralności. W modelu klasycznym nowy organizm może powstać na pustym polu tylko wtedy, gdy pole to graniczy z trzema innymi zajętymi polami (czyli ma 3 sąsiadów). Gdy pole na którym stoi organizm posiada 0, 1, 4 lub więcej sąsiadów, organizm ginie z przeludnienia, a pole, które zajmował robi się puste. Reguły te są trywialnie proste. Okazuje się jednak że są określone układy organizmów, które przejawiają niezwykle złożone zachowania, a ich ewolucja jest trudna do przewidzenia. Niektóre kolonie organizmów stabilizują się, i przestają ulegać zmianom. Inne wykazują tendencję do powtarzania pewnego układu (tzw. oscylatory). Szczególnymi wersjami oscylatorów są kolonie które przemieszczają się po planszy. Wykorzystując niewielkie zespoły organizmów, które wędrują, można przesłać informacje z punktu do punktu. Możliwe zatem staje się symulowanie układów, które komunikują się ze sobą. Udowodniono, że taki system jest maszyną Turing-zupełną, a zatem, że można za pomocą takich organizmów zakodować dowolny algorytm. Jest to niezwykły przykład działania zasad emergentnych, to znaczy takich, gdzie od bardzo prostych reguł przechodzi się do bardzo skomplikowanych zachowań! Symulacje na poziomie profesjonalnym można prześledzić w programie Golly (jest on w stanie symulować kolonie zbudowane z setek milionów organizmów, na planszy bez ograniczenia wielkości, oraz wydajne algorytmy haszujące, wykorzystanie drzew czwórkowych do dzielenia przestrzeni, itp. - bardzo interesujące narzędzie, dostępne za darmo: http://golly.sourceforge.net/).

W zadaniu należy zasymulować życie takich układów. Planszę można rysować w terminalu lub graficznie. Można napisać program, który wygeneruje obrazki z kolejnymi etapami rozwoju kolonii (obrazki można nawet potem połączyć w gotowy film lub animowany gif). Ogólnie jest to dość proste, klasyczne, i ciekawe zadanie, które przynajmniej raz w życiu warto napisać dla własnej satysfakcji i dla podnoszenia swoich umiejętności. Polecam serdecznie zapoznać się także z obszerną wiedzą na temat symulacji - https://pl.wikipedia.org/wiki/Gra_w_%C5%BCycie Jeżeli ktoś tego jeszcze nie znał, przypuszczam, że będzie zachwycony gdy zobaczy jak zrobiono w Golly kolonię np. Metapixel-galaxy, lub inne, w których liczony jest prawdziwy symulator Life, ale wyższej generacji... 😊

Zadanie to można rozszerzyć sobie o dopisanie do niego innych zestawów reguł rządzących systemem. Można także np. spróbować zaprogramować algorytm który generuje Mrówkę Langtona, inny bardzo ciekawy układ chaotyczny, który nagle przestaje być chaotyczny. W opracowaniu można umieścić swoje rozważania na temat tego zjawiska i własne refleksje i wnioski na temat zasad emergentnych. Czy nasz fizyczny świat, opisywany często za pomocą prostych i względnie zrozumiałych równań fizycznych także wykazuje zachowania emergentne prowadzące do nieskończonych komplikacji?

Podsumowanie

Te wszystkie zadania są takimi, które zwykle, co najmniej od paru lat, zadaję studentom, którzy chcą się nauczyć programowania. To są dobre, konkretne przykłady sprawdzonych i stabilnych problemów, które moim zdaniem są idealne do nauczenia się nowego języka. W każdym z tych zadań występują różnorodne problemy, które trzeba rozwiązać, takie jak kontrola błędów, pobieranie informacji ze standardowego wejścia, analiza opcji uruchomienia, wyświetlanie okna z grafiką lub odczyt/zapis plików.

Pomysłów oczywiście jest więcej na pisanie i naukę. Nieskończonym źródłem inspiracji jest matematyka, w której wręcz czasem prosi się o napisanie programu sprawdzającego pewne hipotezy. Nauki ścisłe - fizyka, chemia, statystyka różnego rodzaju - to wszystko zaproszenie do programowania. Nawet proste przetwarzanie informacji dostarcza czasem ciekawych wyzwań. Na przykład - wyobraź sobie, że masz na dysku w różnych miejscach pliki tekstowe. Jak napisać program do zarządzania nimi, wyszukiwania informacji, porównywania, przerabiania, i innych czynności?

Niektóre programy mogą stać się przydatne. Na przykład, program kopiujący zdjęcia z aparatu na dysk z jednoczesną opcją sortowania zdjęć i umieszczania ich w katalogach o takiej nazwie jak data zrobienia zdjęcia. Albo program, który porządkuje dysk, przegląda różne katalogi i każdy znaleziony plik wgrywa w określone miejsce, stosując analizę treści, dzięki czemu tylko najnowsze pliki będą na końcu. Taki program przydaje się wtedy, gdy chcemy zintegrować dwa różne drzewa katalogów - np. stary dysk z nowym, lub zawartość domowego komputera z tym, co utworzyliśmy w pracy. Jeżeli do takiej 'synchronizacji' dodać funkcje automatycznego przeglądania archiwów ZIP/TAR.gz lub inne zaawansowane funkcje... możliwości i wyzwania programistyczne szybko rosną. A dodatkowo można narzucić sobie ciekawe ograniczenia lub wyzwania: jak napisać dany program szybciej, efektywniej, bardziej oszczędnie? Jak pracować z plikami, które nie mieszczą się w pamięci? I tak dalej... niewyczerpana jest liczba wyzwań i tematów, które może zgłębiać informatyk!