od Sylverlin » 9. 6. 2009 22:12
Zadání: Scrabble.
http://www.forum.matfyz.info/viewtopic.php?f=351&t=3272
*SPOULER WARNING*
Řešení:
- je to (evidentně...) úloha na prořezávání stavového prostoru
- slovník reprezentovat dvakrát: prefixová, resp. sufixová trie (tzn. jednou udělaná odzadu, jednou odpředu - kontrolování slov po směru a proti směru)
- a podle slovníku prořezávat
- pozor na speciální případ, kdy přidávám na konec nebo začátek nějakého existujícího slova, ale stavím kolmo na něj - tady je potřeba prořezávání vypnout a prostě projít všechny možnosti. Na druhou stranu, dá se taky zkusit začít kdekoliv, ne jenom na políčkách sousedících s existujícími slovy, což - myslím - tenhle problém obchází. (Což mě napadlo, bohužel, přesně ve chvíli, kdy jsem dostal podpis do indexu. For the record za 1.
)
Tohle jsou klíčové body. Další užitečnost je např. v reprezentování políček hracího plánu: mít odkazy na obsazené sousedy - výrazně to ulehčuje potom načítání slov vytvořených "bokem", dají se asi vymýšlet všelijaké heuristiky (např. projít si na začátku písmenka a zkusit v nich předpřipravit nějaká hotová slova, která by se dala přikládat různě podél existujících slov...), ale hlavní je prořezávání přes ty dvě trie, respektive když se začíná odkudkoliv, stačí jedna.
Jo, nejsem si jistý, jestli se to říkalo v zadání, ale Holan s Töpferem hrajou scrabble tak, že přidávají jenom souvislá pole, tzn. nekříží. Moje řešení fungovalo i pro křížící se slova (hrajeme halt doma scrabble jinak.
), ale to jsou detaily, které se snadno vyřeší na ústním. Tím mým směrem aspoň se to vyřeší snadno a rychle.
Zadání: Scrabble.
[url]http://www.forum.matfyz.info/viewtopic.php?f=351&t=3272[/url]
*SPOULER WARNING*
Řešení:
- je to (evidentně...) úloha na prořezávání stavového prostoru
- slovník reprezentovat dvakrát: prefixová, resp. sufixová trie (tzn. jednou udělaná odzadu, jednou odpředu - kontrolování slov po směru a proti směru)
- a podle slovníku prořezávat
- pozor na speciální případ, kdy přidávám na konec nebo začátek nějakého existujícího slova, ale stavím kolmo na něj - tady je potřeba prořezávání vypnout a prostě projít všechny možnosti. Na druhou stranu, dá se taky zkusit začít kdekoliv, ne jenom na políčkách sousedících s existujícími slovy, což - myslím - tenhle problém obchází. (Což mě napadlo, bohužel, přesně ve chvíli, kdy jsem dostal podpis do indexu. For the record za 1. :-) )
Tohle jsou klíčové body. Další užitečnost je např. v reprezentování políček hracího plánu: mít odkazy na obsazené sousedy - výrazně to ulehčuje potom načítání slov vytvořených "bokem", dají se asi vymýšlet všelijaké heuristiky (např. projít si na začátku písmenka a zkusit v nich předpřipravit nějaká hotová slova, která by se dala přikládat různě podél existujících slov...), ale hlavní je prořezávání přes ty dvě trie, respektive když se začíná odkudkoliv, stačí jedna.
Jo, nejsem si jistý, jestli se to říkalo v zadání, ale Holan s Töpferem hrajou scrabble tak, že přidávají jenom souvislá pole, tzn. nekříží. Moje řešení fungovalo i pro křížící se slova (hrajeme halt doma scrabble jinak. :-) ), ale to jsou detaily, které se snadno vyřeší na ústním. Tím mým směrem aspoň se to vyřeší snadno a rychle.