# Zapoctovy test 22.1.

<{ForumPost(poster="Anonymous", timestamp=2009-01-22 18:53:46)}>
Ahoj, byl jste dneska nekdo na zapoctovem testu z C++? Jake bylo zadani? Nejake commenty? :)
<{/ForumPost}>

<{ForumPost(poster="goophy", timestamp=2009-01-22 19:37:05)}>
**Zadani**  
  
myprogram.exe translations.txt terms.txt  
  
**translations.txt**  
  
Na každém řádku definice překladu:  
\[A-Z]{1}: \[A-Za-z]+  
  
Příklad:  
A: BcD  
A: AX  
B: b  
  
**terms.txt**  
  
na každém řádku textový řetězec, resp. term:  
\[A-Za-z]+  
  
Příklad:  
BXY  
AcD  
BzY  
  
**Postup**  
  
Načíst translations.txt do datových struktur.   
Provést kontrolu, jestli požitím nějaké (nekonečné) posloupnosti překladů může dojít k zacyklení.  
  
**Výstup**  
  
Na konzoli:  
\[načtený výraz] {OK|BAD}  
  
**Komentář**  
  
Jde o to, že pravidla se použiji obdobným způsobem pro dané termy jako třeba úpravy formulí ve výrokové logice. Tj. nějaká podmnožina (tady jeden znak) lze nahradit nějakým řetězcem dle definice z translations.txt. Úkolem je tedy zjistit, jestli se při nějaké kombinaci použití pravidel může úprava výrazu zacyklit.
<{/ForumPost}>

<{ForumPost(poster="R.U.R.", timestamp=2009-01-23 00:33:50)}>
Bylo na to 3,5 hodiny a ještě se nastavovalo takže skoro 4.  
K dipozici bylo obecně cokoliv. Explicitně povolena byla MSDN a libovolné papírové materiály, nicméně používání elektronických zdrojů informací nebylo kontrolováno. Internet byl formálně zakázán, nicméně nikoli reálně, neboť prý v SW1 nejde vypnout :-D No já jsem si teda stejně vystačil s MSDN no. Odejít na toaletu taky samozřejmě nebyl problém, pokud byste někdo myslel že vás spasí nějaká ilegální věc jako přítel na telefonu :twisted:   
  
Zadání bylo celkem stručné a jednoduché, pak ještě zadávající dodal, že samozřejmě by to mělo běžet rozumně rychle a mělo by to ošetřovat nekorektní vstupy. Moje O(N^4) se mu tak úplně nezdálo, když jsem to zlepšil na O(N^3) tak mi to vzal - ale měl jsem trochu pocit že by mi to možná dal i s tim předchozim řešenim. Každopádně nám na konci otráveně řek, že jsme na to měli použít DFS (a podle míry otrávenosti tak asi nikdo neučinil). Nevím jak ostatní, ale já ho viděl jen tak letmo na cvičení z ADS I, a z toho jsem si s sebou poznámky nevzal... (a kdo by to uměl když to nikdy neprogramoval ani se to nikde nezkoušelo, že...)  
  
Úloha byla vlastně čistě algoritmická, takže imho moc nevadilo že jsem s C++ začal v říjnu a na cvičení se toho moc nenaučil a ze zápočťáku mam zatím jen pár řádek a tak.... :-D A když si to tak vybavuju, tak jsem to před ním ani nespustil, zajímalo ho jak jsou udělaný některý netriviální věci, jaký mam datový struktury, kde mam co uložený a jak se na to dostávám... (potěšilo ho když mi to přišel zkouknout a místo obrazovky jsem mu nejdřív ukázal papír s rozborem :-D ). Takže kdybych tam měl někde nějakej minor bug, tak by to vlastně vůbec nebylo vadilo.  
Bylo zdůrazněno, že je to zkouška z C++ a nikoli z C, takže chce vidět C++ postupy jako třídy, dědičnost, vector, string... Těžko říct do jaké míry to bylo nutnou podmínkou, nicméně prý že kdo to napíše v C tak bude vyhozen (což třeba u mě nehrozilo, protože já stejně C neumím, takže spíše než omezující podmínka to pro mě bylo pozitivem :-) ).  
  
Úspěšnost byla imho dobrá, jeden kolega měl hotovo za hodinu, ostatní tak nějak průběžně dokončovali a případně upravovali své programy podle poznámek zadávajícího. Bylo nás asi 13, z toho asi 4 neúspěšní.
<{/ForumPost}>

<{ForumPost(poster="gufy", timestamp=2009-01-23 01:42:43)}>
No, s prohledavanim do hloubky jsem prisel. I kdyz ne pomoci rekurze takze jsem to delal na dva pruchody. Je fakt, ze se vyplati zase to visual studio vypnout (pokud jste jej aktivne hned zapli), vzit papir a tuzku a trochu si rozmyslet, co to zadani vlastne rika. :)   
  
Moje reseni:  
  
Cele to bylo o tom, postavit graf, najit cykly v grafu a najit vrcholy, ktere k nejakym cyklum vedou. Tj. pro kazdy vrchol jsem si nasel dosazitelne vrcholy a zjistil jestli ten vrchol nelezi na cyklu. Druhym pruchodem jsem pro kazdy vrchol zjistil, jestli jeho vzdaleny soused nelezi na cyklu. Vysledkem byl seznam vrcholu/znaku, ktere zpusobi cyklus.  
  
Resil jsem pres pruchod do hloubky skrze zasobnik a nastavovani visited pro jednotlive znaky. *(Navrzene lepsi reseni zadavajicim:)* Proto jsem potreboval druhy pruchod. Pri pouziti rekurze a trech stavu: novy, visited, locked se vsechno zvladne na jeden pruchod. (Pri vstupu na vrchol jej nastavim visited, po prorekurzovani potomku nastavim na locked. Pokud dorazi na vrchol s visited nastavim mu, ze je v cyklu, a zpatky (navratova hodnota rekurzivni fce) predavam informaci o existenci cyklu.)  
  
*gufy*
<{/ForumPost}>

<{ForumPost(poster="R.U.R.", timestamp=2009-01-23 16:40:14)}>
Hm, nechce se mi o tom moc přemýšlet ale to moje N^3 vypadalo podobně.  
  
EDIT: Měl jsem N^2 a jenom neumim počítat, haha :-))
<{/ForumPost}>

<{ForumPost(poster="vidlak", timestamp=2009-01-28 18:11:33)}>
Byla to uloha jako delana na graf, jak psal kolega, tj. postavit graf, najit vrcholy v cyklech a ty pak hledat v druhem souboru. Staci kdyz z prvniho souboru budete ignorovat mala pismena a zbude presne zadani grafu ve tvaru "vrchol : seznam_sousedu". Pak uz si jenom staci rozmyslet jak se bude implementovat graf v pameti. Ja sem zvolil celou incidencni matici 26x26 ('A'..'Z') booleanu, kde true na pozici i,j znamena, ze mezi i a j je hrana. To zarucovalo rychle konstruovani grafu pri cteni prvniho souboru (ktery mohl byt neomezeny), ale zase o neco pomalejsi hledani cyklu v grafu (ktery je naopka docela dobre omezeny). Cykly sem hledal pomoci hledani do sirky z vrcholu a cekal, jestli se do nej nejak dostanu zpatky (26x). Vysledkem bylo pole 26 booleanu, kde pro kazde pismeno byla hodnota true, pokud je v cyklu a false pokud neni v cyklu. To pak zase pomuze rychlemu testovani termu z druheho vstupu. Celkove je to tedy linearni ke vstupum a to hledani cyklu je vlastne konstatni, i kdyz by slo lepe pokud by kazdy vrchol mel seznam sousedu. Mel sem to za 2,75 hodiny i s predvedenim. Jen sem dostal pripominku, ze sem se nemusel rozhodovat mezi celou matici a seznamem sousedu, ale moh sem mit kazdy vrchol jako objekt a ten by mel jak seznam sousedu, tak i pole booleanu, jakozto radek matice. Cteni by pak bylo stejne rychly a hledani cyklu rychlejsi.  
  
Co sem tak zaslechnul, tak hlavni duraz byl na tom, jak je rychle cteni vstupu, jestli sme si vsimli, ze staci hlidat jen velka pismena a jestli je pouzita rozumna struktura. Napr. kdyz nekdo mel pole velke 256 a pouzival jen kousek pro hodnoty znaku 'A' .. 'Z', tak se nesetkal s moc velkym nadsenim  :)
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-03 16:27:21)}>
Je pri testu povolen internet? Jde mi o to, ze MSDN mi moc nevyhovuje, daleko lepsi napoveda je na cplusplus.com ..
<{/ForumPost}>

<{ForumPost(poster="goophy", timestamp=2009-02-04 10:33:54)}>

 > Him wrote:Je pri testu povolen internet? Jde mi o to, ze MSDN mi moc nevyhovuje, daleko lepsi napoveda je na cplusplus.com ..

Internet povolen není.
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-02-04 17:03:21)}>
A nejake jine materialy? knizky, neco na flashce, ... ?
<{/ForumPost}>