Zadanie 2 -- Moria
------------------
Napisać program znajdujący drogę w labiryncie Moria dla zadanej
postaci, którą może ona przebyć nie tracąc wszystkich punktów siły.
'-----------`-----------------------------------
To: `lukpank-at-o2.pl`
Subject: `[xml-wtorek] zad2`
Załączniki: `MoriaWalker.java`
Argumenty: `some-uri.xsd some-uri.xml some-output.xml`
Promise: nazwy plików nie będą zaczynać się od znaku `-`
Wyjście: do podanego pliku `some-output.xml` zapisać rozwiązanie
Przykłady: link:#ex1[Przykładowy dokument i schematy] || link:#ex2[Przykładowe labirynty]
link:#uwagi[Uwagi]
------------------------------------------------
Zasady poruszania się w labiryncie:
1. Labirynt stanowi las elementów `corridor` i po nich można się
poruszać.
2. Z dowolnego elementu labiryntu można poruszać się do rodzica oraz
elementów potomnych. Koszt ruchu rodzic--potomek jest podany w
atrybucie `length` potomka i jest taki sam w obie strony. Jeśli nie
ma atrybutu `length` i schemat nie podaje domyślnej wartości należy
przyjąć jeden.
3. Z elementu posiadającego atrybut `doorto="somepos"` można przejść
do elementu o identyfikatorze `pos="somepos"`, przejście to może
wymagać posiadania klucza o nazwie podanej w atrybucie
`requiredkey`. Koszt przejścia przez drzwi jest zerowy.
4. Wchodząc na pole sąsiednie z polem nieprzyjaciela (każdy kto nie
jest przyjazny jest nieprzyjacielem), trzeba podjąć walkę
(niezależnie od długości korytarza) tzn. wejść na jego pole, walka
kosztuje obie postacie minimum z ich punktów siły, słabsza postać
umiera. Przejście bez podjęcia walki powoduje śmiertelny atak w
plecy (niezależnie od długości korytarza do wrogiej postaci).
5. Po labiryncie poruszamy się postacią określoną przez atrybut
`character` elementu `before` i musimy dotrzeć do korytarza o
nazwie określonej atrybutem `destination` elementu `before`.
6. Rozwiązanie należy podać w elemencie `path` i może zawierać:
+
a) ``, jeśli nie udało się odczytać pliku
wejściowego lub wystąpił błąd walidacji. W tym przypadku tworzymy
nowy dokument.
+
b) ``, jeśli zadanie nie ma rozwiązania.
+
c) ``, podajemy długość ścieżki (ilość punktów siły
zurzytych na poruszanie i walkę), a wewnątrz podjęte kroki:
+
- w kroku podajemy pole docelowe, np. ``, ale
możemy również określić atrybut `usekey` jeśli przechodzimy
przez drzwi wymagające klucza lub/i `pickkey` jeśli podnosimy klucz
znajdujący się w docelowym korytarzu.
7. Jeżeli korytarz którym chce się przejść nie posiada identyfikatora,
należy mu przydzielić unikatowy identyfikator, tak by w opisie
ścieżki można było się do niego odwołać.
[[ex1]]
Przykładowy dokument i schematy
-------------------------------
Przykładowe zadanie wraz z rozwiązaniem oraz schemat dokumentu w
formacie DTD i XML Schema:
htmlize::moria-example.xml[]
htmlize::moria.dtd[]
htmlize::moria.xsd[]
[[ex2]]
Przykładowe labirynty
---------------------
include::zad2_examples.inc[]
[[uwagi]]
Uwagi o oddawaniu zadania
-------------------------
Program jest weryfikowany za pomocą stu w większości losowych
labiryntów.
Jeśli wystąpi błąd (komenda zwraca niezerowy kod wyjścia) podczas
kompilacji, uruchomienia lub sprawdzania pliku wyjściowego nadesłanego
programu `MoriaWalker.java` to odsyłany jest opis błędu: wykonywane
polecenie, standardowe wyjście błędów oraz plik wejściowy (XML i SVG)
oraz wyjściowy plik XML.
Wówczas proszę poprawić i wysłać ponownie (zadanie zapisane do
skrzynki z błędnymi rozwiązaniami). Jeśli wydaje się, że błąd jest w
programie sprawdzającym lub nie jest jasne czego dotyczy proszę
odpowiedzieć na otrzymany list.
1. Sprostowanie: Moja wzorcowa implementacja `MoriaWalker.java` ma 450
linii (czyli 550 to nie za mało), zaś ok. 600 linii ma plik
`gen_zad2.py` przygotowujący zestaw testów.
2. Proszę upewnić się, że mają państwo aktualne (poranek 28.03.2006)
pliki link:moria.dtd[] i link:moria.xsd[], proszę zwrócić uwagę na
definicję atrybutów `haskey` i `pickkey` w `moria.dtd`, która jest
zgodna z typem http://www.w3.org/TR/xmlschema-0/#boolean[boolean]
XML Schema.
3. Jeśli błąd wystąpił podczas uruchomienia `MoriaWalker` to błąd jest
najpewniej w nadesłanym rozwiązaniu, jeśli podczas uruchomienia
`MoriaChecker` wyrzuca wyjątek to błąd jest najpewniej po obu
stronach i proszę mi mój zgłosić to postaram się obsłużyć
przeoczoną sytuację.
4. Program można przesłać jednym poleceniem, które najwygodniej
umieścić w pliku `Makefile`:
+
----
send:
mutt -a MoriaWalker.java `echo -e lukpank-at-o2.pl | sed s/-at-/@/` \
-s '[xml-wtorek] zad2' < /dev/null
----
+
i wysyłać komendą `make send` (zabawa z potokiem `echo`/`sed` służy
tylko temu by nie umieścić adresu wprost na stronie -- można po
prostu wpisać adres).
5. Jeśli kompilator Javy narzeka na śmieci typu base64:
+
----
$ javac MoriaWalker.java
MoriaWalker.java:1: 'class' or 'interface' expected
aW1wb3J0IGphdmEuaW8uSU9FeGNlcHRpb247CmltcG9ydCBqYXZhLmlvLk91dHB1dFN0cmVhbTsK
----
+
to znaczy, że list zawierał błędnie zakodowany załącznik i załącznik
został zapisany bez odkodowania, proszę spróbować ponownie lub wysłać
komendą z punktu 4. Niezidentyfikowany winny jest gdzieś na drodze od
programu pocztowego, przez serwery pośredniczące do programów
ściągających pocztę `fetchmail` i sortującego `procmail`.
6. Wolno przechodzić z pola na to samo pole -- koszt 0, nie grozi atak
w plecy.
7. Niezerowy kod wyjścia z MoriaWalker jest interpretowany przez
tester jako błąd w *programie*, tzn. jeśli działanie programu jest
poprawne (np. poprawne przetworzenie błędnego dokumentu) należy
zwrócić kod zero.
=== OAQ
Czy mogę na pole "exit" wejść z siłą == 0 i wyjść z labiryntu? Czy muszę mieć co najmniej 1? ??
0 oznacza koniec życia, więc trzeba mieć co najmniej 1.
Czy na polu "exit" może być wróg? ??
Może.
Czy klucz który jest na startowym polu jest automatycznie w kieszeni? ??
Nie, trzeba go podnieść. Wolno przechodzić z pola na to samo pole —
koszt 0, nie grozi tu atak w plecy.
Czy można używać kluczy kilka razy? ??
Można.