====== Biblioteka algorithm ======
Zapoznać się z metodami z bilblioteki [[http://en.cppreference.com/w/cpp/algorithm]]. Dla każdej z metod jest w dokumentacji podany przykład użycia kodu.
W przypadku modyfikowania niezainicjalizowanego kontenera może się przydać [[http://en.cppreference.com/w/cpp/iterator/back_inserter]]
====== Ćwiczenia do wykonania ======
- [7 plusów] Przy pomocy algorytmów znajdujących się w bibliotece algorithm należy zaimplementować następujące metody (kolejność przypadkowa):
std::set Keys(const std::map &m);
std::vector Values(const std::map &m);
std::map DivisableBy(const std::map &m,int divisor);
void SortInPlace(std::vector *v);
std::vector Sort(const std::vector &v);
void SortByFirstInPlace(std::vector> *v);
void SortBySecondInPlace(std::vector> *v);
void SortByThirdInPlace(std::vector> *v);
std::vector MapToString(const std::vector &v);
std::string Join(const std::string &joiner, const std::vector &v);
int Sum(const std::vector &v);
int Product(const std::vector &v);
bool Contains(const std::vector &v, int element);
bool ContainsKey(const std::map &v, const std::string &key);
bool ContainsValue(const std::map &v, int value);
std::vector RemoveDuplicates(const std::vector &v);
void RemoveDuplicatesInPlace(std::vector *v);
void InitializeWith(int initial_value, std::vector *v);
std::vector InitializedVectorOfLength(int length, int initial_value);
void CopyInto(const std::vector &v, int n_elements, std::vector *out);
int HowManyShortStrings(const std::vector &v, int inclusive_short_length);
- **[5 punktów]** Zadanie polega na dodaniu do aplikacji Academia możliwości układania harmonogramu zajęć uwzględniającego różne ograniczenia. W podstawowej wersji należy jedynie uwzględnić brak bilokacji (i multilokacji) studentów z danego roku i nauczycieli akademickich. Zajęcia również w danym oknie czasowym i w danej sali mogą się odbywać tylko jedne zajęcia. Każdy nauczyciel musi poprowadzić określoną listę przedmiotów. Ogólnie ułożenie optymalnego planu zadań jest zadaniem [[https://en.wikipedia.org/wiki/List_of_NP-complete_problems|bardzo trudnym]], dlatego prawdopodobnie algorytm będzie rozwijany miesiącami. Jednak zanim specjalny zespół od problemów optymalizacyjnych dostarczy wreszcie gotowe rozwiązanie chcielibyśmy mieć namiastkę działającego oprogramowania! Na szczęście jest to możliwe należy zdefiniować kontrakt w postaci interfejsu **Scheduler** specjalny zespół dostarczy nam za kilka miesięcy algorytm **SophisticatedHighlyOptimizedScheduler**, a my możemy już napisać bardzo uproszczony algorytm zachłanny, który będzie dostarczał często nieoptymalne wyniki, ale na razie wystarczy. Należy więc przygotować klasy:
- **SchedulingItem** pojedynczy element harmonogramu, obiekt wartości, zawiera pola:
- course_id - identyfikator kursu
- teacher_id - identyfikator nauczyciela akademickiego prowadzącego te zajęcia o tej godzinie
- room_id - identyfikator pomieszczenia w którym odbywają się zajęcia
- time_slot - okno czasowe, w którym odbywają się zajęcia, dla uproszczenia cały tydzień jest podzielony na N okien czasowych nie zachodzących na siebie (np. dla 20: 1 => pon 8:00-10:00, 2 => pon 10:00-12:00, ... 20 => pią 14:00-16:00). Zajęcia wymagają zawsze pojedynczego okna czasowego i zawsze są z nim wyrównane tzn. nie mogą zajmować połowę 12ego i połowę 13ego
- year - rok studiów na którym obowiązuje przedmiot
- **Schedule** cały harmonogram, udostępnia następujące metody:
- Schedule OfTeacher(int teacher_id) const - wylicza fragment harmonogramu związany z danym nauczycielem akademickim (może się przydać copy_if...)
- Schedule OfRoom(int room_id) const - j.w. tylko związany z danym pomieszczeniem
- Schedule OfYear(int year) const - j.w. dla danego roku studiów
- std::vector AvailableTimeSlots(int n_time_slots) const - wylicza wektor jeszcze nie zajętych okien czasowych, gdzie n_time_slots jest maksymalną wartością okna czasowego
- void InsertScheduleItem(const SchedulingItem &item) - wstawia nowy element planu
- size_t Size() const - zwaraca rozmiar planu
- **Scheduler** najważniejszy element układacz planu, interfejs czysto abstrakcyjny stanowiący kontrakt między nami a zespołem pracującym nad zoptymalizowaną wersją algorytmu.
- Schedule PrepareNewSchedule(const std::vector &rooms, const std::map> &teacher_courses_assignment, const std::map> &courses_of_year, int n_time_slots)
- rooms - dostępne pomieszczenia
- teacher_courses_assignment - rozpiska nauczycieli (klucz w mapie) i prowadząnych przez nich przedmiotów (wartosć w mapie)
- courses_of_year - kursy (wartość w mapie) wymagane dla danego rocznika (klucz w mapie)
- n_time_slots - ilość slotów czasowych
- **NoViableSolutionFound** wyjątek wyrzucany, gdy nie udaje się stworzyć planu
- **GreedyScheduler** wersja [[https://pl.wikipedia.org/wiki/Algorytm_zach%C5%82anny|zachłanna]] implentacji algorytmu układacza planu zwykła pętla która próbuje przypisywać po kolei przedmioty do sal i nauczycieli