Category: WDI

Zadanie bonusowe – crossout.py (5pkt)

Zadanie polega na napisaniu programu w pythonie, który pomaga w wykreślaniu zadanych słów lub wyrażeń w plikach tekstowych.

Np. wywołanie:

crossout.py -w cholewcia –cross “X” -c 3 –in moj_esej.txt

powinno wczytać zawartość pliku moj_esej.txt, następnie podmienić w niej wszystkie wystąpienia słowa “cholewcia” znakiem “X” powtórzonym trzy razy i wypisać wynik na wyjście standardowe.

Program powinien obsługiwać następujące opcje:

  • -w lub –word, słowo do zastąpienia, powinno posiadać wartość domyślną (Państwa ulubione słowo do wykreślenia)
  • -x lub –cross: znak służący do wykreślania, domyślnie “x”
  • -c lub –count: liczba znaków w wykreśleniu. Jeśli podamy liczbę całkowitą, zawsze wstawiamy tyle znaków (niezależnie od długości słowa), jeśli nie podamy tego parametru, to zamieniamy słowa na tyle “krzyżyków” ile znaków miało słowo
  • -l lub –list, ten parametr zastępuje -w, i określa nazwę pliku, w którym znajduje się lista słów (każde w oddzielnej linijce), które powinniśmy zastępować. Wynik działania dla listy jest taki sam jak dla kolejnego wywołania skryptu crossout.py dla każdego ze słów z osobna.
  • -o lub –out,  nazwa pliku wyjściowego (domyślnie standardowe wyjście)
  • -i lub –in, nazwa pliku wejściowego (domyślnie standardowe wejście)

Warto użyć modułu Argparse, przypominam, że na wykładzie omawialiśmy też przykładowy skrypt z użyciem ArgParse.

Jeśli ktoś chciałby w ten sposób zdobyć dodatkowe punkty, to proszę o wysyłanie rozwiązań a-mailem do mnie ( bartek@mimuw.edu.pl, z załącznikiem w postaci  pliku crossout.py i kluczem [WDI-BONUS] w temacie do najbliższego wtorku, 18.12.2014). Osoby wysyłające rozwiązanie powinny też przyjść w środę 19. lutego o 12.00 do mnie (p. 5770) i opowiedzieć o swoim rozwiązaniu.

Pytania proszę w komentarzach poniżej.

Zadania – skrypty w bashu

  1. Napisz skrypt, który będzie zmieniał rozszerzenie plików w danym katalogu. Skrypt przyjmuje trzy parametry: rozsz1 rozsz2 katalog i będzie zmieniał rozszerzenie plikom, które dotąd miały rozszerzenie rozsz1 na rozsz2 w katalogu katalog.
  2. Korzystając z funkcji read napisz skrypt, który zsumuje wartość drugiej i trzeciej kolumny w pliku podanym jako argument. Przykładowy plik znajduje się tutaj.
  3. Napisz skrypt korzystający z funkcji ls, który wyświetli łączny rozmiar plików w katalogu, w którym został wywołany.
  4. Napisz skrypt, który spakuje (uzywając polecenia tar) wszystkie pliki o rozmiarze większym niż 1MB w katalogu, w którym został wywołany. Można testować używając np. pliku z pierwszego zadania zaliczeniowego.
  5. Napisz skrypt sumujący wszystkie swoje parametry o nieparzystych numerach.
  6. Napisz skrypt, który wypisze swoje parametry w odwrotnej kolejności.

Zadania powtórkowe

  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(25) 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.

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
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi4u.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.

Zadanie zaliczeniowe 2

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.

Lab 9 – wyrażenia regularne

  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.

Lab 8 – tworzenie modułów

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.