játék a betűkkel

Algoritmusok

Szeretnék egy dobókockás "Játék a betűkkel" játékot csinálni. 14 kocka (84 oldal = 84 betű). Betűgyakoriság alapján megvan, hogy melyikből mennyi legyen - már csak az a kérdés, hogy egy kockára mely betűk kerüljenek?

(Arra gondolok, hogy pl. mivel egy P és egy C van, ha ezek egy kockára kerülnek, nem lehet kirakni a "pici" "pacsi" stb. szavakat.)

Csináltam egy olyan listát is, ahol a szavakban előforduló betűpárok gyakorisága szerepel ("alma" -> "al", "am", "aa", ...). Érdemes szerintetek ezzel szórakozni, algoritmizálni, vagy kb. érzésre, találomra?

szaszi

  • 116936 megtekintés

( persicsb | 2013. 01. 03., cs – 14:43 )

Szerintem nem tudsz olyan megoldást mondani, amire nem lehetne találni olyan szót, ami nem rakható ki.

Azaz ha 84 betűd van, és mondjuk ebből valamelyik betű csak n-szer szerepel, akkor biztosan nem rakható ki olyan szó, amiben n+1-szer szerepel a kérdéses betű.

Mivel csak 1 P-t és C-t használsz, így a paripa, pipa, cica, uccu, pép, cucc szavak sem rakhatók ki.

Fogadd el, hogy lesznek olyan szavak, amiket nem lehet kirakni. A szókirakónak nem is az a lényege, hogy minden lehetséges szót ki lehessen rakni, hanem az, hogy adott betűkből milyen szavak rakhatók ki. De nyilván nem szükséges minden lehetséges szónak megoldásnak lennie.

Igen, lesznek nem kirakhatók, de én a meglevő készletből szeretném a lehető legjobbat.

Lehet, hogy már eddig is több időt fordítottam rá, mint szükséges lenne, de hamar átfordult a gyakorlati feladat (fűrészelés, gyalulás) elméleti kérdéssé - ott pedig már nehéz megállni. :-)

"de én a meglevő készletből szeretném a lehető legjobbat."
Mi számít neked lehető legjobbnak? Legtöbb kirakható szó? Ez egy eléggé érdekes optimalizálási probléma, ahhoz, hogy ezt megodjad, definiálni kell, hogy mit tekintesz elfogadható szónak.
Ezért van az, hogy minden ilyen játékhoz jár szótár: a játékosok el tudják dönteni, melyik szó érvényes és melyik nem.
Például érdemes meggondolni, hogy az erdélyi magyarok tájnyelvi szavait is figyelembe veszed-e vagy nem.

Ha megvan az a szóhalmaz, amit elfogadható szavaknak tekintesz, akkor lehet megmondani, hogy miképp kell elhelyezni a kockák oldalain a betűket, hogy a lehető legtöbb szót ki lehessen rakni.

A szógyűjtemény megvan (kicsit több a halmaznál, mert folyó szöveg), a szavak gyakoriságával együtt, ennek kivonata a betűpár-gyakoriság, s ez szerintem elegendő a feladat optimális megoldásához

Tudom, hogy nem triviális a dolog... Pl. kérdés lehet, hogy folyó szövegből, valamilyen szótárból vagy szóhalmazból vegyem a betű- ill. betűpár-gyakoriságokat? Most inkább arra hajlok, hogy a (folyó szövegre épülő) szóhalmaz mégis jobb lenne.

Mivel a matematikai problémát nem igazán lehet pontosan megoldani (hatalmas a problématér, amiből az optimális megoldást ki lehetne választani), én azt csinálnám, hogy olyan betűket raknék egy kockára, hogy kockánként a betűgyakoriságok összege közel egyenlő legyen. Ez egyfajta speciális ládapakolási probléma. Ha közelítő megoldások is jók, akkor lehetne genetikus algoritmussal próbálkozni, a hibafüggvény pedig az lenne, hogy az átlagtól valamilyen metrika szerint mennyire térnek el a kiválasztott gyakoriságok. Lehet ez négyzetösszeg, abszolút érték, sokféle módon lehet kísérletezni.
Persze bevezetnék speciális kockákat is (csak mássalhangzós kocka, csak magánhangzós kocka), hogy kizárjuk azokat az eseteket, ahol véletlenül olyan eredmény jönne ki, amiből biztosan nem lehet szót alkotni.

( r0pi v | 2013. 01. 03., cs – 15:05 )

emeld meg a kockak szamat - 14 kocka amugy sem rakhato ki szepen. 4x4 meg talan tul keves, 5x5 viszont mar majdnem dupla, az mar jo lehet.
emeld meg addig mig a kerdeses betuk elofordulasa min 2 lesz az
osszes oldalra nezve.
rakhatsz bele joker-t.

egyebkent volt valami hasonlo jatek muanyagbol - egy nagy
muanyag kocka aljaban voltak rekeszek kialakitva, ide ultek be
a kis kockak miutan jol meg lett razva a cucc. lehet keresgeles utan meg lehet talalni az ott hasznalt mintat.

( ssikiss | 2013. 01. 03., cs – 16:10 )

Szép feladat! Brute force-t neki, és a felhőbe vele! Had olvadjanak a jégsapkák! ;D

( BaT | 2013. 01. 03., cs – 18:29 )

Én abból indulnék ki, hogy mivel egy kocka hat betűjéből mindig csak egy kerülhet kiválasztásra, ezért annál könnyebb a játék, minél ritkább betűhatosok kerülnek egy kockára. Azt neked kell eldöntened, hogy mennyire könnyű játékot akarsz, ha a legkönnyebbet, akkor nyilván a 14 legritkább betűhatost kell kiválasztanod.

Az már más kérdés, hogy ilyen betűhatosból a magyar abc szerint 44^6, vagyis 7 256 313 856 darab van, de ha erősen megszorítod az abc-t és csak az egyjegyű betűket veszed figyelembe, valamint kidobod a q-t és a w-t, még az is 33^6, vagyis 1 291 467 969 darab (remélem jól számoltam :)). Elég sokáig tartana ezekre mind kiszámolni a gyakoriságokat, jobb lenne a már meglévő betűpárokból kihozni valahogy ezeket a betűhatosokat (vagy legalábbis azon részét, amiből választani szeretnél a kockákra). Persze így a megoldás biztosan nem fog megfelelni a valóságnak, de figyelembe véve néhány további statisztikai tulajdonságot, talán jól lehet közelíteni a megoldást. Pl. átlagos magánhangzó/mássalhangzó arány, bizonyos egymással gyakran, vagy épp ritkán előforduló betűk, betűpárok, stb...

Még valami, a joker betűt tekintheted úgy, mint egy olyan betű, ami minden szóban előfordul, vagyis gyakorisága maximális.