Monthly Archives: December 2012

Przykład do zadania 2

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)]

Bash – zajęcia 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:

  1. W pliku avgs.txt dana jest lista miejscowości wraz ze średnią temperaturą w grudniu. Posortuj ją używając potoków w kolejności rosnącej średniej temperatury.
  2. Wypisz nazwę i rozmiar 5 największych plików z katalogu domowego.
  3. Przeszukaj swój katalog domowy rekurencyjnie i znajdź wszystkie wystąpienia plików o tej samej nazwie (mogą się różnić co najwyżej wielkością liter). Na wyjściu chcemy dostać takie nazwy poprzedzone liczbą wystąpień.
  4. Policz liczbę takich nieunikalnych nazw plików z poprzedniego zadania.
  5. Wypisz do pliku bests.txt początek, koniec i score z pliku dmel.gff posortowane po score do pliku best_scores.txt.
  6. Wypisz wartości score z wygenerowanego pliku best_scores.txt na pozycjach od 1000 do 2000.

Lab 9

  1. Napisz funkcję zip_code(s), która sprawdzi, czy napis s jest poprawnym polskim kodem pocztowym.
  2. Napisz funkcję remove_numbers(s), która usunie z napisu s wszystkie cyfry.
  3. Napisz funkcję sum_all(s), która dla zadanego napisu s zsumuje wszystkie liczby całkowite występujące w napisie s.
  4. Napisz funkcję trim_all(s), która zamieni wszystkie ciągi białych znaków w napisie s na pojedynczą spację, czyli np.
    trim_all("Ala     ma kota   .")=="Ala ma kota ."
  5. Załóżmy, że mamy napisać fragment strony internetowej w języku przypominającym html. Do dyspozycji mamy trzy rodzaje znaczników: em, b i br. Znaczniki em i b otaczają fragment tekstu powodując zmianę wyglądu jego czcionki. Z tego powodu występują dwie odmiany tych znaczników: odmiana otwierająca (<em>, <b>) i zamykająca (</em>, </b>). Znacznik br natomiast występuje tylko w jednej wersji (<br/>) powodującej złamanie wiersza w miejscu jego wystąpienia. Dodatkowo chcemy, aby były to jedyne znaczniki występujące w tekście (nie chcemy innych wystąpień znaków < i > w tekście) oraz nie chcemy, aby wewnątrz znaczników em i b znajdowały się inne znaczniki oraz chcemy, aby znaczniki były poprawnie domknięte. Napisz funkcję test_markups(s), która sprawdzi, czy napisany przez nas tekst s spełnia te wymogi.
  6. Napisz funkcję pretty_printer(s), która znajdzie wszystkie wystąpienia liczb całkowitych w tekście s i wypisze je w oddzielnych liniach w formacie:

    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.

  7. Napisz za pomocą pojedynczego wyrażenia regularnego funkcję, która dla pliku dmel stworzy nowy plik, składający się ze wszystkich wpisów o funkcji OrthoDB i roli orthologous_to, które zawierają dwa wystąpienia tego samego znaku (+ lub -). Dodatkowo chcemy, aby w nowym pliku kolumny zawierające początkową i końcową pozycję wpisu były ze sobą zamienione miejscami.

Drugie zadanie zaliczeniowe (20 punktów)

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!

Zadania powtórkowe przed kolokwium poprawkowym

  1. Dana jest tablica kwadratowa A rozmiaru n x n wypełniona liczbami całkowitymi. Napisz funkcje sum_iter(A) i sum_rec(A) zwracające tablicę B, która na pozycji (i, j) ma sumę wszystkich pozycji (k, l) z tablicy A, dla których 0 ≤ k ≤ i i 0 ≤ l ≤ j.
  2. Niech S(f, n) oznacza sumę wartości funkcji f dla wszystkich liczb naturalnych od 0 do n. Funkcja g zdefiniowana jest tak:
    • g(0) = 1
    • g(n) = S(g, n-1) + 6, dla n > 0.

    Funkcja h natomiast zdefiniowana jest tak:

    • h(0) = 2
    • h(n) = S(h, n-1) – S(g, n-1) + 6, dla n > 0.

    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.

  3. Napis s został zakodowany w taki sposób, że wszystkie jego spółgłoski i samogłoski zostały ułożone w odwrotnej kolejności, tzn. pierwsza samogłoska została zamieniona kolejnością z ostatnią, następnie druga z przedostatnią, itd. Analogicznie postępowano ze spółgłoskami. Napisz procedurę decode(s), która zdekoduje napis s zakodowany opisanym szyfrem.

Lab 8

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.