Matfyz Wiki
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í..