minimal unreachable

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:	Przykładowy dokument i schematy \|\| Przykładowe labirynty
	Uwagi

Zasady poruszania się w labiryncie:

Labirynt stanowi las elementów corridor i po nich można się poruszać.
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.
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.
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).
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.
Rozwiązanie należy podać w elemencie path i może zawierać:

a) <path status="error"/>, jeśli nie udało się odczytać pliku wejściowego lub wystąpił błąd walidacji. W tym przypadku tworzymy nowy dokument.

b) <path status="impossible"/>, jeśli zadanie nie ma rozwiązania.

c) <path length="12">, 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. <go to="close_to_exit">, 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.
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ć.

Przykładowy dokument i schematy

Przykładowe zadanie wraz z rozwiązaniem oraz schemat dokumentu w formacie DTD i XML Schema:

<!DOCTYPE mr:moria SYSTEM "moria.dtd">
<mr:moria xmlns:mr="http://example.com/moria">
  <characters>
    <character name="Gandalf">
      <strength>40</strength>
    </character>
    <character name="Barlog">
      <strength>39</strength>
      <friendly>false</friendly>
    </character>
  </characters>
  <before character="Gandalf" destination="exit">
    <corridor character="Barlog">
      <corridor length="3">
        <corridor character="Gandalf" pos="entrence">
          <corridor pos="green" length="5" haskey="true"/>
          <corridor doorto="close_to_exit" requiredkey="green"/>
        </corridor>
      </corridor>
      <corridor>
        <corridor pos="close_to_exit">
          <corridor pos="exit"/>
        </corridor>
      </corridor>
    </corridor>
  </before>
  <!-- dalsze części dodane przez MoriaWalker -->
  <!-- <path status="impossible"/> -->
  <!-- <path status="error"/> -->
  <path length="12">
    <go to="green" pickkey="true"/>
    <go to="entrence"/>
    <go to="need_to_add_unique_id_for_this_corridor"/>
    <go to="close_to_exit" usekey="green"/>
    <go to="exit"/>
  </path>
</mr:moria>

<!ELEMENT moria ((characters,before)?,path?)>
<!ATTLIST moria
          xmlns CDATA #IMPLIED>

<!ELEMENT mr:moria ((characters,before)?,path?)>
<!ATTLIST mr:moria
          xmlns:mr CDATA #IMPLIED>

<!ELEMENT characters (character*)>

<!ELEMENT character (strength,friendly?)>
<!ATTLIST character name ID #REQUIRED>

<!ELEMENT strength (#PCDATA)>

<!ELEMENT friendly (#PCDATA)>

<!ELEMENT before (corridor+)>
<!ATTLIST before
          character IDREF #REQUIRED
          destination IDREF #REQUIRED>

<!ELEMENT corridor (corridor*)>
<!ATTLIST corridor
          length NMTOKEN #IMPLIED
          pos ID #IMPLIED
          doorto IDREF #IMPLIED
          requiredkey IDREF #IMPLIED
          haskey (false|0|true|1) "false"
          character IDREF  #IMPLIED>

<!ELEMENT path (go*)>
<!ATTLIST path
          length NMTOKEN #IMPLIED
          status (impossible|error) #IMPLIED>

<!ELEMENT go EMPTY>
<!ATTLIST go
          to IDREF #REQUIRED
          pickkey (false|0|true|1) #IMPLIED
          usekey IDREF #IMPLIED>

<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema"
            xmlns:mr="http://example.com/moria"
            targetNamespace="http://example.com/moria">

<xsd:element name="moria" type="mr:Moria"/>

<xsd:complexType name="Moria">
  <xsd:sequence>
    <xsd:sequence minOccurs="0">
      <xsd:element name="characters" type="mr:Characters"/>
      <xsd:element name="before" type="mr:Before"/>
    </xsd:sequence>
    <xsd:element name="path" type="mr:Path" minOccurs="0"/>
  </xsd:sequence>
</xsd:complexType>

<xsd:complexType name="Characters">
  <xsd:sequence>
    <xsd:element name="character" type="mr:Character"
                 maxOccurs="unbounded">
    </xsd:element>
  </xsd:sequence>
</xsd:complexType>

<xsd:complexType name="Character">
  <xsd:sequence>
    <xsd:element name="strength" type="xsd:positiveInteger"/>
    <xsd:element name="friendly" type="xsd:boolean" minOccurs="0"/>
  </xsd:sequence>
  <xsd:attribute name="name" type="xsd:ID"/>
</xsd:complexType>


<xsd:complexType name="Before">
  <xsd:sequence>
    <xsd:element name="corridor" type="mr:Corridor"
                 maxOccurs="unbounded"/>
  </xsd:sequence>
  <xsd:attribute name="character" type="xsd:IDREF"/>
  <xsd:attribute name="destination" type="xsd:IDREF"/>
</xsd:complexType>

<xsd:complexType name="Corridor">
  <xsd:sequence>
    <xsd:element name="corridor" type="mr:Corridor"
                 minOccurs="0" maxOccurs="unbounded"/>
  </xsd:sequence>
  <xsd:attribute name="length" type="xsd:nonNegativeInteger"/>
  <xsd:attribute name="pos" type="xsd:ID" use="optional"/>
  <xsd:attribute name="doorto" type="xsd:IDREF" use="optional"/>
  <xsd:attribute name="requiredkey" type="xsd:IDREF" use="optional"/>
  <xsd:attribute name="haskey" type="xsd:boolean" default="false"/>
  <xsd:attribute name="character" type="xsd:IDREF" use="optional"/>
</xsd:complexType>

<xsd:complexType name="Path">
  <xsd:sequence minOccurs="0" maxOccurs="unbounded">
    <xsd:element name="go">
      <xsd:complexType>
        <xsd:attribute name="to" type="xsd:IDREF"/>
        <xsd:attribute name="pickkey" type="xsd:boolean"/>
        <xsd:attribute name="usekey" type="xsd:IDREF" use="optional"/>
      </xsd:complexType>
    </xsd:element>
  </xsd:sequence>
  <xsd:attribute name="length" type="xsd:nonNegativeInteger" use="optional"/>
  <xsd:attribute name="status" use="optional">
    <xsd:simpleType>
      <xsd:restriction base="xsd:string">
        <xsd:enumeration value="impossible"/>
        <xsd:enumeration value="error"/>
      </xsd:restriction>
    </xsd:simpleType>
  </xsd:attribute>
</xsd:complexType>

</xsd:schema>

Przykładowe labirynty

minimal unreachable

minimal-unreachable.xml

Name: minimal unreachable
You: A1Z

A Z

minimal to weak

minimal-to-weak.xml

Name: minimal to weak
You: A1Z

A1Z

door by door

door-by-door.xml

Name: door by door
You: A5E
Keys: AC
Doors: BCA CDA DEC

  B
E9A9C
  D

key order

key-order.xml

Name: key order
You: A7G
Keys: BD
Doors: EFD FGB

BCDE F G
 A

one way ticket

one-way-ticket.xml

Name: one way ticket
You: A5F
Keys: BD
Doors: CD DCB EFD

  A
  1
B1C D
  E

  F

one friendly and one unfriendly

one-friendly-and-one-unfriendly.xml

Name: one friendly and one unfriendly
You: A7E
Doors: BE
Characters: C2u F3f

A1B2C
3
D3E
1
F

early fight necessary

early-fight-necessary.xml

Name: early fight necessary
You: A7G
Characters: E1
Doors: AD CF

GF
 5
 E
ABC
  D

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.

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.
Proszę upewnić się, że mają państwo aktualne (poranek 28.03.2006) pliki moria.dtd i moria.xsd, proszę zwrócić uwagę na definicję atrybutów haskey i pickkey w moria.dtd, która jest zgodna z typem boolean XML Schema.
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ę.
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).
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.
Wolno przechodzić z pola na to samo pole — koszt 0, nie grozi atak w plecy.
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.