Płaszczaki - Dokumentacja Projektu

Opis problemu

Zapanował popłoch. Uznano, że jacyś intruzi spoza Krainy musieli zamienić w słowie „boli” literę b na p. Aby chronić piękną opowieść-melodię zapisaną na Stronie, postanowiono zbudować płot naokoło Krainy, wykorzystując punkty orientacyjne. Płot zbuduje się z odcinków długości 1 (można je ciąć). Odcinki będą nosić tragarze. Wśród płaszczaków żyją dwa rodzaje tragarzy: ci z rękoma z tyłu i ci z rękoma z przodu. W świecie dwuwymiarowym niemożliwe jest przełożenie rąk (z przodu do tyłu oraz 1 odwrotnie). Do przeniesienia odcinka potrzebny jest tragarz z rękoma z tyłu oraz drugi z rękoma z przodu. Nie wszyscy tragarze się lubią i nie zawsze chcą ze sobą współpracować. Trzeba delikatnie dobierać tragarzy w pary. Rysunek 2: Po lewej zaprzyjaźnieni tragarze poprawnie niosący odcinek, po prawej zwaśnieni tragarze, którzy nie chcą współpracować Rysunek 3: Zaprzyjaźnieni tragarze, którzy nie mogą nieść odcinka, gdyż mają ręce z tej samej strony Odcinki są produkowane w fabryce i następnie siecią wąskich dróg przenoszone do punktów odbioru. Problem. Ustalić, w jaki sposób są transportowane odcinki z fabryki do miejsca budowy płotu. Możliwie szybko i możliwie małym kosztem zbudować płot.

Nasza interpretacja

Ten problem można podzielić na dwa podproblemy. Pierwszy problem to, mając dany zestaw pracowników oraz określone warunki i relacje, celem jest obliczenie maksymalnej liczby możliwych par. Drugi problem to generowanie granicy wokół zbioru punktów i konstruowanie sieci przepływu między nimi, na podstawie określonych kryteriów krawędzi. Obliczenie potrzebne, to ilość dni potrzebnych do zbudowania muru wokół granicy, jeśli pary pracowników mogłyby składać elementy muru wokół każdego punktu granicznego.

Instrukcje uruchomienia

Ten program działa w 3 trybach.

Pierwszy tryb pozwala użytkownikowi wybrać pliki .txt z konsoli i wyświetla odpowiedź w konsoli:

.\build1.bat

Drugi tryb jest rozszerzeniem pierwszego, dodatkowo wyświetla informacje debugowania w konsoli:

.\build1.bat debug

Trzeci tryb to tryb testowy, pozwalający przeprowadzić serię testów bez potrzeby ręcznego wprowadzania każdej nazwy pliku .txt:

.\build1.bat test

Każdy tryb ma interfejs GUI, do pokazywania skonstruowanego grafu, zbudowany w SFML.

Pliki

Rozwiązanie tego problemu składa się z:

problem1.cpp WorkerRelations.cppWorkerRelations.hBorderHandler.cpp BorderHandler.h GraphHandler.cppGraphHandler.h

Dane wejściowe

W każdym przypadku testowym potrzebne są 2 pliki .txt. Pierwszy plik zawiera szczegóły dotyczące pracowników i ich relacji (p[x]_w[x].txt). Drugi plik zawiera wszystkie punkty i ich współrzędne, a także krawędzie określone z określoną wartością przepływu (p[x]_c[x].txt).

Dane wyjściowe

Po każdym obliczeniu granicy, liczba punktów granicznych oraz losowo wygenerowane wartości jasności od 1 do 100 dla każdego z nich są przechowywane w pliku p3_path[x].txt do wykorzystania w problemie 3.

Testy

Seria przeprowadzonych testów jest widoczna w folderze /txt. Większość została wygenerowana za pomocą skryptu GenerateTests.py, z dodatkowymi testami stworzonymi ręcznie w celu przetestowania przypadków brzegowych. Przykłady obejmują: Brak par pracowników, Mniej niż 4 punkty testowe, test fabryki będącej częścią granicy, testy wrażliwe na wartości zmiennoprzecinkowe (dla możliwych błędów zmiennoprzecinkowych), dziwne testy graniczne.

Złożoność i dowód

Używane algorytmy to:

- Algorytm Jarvisa (obliczenie granicy, z pomocą Natana); Złożoność O(N*H), gdzie N to całkowita liczba punktów, a H to całkowita liczba punktów leżących w otoczce wypukłej (granicy),

- Dostosowany algorytm Edmondsa-Karpa (dla sieci przepływu i ścieżki powiększającej); Dostosowany, ponieważ dodaję wirtualny węzeł zlewni, aby obsłużyć wiele zlewni w algorytmie. Złożoność bazowa O(V*E^2), gdzie E to liczba krawędzi, a V to liczba wierzchołków,

- Algorytm Hopcrofta-Karpa (Znajdowanie maksymalnego skojarzenia w strukturze danych par); Złożoność O(E*sqrt(V)), gdzie E to liczba krawędzi w grafie dwudzielnym, a V to liczba wierzchołków,

- Dostosowany algorytm filtrowania par; Złożoność O(n), gdzie n to rozmiar wektora upodobań przekazywanego do funkcji. Ta analiza zakłada średnią wydajność operacji na mapie skrótów, które zazwyczaj mają złożoność O(1) dla wyszukiwania i wstawiania. Ten algorytm gwarantuje zakończenie, ponieważ skończony zestaw par jest dzielony na 2 nieposortowane mapy w zależności od kierunku rąk, a następnie łączony w pary na podstawie relacji i tego, czy są one znalezione w przeciwległych mapach. Jeśli zakładamy, że nie ma warunku zatrzymania, lista pracowników musiałaby być nieskończona, ponieważ to jedyna możliwość. Jeśli nie można dopasować pracowników, zwracany jest pusty zestaw pracowników.

Opis problemu

Problem. Zapisać opowieść-melodię w maszynie Informatyka, zamieniając wcześniej „poli” na „boli” oraz próbując oszczędzić wykorzystane miejsce. Znaleźć rozwiązanie problemu ewentualnej zamiany innych fragmentów opowieści-melodii, który niepokoi Heretyka oraz Informatyka.

Nasza interpretacja

Musimy wyszkiwać wzorzec, podmienić go, a następnie całą pieść poddać kompresji. W tym celu wykorzystamy algorytm Knutha-Morissa-Pratta oraz algorytm Huffmana.

Pliki

plik główny: problem2.cpp

plik pomocniczy z funkcjami niezwiązanymi z algorytmem KMP/Huffmana: filtering.h

wyszukiwanie wzorca: KMP.h

kompresja: huffman.h

Dane wejściowe

wejście: nasza pieśń która będzie plikiem tekstowym (z przerobionymi wyrazami), oraz plik z parami wyrazów pierwszy niepoprawny (ten w piosence) a drugi poprawny (heretyk przy użyciu swoich kontaktów z siłami nadprzyrodzonymi wie które są przerobione), wyrazy są ustawione w następujący sposób

poprawny zły

poprawny zły

itd

Dane wyjściowe

wyjście: plik z pieśnią do której mają dostęp informatyk oraz heretyk, która została poddana obróbce zgodnie z tym co należy przerobić według heretyka oraz zakodowana i skompresowana zgodnie z algorytmem Huffmana

Testy

Łatwo idzie zauważyć, że program ten działa. Wystarczy wpisać dowolny tekst z podmienionymi paroma wyrazami, oraz uzupełnić plik tekstowy na słowa i otrzymamy naszą pieśń skompresowaną zgodnie z algorytmem Huffmana. Zastępowanie liter/wyrazów funkcjonuje bez najmniejszych problemów pragnę więc skupić się na specyficznych przypadkach:

1. wejście puste:

W przypadku gdy jedno z wejść jest puste program nas poinformuje o zakończeniu działania.

2. nasz wyraz będzie dłuższy od tekstu/równy lub wzorzec == wyraz do podmiany

W takim przypadku funkcja errorChecking w KMP.h zajmie się sprawdzeniem tych przypadków i odpowiednią reakcją na nie

3. wejście to pojedynczy znak

Program ten jest przystosowany do takiej ewentualności jednakże będzie również przyjmował znak nowej linii.

Złożoność i dowód

Przed próbą dowiedzenia poprawności pragnę zauważyć, że istnieje szansa na powstanie konfliktu w kolejności podmiany np:

rower podmieniamy na kajak

kaj podmieniamy na maj

wynikiem końcowym powinien być wyraz majak jednakże rozważmy następującą sytuację:

kaj -> maj

rower -> kajak

Łatwo idzie zauważyć, że bez odpowiedniej reakcji wynikiem końcowym będzie wyraz kajak, albowiem nie znajdziemy na początku dopasowania dla kaj. W związku z czym musimy nasz zbiór wyrazów posortować względem liczby znaków, a dokładniej rzecz ujmując malejąco.

Pomimo posortowania malejąco dalej możemy natrafić na konflikt, weźmy pod uwagę następującą sytuację:

a -> b

c -> d

b -> c

Posortowane pod względem rozmiaru ewidentnie to jest, jednakże nadal występuje konflikt, albowiem dla wejścia:

aaa

otrzymamy:

ccc

Powodem tego jest to, iż nie posortowaliśmy naszego wejścia (wyrazów do podmiany) leksykograficznie, po takim działaniu będziemy mieli następującą kolejność:

a -> b

b -> c

c -> d

Czyli dla naszego wejścia aaa wyjściem będzie ddd.

Możemy starać się z całego serca zredukować konflikt jednakże to jeszcze nie jest koniec, bo co w sytuacji gdy:

a -> z

c -> a

z -> b

Długość wyrazów ta sama? Jest. Wyraz do podmiany posortowany leksykograficznie? Również jest. To dlaczego dalej mamy konflikt?

W celu otrzymania pełnej poprawność musimy jeszcze wyrazy zastępujące również posortować leksykograficznie.

Przykład we/wy może być analogiczny do poprzedniego więc pozostawię go wyobraźni.

Reszta kodu to jest algorytm Knutha Morrisa Pratta oraz algorytm Huffamana które zostały już dawno dowiedzione przez ludzi z znacznie większą wiedza ode mnie więc zaufam im na słowo.

Ogólna złożoność czasowa:

Złożoność KMP: O(k⋅(n+m), gdzie k to liczba wywołań pattern, n to długość tekstu, a m to długość wzorca.

Złożoność Huffmana: O(n logn) dla tworzenia drzewa, O(n) dla kompresji i dekompresji.

Ogólna uproszczona złożoność: O(k * (n + m) + n * log n)

Złożoność przestrzenna:

Odczyt plików: O(n), gdzie n to liczba znaków w pliku.

Algorytm KMP: O(n) dla przechowywania wzorców i tekstu.

Algorytm Huffmana: O(n) dla przechowywania drzewa i skompresowanego tekstu.

Nasza interpretacja

Problem trzeci w mojej interpretacji wyglądał następująco: Wybudowanego w pierwszym zadaniu płotu należy pilnować. Takie zadanie mają płaszczaki, które pełnią funkcję strażnika. Każdy z nich ma losowo dobraną energię (od 1-10). Na jej podstawie wybierany jest grafik - im strażnik ma większą energię, tym pierwszy jest w kolejce do grafiku. Należy też przestrzegać paru ważnych zasad: ⦁ strażnicy mogą mieć urlopy, ⦁ po pilnowaniu muszą odbyć 7 dni odpoczynku, aby móc ponownie patrolować płot. Każdy punkt płotu ma swoją jasność w skali 1-100 (współrzędne w mojej interpretacji nie mają znaczenia). W inpucie dostajemy dodatkową ilośc kroków strażników, po których muszą sie zatrzymać i rozejrzeć. Jeśli ta ilość równa się trzy, płaszczak może się zatrzymać po jednym, dwóch i trzech krokach, najważniejsze jest, aby punkt na którym się zatrzyma, był ciemniejszy od poprzedniego. Dla punktów 3 18 2 najkorzystniejsze jest przejście z punktu z jasnością 3 do punktu z jasnością 2, ponieważ 2 ma mniejszą jasność niż 18. Jest to ważne w kontekście zadania, ponieważ gdy w sytuacji gdy mamy punkty 30 31 32 zatrzymując się i na punkcie z jasnością 31, i na punkcie z jasnością 32 trafiamy na punkty jaśniejsze, przez którą strażnicy muszą przesłuchać melodię, a słuchanie jej często bardzo nudzi płaszczaków. W takiej sytuacji lepiej przejść do punktu 32, wtedy ilość przesłuchań melodii jest mniejsza. W programie dążę do ustalenia grafiku strażnikow z uwzględnieniem ich losowo wygenerowanej energii, urlopów oraz 7 dni odpoczynku oraz do ustalenia ścieżki, gdzie liczba przesłuchań melodii jest najmniejsza.

Pliki

Pliki nagłówkowe: route.h, guards.h Pliki główne: problem3.cpp (main), guards.cpp, route.cpp ANALIZY PLIKÓW problem3.cpp To jest funkcja główna. Łączy ona wszystkie 5 plików ze sobą. W środku znajduje się automatyczne wczytywanie testów, wczytywanie informacji z dwóch plików, losowanie energii strażnikow, inicjalizacja map analizujących urlopy i energie, sprawdzanie najkorzystniejszej ilości przesłuchań melodii oraz wypisanie wyniku na terminal. guards.cpp Połączona jest z plikiem nagłówkowym guards.h Ten plik ma za zadanie stworzenie grafiku strażników na podstawie energii, dni urlopowych i wymaganych 7 dni odpoczynku. Jest to analizowane na podstawie map nieposortowanych oraz kolejki priorytetowej route.cpp W tym pliku wybieramy najkorzystniejszą ścieżkę, aby ilość przesłuchań melodii była jak najmniejsza. W tej funkcji wraz z Natanem i Mikołajem uwzględniliśmy zatrzymywanie się na każdym punkcie i analizowaniu, czy jest jaśniejszy/ciemniejszy od poprzedniego. Jeśli żaden z punktów nie był ciemniejszy, zatrzymuje się na kroku o wartości max_steps (maksymalna ilość kroków) nalicza nam jedno wysłuchanie melodii i jeden krok. W programie uwzględniłam wypisanie ilości zatrzymań, które zrobił strażnik, aby łatwiej było przeanalizować poprawność kroków strażnika. Program uwzględnia ruch do punktu ostatniego i analizowanie przesłuchań i jasności - wtedy strażnik wybiera się na odpoczynek.

Dane wejściowe

Input w moim rozwiązaniu polega na dwóch plikach: ⦁ problem3.vacationx (x - numer testu) - odpowiadający za ilość analizowanych dni, kroków oraz dni wolnych strażników ⦁ problem3.pathx - odpowiadający za ilość punktów i poziomu jasności punktów

Dane wyjściowe

W outpucie mamy numer testu, poszczególne energie każdego strażnika, a następnie grafik oraz liczba przesłuchań melodii

Testy

Testy przeprowadzałam na wielu przypadkach w tym mowa o tych skrajnych: np: ⦁ wszyscy strażnicy mają urlop 1-ego dnia ⦁ jeden strażnik ma urlop każdego dnia ⦁ każde kolejne punkty są od siebie większe ⦁ uwzględnione 14 dni zamiast 7

Złożoność i dowód

Route.cpp: Złożoność czasowa: O(n3)

Złożoność pamięciowa: O(n)

Guards.cpp: Złożoność czasowa: O(g log g)

Złożoność pamięciowa: O(g)

problem3.cpp: Złożoność czasowa: O(days * (g log g + n * brightness.size()))

Złożoność pamięciowa: O(g + n)