Pozor na Toma!

Uživatelský avatar
wintermute
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 23. 5. 2005 22:06
Typ studia: Informatika Mgr.

Pozor na Toma!

Příspěvek od wintermute »

Tak jsem byl v pátek 20.5. na zkoušce a mam takovej pocit, že se s Tomem děje něco zlýho. Možná, že jsem v zápalu psaní písemky akorát něják špatně viděl, ale měl jsem pocit, že Tom NEMĚL ŽLUTÝ TRIČKO! Takže bacha na něj!
Jinak jak vypadala zkouška: Jako jednoduchej příklad jsem měl destruktivní průnik dvou spojáků.
Hlavní úkol byl naprogramovat proceduru, která najde nejlepší tah ve Scrabble. Vstup byl slovník (max. 100 000 slov) a plán rozehrané hry. Paměťové nároky měly být "rozumné," tj mohli jste mít v paměti třeba i pár exemplářů slovníku (ale né n-násobek apod.).
Dneska jsem byl na ústním - trvalo to asi 40min, z toho 5min jsem popisoval ten spoják, 30min jsme strávili rozebíráním toho scrabblu a 5 min vyprávěním o hashování. Dostal jsem za 2, takže v pohodě.
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

A nechtelo by se ti aspon naznacit, jak jsi na to sel / jak melo vypadat optimalni reseni?
Uživatelský avatar
wintermute
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 23. 5. 2005 22:06
Typ studia: Informatika Mgr.

Příspěvek od wintermute »

Úkolem bylo napsat proceduru INIT a TAH
v proceduře INIT:
-setřídíš si slova
-vyrobíš si hashovací tabulku a naplníš jí ukazatelama na slova.

v proceduře TAH
1. vygeneruješ si všechny startovací pozice(tj ty, které aspoň jednou hranou sousedí s nějákým písmemem, které je už na hracím plánu)
2. na každou takovou startovací pozici zavoláš procedury "vertikální subtah" a "horizontální subtah" (ten se liší akorát tím, že prohodíš X-y s Y-ama). Těmhle funkcím předáš:
- souřadnice zkoušeného políčka
- seznam dostupných písmen
- modifikátor chování (pokud nad zkoušeným políčkem není ani staré políčko, ani jiné možné startovní, měl by subtah zkoušet umísťovat písmena i nad něj, v opačném případě je to zbytečný)

v proceduře vertikální subtah:
1. koukneš se nad sebe. Tam je nějákej zárodek novýho slova. Poznamenáš si, kde ve slovníku jsou slova, která takhle začínají (slovník máme setříděnej, takže přípustné možnosti budou tvořít nějáký interval).
2. uděláme cyklus, kde zkoušíme na naše místo přidat všechna písmena, která nám zůstala v zásobě.
V každém průchodu cyklem:
-zkontrolujeme, jestli nám v horizontálním směru nevzniklo něco nepřípustnýho - pokud je tam nějákej souvislej sled písmen, stačí ho zahashovat a kouknout se, jestli je ve slovníku.
-zavoláme rekurzivně vertikální subtah na políčko pod námi (předáme jí dosavadní hrací plán, včetně změn, které na něm provedly předchozí úrovně rekurze + seznam písmen, která jsou ještě k dispozici)
3. pokud výsledky všech rekurzivních volání indikují, že nebylo nalezeno žádné přípustné řešení, případně se dolů už nedá táhnout, protože je to tam zabarikádovaný starým písmenem nebo krajem hracího pole, zkusíme, jestli aspoň náš dosavadní sled nově přidaných písmen netvoří nějáké smysluplné slovo. Pokud ano, ohodnotíme tah a pokud je za ten tah víc bodů, než za nejlepší dosud nalezený, uložíme ho do nějáké globální datové struktury jako nejlepší.

-při rekurzivním volání subtahu můžeme předávat informace o tom, v jakém intervalu slovníku jsme pracovali na předchozí úrovni rekurze (na hlubší úrovni rekurze nemůže být interval přijatelných slov širší)
-musíme něják implementovat, aby při nastaveném příznaku "nahoru" zkoušel subtah umísťovat písmenka i nahoru

Je to nejspíš trochu zmatený, ale nemůžete čekat, že to srozumitelně popíšu na pár řádek, když jsem na zkoušce popsal čtyři A3.
Návštěvník

Příspěvek od Návštěvník »

Hm, ja tam prisel, vysvetlil mu svuj velkej priklad a sel domu s jednickou :).

Holanovo reseni (aspon to co sem stihl z nej pochytit) vyuzivalo sestrizeni slov podle prvniho, druheho, tretiho... atd pismenka. To kvuli tahum, kdyz se pridava zepredu k existujicimu slovu (pak by se musel kazdy vhodny tah kontrolovat). Jak ten algoritmus s timhle pracuje uz si fakt nepamatuju.

Ja jsem resil pres lexikograficky strom (naplneny slovnikem) a pres vhodne prorezany strom pripustnych tahu (treba za sebou nesmi nasledovat takove trojice pismen, ktere se nikdy nevyskytnou ve slovniku). To se stavi jednou za cely tah, takze to je zanedbatelna prace. Pri pridani pismen za existujici slovo vetsinou kontrolujeme jen hodne malou cast slovniku i kombinaci (vlastne prochazime prunik dvou stromu). Holanova vytka byla prave k pridavani pred slovo. Reseni je to postavit oboje i odzadu (tj. koren je posledni pismenko) a vzdycky si vybrat, co je vhodnejsi pouzit. Nema cenu to vysvetlovat do detailu, protoze to neni slozita myslenka a tenhle priklad tam pravdepodobne znova nedaj :).
Odpovědět

Zpět na „2004“