# Zápočtový test 19.2.2009 [by Ondřej Kunčar]

<{ForumPost(poster="Him", timestamp=2009-02-19 21:20:31)}>
**Motivace:** Dnes bylo úkolem zkontrolovat, zda konverze z jednoho datového typu na druhý nevyvolá chybu kompileru. Problém spočívá v tom, že kompiler se nemůže rozhodnout jak konverzi provést v případě, že po ocenění, jak moc jsou konverze z jednoho datového typu na druhý drahé, se objeví dvě (či více) možností jak konverzi provést -> proto vyvolá kompiler chybu (je zmaten :-))  
  
**Zadání (nepřesné):** Nicméně pravým úkolem bylo ohlásit v grafu takové cesty, které mají stejný první vrchol a stejný poslední vrchol a navíc tyto cesty mají stejnou cenu.  
  
Testovací vstup: Takto vypadal jeden testovací graf

    T1 ->  T2  -> T3
     |      |      |
     v      v      v
     T4 -> T5  -> T6
     |      |      |
     v      v      v
     T7 -> T8  -> T9
    

na vstupu byl zadán takto:  

    T1: T2, T4
    T2: T5, T3
    T3: T6
    T4: T5, T7
    T5: T8, T6
    T6: T9
    T7: T8
    T8: T9
    

**O vstupu:** Ze vstupu výše je vidět, že na každém řádku bylo: <identifikátor vrcholu><dvojtečka><identifikátory vrcholů oddělené čárkami>  
  
Podrobnosti řádce vstupu:  
o pokud je řádka prázdná, pak ji ignorujeme a pokračujeme na další  
o identifikátor vrcholu by se dal pomocí regulárního výrazu zapsat takto: \[a-zA-Z]\[a-zA-Z0-9]* --- tedy na začátku jeden znak a pak libovolný (i nula) znaků složených z alfanum znaků  
o okolo identifikátorů vrcholů může být libovolný počet mezer (př. T1    :   T2        ,     T4)   - je třeba si napsat něco na TRIMování  
o za identifikátorem může být v závorce uvedena cena hrany:  

    T1: T2(5), T4, T18(2)
    

   Takže z vrcholu T1 do T2 vede hrana s cenou 5, z T1 do T4 vede hrana s cenou 1 (defaultně 1, pokud není uvedeno jinak pomocí zápisu se závorkami), z T1 do T18 hrana s cenou 2  
o Řádka, která by obsahovala v seznamu sousedů sama sebe není povolena a má se vyhodit chybová hláška a skončit, př.

    T1: ..., T1 ,...
    

o Řádka, která obsahuje jen jméno vrcholu a neobsahuje žádné sousedy je také zakázána (řešení stejné jako výše).  
  
**Výstup (na příkladu výše):**  
  
T1, T5: (T4), (T2)  
T1, T6: (T2, T3), (T4, T5)  
...  
  
První dva vrcholy značí první a poslední vrchol cesty, následuje dvojtečka a v závorkách je vždy uvedena cesta bez počátečního a konečného vrcholu.  
  
o Ve výpisu se objeví pouze cesty, které mají stejnou celkovou cenu - ALE - pokud by existovaly např. čtyři cesty se stejnými počátečními a konečnými vrcholy, dvě by měly váhu 10 a dvě 20, pak vypisujeme jen ty s váhou 10 - tj. minimální váhu.  
  
**Čas:** 3h  
  
Měl jsem to hotové za 2.5h s tím, že jsem příliš nekoukal na efektivitu. Při procházení kódu jsem ještě přišel s jednoduchou úpravou, která drasticky snížila objem nutné paměti - když jsem tohle opravil, tak jsem měl splněno. Odcházel jsem přesně po třech hodinách jako první, subjektivní pocit je, že předchozí kola byla jednodušši.. statistiku úspěšnosti netuším, třeba někdo doplní..
<{/ForumPost}>

<{ForumPost(poster="Cabroušek", timestamp=2009-02-19 22:23:11)}>
Pokoušel jsem se to udělat tak nějak, jak fungují routovací tabulky a úplně jsem do toho zamotal. (Měl jsem radši vytáhnou Dijkstru). Vzdal jsem po necelých tři a půl hodinách a v ten moment se počet lidí odpovídající přibližně počtu prstů jedné ruky tvařil, že jim stačí jen chvilinka a budou moci odevzdávat, nicméně kolega Him byl v ten moment stále jediným, dko úspěšně odevzdal.
<{/ForumPost}>

<{ForumPost(poster="Chapadlo", timestamp=2009-02-20 02:54:01)}>
mno bylo sice nastaveno cca 30 min ale co jsem stihl sledovat tak uspesne odevzdali celkem 4 lidi coz neni moc. Na muj vkus bylo zadani docela prestrelene, 3hod bylo opravdu malo  :|
<{/ForumPost}>