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.
Szkoda, że miało być przed świętami a jest po.
A pytanie: czy mamy brać pod uwagę to, że będą używane polskie znaki typu ąę?
“następującą po nich ilości” << ilość występuje przed nazwą prezentu
Można założyć, że Mikołaj nie używa polskich znaków.
BW
Pierwsza napotykana kropka jest w adresie jest po ul. więc chyba mamy zrobić do ostatniej kropki w linii? Czy może uwzględnić to, że w adresie może być ul. lub al lub pl.?
ostatnia kropka w linii brzmi sensowniej niż rozpatrywanie specjalnych przypadków.
1) W odniesieniu do powyższego pytania o kropki – czy nie lepiej by było wobec tego w listach posiadać na końcu linii z adresem tylko znak końca wiersza? Dzieci zapewne nie piszą kropek na końcu swoich adresów, a faktycznie niepotrzebnie komplikuje się walidacja danych – w szczególności, jeśli założyć, że patrzymy nie do pierwszej, tylko do drugiej kropki w wierszu, to:
a) ktoś może podać swój adres w postaci “ulica Kubusia Puchatka 1/2.” i kropka już nie jest druga, tylko pierwsza.
b) ktoś może podać swój adres w postaci “ul. Gen. J.A. Nowaka.” i wtedy kropka nie jest już ani druga, ani pierwsza, tylko (przez indukcję) o dość losowym numerze.
2) “Jako wynik funkcja prezenty zwraca słownik, którego indeksami są nazwy prezentów, a kluczami jest łączna liczba sztuk prezentu wymieniona w liście.” – zapewne miało być “kluczami” i “wartościami”?
3) “Pierwsza z nich – uzupelnij(plik) wczytuje słownik” miało zapewne oznaczać “wczytuje dane z pliku i zwraca słownik”? Nazwa funkcji jest ciut zdradliwa, bo sugeruje, że jakiś słownik być może już jest i należałoby go “uzupełniać” tym, co jest w pliku (ale *chyba* nie o to chodziło?).
4) Szczegół, ale “jest mniejszy leksykograficznie” jest zapewne skrótem myślowym od “jest wcześniej w porządku leksykograficznym”?
5) “W szczególności w którymś momencie odwiedzi dziecko o podanym em>adresie.”: zgubiło się “<" przy "em".
6) Prośba ogólna: zamieszczone powyżej testy są super, poza drobnym szczegółem, że wordpress automatycznie zamienia cudzysłowy proste na drukarskie i skopiowanie testu żywcem skutkuje błędami (opis jak to wyłączyć tutaj: http://www.ironpaper.com/webintel/articles/fix-wordpress-quotes-by-displaying-straight-quotation-marks/). Dosłownie *mała* rzecz, a by ucieszyła
7) Biorąc pod uwagę Pańską odpowiedź "Można założyć, że Mikołaj nie używa polskich znaków" czy można poprosić o dostosowanie odpowiednich plików z listami i przykładów wywołań funkcji aby było wiadomo czy rzeczywiście we wszystkich miejscach pozbywamy się polskich znaków, czy na przykład w adresie albo w prezencie "rózga" (albo w nieistotnej części treści listu jak "Do zobaczenia w Święta") polskie znaki mają pozostać?
ad 1) To elfy wpisują adresy do pliku, więc już zostańmy przy ostatniej kropce.
ad 2) indeksy -> klucze, klucze -> wartości
ad 3) wszystko się zgadza, ale myślę, że troche dzielimy tu włos na czworo. Jak widać Pana/Pani Anonima nie zwiodło to zdradliwe sformułowanie
ad 4) zgadza się, to często stosowany skrót myślowy wśród informatyków
ad 5) dziękujemy, spróbujemy, może i my się czegoś nauczymy
ad 6) poprawimy
W komentarzach również się cudzysłowy zamieniają z prostych na drukarskie. Żeby to zmienić jeszcze należałoby dopisać: remove_filter(‘comment_text’, ‘wptexturize’);
Mam takie pytanie co do tej kolejności leksykograficznej adresów: czy mamy brać pod uwagę dopiero nazwę ulicy, czy mamy założyć, że dzieci mieszkające przy alejach będą zawsze dostawać prezenty wcześniej niż dzieci przy ulicach? A czy jeśli tak jest to czy w takiem razie prezent jako pierwszy dostanie dziecko które napisało w liście “ul.” a nie “ulica”? Czy to mieć w ogóle znaczenie?
ps. Zadanie jest napisane tak pięknie, że aż przyjemnie się za nie zabrać!
Ogólnie, myślę, że dużo Państwo przywiązują wagi do tych początków adresów. Najkrócej mówiąc, nie o to nam chodzi w zadaniu, żeby rozstrzygać problem skrótów ‘ul.’ i ‘al.’…
Jeśli Państwu jest tak wygodnie, to można założyć skrócone wersje nazw ulic (bez ul. al. i pl. ) i założyć, że Paczki od Mikołaja i tak jakoś dotrą.
Będą jakieś dane testowe?
Do każdej funkcji są już jakieś dane testowe. Dodatkowy pakiet danych, na których będzie można potestować działanie programu pojawi się, ale dopiero w okolicach 10. stycznia.
Rozumiem, że w funckji zapotrzebowanie, mamy postąpić tak jak w poprzedniej i dopiero dokupić prezenty jak już nie będzie można przydzielić więcej, a nie każdemu dziecku przydzielić to czego chce najwięcj a potem uzupełniać?
Każdemu dziecku przydzielić to, czego chce najwięcej, a potem uzupełniać. Uwzględniając przy tym, że jedno dziecko może sobie zażyczyć w liście więcej niż jeden prezent.
1) Czy funkcja ‘zapotrzebowanie(…)’ ma wypisywać, że potrzeba 0 danego prezentu, jeśli nie potrzeba więcej, czy po prostu nie uwzględniać takiego klucza?
2) W ostatnim akapicie przykładów jest ‘rozdziel’ w miejscu, gdzie powinno być ‘zapotrzebowanie’.
3) Czy złożoność obliczeniowa podlega ocenie?
Ad 2)
Racja – poprawione – dziękuję.
Ad 3)
Nie.
@Jędrzej
1)”Jeśli danego prezentu jest w magazynie odpowiednia ilość, nie należy zawierać jego nazwy w wynikowym słowniku.”
A w ostatnim module w ostatniej funkcji co to są za obieky?
(“wrotki”:3)
bo to ani lista, ani słownik (nie ma to takiej formy jak dane z funkcji rozdziel)
Racja – w niektórych miejscach były dwukropki zamiast przecinków – chodzi o krotki.
I po co nam są potrzebne ilości prezentów w funkcji kiedy_prezent
wysztarczyło by jako prezenty dać słownik w formacie
{“adres”:”prezent”,…}
I byłoby trochę łatwiej.
Żeby było możliwe użycie wyjścia funkcji rozdziel bezpośrednio jako wejścia funkcji kiedy_prezent.
Rozumiem, że zamysłem funkcji zapotrzebowanie było to, by użyć do niej funkcji rozdziel tzn. zwrócić różnicę pomiędzy ilością wybranego za pomocą funkcji rozdziel prezentu (albo sumą ilości, jeśli prezent jest wybrany dla kilku dzieci) a ilością prezentu w magazynie (jeśli ta różnica jest większa od zera).
Dlaczego w takim razie w podanym przykładzie wyników dla funkcji zapotrzebowanie dla wrotek jest 4, skoro zgodnie z działaniem funkcji rozdziel wrotki dostaje tylko dziecko z adresem “ul. Gdyńska 5/2, Gdańsk”, łącznie 3, a w magazynie jest ich 4?
Ponieważ funkcja rozdziel nie ma tutaj niczego do rzeczy. Chodzi o ogólne wysondowanie zapotrzebowania i zupełnie nie interesuje nas tutaj to, jakie prezenty akurat w tym roku były przyznane.
Na dole treści zadania pojawiły się dodatkowe dane testowe wraz z instrukcja obsługi.
Czy rózgi są składowane w magazynie, czy są brane prosto z lasu? 😉
Dobry wieczór, czy gdzieś w dodatkowych testach nie kryje się błąd?
Kiedy puszczam test.py dostaję:
“Traceback (most recent call last):
File “test.py”, line 40, in
assert dicts_equal(stany_magazynowe[i], magazyn.uzupelnij(magazyny_pliki[i]))
AssertionError”
natomiast kiedy wykonuję “ręcznie” funkcję uzupelnij na plikach magazyn(0-4).txt z folderu “pliki_testowe” otrzymuję takie same wyniki jak oczekiwane w stanach magazynowych w pliku test.py.
Pozdrawiam serdecznie
Nie wydaje mi się. Oczywiście mogę się mylić. Proszę wpisać w pliku test.py przed wywołaniem:
assert dicts_equal(stany_magazynowe[i], magazyn.uzupelnij(magazyny_pliki[i]))
linię:
print stany_magazynowe[i], magazyn.uzupelnij(magazyny_pliki[i])
i wysłać do mnie mailem wynik.
Pozdrawiam,
Paweł Bednarz
Czy dobrze rozumiem instrukcję obsługi testu: “robimy: python test.py” – mam po prostu uruchomić ‘test.py’ podwójnie klikając/używając entera, tak? Na chwilę pojawia się okno i prawie od razu znika. Moje wątpliwości budzi to, że kiedy wpisałem do kodu błąd, działało tak samo, tylko szybciej skończyło pracę. Kiedy wkliłem i odpaliłem kod z ‘test.py’ nie ma błędów, ale na końcu jest 30 długich list adresów (6x pierwszy, 6x drugi, 6x pierwszy, 6x trzeci, 6x pierwszy).
A dziecko, które życzy sobie rowery różnych kolorów bez dwóch zdań zasługuje na rózgę
Z testami wszystko jest w porządku. Błąd był u mnie.
Znalazłem błąd (‘print’ w kodzie) i teraz wszystko działa jak należy.
czy wywołująć funkcję (rozdziel(magazyn, zyczenia)) należy podać jako magazyn i życzenia pliki, np. rozdziel(“magazyn.txt”, “zyczenia.txt”) czy mamy jako magazyn podać słownik: {“klocki”: 5, “samochodziki”: 2, “wrotki”: 4} a jako zyczenia : {“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)}? jeśli ta druga wersja, to dlaczego to nie jest w cudzysłowach? i czy tam na końcu nie brakuje nawiasu?
W treści zadania, przykładach (i testach) jest wyraźnie napisane, że ta druga opcja. Notacja słowników w pythonie nie używa cudzysłowów, dopóki w słowniku nie trzymamy napisów – nie ma powodu, dla którego miałyby tam być jakieś dodatkowe cudzysłowy.
W przykładzie, w słowie “samochodziki: 2 brakuje cudzysłowu, i dlatego mi się nie kompilowało i myślałam że może nie można wywołać funkcji od 2 słowników.
Już poprawiłem. Dziękuję za poprawkę.
Zadanie można ostatecznie przesyłać do poniedziałku tj. 27.01?
W sprawie terminu, to wkradło się małe zamieszanie (inna data początkowo w treści, inna w mailu, w którym zadanie ogłoszono). Zmieniłem datę w treści zadania i ostatecznie zostajemy przy przyszłym poniedziałku (27.01, 12:00), przy czym dalej obowiązuje zasada mówiąca, że ocenę dostaje się dopiero po prezentacji zadania u prowadzącego ćwiczenia.
Czy testy do projektu 1 są gdzieś tu na stronie? Nie mogę ich znaleźć, a chyba były na forum pod treścią zadania. Jeśli zostały usunięte to ja je poproszę.
Mógłby mi ktoś napisać ile powinno zwracać competitions dla kilometraz.txt i jakiejs listy?
Czy jeśli się nie zrobiło wszystkich funkcji z projektu drugiego, to będzie można dosłać po terminie za mniejszą ilość punktów?
To jest dyskusja odnośnie zadania drugiego. Komentarze odnośnie zadania pierwszego można zobaczyć po kliknięciu na nagłówek postu z zadaniem pierwszym. Tam też znajdują się wyniki przykładowych wywołań funkcji z tego zadania.
Zasada poprawiania nie zmieniła się: można raz poprawić / przysłać rozwiązania każdego zadania po terminie. Punktacja w tym przypadku jest taka, że dodatkowe punkty zdobyte w stosunku do poprzedniej wersji są dzielone przez 2. W szczególności, jeśli ktoś nie przysłał pierwszej wersji w ogóle, to ma do zdobycia połowę punktów.