Month: December 2013

Nie łatwo być Mikołajem. Każdego roku trzeba przeczytać miliony listów i wywnioskować z nich, o jakich prezentach marzą dzieci. Później życzenia przekazuje się elfom, które skrzętnie wyszukują w magazynach odpowiednie przedmioty i pakują je do paczek. Następnie zamiast w Wigilię spokojnie zajadać się barszczem wsiada się na sanie i gimnastykuje w kominach, żeby każda paczka trafiła do odpowiedniego adresata. Ponieważ jednak mamy XXI wiek, możemy wspomóc Mikołaja w jego corocznych wysiłkach. W tym celu napiszemy pakiet mikolaj_2_0, który usprawni system roznoszenia prezentów w przyszłym roku.

Pakiet będzie składał się z trzech modułów: listy, magazyn i dostawa.

Zadaniem modułu listy będzie obsługa przychodzącej korespondencji i przekazywanie do magazynu życzeń w postaci list opatrzonych adresami dzieci. Zakładamy, że listy, które przychodzą są już przepisane komputerowo i w postaci plików zapisane na twardym dysku. Przykładowe pliki z listami to list1.txt i list2.txt. W module listy powinny się znaleźć dwie funkcje.
Pierwsza o nazwie adres(plik) zwróci napis reprezentujący adres dziecka dla listu zapisanego w pliku. Adres to ciąg znaków następujący po napisie Adres: (na końcu jest spacja), aż do ostatniej napotkanej kropki w linijce adresu (kropka nie jest częścią adresu).
Druga funkcja, prezenty(plik), znajduje w pliku wszystkie wystąpienia nazw prezentów wraz z poprzedzającą ją liczbą sztuk. Zakładamy, że nazwą prezentu jest każde słowo następujące po wystąpieniu liczby w tekście listu. Zakładamy, że interesują nas tylko prezenty występujące w tekście po adresie. Nie przejmujemy się odmianą wyrazów – można bezpiecznie założyć, że kolejka i kolejki to dwa różne prezenty. Jako wynik funkcja prezenty zwraca słownik, którego kluczami są nazwy prezentów, a wartościami jest łączna liczba sztuk prezentu wymieniona w liście. W jednym liście dany prezent może występować kilka razy (wtedy interesuje nas suma ilości sztuk tego prezentu). Można założyć, że w każdym liście jest mowa przynajmniej o jednym prezencie.
Dla przykładu:

adres(“list1.txt”) == “ul. Basniowa 5/10, 25-231 Otwock”

prezenty(“list1.txt”) == {“samochodziki”: 2, “klocki”: 1}

W module magazyn dostępne będą dwie funkcje.

Pierwsza z nich – uzupelnij(plik) wczytuje dane z pliku i zwraca słownik, którego kluczami są nazwy produktów, a wartościami – ich ilości, z pliku w formacie:
produkt1 ilość1
produkt2 ilość2
…
Przykładowy plik w tym formacie to magazyn.txt.

Druga natomiast (rozdziel(magazyn, zyczenia)) służy do podejmowania decyzji, jakie prezenty dzieci dostaną w tym roku. Wynikiem funkcji jest słownik, gdzie kluczami jest adres dziecka, a wartością para: (nazwa prezentu, ilość). Prezenty przydzielane są według następujących zasad. Każde dziecko dostaje ze swojej listy tylko jeden prezent (przy czym zawsze w ilości, którą sobie zażyczyło). Spośród dzieci, którym prezent nie został jeszcze przydzielony, realizowane jest największe pod względem ilości zamówienie, dla którego w magazynie jest odpowiednia liczba przedmiotów. W przypadku kilkorga dzieci z tym samym, maksymalnym możliwym do realizacji życzeniem, pierwsze w kolejności dostaje prezent dziecko, którego adres jest mniejszy leksykograficznie. W przypadku remisów w ramach życzeń jednego dziecka, dziecko dostaje prezent, którego nazwa jest mniejsza leksykograficznie. Procedura powtarzana jest do momentu, kiedy żadne życzenie nie może już być zrealizowane. Wszystkie dzieci, którym w wyniku tej procedury nie przydzielono jeszcze prezentu dostają w wynikowym słowniku rózgę (a dokładniej parę (“rozga”, 1)). magazyn jest słownikiem postaci takiej, jak zwracana z funkcji uzupelnij. zyczenia natomiast to słownik, w którym kluczami są adresy dzieci, a wartościami słowniki w formacie jak zwracany przez funkcję prezenty.

Dla przykładu:

uzupelnij(“magazyn.txt”) == {“klocki”: 5, “samochodziki”: 3, “rowery”: 2}

rozdziel({“klocki”: 5, “samochodziki”: 2, “wrotki”: 4}, {“ul. Krucza 2/3, Krakow”: {“klocki”: 4, “wrotki”: 4}, “ul. Wolominska 17/27, Warszawa”: {“klocki”: 4, “samochodziki”: 5}, “ul. Gdynska 5/2, Gdansk”: {“wrotki”: 3, “klocki”: 1}, “ul. Czysta 24/7, Czestochowa”: {“samochodziki”: 2, “rowery”: 6}}) == {“ul. Krucza 2/3, Krakow”: (“klocki”, 4), “ul. Wolominska 17/27, Warszawa”: (“rozga”, 1), “ul. Gdynska 5/2, Gdansk”: (“wrotki”: 3), “ul. Czysta 24/7, Czestochowa”: (“samochodziki”: 2)}

W module dostawa należy zaimplementować dwie funkcje.

Pierwsza – zapotrzebowanie(magazyn, zyczenia) – pomoże Mikołajowi odpowiednio uzupełnić magazyn przed przyszłymi świętami. Parametry przekazywane są w tym samym formacie, co w przypadku funkcji rozdziel. Wynikiem jest słownik zawierający jako klucze nazwy prezentów występujące w zyczeniach, a jako wartości liczbę sztuk prezentu, której zabrakło, aby móc obdarować wszystkie dzieci prezentem o tej nazwie w ilości przez nie zgłaszanej w listach (tzn. jeśli troje dzieci życzyło sobie dostać po 3 paczki klocków, a w magazynie było ich tylko 5, to w wynikowym słowniku powinna się znaleźć liczba 4). Jeśli danego prezentu jest w magazynie odpowiednia ilość, nie należy zawierać jego nazwy w wynikowym słowniku.

Ostatnią funkcją jest funkcja kiedy_prezent(adres, prezenty), która będzie zupełnie nową usługą zaproponowaną dzieciom przez Mikołaja. Dzięki niej każde dziecko, podając swój adres, będzie mogło się dowiedzieć, jako które w kolejności dostanie swój prezent. Mikołaj roznosi prezenty w kolejności alfabetycznej, tzn. rózga zawsze będzie dostarczona później niż klocki. Na swoje sanie Mikołaj zabiera tylko prezenty jednego typu i wędruje od adresu do adresu w kolejności alfabetycznej, po czym wraca do Laponii po kolejny typ prezentu. adres to napis – adres dziecka, a prezenty to słownik w formacie takim, jak wynik funkcji rozdziel. Opisana wcześniej procedura wyznacza jednoznacznie kolejność, w jakiej Mikołaj będzie odwiedzał kolejne dzieci. W szczególności w którymś momencie odwiedzi dziecko o podanym adresie. Jako wynik funkcja kiedy_prezent powinna zwracać właśnie numer przypadający temu dziecku na trasie Mikołaja. Zakładamy, że adres występuje jako klucz słownika prezenty. Przyjmujemy pythonową numerację kolejności – pierwsze dziecko ma numer 0.

Dla przykładu:
zapotrzebowanie({“klocki”: 5, “samochodziki”: 2, “wrotki”: 4}, {“ul. Krucza 2/3, Krakow”: {“klocki”: 4, “wrotki”: 4}, “ul. Wolominska 17/27, Warszawa”: {“klocki”: 4, “samochodziki”: 5}, “ul. Gdynska 5/2, Gdansk”: {“wrotki”: 3, “klocki”: 1}, “ul. Czysta 24/7, Czestochowa”: {“samochodziki”: 2, “rowery”: 6}}) == {“klocki”: 4, “wrotki”: 3, “samochodziki”: 5, “rowery”: 6}.
kiedy_prezent(“ul. Wolominska 17/27, Warszawa”, {“ul. Wolominska 17/27, Warszawa”: (“wrotki”, 3), “ul. Krucza 2/3, Krakow”: (“wrotki”, 4) , “ul. Czysta 24/7, Czestochowa”: (“wrotki”, 2), “ul. Gdynska 5/2, Gdansk”: (“klocki”, 1)}) == 3

Punktacja za poszczególne funkcje:

• adres – 2pkt
• prezenty – 3pkt
• uzupelnij – 2pkt
• rozdziel – 6pkt
• zapotrzebowanie – 2pkt
• kiedy_prezent – 5pkt

Należy trzymać się wytycznych dotyczących struktury modułów w pakiecie. Za rozbieżności w stosunku do treści zadania, mogą być odjęte punkty. Zadania w postaci pakietu (sam kod źródłowy rozmieszczony w odpowiednich katalogach) spakowanego w formacie zip lub tgz należy przesłać do wykładowcy (bartek@mimuw.edu.pl) oraz prowadzącego odpowiednią grupę ćwiczeniową (pawel.bednarz@mimuw.edu.pl lub mist@mimuw.edu.pl lub pwl@mimuw.edu.pl). Termin przesyłania zadania: 27.01.2014, godzina 12:00. W tytule e-maila należy umieścić dopisek [WDI-2]. Ocenianie, jak poprzednio osobiście z prowadzącymi ćwiczenia. Zadania należy rozwiązywać samodzielnie. Powodzenia!

PS. Zbiór dodatkowych testów dostępny tutaj. Instrukcja obsługi: rozpakowujemy dane testowe do jakiegoś katalogu. Następnie w tym katalogu umieszczamy swój pakiet mikolaj_2_0 i robimy: python test.py. Jeśli wszystkie funkcje działają jak należy, program nie powinien zwrócić żadnego wyjścia.

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.

Wyrażenia regularne:
Howto

Nieznacznie zmienione w stosunku do wersji zeszłorocznych Wykłady szósty (o zmiennych) i siódmy o modułach.

Dodatkowo moduł wdi (do wykładu 7.)

Skrypt  simple z użyciem sys.argv

i Skrypt z użyciem modułu Argparse

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.