Projekt z przedmiotu Algorytmy dla Problemów Trudnych Obliczeniowo

Zadanie: Krysztaly

Tresc zadania znajduje sie w pliku:

Sprawy organizacyjne

Prowadzący przedmiot:

  • dr hab. inż. Piotr Faliszewski
  • dr inż. Marcin Kurdziel
  • dr inż. Marek Gajecki

Terminy oddania projektu:

  • Pierwszy termin: 16 czerwca 2017r, godz 23.59.
  • Drugi termin: 10 wrzesnia 2017, godz 23.58.
  • Trzeci termin: 17 września 2017, godz 23.59.
Zaliczenie projektu w terminie późniejszym niż pierwszy skutkuje ocena końcową z przedmiotu nie wyższą niż 3.0.

Do wykonania w ramach projektu:

  • Należy napisać program, który rozwiązuje zadanie opisane poniżej oraz wysłać go do systemu arbitrażowego dla zadania.
  • Należy także dostarczyć dokumentacje programu. Dokumentacja nie może przekraczać 8 stron tekstu czcionką 11pt, przy rozsądnych marginesach. Dokumentacja powinna zawierać wyłącznie informacje na temat użytych algorytmów i pomysłów rozwiązania zadania, a nie szczegółów technicznych implementacji. Dokumentacja istotnie krótsza wcale nie musi być wadą projektu.

Języki programowania: Jedyne dwa dopuszczalne języki programowania to C oraz C++/C++11 (obecnie zainstalowany kompilator to gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3).

Zasoby/współbieżność: Programy nie mogą odwoływać się do systemu plików, nie mogą próbować nawiązywać połączeń sieciowych, być wielowątkowe, wieloprocesorowe, itp. Programy powinny jedynie wczytać ze standardowego wejscia opis zadania, wykonać obliczenia w pamięci i wypisać wynik na standardowe wyjście. Złamanie tych zasad, w szczególności odwołania do sieci oraz próby hackowania systemu arbitrażowego, mogą skutkować brakiem zaliczenia przedmiotu. (Istnieje takze mozliwosc, ze taka osoba bedzie musiala wysluchac bezposrednio od prowadzacych jak bardzo nas rozczarowala.)

Oceny:

  • Na Państwa ocenę największy wpływ ma jakość działania zgłoszonego programu, a w drugim rzędzie jakość dokumentacji. Wyróżniająca się dokumentacja podnosi ocenę z projektu o 0.5 stopnia. Wyjątkowa zła dokumentacja (w tym nieistniejąca) obniża ocenę o 0.5 stopnia (w przypadku zaliczenia w terminie innym niż pierwszy dokumentacja, lub jej brak, nie wpływa na ocenę).
  • Programy będą oceniane na podstawie liczby plansz, które będą w stanie rozwiązać. Dla każdej planszy będzie zadane ograniczenie czasowe (od kilku do kilkunastu sekund) oraz dostępna ilość pamięci (dokładne dane zostaną udostępnione później).
  • Aby uzyskać zaliczenie, Państwa program musi być w stanie rozwiązywać zestaw podstawowych testów, który udostępnimy Państwu przez system arbitrażowy.
  • Aby uzyskać wyższą ocenę, program musi być w stanie rozwiązywać odpowiednio trudniejsze testy. Oceny powstaną na podstawie porównania jakości programów.
  • Kod źródłowy państwa programów nie jest oceniany, ale może być przeglądany, więc proszę stosować komentarze i wcięcia.
  • W przypadku wykrycia plagiatu, obie zaangażowane osoby otrzymują ocenę 2.0 z wszystkich trzech terminów.

Wymagania na ocenę 3.5

Plansze na oceny 3.5 będą ograniczone do rozmiarów 6x6 (tj., dopuszczalne są, na przykład, plansze o rozmiarach 3x3, 6x6, 1x1, ale---na 3.5---nie będzie plansz o rozmiarach 7x7, 128x128 itp.).

Dodatkowe informacje, programy i dane

Dodatkowe programy i informacje zostana udostepnione pozniej. Program sedziego (judge.py) został zaimplementowany w języku Python, dla interpreterów z rodziny 2.7. Oprocz sedziego dostepny jest tez program do wizualizacji labiryntow (view.py), ktory dla danego pliku wejsciowego generuje plik PNG z zaznaczona trasa promienia.

Wywołanie sędziego: 

  python judge.py input output
gdzie input to opis planszy z zadaniem, a output to opis planszy z rozwiązaniem.

Wywoalnie przegladarki plansz: 

  python view.py output
  eog output.png
gdzie output to plik z rozwiazaniem (albo i nie).

System arbitrażowy

System arbitrażowy dostępny jest pod następującymi adresami: