DAUT2014/Zadania

Ogólne zasady

  • zadania wykonujemy indywidualnie,
  • rozwiązania zadań muszą zostać umieszczone w repozytorium git,
  • rozwiązania zadań są automatycznie testowane, punkty nie będą przyznane bez przejścia automatycznego testu,
  • przygotowując rozwiązanie należy dokładnie trzymać się wytycznych (w szczególności co do „wielkości” liter w nazwach plików, lokalizacji plików).

Zadania będą podzielone na cztery działy:

  • symbol X — zadania rozgrzewkowe, przykładowe itp.,
  • symbol A — automaty skończenie stanowe, teoria,
  • symbol B — wyrażenia regularne,
  • symbol C — automaty skończenie stanowe i przetworniki, praktyczne zastosowania,
  • symbol E — zadania tylko dla studentów z Erasmusa.

Spośród działów A, B i C można wykonać co najwyżej jedno zadanie. W dziale X można wykonać dowolną liczbę zadań.

System operacyjny i języki programowania

Rozwiązania zadań muszą działać w systemie operacyjnym Linux. Następujące języki są dopuszczalne:

  • Bash,
  • C,
  • C++,
  • Haskell,
  • Java,
  • JavaScript,
  • Lisp,
  • OCaml,
  • Perl,
  • Python (wersja 2 bądź 3),
  • Ruby,
  • Rust,
  • Scala.

Nie będą akceptowane rozwiązania w następujących językach: C#, Objective-C, PHP.

Struktura zadań i rozwiązań

Z każdym zadaniem związany jest osobny katalog o nazwie TaskXYY, gdzie X reprezentuje dział, YY to numer zadania.

Prowadzący zajęcia dostarcza w katalogu TaskXYY:

  • plik description.txt — opis zadania (łącznie z liczbą punktów i terminem wykonania)
  • pliki xyz.in, xyz.exp i opcjonalnie xyz.arg, gdzie:
    • xyz.in — plik wejściowy (podawany na standardowym wejściu),
    • xyz.arg — dodatkowy plik wejściowy (tylko w wypadku niektórych zadań),
    • xyz.exp — oczekiwane wyjście.

Rozwiązujący powinien dostarczyć następujące pliki:

  • run — plik wykonywalny,
  • Makefile (tylko dla języków kompilowalnych) — plik ten powinien zawierać opis kompilacji programu,
  • dodatkowe pliki — można rozbić rozwiązanie na kilka plików, np. w celu zwiększenia czytelności.

Plik run będzie dla każdego testu wywoływany w następujący sposób:

TaskXYY/run xyz.arg < xyz.in > xyz.out

Test zakończy się powodzeniem, jeśli plik xyz.out będzie identyczny z plikiem xyz.exp

W wielu zadaniach plik wejściowy (czasami też plik wyjściowy) zawiera opis automatu skończenie stanowego. Zob. dokładną specyfikację formatu opisu automatów.

W czasie wykonywania automatycznych testów powstają następujące pliki:

  • xyz.out — wynik działania programu,
  • xyz.res — różnica między plikiem xyz.out a xyz.exp, jeśli wszystko poszło dobrze, plik ten powinien być pusty,
  • report.txt — podsumowanie wyników testów w formacie TAP.

Poniżej podaję dokładniejsze wytyczne co do sposobu przygotowywania rozwiązania w rozbiciu na typy języków programowania.

Języki skryptowe

W wypadku języków skryptowych (Bash, Python, Perl, Ruby, Scala) plik run może po prostu zawierać kod w danym języku, należy przy tym na początku pliku umieścić preambułę „shebang”, np. dla Pythona 2:

#!/usr/bin/python2

kod w Pythonie

Alternatywnie (jest to nieco bardzie eleganckie rozwiązanie), plik run może być tylko owijką w Bashu, która wykonuje właściwe rozwiązanie:

#!/bin/bash
python2 TaskXYY/run.py "$@"

("$@" potrzebne jest, by przepchać dodatkowe argumenty potrzebne w niektórych zadaniach).

Właściwe rozwiązanie znajduje się wówczas w osobnym pliku z rozszerzeniem typowym dla danego języka programowania (np. .py dla Pythona), co z różnych powodów może być wygodne

W katalogu TaskX01 znajduje się gotowe, przykładowe rozwiązanie zadania przy użyciu języka skryptowego.

Języki kompilowalne

W wypadku języka kompilowalnego (C/C++, Java, Haskell) należy w pliku TaskXYY\Makefile opisać sposób kompilacji (jako przepis dla programu make), zob. TaskX02/Makefile jako przykład.

Dla języków kompilowalnych do kodu maszynowego (C/C++, Haskell) plik run będzie po prostu plikiem binarnym, efektem kompilacji.

Dla języków kompilowalnych do kodu bajtowego (Java, Scala) plik run powinien być prostą owijką w Bashu uruchamiającą plik .jar, np.:

#!/bin/bash
java -jar TaskXYY/run.jar "$@"

Przykładowy Makefile dla Javy

Zakładamy, że plik źródłowy to Runner.java (oczywiście może być ich więcej i mogą inaczej się nazywać).

BINARIES += TaskXYY/run.jar

# sztuczka, żeby nadrzędny Makefile aktywował cel TaskXYY/run.jar
.PHONY: TaskXYY/run
TaskXYY/run: TaskXYY/run.jar

TaskXYY/run.jar: TaskXYY/Runner.class
	(cd TaskXYY ; jar -cvfe run.jar Runner Runner.class) # pakowanie musi odbyć się w katalogu TaskXYY

TaskXYY/Runner.class: TaskXYY/Runner.java
	javac $<

Nie wolno umieszczać w repozytorium plików binarnych. Zalecane jest dodanie listy plików binarnych do pliku .gitignore (trzeba go też zatwierdzić i wypchnąć!). Zob. też ignoring files.

Jak sprawdzić rozwiązanie

Aby sprawdzić wszystkie swoje rozwiązania, należy wywołać polecenie make:

cd daut-2014-s123456 # rzecz jasna, trzeba być w swoim katalogu
make

Aby sprawdzić pojedyncze rozwiązanie, należy wydać polecenie:

make TaskXYY/report.txt

Aby sprawdzić rozwiązanie na pojedynczym teście, należy wydać polecenie:

TaskXYY/run xyz.arg < xyz.in

wynik zostanie wypisany na standardowym wyjściu; jeśli wcześniej tego nie uczyniliśmy być wpierw skompilować program (make TaskXYY/run).

Jeśli z niejasnych powodów otrzymujemy nieoczekiwane wyniki, można usunąć wszystkie pośrednie pliki, tak aby proces testowania przeszedł w całości:

make clean