@ MIM UW
Chcieli Państwo przykład do zadania drugiego.
Np. Jeśli weźmiemy następujący opis planszy:
4
5
p 1 3 1
l 1 5 2
l 2 3 1
j 3 3 2
s 4 4 -3
j 4 3 -2
p 4 2 2
to wyświetla nam się coś takiego
A funkcja play([2,3,2,2,4,3,3,6,5,2]) zwraca:
[(1, 1),
(1, 3),
(1, 3),
(3, 5),
(1, 4),
(3, 5),
(4, 5),
(4, 2),
(4, 2),
(4, 2),
(4, 1)]
Prezentacje:
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi1u.pdf
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi2u.pdf
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi3u.pdf
Zadania:
Wyrażenia regularne:
Howto
trim_all("Ala ma kota .")=="Ala ma kota ."
start end number number_pow
gdzie start i end to początkowa i końcowa pozycja liczby number w tekście s, a number_pow to liczba 2 podniesiona do potęgi number.
Zadanie polega na symulacji ruchów graczy w zmodyfikowanej wersji gry “drabiny i węże” (zobacz strona gry na wikipedii).
Zasady gry:
Numeracja pól:
Plansza ma wymiar n x m. Numery pól będziemy oznaczać jako krotki (k,l) liczb całkowitych, gdzie 1 ≤ k ≤ n i 1 ≤ l ≤ m. Pole numer (1,1) znajduje się w lewym dolnym rogu. Kolejne pola numerowane są według następującej zasady: numery są przydzielane kolejno liniami poziomymi, przy czym kolejność przydzielania numerów w następujących po sobie liniach poziomych jest przeciwna. Przydział początkowych numerów wygląda więc następująco: 1->(1,1), 2->(1,2), …, m->(1,m), m+1->(2,m), …, 2m->(2,1), …, 2m+1->(3,1), … . W razie wątpliwości sytuacja została zilustrowana tu dla planszy o wymiarach 10×10. W szczególności taka kolejność oznacza, że w zależności od parzystości n pole końcowe – (m, n) może znaleźć się w lewym górnym lub prawym górnym rogu planszy.
Zasady ogólne:
Gracz porusza się po planszy w przód zgodnie z zadaną sekwencją rzutów kostką. Na planszy występuje kilka rodzajów pól specjalnych parametryzowanych liczbą całkowitą (dodatnią w wypadku pauz):
– skoki o k pozycji do tyłu lub do przodu
– pauzy – stanięcie na takie pole powoduje zignorowanie k kolejnych rzutów i pozostanie na obecnej pozycji w k następnych kolejkach
– drabiny i węże – stanięcie na takie pole przenosi gracza o k poziomów planszy (linii poziomych) w górę (drabiny) lub w dół (węże)
Gra kończy się po osiągnięciu przez gracza ostatniego pola, przy czym dokładny sposób zakończenia gry różni się w zależności od wersji gry.
Opis planszy:
Format pliku z planszą jest następujący:
<n>
<m>
<a_1> <r_1> <c_1> <k_1>
<a_2> <r_2> <c_2> <k_2>
…
gdzie:
<n> to liczba całkowita dodatnia, wskazująca liczbę wierszy
<m> to liczba całkowita dodatnia, wskazująca liczbę kolumn
<a_i> to litera, oznaczająca typ pola specjalnego: “p” – pauza, “j” – skok, “l” – drabina/wąż
<r_i>, <c_i> to liczby całkowite dodatnie oznaczające odpowiednio wiersz i kolumnę pola specjalnego
<k_i> to w przypadku pauzy – liczba całkowita dodatnia oznaczająca długość pauzy; w przypadku skoku – liczba całkowita (być może ujemna lub zero), oznaczająca ilość pól, o które gracz zostanie przesunięty, po stanięciu na tym polu (liczba ujemna oznacza ruch w tył); w przypadku drabiny/węża – liczba całkowita, oznaczająca liczbę poziomów górę (liczba dodatnia, drabina) lub w dół (liczba ujemna, wąż), o które dana drabina/wąż przenosi (zakładamy, że te ruchy zawsze odbywają się w osi pionowej).
Będziemy rozważać dwie odmiany gry:
– odmiana łatwiejsza:
Można założyć, że na planszy nie ma pól cyklicznych, czyli skoków/drabin/węży przenoszących gracza w nieskończoność pomiędzy polami. Gra kończy się, gdy gracz stanie na ostatnim polu lub “przekroczy” je.
– odmiana trudniejsza:
Na planszy mogą występować sekwencje cykliczne, których należy unikać. W wypadku braku możliwości dojścia do mety z tego powodu, należy zwrócić None. Gra kończy się, gdy gracz znajdzie się dokładnie na ostatnim polu (ruch, który powodowałby przejście za ostatnie pole jest ignorowany – gracz pozostaje w tym samym miejscu). Fakt ten należy odnotować na liście ruchów.
Zadanie:
1) (4pkt) Napisz funkcje encode(coords) i decode(square_no), które odpowiednio zakodowują pozycję dwuwymiarową coords=(a,b) na numer pola i odkodowują numer pola square_no do współrzędnych dwuwymiarowych.
2) (2pkt) Napisz funkcję show_board(), która wypisze sytuację na planszy w danym momencie gry. Po lewej stronie oraz na dole planszy powinny zostać wypisane współrzędne. Pole, na którym stoi gracz powinno być oznaczone literą D. Drabiny oznaczamy literą L oraz liczbą oznaczającą długość drabiny (np. L5), węże literą S (znowu z długością, np. S3), skoki literą J (np. J4), a pauzy literą P zakończoną ilością kolejek (np. P4). Plansza powinna wyglądać “ładnie”, tzn. każde pole powinno mieć odpowiedni i taki sam wymiar. Przykład dla planszy 10×10:
10 S8 P3
9
8 L2
7 D
6 P1
5
4 J4
3 L3
2
1
1 2 3 4 5 6 7 8 9 10
3) (6pkt w wersji łatwiejszej, 8pkt w wersji trudniejszej) Napisz funkcję play(board, rolls), która dla listy rzutów kostką rolls i nazwy pliku z opisem planszy board zwróci listę pozycji, na których znajdował się gracz po wyrzuceniu odpowiednich liczb oczek z listy rzutów. Pomijamy na tej liście początkową pozycję gracza (pole (1, 1)), a jako końcową pozycję przyjmujemy ostatnie pole (nawet jeśli implementujemy wersję “łatwiejszą” i ostatni rzut powodował “przekroczenie” ostatniego pola). Jeśli chodzi o uwzględnianie skoków, drabin i węży, to po danym ruchu zapisujemy tylko końcową pozycję gracza, a nie możliwą sekwencję ruchów po polach specjalnych, prowadzących ostatecznie do tej pozycji. Każdą k-kolejkową pauzę odnotowujemy jako k+1-krotne pozostanie na tym samym polu. Pozycję gracza zapisujemy w formacie (i, j), gdzie i jest numerem wiersza, a j kolumny pola, na którym znajduje się gracz.
4) (6pkt) Wprowadźmy do gry następującą zasadę: w razie wyrzucenia przez gracza sześciu oczek, wykonuje on odpowiedni ruch o sześć pól do przodu, po czym podejmuje decyzję:
– może pozostać na tym polu, z ew. tego skutkami, tzn. jeśli w tym miejscu znajduje się pole specjalne, to wykonujemy przypisaną mu akcję, lub
– może wykonać następny ruch wynikający z kolejnego rzutu kostką, pomijając przy tym efekt ew. pola specjalnego, na którym znajduje się gracz (wtedy wyrzucenie początkowo szóstki daje efekt sklejenia pierwszego ruchu z kolejnym). Akcja ta może być propagowana dalej, tzn. można skleić np. 6, 6, 3 w jeden ruch o długości 15. W wynikowej sekwencji pozycji taki ruch odnotowywany jest jako oddzielne ruchy, czyli sklejenie ruchów o długości 6, 6, 3 będzie działało jak jeden ruch, ale zostanie odnotowane jako trzy oddzielne ruchy.
Zadanie polega na napisaniu funkcji optimal_path(board, rolls), która dla nazwy pliku board, zawierającego opis planszy i listy rzutów kostką rolls, znajdzie ścieżkę prowadzącą do ostatniego pola, która wykorzystuje minimalną możliwą liczbę rzutów kostką. Wynikiem jest sekwencja pozycji, na których znajdował się gracz po wykonaniu kolejnych ruchów.
Dodatkowe założenia:
Można założyć, że wszystkie pola specjalne znajdują się w obrębie planszy, a skoki, drabiny i węże nie wyprowadzają poza nią. W razie, gdy sekwencja rzutów kostką (w zadaniu 1) nie pozwala na przejście gry, należy zwrócić sekwencję pozycji gracza aż do wykorzystania wszystkich dostępnych rzutów kostką (włącznie z pozycją po ostatnim rzucie). Można też założyć, że ostatnie pole nie jest specjalne. Jest to szczególnie istotne w przypadku, gdy implementujemy “odmianę trudniejszą” i np. wąż w tym miejscu nie dawałby szansy przejścia gry w ogóle.
Szczegóły implementacyjne:
Zadania w postaci kodu źródłowego (w jednym pliku zadanie2_nr-indeksu.py) przesyłają Państwo do obu prowadzących ćwiczenia (bartek@mimuw.edu.pl i pawel.bednarz@mimuw.edu.pl) do rozpoczęcia wykładu dnia 07.01.2013 . Proszę o umieszczenie w tytule e-mail’a hasła [WDI-2] i o wysyłanie ze skrzynek studenckich (aby łatwiej było zidentyfikować autora i ew. “zapożyczenia”). W tym zadaniu będziemy zwracać większą uwagę na ścisłe trzymanie się detali poleceń. W związku z tym proszę zwrócić uwagę na nazwy przesyłanych plików, nazwy i interfejsy implementowanych funkcji, format zwracanych wyników, zapis pozycji na liście itd.
Powodzenia!
Funkcja h natomiast zdefiniowana jest tak:
Napisz rekurencyjne i iteracyjne wersje funkcji g i h. Która z nich działa szybciej? Spróbuj policzyć h(10) dla każdej z nich.
Dzisiejszym zadaniem jest stworzenie pakietu testującego szybkość napisanych przez nas funkcji sortujących. Do zadań pakietu należeć będzie wczytywanie list – instancji problemów zapisanych w kilku różnych formatach, a następnie opracowanie porównania szybkości działania różnych funkcji sortujących na wczytanych listach. Dodatkowo chcemy mieć funkcję generate_list(file_name, swaps_no, length), która zapisze do pliku o ścieżce file_name listę liczb naturalnych od 1 do length wg algorytmu o następującym pseudokodzie:
a ← range(length)
for i from swaps_no to 1
do
di ← random element of { 0, ..., (length - swaps_no + i - 2) }
swap a[di] and a[length - swaps_no + i - 1]
return a
Szczegóły implementacji:
Pakiet ma się składać z trzech modułów. Pierwszy z nich będzie zawierał funkcje sortujące (ważne, żeby były to funkcje o takim samym interfejsie, czyli przyjmujące jako jedyny parametr listę, a zwracające listę posortowaną). Drugi moduł będzie zawierał funkcje wczytujące listy z plików w następujących formatach:
li1:
[4, 3, 1, 2, 4, 5]
li2:
4
3
1
2
4
5
li3:
4 3 1 2 4 5
W drugim module powinny się znaleźć trzy funkcje, które przyjmują jako parametr nazwę pliku, a zwracają wczytaną z tego pliku listę.
Trzeci moduł ma przeszukiwać bieżący katalog w poszukiwaniu instancji problemów (plików o rozszerzeniach li1, li2 lub li3) i dla każdego z takich plików ma wywoływać wszystkie dostępne w pierwszym module funkcje testujące wraz z informacją na temat czasu działania każdego z nich na poszczególnych instancjach problemu. Dodatkowo ma zawierać funkcję generate_list.
Trzeci moduł powinien dawać się wywoływać z linii poleceń za pomocą polecenia: python compare_sorts.py [opcje]. Powinien udostępniać przynajmniej opcje:
-h – pomoc na temat sposobu wywołania skryptu
-g len – generowanie zestawu 9 plików testowych, zawierających listy o długości len, po trzy w każdym formacie. Dla każdego formatu pliki powinny zostać wygenerowane funkcją generate_list z parametrami swaps_no równymi odpowiednio 10, (len / 3) i len – 1.