Szókirakós játék Javascriptben (1. rész)
A nyelvi játékok szerelmesei biztosan jól ismerik a Szókirakós játékot. Ez a gyors függőséget okozó szórakozás viszonylag egyszerű szabályokkal rendelkezik. Van egy N x N méretű táblánk. A tábla minden eleme egy-egy véletlenszerű betű. Ezen betűkből kell a játékosnak értelmes szavakat kiraknia úgy, hogy egy betű folytatásaként csak a még felhasználatlan szomszédjaiból választhat.

Így például a középső R betűből kiindulva, balra majd le mozdulva a RÉS szó rakható ki. A feladatunk jelen esetben az, hogy egy előre megadott táblából válasszuk ki az összes lehetséges kirakható szót. Jelen példában NodeJS-t használunk ES6 szintaxissal.
Az összes útvonal végigjárása
Első körben határozzuk meg egy koordináta reprezentálását. Bármelyik táblában szereplő betű meghatározható egy sor és oszlop koordinátával. A H betű például a (0, 0), az R pedig az (1, 1) pozícióban található.
function Coord(row, col) {
this.row = row;
this.col = col;
this.eq = coord => coord.row === row && coord.col === col;
this.toString = () => `[R:${this.row}, C:${this.col}]`;
};Egy konstruktor függvényt határoztunk meg, row és col tulajdonságokkal, illetve egy eq (equals) és egy segítő toString metódussal. Az eq lényege az, hogy két koordinátát hasonlíthassunk össze:
const coord1 = new Coord(2, 3);
const coord2 = new Coord(2, 3);
coord1.eq(coord2); // trueLássuk melyek egy koordináta szomszédjai, azaz mely irányokba haladhatunk egy adott koordinátától:
const neighbors = coord => [
// up
new Coord(coord.row - 1, coord.col),
// up-left
new Coord(coord.row - 1, coord.col - 1),
// up-right
new Coord(coord.row - 1, coord.col + 1),
// down
new Coord(coord.row + 1, coord.col),
// down-left
new Coord(coord.row + 1, coord.col - 1),
// down-right
new Coord(coord.row + 1, coord.col + 1),
// left
new Coord(coord.row, coord.col - 1),
// right
new Coord(coord.row, coord.col + 1)
];// Igy kerjuk le egy koordinata szomszedait:
// Egy Coord objektumokbol allo Arrayt terit vissza
console.log( neighbors(new Coord(0, 0)) );
Észrevehetted, hogy a neighbors koordináták között egyesek nem lesznek valósak (pl. Coord(-1, -1) az upLeft esetén). Ezzel is foglalkozunk a későbbiekben. Viszont először szögezzük le az algoritmus működésének folyamatát.
- Kiindulunk egy adott koordinátából.
- Az illető koordinátát bejártnak tekintjük.
- Felderítjük a még nem bejárt szomszédokat.
- Egy-egy megoldási szálat indítunk rekurzióval minden még nem bejárt szomszéd irányába.
- Minden megoldási szál esetében addig ismételjük ezt a 4 lépést, amíg kifogyunk a szomszédokból, azaz nincs több lehetőségünk a folytatásra.
Ez nem egyéb, mint a breadth-first gráf bejárási algoritmus definíciója. Hogy el tudjuk képzelni mi is történik a színfalak mögött, vegyünk egy banális 2x2-es táblát, és léptessük az algoritmust:
-----
|A|B|
-----
|C|D|
-------> Start:
utvonal: Coord(0, 0) // A
bejaratlan szomszedok: Coord(0, 1); Coord(1, 1); Coord(1, 0)--> szal #1:
utvonal: Coord(0, 0); Coord(0, 1);
bejaratlan szomszedok: Coord(1, 1); Coord(1, 0)
--> szal #1#1:
utvonal: Coord(0, 0); Coord(0, 1), Coord(1, 1)
bejaratlan szomszedok: Coord(1, 0)
--> szal #1#1#1
utvonal: Coord(0, 0); Coord(0, 1), Coord(1, 1), Coord(1, 0)
bejaratlan szomszedok: NINCSENEK, van egy megoldasunk: "ABDC"
--> szal #1#2
utvonal: Coord(0, 0); Coord(0, 1); Coord(1, 0)
bejaratlan szomszedok: Coord(1, 1)
--> szal #1#2#1
utvonal: Coord(0, 0); Coord(0, 1); Coord(1, 0), Coord(1, 1)
bejaratlan szomszedok: NINCSENEK, van egy megoldasunk: "ABCD"--> szal #2: ugyanigy, csak a Coord(1, 1) a masodik elem...
"ADBC", "ADCB" megoldasok--> szal #3: ugyanigy csal a Coord(1, 0) a masodik elem...
"ACBD", "ACDB" megoldasok
Azt vehetjük észre a léptetés során, hogy ha mindig a Coord(0, 0)-ás elemből indulunk ki, akkor csak minden “A”-val kezdődő megoldást kapunk meg. Ha az összes betűre kezdődő megoldás érdekel, akkor ugyanezt az algoritmust végig kell játszani rendre Coord(0, 1) B, Coord(1, 0) C és Coord(1, 1) D kezdő koordinátákkal.
Valójában a kód egyszerűbb mint az előbbi okfejtés. Lássuk hogyan néz ki:
Először is létrehozunk egy Table függvényt, ami az illető táblát kapja meg argumentumként mátrix formában. Az isSquare(table) segédfüggvénnyel lecsekkoljuk, hogy a kapott tábla valóban négyzet alakú. A step() függvény a rekurzív függvényünk, mely mindig a következő lépés elindításáért felelős. A step-en belül egy availableNeghbors() segédfüggvény gondoskodik arról, hogy megtudjuk melyek a még bejáratlan (isNotVisited függvény) és valós koordinátájú (isValidCoord függvény) szomszédok.
Az algoritmus “reaktora” valójában a következő snippet:
const ns = availableNeighbors();
return ns.length > 0 ?
flatMap(ns, nextCoord => step(nextCoord, [...path, coord])) :
pathToWord([...path, coord]);Ebben lekérdezzük a bejárásra váró szomszédokat. Amennyiben van legalább egy ilyen, akkor rekurzívan újrahívjuk a step() függvényt, a path argumentumhoz hozzáadván az aktuális koordinátát. Ha viszont nincs több bejárandó szomszéd, akkor egy megoldás szál végére értünk, és van egy potenciális megoldásunk.
A pathToWord(path) függvény a Coord objektumokat az illető útvonalnak megfelelő stringgé alakítja. Ez kerül visszatérítésre, így lépünk ki a rekurzív láncból. A flatMap célja az, hogy a step() által véglegesen visszatérített Array egydimenziós (vektor) és ne mély sokdimenziós tömb legyen.
A Table függvény visszatérít egy publikus API-t, melynek jelen esetben csak egyetlen traverse() metódusa van. A traverse célja az, hogy az algoritmust a tábla összes kezdő koordinátájával meghívja. Azaz ennek hatására lesznek A…, B…, C…, D… megoldásaink.
A megoldások kinyerése
Nos eddig azt értük el, hogy a Table.traverse() egy tömbnyi string alakú útvonalat térítsen vissza. Ezen stringek nagy része viszont értelmetlen. Bizonyos stringek pedig a jó megoldáson kívül némi ballasztot is tartalmaznak a string végén.
A végső feladatunk az, hogy egy szótárfájl alapján kinyerjük az összes értelmezhető szavat a traverse() visszatérített értékeiből.
Először is írunk egy banális fájlbeolvasó függvényt:
function Dict(path, encoding = 'utf8') {
const wordSet = new Set();
const data = fs.readFileSync(path, encoding).split("\n");
return {
index: cond => data.filter(cond).forEach(word => wordSet.add(word.toLowerCase())),
has: word => wordSet.has(word.toLowerCase())
};
}Tehát adunk a Dict() függvénynek egy path-et a text fájlunkhoz. Sorokra tördeljük azt. Majd a szavakat az index() metódussal egy Set-be mentjük. A Set azért nagyon jó, mert egyrészt biztosak lehetünk benne, hogy egy szó csakis egyszer szerepel benne. Valamint mert van egy hasznos metódusa, a .has(), amivel lekérdezhető, hogy egy bizonyos szó szerepel-e a Set-ben.
Végül kell egy megoldó függvény. Ez így néz ki:
function Solver(words, dict) {
return {
solve: () => {
const solutions = new Set();
flatMap(words, word =>
range(2, word.length).map(subWordLen => word.substr(0, subWordLen))
)
.filter(subWord => dict.has(subWord))
.forEach(wordFound => solutions.add(wordFound));
return solutions.values();
}
};
}A Solver-ben is nagyszerűen érzékelhető a funkcionális programozás elegáns mivolta. Mintha csak egy csövön engednénk át az adatot, minden egyes “kapunál” kicsit módosítva az eredményt.
Az első flatMap-ben a words argumentumban kapott stringek tömbjének minden elemét rész-szavakra bontjuk. Például: “abcdef” → “ab”, “abc”, “abcd”, “abcde”, “abcdef”. Így küszöböljük ki a stringekben fellelhető balaszt problémáját. Azt is elérjük, hogy csak a 2 vagy hosszabb karakterből álló szavakra keressünk.
A filteren átfuttatjuk az összes flatMap-től kapott stringet, és csak azokat engedjük tövább, melyeket megtalálunk a szótárban.
Végül egy forEach-el a végső megoldásokat egy Set-be mentjük, így biztosan nem kerül ugyanaz a szó kétszer a megoldások halmazába.
A programunk végső logikája így néz ki:
const huDict = Dict('./dicts/hu.txt');
huDict.index(word => word.length > 2);const table_3x3 = [
['S', 'M', 'P'],
['O', 'L', 'O'],
['K', 'O', 'H']
];
const paths = Table(table_3x3).traverse();const solutions = Solver(paths, usaDict).solve();
const solutionsArray = Array.from(solutions);
Elegáns, nem? A végső eredmény egy értelmes szavakból álló iterable lesz, amit kényünk kedve szerint bármivé alakíthatunk (pl Array-á).
Végszó
Ez az algoritmus közel sem nevezhető optimálisnak. Lehetne gyúrni például a szótár keresés optimalizálására. Vagy át lehetne gondolni egy kicsit a breadth search logikáját. Viszont így is egész jól fűrészel. Tapasztalatom szerint egy 150k-es szótár fájllal is kevesebb mint egy másodperc a futási idő.
A teljes forrást itt lehet elérni:
https://bitbucket.org/snippets/frantzdae/zyjLxd