Zk 13.6. pisemka

[Void]

Teda je pravda, ze ty lehci priklady sou lehky, ale zase zatimco ostatni prevracely svoje spojaky nebo vkladali do BVS, ja mel bez uziti rekurze vypsat ohodnoceni uzlu binarniho stromu, serazenych vzestupne podle klice, coz me az tak uplne nejjednodussi nepride...

Co jsem ale hlavne chtel napsat? No prece zadani (+ moje chabe reseni) tezkeho prikladu, abych se taky dozvedel od nekoho jinyho a programatorsky zdatnejsiho, jak (by) to resil on

Zadani moc slozite nebylo:
Mame udelat proceduru, ktera vymysli nasledujici tah ve hre SCRABBLE tak, aby byl nejcenejsi, ale zaroven to musi vymyslet rychle.
Policka muzou byt prazdna, s pismenem, 2x cena pismena, 3x cena pismena, 2x cena slova, 3x cena slova ... proste jak normalni scrabble, tj. muze se pridavat jen do jedny souvisly rady za tah, cast noveho slova musi byt napojena na uz existujici slovo atdatd.

Moje reseni uz vubec slozite nebylo:
Slova sem si setridil podle abecedy do pole ( slo by i udelat si nejakej strom - proste kvuli rychlemu vyhledavani ) a pak jsem si udelal jeste jedno pole, udelane ze slov pozpatku, taky setridenych podle abecedy.

Mno a ted uz jsem na to sel jen celkem tupe - zacal jsem v okoli 3x slovo policek a zkousel tam napasovat slovo z tech kamenu, co mam ( tady se hodi mit i ty slova pozpatku - kdyz vime konec slova nebo tvorime slovo smerem doleva/nahoru )... slo tam nejak vhodne omezovat jejich pocet.
Kdyz to neprineslo zadny nebo jen zhnily ovoce, tak jsem sel prohledavat pole 2x slovo, mno a pri nouzi nejvetsi jsem se podival na nejdelsi existujici slovo nebo i kratsi, ale s cenejsima pismenkama a snazil se ho nejak natahnout atd.

Takze jsem otevren prispevkum a komentarum k reseni scrabble, kdyby nekdo chtel napsat nejakou zkusenost ze zkousky u Töpfera, taky se nebudu branit.

[tommy]

Moj lahky priklad bol jeden z tych baladickych typv : zjednotenie dvoch spojakov, pricom oba maju ostat zachovane.

A tazky som riesil asi podobne ako kolega (ale urcite nie nejako excelentne ):
mal som 2 slovniky jeden normalny a jeden spiatocny a navyse som ich mal v takomto tvare SLOVNIK : array[0..1,1..N,1..Z,1..#slov] of string kde prvy index je ci je spatocny alebo normlany, druhy index je pocet pismen slova, treti je zaciatocne pismeno a 4 je uz len index celeho pola v ktorom su zotriedene slova bez zaciatocneho/koncoveho pismena. spiatocny slovnik pozostava zo slov obratenych.
Pre kazde pismenko na hracom plane som skusal ake slovo by sa tam dalo doplnit. bud sa slovo zacinalo nejakym pismenom a bolo dlhe max par znakov(hladame v normalnom slovniku), alebo sa slovo koncilo na nejake pismeno a pred nim bolo niekolko pismen(hlada sa v spiatocnom slovniku), alebo sa zacinalo a koncilo na nejake pismenko/retazec(hladame v oboch slovnikoch).
Na pisomke som to robil ale drevorubacsky, lebo som zistil vsetky moznosti slov pre kazde policko zaradom a potom vsetky tahy ohodnotil a vybral najlepsi. Tu by sa zisla heuristika prehladavat podla stlpcov a riadkov v ktorom su nejake znasobenia a zacat v nich urcovat pripustne slova a ohodnotit tahy. Tieto tahy by boli tie z tych najlepsich.
No tolko asi k mojmu rieseniu. Uvidime aky zhovievavy bude pan Holan zajtra na ustnej a kolko mi toho uzna.

[Staon]

V principu jsem to řešil stejně, jako ostatní.

Slovníky jsem měl uložené ve stromu (uzel písmeno, potomci jsou všechna písmena, která mohou následovat, plus ještě příznak, zda tento uzel je konec slova). Slovníky jsem měl takto udělané odpředu a druhý odzadu.

Udržoval seznam již ucelených kusů slov (úseky) na ploše, kde jsem si jako celkem nepatrné zrychlení udržoval už spočítané ohodnocení tohoto kusu.

Také jsem si udržoval seznam polí, z kterých je možno hrát (tzn. která sousedí s nějakým už obsazeným polem). Tento seznam jsem postupně procházel a z těchto míst jsem se pokoušel postavit slovo do směrů, kam můžu. Pro snadné modifikace jsem si do seznamu volných polí ukazoval také z dvourozměrného pole ukazatelů, kde souřadnice odpovídaly pozici na hrací ploše.

Jedna položka seznamu možných tahů obsahovala ukazatele na sousedící úseky a ještě ukazatel na pozici ve slovníku, která odpovídala písmenům v úseku. Takže jsem mohl okamžitě testovat, jestli některé písmeno, z těch které mám možnost použít v tahu, může navazovat na sousední úsek.

Uff, a to by bylo ve zkratce všechno. Netvrdím, že to je správné řešení, ale protože už mám po ústní, mohu s určitostí tvrdit, že mi bylo přijato za jedna

Zkoušel mě Töpfer a bylo to naprosto v pohodě. Velký příklad vlastně vůbec nečetl, rovnou jsem mu to vysvětloval a ukazoval v papírech, o čem zrovna mluvím. Neměl jsem tam prakticky ani řádku kódu, ale to mu bylo jedno.

Na ústní se mě ptal na vyhodnocení infixového výrazu - řekl jsem mu o použití gramatiky a potom algoritmus se dvěma zásobníky. Nakonec jsem v pohodě (a že jsem si tak po velkém příkladu nepřipadal) odešel za jedna

[themish]

no, tak ja mel jako lehky priklad secteni tri libovolne dlouhych desetinnych cisel ze souboru.. jsou i tezsi, ale za hodku jsem to nejak nestih...

co se tyce tezkeho prikladu tak o tom jsem neco nasel tady:
http://forum.matfyz.info/viewtopic.php? ... e6b5521837

moje reseni tu snad ani psat nebudu

[Schiroo]

V malých úlohách jsem si vytáthl bingo - přidávání do binárního vyhledávacího stromu. U scrabblu bylo jedno omezení, které mi úlohu poměrně podstatně usnadnilo - nelze přikládat křížem, tzn. všechna přiložená písmena se musejí navzájem do týkat, nelze např. z písmen KÁŠMÍXF na zásobníku vytvořit na desce slovo ŠMÍ(R)ÁK, které by navazovalo na R ležící na desce.

Moje řešení se trochu liší od ostatních, která tu jsou, proto ho tu prezentuji ( a bylo uznáno ). V teorii se mě ptal na přihrádkové třídění a po chvilce tupého mlčení mi prozradil, že se jedná o radixsort:) Za 1 s přimhouřením Topferova oka

Scrabble
Slovník jsem měl uložený jako BVS, který jako uzel má toto:
slovo a a ukazatele na BVS obsahujici vsechny pripustne predpony a pripony.
Rozdelil jsem to podle delky pripon, takze tech ukazatelu bylo 2*(N-1) (2 kvuli predponam a priponam, (N-1) je maximalni delka pripony).
Procedura INIT nacetla slovnik do pameti.

Tah jsem rozdelil na dvě casti
1, Prodlužuju existující slovo ( i jednopísmenné)
neboli hlavní slovo, které přikládám, bude obsahovat aspoň jedno písmeno ležící na desce:
projdu všechna slova ležící na desce (max stovky) a pro každé slovo zjistím, kolik písmen se vejde před/za něj, ve slovníku vyhledám všechny před/přípony do dané délky, zkontroluju se zásobníkem, zda je můžu vytvořit a zkusím slovo položit. Zkontroluju, že všechna případná další slova jsou ve slovníku a započítám bodovou hodnotu. Je-li lepší než dosavadní nejlepší hodnota, uložím ji.

Note: je potřeba rozmyslet, jak se vyporadat s tim, kdyz zacatek i konec slova jiz lezel na desce a ja prilozil jenom střed.

2,
Vytvářím zcela nové slovo
neboli hlavní slovo, které přikládám, se bude skládat pouze z písmen v zásobníku a navazovat pomocí nějakého vedlejšího slova:
propermutuju všechna písmena v zásobníku a uložím si slova, která z nich můžu vytvořit ( 7písmen -> 7! = 5000 ). Poté pro projdu všechna pole, která sousedí s polem, kde je písmeno, zjistím, jaké písmeno na takové pole můžu přiložit a pokusím se přes toto pole navázat postupně všechna slova, která můžu ze zásobníku vytvořit (stovky sousedních polí, stovky slov, 100*100 = 10 000, to pořád ještě jde:) ). Spočítám, případně uložím, pokud je to dosud nejlepší hodnota.

Toť k mému algoritmu vše, snad je aspoň trochu pochopitelný.

A pro náročné, kterým se to zdá neefektivní a příliš stručné přidávám odkaz na diplomovou práci, která se přesně tímto zabývá - je tam i stručný výcuc - neboli jak by mohla vypadat ideální písemka
http://nlp.fi.muni.cz/projekty/pismenov ... index.html

[tommy]

Tak som dnes bol na ustnej a aby som sa sam zacitoval :

Moj lahky priklad bol jeden z tych baladickych typv : zjednotenie dvoch spojakov, pricom oba maju ostat zachovane.

Myslel som si, ze maly priklad mam bezchyby(nemoze spadnut), a ze na skuske ma bude istit ked bude najhorsie.

znamka : 2-
-neinicializoval som jednu premennu a mal som zbytocne velku zlozitost .... (zivot je proste plny prekvapeni )

-velky priklad : spolu sme to presli. Vsetko, na co sa spytal, som mu vysvetlil. Este mi dal par otazok pomimo-napr ako najrychlejsie vyhladat v slovniku slovo(pouzit hasovaciu tabulku vacsiu ako slovnik) a tiez mi ukazal nevyhody mojho riesenia a vyhody toho jeho
takze znamka asi tak 2-3 mozno.. neviem presne, ale povedal, ze som to nemal velmi dobre reprezentovane ...

-ustna : dynamicke programovanie
Tak to som sa potesil ze ukazem matice a bude ale tu uvodnu omacku, kedy sa to pouziva a tak, som skladal za pochodu, kedze som sa nemal odkial naucit ju presne. a na tom to chvilu viazlo. Podstata bola ze PREDPOKLADAME ze uloha sa da zlozit z mensich poduloh ktore maju optimalne riesenie... etc ale teraz ma to uz netrapi ...

overall : 2

takze spokojnost. Konecnce sa mozem ucit na zajtrajsi UNIX

[tommy]

propermutuju všechna písmena v zásobníku a uložím si slova, která z nich můžu vytvořit ( 7písmen -> 7! = 5000 ).

maly detail ze je o cosi viac tych vsetkych moznych slov = 13699 = sum (7-i)! = 7! . e Ale to je len tak na okraj, pre tych, ktorych by to mozno zaujimalo, pri vypoctoch zlozitosti.

Hlavne pre tych co sa na to este len chystaju. Davajte si pozor na maly priklad a premyslite si zbytocne veci, na ktorych vas moze Holan nachytat, nebodaj i vyhodit. Ono to vyzera mozno primitivne, niektore tie ulohy, mozno ich napisete sice ok, ale nie uplne najidealnejsie a cele vase snazenie je v ... Mam to overene od par ludi

[LordWolverin]

Mno, a je to za nami... Mel jsem z toho vitr, ale nakonec ok. Jak to probihalo?

Maly priklad
Nacist ze souboru posloupnost cisel, vyhodit tri nejvyssi a vytvorit BVS. Vcelku legrace, ovsem ja jsem nejak prehledl, ze nemusi byt vyvazeny a naimplementoval dynamicke pole, quicksort a jeste vytvoreni dokonale vyvazeneho BVS, cimz jsem si pridelal dost prace... Chvili jsme nad tim debatovali (chytre reseni podle nej je udelat si trojprvkove pole a do nej postupne ukladat, az v nem jsou tri nejvetsi prvky), ale za 1.

Velky priklad
Me reseni nebylo nicim prevratne, na nektere myslenky jsem prisel (jako ze je mnohem lepsi zacit od toho, kam se da pridavat, nez permutovat zasobnik), ale TAH jsem mel nedomysleny, takze nakonec 2 jeste s malou minuskou

Jako doplnujici otazku jsem mel Quicksort a jeho modifikaci (s tim zmenenym poradim volani rekurze), kratce se me zeptal i na hledani medianu. Parkrat me musel postrcit, ale nakonec shrnul: "To jste celkem vedel, pokud byste chtel jednicku, dam vam jeste doplnujici otazku..."

Predstava, ze se svou schopnosti zmatkovat vysvetluju B-Stromy nebo neco takoveho me od teto varianty odradila, takze nakonec za 2... Vzhledem k prubehu zkousky mozna malinko zklamani, ale v souladu se znamym prislovim kdo chce moc, nedostane nic spokojenost.