Teaching

Wyrażenia regularne:
Howto

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.

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!

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.

Moduł wdi (w archiwum wdi.tgz)

slajdy tu

 

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.

Dzis zamiat slajdow do wykladu plik z kodem i komentarzami:

 

#WDI Wykład 6

#O zmiennych,
#czyli 100 sposobów strzelenia sobie w stopę

#Bartek Wilczyński

#zmienne lokalne w funkcjach

#Funkcje mogą używać zmiennych lokalnych
y=3
def f():
#tu juz nie widze zmiennej globalnej y
y=5
return y

#mogą też używać zmiennych globalnych
def g():
#tu widze zmienna y
return y

#ale nie mozemy mieszac tych dwoch stylow!

#to bedzie dzialac
def py():
print y

#a to juz nie!
def ppy():
print y
y=1

#Dlaczego? Dlatego, że zmienna y byłaby globalna w 1 linii i lokalna w 2giej

#Czasem chciałbym _zapisać_ coś na zmiennej globalnej
#mogę wtedy użyć deklaracji "global"
#np. tak:

count=0
def add_count():
global count
count+=1
return count

#to oczywiscie bez global nie zadziala...
def add_count():
#global count
count+=1
return count

#A jakie sa argumenty funkcji: globalne, czy lokalne?
y=1
def f(x):
x+=1
return x
print f(y)
y

#jak widac - lokalne,
#tzn nie nie mozemy nadpisac zmiennej globalnej, przekazanej przez parametr

#Ale, czy tak jest zawsze?

def f(x):
x+=x
#jesli uzyje f(liczba), to dobrze
y=1
f(y)
y

#ale dla list dzieje sie cos dziwnego...
l=[1,2]
f(l)
l

#co ciekawe, lekka zmiana funkcji f:
def f(x):
x=x+x

#naprawia dzialanie dla list
l=[1,2]
f(l)
l
# i nie psuje dla liczb:
y=1
f(y)
y

# O co tu chodzi????

#Podobny mechanizm bedzie dzialal dla list i slownikow przy wstawianiu

def f(x):
x[0]=1

#
l=[1]
f(l)
l

d={}
f(d)
d

#Otóż chodzi o to, że python "ulokalnia" zmienne tylko wtedy
#gdy używamy instrukcji przypisania np x=x+x
# a nie wtedy gdy "uzywamy" zmiennej:
#np x[0]=1 czy nawet x+=x

#Ale dlaczego f(x) dzialalo dla liczb? def f(x):
def f(x):
x+=x
print x
#jesli uzyje f(liczba), to dobrze
y=1
f(y)
y

#???

I jeszcze dla napisów też:
s="ala"
f(s)
s
#???????

#Otóż to się wiąże z różnymi rodzajami zmiennych:
# modyfikowalne (mutable) - takie jak listy i słowniki
# niemodyfikowalne (immutable) - takie jak liczby i napisy

#zmienne modyfikowalne będą "pozwalały" zmieniać swoją wartość
#a niemodyfikowalne - nie

#to się wiąże z pojęciem referencji, czyli "odnosnika" do wartosci
#w pythonie (jak w wiekszosci jezykow dynamicznych) miedzy wartosciami (miejsca w pamięci)
#a zmiennymi sa referencje
#zwykle podczas przypisania zmieniamy tylko referencje:

l=[1,2,3]
l2=l
l2+=[1]
l
# zmienna l2 jest tylko "referencja" do zmiennej l
# to samo dzieje sie w przypadku przekazywania parametrow
#python uzywa przekazywania "przez referencje"

#ale zmienne niemodyfikowalne sa bardziej skomplikowane:

s="ala"
s2=s
s2+="ala"
#tutaj w momencie przypisania dokonywane jest "odwiazanie" (dereferencja)...
print s
print s2

#Mozemy sprawdzac "rownosc" referencji przy pomocy funkcji id() i konstrukcji "is"

l=[1]
l2=l #ta sama lista
l3=[1] # inna lista...?

id(l)
id(l2)
id(l3)

l==l2 #?
l==l3 #?

l is l2 #?
l is l3 #?

#To oczywiscie dziala inaczej dla wartosci niemodyfikowalnych

s="ala"
s2=s # ten sam napis
s3="ala" # inny napis?

s is s3 #?

#Trzeba tez bardzo uważać zinicjowaniem list...
ll= [[]] *5
print ll
ll[0].append(0)
print ll[0] # ok

print ll #oops!

#ale tez z parametrami domyslnymi

def f(l=[]):
l.append(1)
return l

print f() #ok...
print f() # ???

#No to jak "rozplesc" dwie listy?

l=[1,2,3]
l2=l
l3=l[:]

l2.append(2)
l3.append(3)
print l2
print l3
print l #?

#ze slownikami jest podobnie, do kopiowania sluzy metoda .copy()

d={}
d2=d
d3=d.copy()

d[1]=[]
print d,d2,d3

d[1].append(1)
print d

#ale kopiowanie jest "plytkie"...
d4=d.copy()
print d4

d[1].append(2)
print d4
## Juz wartosci pod kluczami pozostaja "wspolne"....

#Mamy na szczescie modul copy
import copy

#ktory umie robic kopie "glebokie":
d5=copy.deepcopy(d)
print d,d5
d[1].append(4)

print d,d4,d5

#Sprobujmy sobie jeszcze skomplikowac zycie,
#I zdefiniujmy funkcje wewnatrz funkcji:

y=1
def f(x):
y=5
def g(x):
y=x+6
return y
print y
return y+g(x)

f(y) #?
y #?

y=1
def f(x):
y=5
def g(x):
global y # mala zmiana?
y=x+6
return y
print y #tego y'ka nie ruszylismy...
return y+g(x)

f(y)
y

# A co sie stanie jesli zmienimy wartosc zmiennej po deklaracji funkcji...

x=1
def f():
return x

f()
x=2
f()

#Chyba, ze uzyjemy "domkniecia":

def pomnoz_przez(x):
def f(y):
return x*y
return f

x=5
przez_5=pomnoz_przez(x)
przez_5(10)
x=20
przez_5(20)

#
#

slajdy tu

Słowniki:

1. Stwórz pusty słownik. Zapoznaj się z funkcjami, jakie są dla niego dostępne. Dodaj do niego następujące elementy: pod kluczem 1 wartość 3, 5->2, “a”->4. Usuń jeden z elementów używając metody del, a drugi używając metody pop. Przypisz na pozostały element wartość 10.
2. Sprawdź, jak działają metody iterkeys, itervalues, iteritems. Której z nich odpowiada zwykła iteracja pętlą for?
3. Stwórz słownik dla tekstu z zadania 4 (lab4), w którym kluczem będzie numer słowa w tekście, a wartością to słowo. Użyj funkcji enumerate.
4. Stwórz funkcję zwracającą dla zadanego napisu słownik, który pod indeksem odpowiadającym danemu słowu zawiera jego długość.
5. Rozwiąż poprzednie zadanie używając funkcji map i zip.
6. Używając klasy defaultdict (moduł collections) stwórz funkcję zwracającą dla danego słowa słownik, który pod indeksem odpowiadającym danej literze będzie zawierał liczbę jej wystąpień.
7. Używając klasy defaultdict stwórz dla zadanego napisu słownik, zawierający dla słów z napisu ilość ich wystąpień.
8. Rozwiąż zadanie 5.2 (lab 4) korzystając ze słowników.

Zbiory:

1. Stwórz zbiór słów z napisów “alabama” i “alaska”. Jak wygląda różnica pomiędzy jednym zbiorem a drugim (użyj operatora “-“)?
2. Zobacz jakie inne funkcje na zbiorach są dostępne w pythonie.
3. Stwórz zbiór słów z pliku the_emperors_new_clothes.txt (usuń najpierw znaki interpunkcyjne zastępując je spacjami).
4. Stwórz również zbiór słów z pliku the_bell.txt i wypisz słowa występujące w pierwszym, ale nie występujące w drugim.
5. Znajdź słowa, które występują dokładnie w jednym z powyższych plików oraz słowa wspólne dla obu plików.
6. Dla danego zbioru wygeneruj jego zbiór potęgowy (zbiór wszystkich podzbiorów tego zbioru).

1. Binarny ciąg Van der Corputa powstaje poprzez odwracanie zapisu binarnego kolejnych liczb naturalnych. Przed odwróceniem zapisy binarne są najpierw uzupełniane zerami do odpowiedniego miejsca. Np. jeśli rozpatrujemy ciąg trzycyfrowy (w zapisie binarnym), to przed odwróceniem mamy ciąg zapisów: [000, 001, 010, 011, 100, 101, 110, 111], co tłumaczy się na ciąg [0, 1, 2, 3, 4, 5, 6, 7]. Po odwróceniu zapisów mamy natomiast [000, 100, 010, 110, 001, 101, 011, 111], co tłumaczy się na ciąg [0, 4, 2, 6, 1, 5, 3, 7]. Napisz funkcję vdcorput(p), która dla zadanej liczby cyfr p zwróci odpowiadający jej ciąg Van der Corputa.
2. Napisz iteracyjną i rekurencyjną wersję funkcji incr_segment(v), która dla zadanej listy v zwróci jej najdłuższy rosnący segment (spójny kawałek).
3. Napisz funkcję prefix(s, w), która dla dwóch słów s i w zwróci najdłuższy wspólny prefix obu słów.
4. Napisz funkcję ol_concat(s, w), która sklei ze sobą dwa słowa być może nakładając na siebie koniec s z początkiem w lub koniec w z początkiem s (jeśli są identyczne) aby otrzymać najkrótsze w tym sensie połączenie tych słów. Np. dla słów ol_concat(kajak, kredka) powinno być równe kredkajak, gdyż można je skleić albo do kredkajak, albo do kajakredka, ale pierwsze z tych słów jest krótsze w zapisie.
5. Napisz funkcję convert(n, p1, p2), która przekształci liczbę n w systemie p1-tkowym na liczbę w systemie p2-tkowym. Można założyć, że zarówno p1 jak i p2 są z przedziału [2, 9]. Np. convert(23, 10, 2)=10111.
6. Zaimplementuj funkcję bucket_sort(v), która posortuje ciąg liczb całkowitych z przedziału [-10000; 10000] używając sortowania kubełkowego.