Posts tagged ‘algorithms’

Facebook, gry webowe i problem inwestycji

2010-04-01 17:12

No i stało się – kierowany zapewne diabelskimi podszeptami, zarejestrowałem się na Facebooku. Zło (a nawet Zuo) w najczystszej postaci żem uczynił i oprócz formułowania próśb o przebaczenie mogę jedynie usprawiedliwiać się, co mnie do tego zgubnego w skutkach czynu popchnęło. A owym skutkiem (a “zupełnie przypadkiem” również przyczyną) było to, że przyjrzałem się największemu bogactwu tego serwisu, czyli… grom, rzecz jasna :)
Gry na Facebooku dzielą się w sumie na dwie kategorie. Pierwsza z nich to wyewoluowana forma małych, szybkich gier flashowych, które służą do zabijania tych krótkich odcinków czasu, gdy akurat nie chce się nam robić czegoś pożytecznego. Ewolucja polegała tutaj na wykształceniu możliwości porównywania wyników ze znajomymi, co oczywiście natychmiast podnosi grywalność przynajmniej o 120% i jednocześnie uspokaja nas, że nie jesteśmy jedynymi osobami, które się obijają :)
Drugi typ to zabawa w systematyczne klikanie: należy mniej więcej raz na kilkanaście godzin zalogować się i coś zrobić, by posunąć rozgrywkę do przodu. Cokolwiek to jest, nie możemy tego zrobić częściej, bo nie pozwala na to mechanika gry pod postacią regenerującej się w czasie energii/many/itp. (jak choćby w Mafia Wars) czy też nierealistycznie krótkiego okresu wegetacyjnego truskawek (tak, mam tu na myśli oczywiście Farmville).

Jak widać w obu przypadkach nie jest to specjalnie absorbujące zajęcie. Z gier pierwszego typu do gustu przypadła mi Word Challenge, dzięki której wydatnie (czyli o jakieś 5%) poszerzył się mój zasób angielskich słówek (niestety jedynie takich, które mają co najwyżej sześć liter). Wybraną przeze mnie pozycją z kategorii drugiej jest z kolei Castle Age – coś w rodzaju MMORPG-a przez przeglądarkę, całkiem zresztą udanego. I właśnie z tym związany jest pewien ciekawy problem…

W rzeczonej grze oprócz niewątpliwie ekscytującego odklikiwania kolejnych questów mamy też – że powiem nieco na wyrost – wątek ekonomiczny. Należy tam bowiem kupować nieruchomości, które później co godzinę generują nam przypływ świeżej gotówki. Budynki różnią się ceną i uzyskiwanym z nich przychodem, a ponadto możemy kupować je nie tylko pojedynczego, ale i w pakietach (po 5 lub 10).
Jak pewnie nietrudno się domyślić, nasuwającym się tu od razu pytaniem jest to o optymalną strategię nabywania kolejnych budynków, skutkującą największym zyskiem w dłuższej perspektywie czasowej. Tak naszkicowany problem inwestycji (nazwa brzmi cokolwiek poważnie!) miałby więc następujące założenia:

  • Istnieje n \in \mathbb{N} rodzajów budynków z przypisanymi cenami początkowymi c_1, \ldots, c_n i zyskiem generowanym na jednostkę czasu: z_1, \ldots, z_n. Początkowo posiadamy k_1 = \ldots = k_n = 0 budynków i p pieniędzy, ale w każdej jednostce czasu możemy dokonać dowolnej liczby zakupów, o ile posiadane środki na to wystarczają.
  • Każdorazowo po dokonaniu zakupu budynku danego rodzaju, jego cena wzrasta o ustaloną wartość d_i dla i \in {1, \ldots, n}. Zakupu możemy dokonywać pojedynczo lub też w ilościach określonych przez zbiór L \subset \mathbb{N} (w Castle Age mamy L = \{ 5, 10 \}), jednak zawsze tylko jednego rodzaju budynków naraz.
  • Istnieje ograniczenie k \in \mathbb{N} na maksymalną posiadaną liczbę budynków jednego rodzaju – zatem zawsze zachodzi: \forall i \le n, i \in \mathbb{N} \quad k_i \le k. Dla ułatwienia możemy przyjąć, że ograniczenie to jest stałe (w Castle Age jest ono związane z poziomem doświadczenia).

Pytamy tutaj o to, kiedy, ile i jakie budynki powinniśmy kupować, aby zmaksymalizować swój zysk w długim (najlepiej dowolnie długim) przedziale czasu. W szczególności zastanawiamy się, czy działa tu prosta strategia zachłanna – podobna do rozwiązania ciągłego problemu plecakowego – polegająca na zbieraniu zawsze takiej ilości gotówki, aby kupować maksymalną ilość najbardziej “efektywnych” budynków, tj. tych o największym ilorazie zysku do bieżącej ceny. Intuicja podpowiadałaby, że nie dla wszystkich zestawów danych musi tak być…

Zostawiam więc to zadanie jako materiał do przemyśleń na wolne dni. Nagroda za jego rozwiązanie będzie wielka: udowodni się w ten sposób, że gry z Facebooka mogą się do czegoś przydać!

Tags: , ,
Author: Xion, posted under Games, Internet, Programming » 1 comment

Nowoczesne wyliczanie

2009-11-04 1:33

W chyba każdy języku posiadającym pojemniki (jak wektory czy listy) istnieje koncepcja iteratorów: obiektów, które pozwalają na przeglądanie kolekcji i są uogólnieniem wskaźników. W najprostszym pozwalają one tylko na pobranie aktualnego elementu i przejście do następnego, ale jest to zupełnie wystarczające do celów wyliczania.
Z wierzchu więc wyglądają one całkiem prosto i przejrzyście – zwłaszcza, jeśli język udostępnia pętlę typu foreach, która ładnie i przezroczyście je opakowuje. Dlatego może wydawać się dziwne, czemu zazwyczaj mechanizm ten jest używany właściwie tylko dla pojemników; w teorii bowiem za pomocą iteratorów (zwanych gdzieniegdzie enumeratorami) można by było przeglądać dosłownie wszystko.
Weźmy chociażby wyszukiwanie plików na dysku – sporo programów w jakimś momencie swojego działania musi znaleźć pliki np. o danej nazwie w określonym katalogu. Wtedy zwykle zakasujemy rękawy i piszemy odpowiednią procedurę rekurencyjną lub bawimy się ze stosem czy kolejką. A czy nie fajniej byłoby, gdyby dało się to zrobić po prostu tak:

  1. for (FsIterator it = ListFiles("c:\\", "*.exe"); it; ++it) { /* zrób coś */ }

oczywiście przeszukując w ten sposób również podkatalogi bez jawnego “wchodzenia” do nich?… Według mnie to by było bardzo fajne :)

Od razu zaznaczę więc, że wbrew pozorom taki iterator jest jak najbardziej możliwy do napisania. Problemem jest jednak to, jak należy przechowywać jego stan. Kiedy wyszukiwanie czy przeglądanie zaimplementowane jest bezpośrednio jako jedna funkcja, robi się to w zasadzie samo: w postaci zmiennych lokalnych (stos/kolejka) albo parametrów (rekurencja). Nikt specjalnie nie zwraca na ten fakt uwagi. Jednak w momencie próby “wyciągnięcia” z algorytmu operacji Next (w celu stworzenia iteratora) okazuje się nagle, że wymaga to jawnego pamiętania tych wszystkich danych, które pozwalają obliczyć następny element. Przy przeszukiwania katalogów trzeba by na przykład pamiętać jakiś systemowy uchwyt wyszukiwania dla aktualnego katalogu, poziom zagnieżdżenia oraz analogiczne uchwyty… dla każdego takiego poziomu!
Zawracanie głowy, prawda? :) Nic dziwnego, że traktowanie wyszukiwania “per iterator” nie jest popularną praktyką. Z punktu widzenia piszącego algorytm wyliczania nieporównywalnie łatwiej jest po prostu wymusić jakiś callback i wywołać go dla każdego elementu; niech się programista-klient martwi o to, jak ten callback wpasować w swój kod. A że ten byłby o wiele czytelniejszy, gdyby w grę wchodziły iteratory? No cóż, iteratorów tak łatwo pisać się nie da…

…chyba że programujemy w Pythonie. Tam bowiem “iteratory” (zwane generatorami) piszemy w zupełnie unikalny, łatwy sposób. Weźmy dla przykładu taką oto klasę drzewa binarnego (BST – Binary Search Tree):

  1. class Tree:
  2.     def __init__(self, key, left = None, right = None):
  3.         self.key = key
  4.         self.left = left
  5.         self.right = right
  6.     def __insert(self, k): # wstawianie elementu
  7.         if (k < self.key):
  8.             if (self.left != None): self.left.__insert (k)
  9.             else:                   self.left = Tree(k)
  10.         else:
  11.             if (self.right != None): self.right.__insert (k)
  12.             else:                   self.right = Tree(k)
  13.     def insert(self, *keys): # wst. wielu elementów
  14.         for k in keys: self.__insert(k)&#91;/python]
  15. Żeby dało się je przeglądać zwykła pętlą <code>for</code> w porządku <em>inorder</em> (dającym posortowanie kluczy), piszemy do niego odpowiedni generator:
  16. [python]    def inorder(self):
  17.         if (self.left != None):
  18.             for t in self.left.inorder(): yield t
  19.         yield self.key
  20.         if (self.right != None):
  21.             for t in self.right.inorder(): yield t

I już – to wystarczy, by poniższa pętla:

  1. for i in tree.inorder():

rzeczywiście “chodziła” po krawędziach drzewa “w czasie rzeczywistym” – bez żadnego buforowania elementów na liście.

Tajemnica tkwi tutaj w instrukcji yield – działa ona jak “tymczasowe zwrócenie” elementu, który jest przetwarzany przez ciało pętli for. Gdy konieczny jest następny element, funkcja inorder podejmuje po prostu działanie począwszy od kolejnej instrukcji – i tak do następnego yielda, kolejnego cyklu pętli i dalszej pracy funkcji. yield działa więc jak callback, tyle że w obie strony. Całkiem zmyślne, czyż nie?
Aż chciałoby się zapytać, czy w innych językach – zwłaszcza kompilowanych – nie dałoby się zrobić czegoś podobnego. Teoretycznie odpowiedź jest pozytywna: przy pomocy zmyślnych sztuczek na stosie wywołań funkcji (technika zwana ‘nawijaniem stosu’ – stack winding) można uzyskać efekt “zawieszenia funkcji” po zwróceniu wyniku i mieć możliwość powrotu do niej począwszy od następnej instrukcji. Nie jestem jednak przekonany, jak taki feature mógłby współpracować z innymi elementami współczesnych języków programowania, jak choćby wyjątkami. Trudno powiedzieć, czy jest to w ogóle możliwe.

Ale skoro w Pythonie się da, to może już C++2x będzie to miał? ;-)

Tags: , , , , ,
Author: Xion, posted under Programming » 4 comments

Małe algorytmy

2008-10-08 13:44

Informatyka zna świetne rozwiązania wielu złożonych problemów, takich jak sortowanie czy wyszukiwanie najkrótszej drogi. Użycie tych powszechnie znanych algorytmów – nawet tych najbardziej skomplikowanych – jest zwykle całkiem proste. Albo bowiem dysponujemy już gotową implementacją, albo bez większych problemów możemy takową samodzielnie popełnić – z ewentualnymi usprawnieniami własnymi.

Często jednak zdarza się, że trzeba wymyślić coś znacznie mniejszego, rozwiązującego mniej modelowy, ale za to bardziej praktyczny problem. Niepotrzebne jest wtedy arcydzieło algorytmiki, lecz coś, co po prostu będzie dobrze działać. Osobiście uważam, że opracowywanie właśnie takich małych rozwiązań jest jedną z najciekawszych rzeczy w programowaniu w ogóle.
Przykłady? Jest ich tak dużo i są tak odmienne od siebie, że chyba niemożliwe jest podanie choćby kilku odpowiednio reprezentatywnych. Może to być krótki kod parsujący jakiś prosty tekst i wyciągający z niego pewnie informacje. Może to być metoda na przeskalowanie obrazka z zachowaniem jego aspektu (ilorazu szerokości do wysokości). Może to być również kod pozycjonujący jakąś kontrolkę wewnątrz okna o zmiennym rozmiarze. Może też chodzić o wyznaczenie rezultatu pojedynczego ataku w turowej grze strategicznej czy RPG. A nawet o, jak to ktoś ładnie nazwał, “silnik do pauzy” w owej grze ;] I tak dalej…

Niby nic skomplikowanego, czasami wręcz oczywistego – a jednak przecież trzeba to w miarę potrzeb wymyślać i zakodowywać. Bo gotowych rozwiązań problemów tak specyficznych po prostu nie ma. A bez takich małych algorytmów nie działałby żaden program – także ten, który musi używać również i tych “dużych” rozwiązań.
Może więc właśnie tutaj tkwi istota programowania?… Kto wie :)

Tags:
Author: Xion, posted under Programming, Thoughts » 5 comments

Podział wielokątów na trójkąty

2008-04-27 21:39

Podział wypukłego wielokąta na trójkątyKolega rr- rzucił dzisiaj na kanale #warsztat ciekawy problem rysowania dowolnych wielokątów za pomocą samych trójkątów. Jak wiadomo, karty graficzne posługują się właśnie trójkątami, zatem w celu wyświetlenia wielokąta należy go odpowiednio podzielić. Matematycy dowodzą, że jest to zawsze możliwe, i podają prosty sposób dla wielokątów wypukłych: należy po prostu narysować wszystkie przekątne wychodzące z jednego wierzchołka. Nie jest trudno przełożyć ten przepis na kod.

Co jednak z dowolnymi wielokątami? Tu sprawa wydaje się bardziej skomplikowana, chociaż – jak się ukazuje – rysowanie przekątnych można na ten przypadek uogólnić. Wpadłem jednak na inny pomysł, polegający na odpowiednim “chodzeniu” po wierzchołkach naszego wielokąta i “odcinaniu” od niego kolejnych trójkątów brzegowych. Wygląda to mniej więcej tak:

  1. Startujemy od dowolnego wierzchołka wielokąta.
  2. Mając i-ty wierzchołek sprawdzamy, czy da się go połączyć z (i+2)-im (modulo liczba wierzchołków) tak, aby powstały przy tym odcinek mieścił się w wielokącie:
    • jeśli tak, to z wierzchołków: i-tego, (i+1)-ego i (i+2)-ego tworzymy nowy trójkąt, wierzchołek (i+1)-szy usuwamy z wielokąta i przechodzimy do (i+2)-ego
    • jeśli nie da się tak połączyć wierzchołków, przechodzimy do wierzchołka (i+1)-ego i próbujemy dalej
  3. Po wykonaniu pełnego cyklu kontynuujemy przechodzenie po wielokącie, usuwanie wierzchołków i tworzenie trójkątów – aż do momentu, gdy sam nasz wielokąt stanie się trójkątem. Będzie to oczywiście ostatni składający się na niego trójkąt.

Na tym rysunku można prześledzić, jak wyglądają kolejne cykle spaceru po krawędziach wielokąta – oznaczyłem je różnymi kolorami:

Podział dowolnego wielokąta na trójkąty

Z tym sposobem wiąże się oczywiście problem stwierdzenia, czy dany odcinek należy do wielokąta – co w ogólności nie musi być takie proste ani efektywne (może mieć złożoność liniową). Dodatkowo wielokąt może być “wredny” i niezbyt dobrze poddawać się operacji obcinania trójkątów. Na szczęście można udowodnić, że w każdym cyklu da się przynajmniej jeden taki trójkąt wyodrębnić. Te dwa fakty powodują, że cała operacja może mieć złożoność sięgającą nawet O(n3), chociaż pewnie da się ją zaimplementować lepiej.
Jest naturalnie bardzo możliwe, że algorytm ten jest znany od dawna, a ja po prostu nie przeczesałem Internetu dość dokładnie w poszukiwaniu już istniejącego opisu. Jednak biorąc pod uwagę to, co przed chwilą powiedziałem o jego możliwej “efektywności”, nie jest to znów takie pewne ;-) Istnieje aczkolwiek szansa, że może się on przydać komuś, kto implementuje bibliotekę graficzną 2D w oparciu o API w rodzaju DirectX czy OpenGL.

Walidacja wszerz

2007-07-22 18:42

Dzisiaj będzie trochę algorytmicznie :) Zajmowanie się programowaniem grafiki i konstruowaniem silnika jest oczywiście satysfakcjonujące, ale programowanie to przecież nie tylko tworzenie, lecz także rozwiązywanie problemów. Dlatego czasami dobrze jest sobie jakiś problem wynaleźć i go rozwiązać :D

Dzisiejszy wprawdzie nie wziął się znikąd, jako że wynalazłem go już jakiś czas temu przeglądając część mojej biblioteki zajmującą się operacjami na łańcuchach. Zagadnienie dotyczy zaś sprawy dość przydatnej i nie tak znowu trywialnej.
Chodzi tu tzw. filtry wildcards. Jest to bardzo znany (zwłaszcza w Windows) sposób zapisywania szablonów nazw plików, przydatny zwłaszcza przy wyszukiwaniu. Jego reguły są bardzo proste: w filtrze mogą występować w dowolnej ilości dwa znaki specjalne:

  • gwiazdka (*), która symbolizuje dowolny ciąg znaków (także pusty)
  • znak zapytania (?), który symbolizuje dokładnie jeden dowolny znak

Oprócz tego szablon może też zawierać dowolne inne znaki, które muszą być dopasowane dosłownie. Typowe “plikowe” przykłady takich szablonów to:

  • *.exe – pasuje do wszystkich nazw plików wykonywalnych (z rozszerzeniem EXE)
  • file????.tmp – pasuje do file0000.tmp, file0001.tmp, ale też fileqwer.tmp, itd.
  • *.? – pasuje do wszystkich nazw plików z jednoliterowym rozszerzeniem

Wildcards (swoją drogą, ciekawa nazwa – ktoś zna jej pochodzenie?) stały się na tyle popularne, że rozpoznaje je także większość wyszukiwarek internetowych. Są bowiem całkiem elastyczne, a o wiele prostsze od wyrażeń regularnych.

Jaki więc problem jest z nimi związany? Chodzi po prostu o sprawdzenie, czy podany ciąg znaków pasuje do podanego wzorca wildcards. Na pierwszy rzut oka może wydawać się to proste – niby wystarczy szukać kolejnych “części stałych” i sprawdzać, czy odstępy między nimi są odpowiednio duże. Ten algorytm jest jednak niepoprawny, bowiem czasami znaki sprawdzanego tekstu musimy traktować na różne sposoby. Przykładowo dla szablonu “a*ba” ciąg “ababa” będzie uznany za niepoprawny, gdyż algorytm dopasuje pierwsze “ba” z tekstu do “ba” zapisanego na sztywno we wzorcu zamiast potraktować je jako dowolny ciąg pasujący do gwiazdki.
Poprawne rozwiązanie musi sprawdzać wszystkie możliwe dopasowania – w tym przypadku oba wystąpienia ciągów “ba”. W swoim algorytmie dla poprawienia efektywności zastosowałem jeszcze wstępne przetwarzanie, dzielące wzorzec na fragmenty – czyli części stałe – oraz zakresy – sekwencje znaków * i ?. Samo sprawdzanie polega natomiast na znajdowaniu wszystkich wystąpień fragmentów, które są w odpowiedniej odległości od siebie (wyznaczanej przez zakresy) i dodawaniu ich do kolejki. Potem są one pobieranie i używane do znalezienia dopasowań następnego fragmentu.
Zasadniczo jest to bardzo podobne do przeszukiwania wszerz wyimaginowanego “grafu dopasowań”. Swoją drogą to ciekawe, że szkielet tego algorytmu grafowego może być użyty do tak wielu rzeczy (jak np. wyszukiwanie najkrótszej drogi między dwoma miastami (algorytm Djikstry) czy szukanie węzłów XML pasujących do wyrażenia XPath). Tak jest oczywiście dlatego, że w tych problemach zawsze wchodzi w grę jakiś mniej lub bardziej intuicyjny graf, tyle że w większości wypadków zastanawianie się nad tym, jak on wygląda, nie ma zbytniego sensu. A tak przy okazji, to w moim algorytmie wildcards można by zmienić kolejkę na stos i wszystko byłoby OK – wtedy mielibyśmy po prostu coś w stylu przeszukiwania wgłąb.

Hmm… wyszedł z tego trochę przydługi miniwykładzik ;) Pozwolę sobie jednak nie kończyć go nieodzowną kwestią “Czy są jakieś pytania” – załóżmy po prostu optymistycznie, że pytań nie stwierdzono ;)

Tags: ,
Author: Xion, posted under Programming » Comments Off on Walidacja wszerz
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.