# [Zk] 13. 6. pisemka

<{ForumPost(poster="tutchek", timestamp=2005-06-13 15:18:52)}>
Rubikova kostka,  
-datova reprezentace,  
-definice tahu,  
-nalezeni nejkratsi cesty (tahu) mezi kompozici kostky 1 a 2  
-mame pripravenou funkci ktera rekne jestli to jde (citace Kryl - az budete na zkousce z teorie grup, muzete chtit tohle programovat)  
- nejake undo  
- trasovani tahu + moznost nejakych podprogramu s tim  
  
  
podstatny je ta nejkratsi cesta, ostatni by melo byt... + jeste nejyk veci jsme meli delat ale ty byly tezce volitelne a to fakt nevim (napr. skladani kostky, nebo kvalifickace stavu(?) - neco jako "horni stena slozena" atd)  
  
mno... nemam z toho dobry pocit
<{/ForumPost}>

<{ForumPost(poster="Che", timestamp=2005-06-13 15:29:19)}>

 > tutchek wrote:
 > mno... nemam z toho dobry pocit

mno, já taky ne... :roll: Hledání nejkratší cesty tam nemám prakticky vůbec, nestíhal jsem...
<{/ForumPost}>

<{ForumPost(poster="pcv", timestamp=2005-06-13 15:39:21)}>
Taktéž to nevidím dobře.   
Především první část: Zatímco ostatní "trapáci" si obraceli spojáky apod. Já dostal setřídit spoják čísel podle počtu jejich různých prvočíselných dělitelů...takže dva spojáčky(jeden s počty dělitelů), milion pomocných pointerů  :? a za hodinu jsem tak akorát úspěšně počmáral papír.   
No nic, doufám, že mě zítra na ústním nevyhodí hned na začátku.
<{/ForumPost}>

<{ForumPost(poster="nohis", timestamp=2005-06-13 18:19:11)}>
Tak to je docela hnus...já dostal destruktivní sjednocení uspořádaných množin. Není to tak hrozný ale zmršil sem to teda nevídaně  :(   
A ta kostka no comment...
<{/ForumPost}>

<{ForumPost(poster="gris", timestamp=2005-06-13 19:00:11)}>
Jakpak jste reprezentovali kostku? Delali vsichni 6 poli 3x3 nebo nekdo vymyslel neco jineho?  
  
A z tech sesti stastlivcu, co byli dnes na zkousce, pochlubte se, kdo zkousel a jake to bylo  :)
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2005-06-13 19:03:48)}>
Tak ja mam za sebou aj ustnu... BLEEEE.  
Maly priklad som mal destruktivny prienik dvoch spojakov, ten bol v poho za jedna a velky... no, po pol hodine rozhovoru, ktory prebiehal fakt zvlastne, lebo sme sa akosi nerozumeli, mi povedal, ze to mam "blbe", ale ze ked mam z maly za jedna, tak este za tri moze byt... tak som dostal vonkajsie triedenia, hovorim si tazka pohoda... to nebola, lebo ma presvedcil, ze tomu v podstate vobec nerozumiem a dal mi zachrannu otazku... rozdiel medzi predavanim parametru hodnotou a referenciou... dalsia tazka pohoda... ja viem, nesmejte sa, ale vobec mi nejako nedochadzalo, pytal sa ma na take veci, co ma ani nenapadli  :oops: . Tak si tu teraz trepem hlavu o stenu, ze som bol milimetrik od trojky... ale vlastne mi ju nemal za vo dat.  
A chalan predo mnou dostal quicksort... kua, som v duchu opravoval vsetko, co povedal zle... no co uz, see ya 28... alebo tak nejak...
<{/ForumPost}>

<{ForumPost(poster="Che", timestamp=2005-06-13 19:15:05)}>
A kdo tě zkoušel? Respektive, komu patřil druhý sloupek? :?:  :)
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2005-06-13 19:42:53)}>
Kryl... a inak si nepamatam, kto ma ktory stlpcek...
<{/ForumPost}>

<{ForumPost(poster="airman", timestamp=2005-06-13 20:58:37)}>

 > jaruch wrote:Kryl... a inak si nepamatam, kto ma ktory stlpcek...

A co jsi tama si tak měl, jak jsi to reprezentoval a tak??  
  
Těch 6 polí 3x3 jsem tam taky uváděl ale nakonec jsem to rysknul a použil takovej podivnej stromeček (ani nevim jak mě ta střeštěnost mohla napadnout ;o) ). Ale celkem dobře se s tim rotovalo (líp než s těmi poli). Jsem zvědavej co mi na to řekne.  
  
Malej: vymazání intervalu z BVS. Nic hroznýho. Doufám že jsem neudělal nějakou blbou chybu.  
  
Ale stejně závidim co měli otočit spoják - to je vážně hned a na pár řádku ;o).  
To řazení je hnus :o(
<{/ForumPost}>

<{ForumPost(poster="JJ", timestamp=2005-06-13 21:32:49)}>
Hm tak se zda ze mam zatim nejvetsi silenost co se reprezentace tyce   :?   
Ja to reprezentoval jako pole ukazatelu na ukazatele  :D  takze se budu nekde modlit  :twisted:  a cekat na stredu
<{/ForumPost}>

<{ForumPost(poster="MyS", timestamp=2005-06-13 22:20:35)}>

 > jaruch wrote:Kryl...
Tak to uz jsem si tipnul z popisu prubehu zkouseni :o .
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2005-06-13 22:52:20)}>
co je na tom take unikatne?
<{/ForumPost}>

<{ForumPost(poster="MyS", timestamp=2005-06-13 23:56:27)}>

 > jaruch wrote:po pol hodine rozhovoru, ktory prebiehal fakt zvlastne, lebo sme sa akosi nerozumeli, mi povedal, ze to mam "blbe"
...ale treba mu krivdim, mam vlastne jen secondhandove infce...
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2005-06-14 10:34:31)}>
... ale bol celkom v pohode, tu trojku mi chcel dat, len akosi nemal za co... aj ked zase dost ma tam obracal.
<{/ForumPost}>

<{ForumPost(poster="Almer", timestamp=2005-06-14 11:04:36)}>
Ahoj...tak i ja sem pridavam svou "vizi" vcerejsiho programka.  
  
Takze uz pri vytazeni kostky, jsem si tise povzdychl a rekl si, to nebude dobre :shock: No...ale co...snad to nejak dam....  
  
Prisel ke me ...a ejhle...dostal jsem maly priklad...destruktivni sjednoceni dvou BST...rikam si pohoda....jenze pak ctu dale, "nedelat otrhanim jednoho z nich" a sakra....takze jsem to delal jinak...sice taky pohodicka, ale nez nastavite v jakem int (alfa, beta) se muze vlozit cely kus druheho stromu, tak probehne asi 20 podminek, a to jeste musete mit otce prvku, pod ktery to pridavate, a takove jakoze co kdyz otec tam neni atd atd :roll:  :roll:   
  
priklad jsme odevzdal jako posledni, ale mam ho...tak tak... 8)   
  
No potom kostka...jezisi...to bylo....ale nakonec jsem vymyslel docela dobrou reprezentaci a to tak, ze to budu reprezentovat v poli, protoze jedna stena ma 9 ctvrcu a je 6 sten...takze treba 35 pole je 3 stena a 5 policko....docela sikovne pak na manipulaci, v pameti sem pak mel pole pointru na ty "kostky" a to ve velikosti pamet /4 takze se tam dalo dost ulozit, a pri prohledavani v algoritmu, se dalo urcit, jestli jsem uz na nejakou takovou konfikuraci Rubikovky nenarazil:)  
  
No dost jsme tam obkecaval ostatni veci, krome hledami konfirugace z K1 do K2...jenze to bylo proto, protoze jsme to postupnym rozkladem prevedl a hledani nejkratsim cesty v nezaporne ohodnocenem grafu a Dijkstr je tak na 5 radku..(skoda ze nebyl cas to tam nabusit v pascalu, mam pouze slovni popis)..  
  
Na ustni jdu zitra v 13.00 takze uvidime, snad by to mohlo vyjit, jestli dostanu 3 tak budu skakat radosti a dokonce si uz reknu, ze neco z toho programka "umim" :P
<{/ForumPost}>

<{ForumPost(poster="matoman", timestamp=2005-06-14 11:32:06)}>
Neviem ci sa mam bat viac Kryla alebo Holana v ciernom tricku (-:
<{/ForumPost}>

<{ForumPost(poster="Almer", timestamp=2005-06-14 12:16:36)}>

 > matoman wrote:Neviem ci sa mam bat viac Kryla alebo Holana v ciernom tricku (-:

To je snad jasne...Holan v Cernem....
<{/ForumPost}>

<{ForumPost(poster="gris", timestamp=2005-06-14 12:52:51)}>
Tak at je obludarium reprezentaci Rubikovy kostky jeste silenejsi, posilam jeste jeden postreh:  
  
Kdyz si vsimneme, ze nezalezi na otoceni kostky jako takove, a ze konfigurace kostky je plne urcena polohou rohovych kosticek a polohou hranovych kosticek, muzeme si konfiguraci pamatovat jako permutaci 8 rohovych kosticek a permutaci 12 hranovych kosticek. Vyhoda je mensi pametova narocnost, pretaceni vrstev se pak implementuje na jeden radek jenom prehazenim prislusnych 4 prvku permutace.
<{/ForumPost}>

<{ForumPost(poster="pcv", timestamp=2005-06-15 08:48:12)}>

 > Kdyz si vsimneme, ze nezalezi na otoceni kostky jako takove, a ze konfigurace kostky je plne urcena polohou rohovych kosticek a polohou hranovych kosticek, muzeme si konfiguraci pamatovat jako permutaci 8 rohovych kosticek a permutaci 12 hranovych kosticek. Vyhoda je mensi pametova narocnost, pretaceni vrstev se pak implementuje na jeden radek jenom prehazenim prislusnych 4 prvku permutace.

Jo, jo, presne to na me vybalil dr. Holan u ustni jako spravnou reprezentaci.  
Jinak u zkousky byl velmi prijemny a na to ze prvni cast jsem nemel prakticky vubec, v druhe casti jsem mel vic nesmyslnych kydu nez hodnotnych myslenek to probihalo velmi pohodove. Jo a odesel jsem s velmi hezkou znamkou  :)
<{/ForumPost}>

<{ForumPost(poster="Lovec", timestamp=2005-06-15 18:16:26)}>

 > pcv wrote:
 > Jinak u zkousky byl velmi prijemny a na to ze prvni cast jsem nemel prakticky vubec, v druhe casti jsem mel vic nesmyslnych kydu nez hodnotnych myslenek to probihalo velmi pohodove. Jo a odesel jsem s velmi hezkou znamkou  :)

  
Kua, proc ja musim mit tu smulu a dostat kryla??????? Malej priklad v pohode, akorat jsem nemel osetreny jeden NIL. 1-, rubikova kostka? myslel jsem ze to mam docela dobre, on naznal ze tam pisi jen slova a vubec nevim o cem to je :oops: takze velkej za 4, pry mam jeste sanci na 3. Dal mi virtualni metody, tak povidam, povidam a kdyz dojdu k tomu ze VMT vyplnuje konstruktor tak me zarazil ze to neni pravda :shock: , a rekl at mu dam zkusebni zpravu - 4, kuaaaaaaa
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2005-06-15 18:24:53)}>
a kto ju potom teda vyplnuje??? lebo ja by som povedal to iste...  
inak podobne prebiehala moja skuska :evil:
<{/ForumPost}>

<{ForumPost(poster="MyS", timestamp=2005-06-15 20:36:46)}>
No. Kdyz na to zkusim pohlednout stejne "chapavym a nechci-nikoho-topit" pohledem jako pan zkousejici, tak by se to dalo pochopit, ze: VMT vyplnuje kompiler, ale ukazatel na ni vyplnuje konstruktor... 8)
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2005-06-15 21:56:41)}>
to by mi tiez napadlo... ale az potom, ako by som povedal to predtym... :?
<{/ForumPost}>

<{ForumPost(poster="ma3n", timestamp=2005-06-17 16:22:18)}>
Maly priklad som mal "iba" nedestruktivne zjednotenie dvoch mnozin reprezentovanych spojovym zoznamom. To sa mi zdalo celkom vpohode, no na ustnej mi potom k tomu Kryl dost pododaval a skritizoval, ale ohodnotil to celkom fajn 1-.  
Rubikovu kocku som robil asi takto.  
**Reprezentacia**: Ako pole 6 stien, kazda stena mala 9 malych kociek, a kazda mala kocka si ukazovala na svoje susedne male kocky.  
**Tahy**: sa robili potom v pohode. Stacilo otocit farby na jednej stene a zmenit potom farby aj kockam na ktore ukazovali kocky tejto steny.  
(tahy som mal iba otocenie jednej steny v smere + alebo -)  
**Vrat tah**: Pomocou pomocneho zasobnika do ktoreho som si ukladal cislo steny(1..6) a smer (+ -). Vybral som cislo a znak zo zasobnika a previedol som otocenie steny cislo (cislo) a otocil v opacnom smere ako je smer (znak).  
**Vstup vystup **: pre clovek proste zobrazit siet kocky.  
Na citanie zo suboru lepsi by bol zoznam farieb malych kociek jednotlivych stien.  
**Cesta z K1 do K2**:Prehladavanim do hlbky s pomocnym zasobnikom napr. velkosti 1000, a pomocnym polom cesty. Tahy usporiadam tak aby som nebral dalsi tah inverzny k predchadzajucemu. Ked najdem daku cestu uchovam si jej dlzku a dalej uz prehladavam len do hlbky najkratsej dosial najdenej cesty.  
Na ustu som siel ku Krylovi, ale podla mna bol celkom ferovy. Cez tuto velku pisomku sme presli za asi 3 minuty. Povedal dobre, dal mi za nu jednotku a potom sa ma uz nic nepytal. Takze super. :D
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2005-06-17 21:50:21)}>
ty male ulohy jsou se setridenymi spojaky?  
  
DIK!
<{/ForumPost}>