Szókirakós játék Javascriptben (1. rész)

Faluvegi Ferenc
Jul 10, 2017 · 5 min read

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.

Példa (www.szokirakos.com)

Í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); // true

Lá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.

  1. Kiindulunk egy adott koordinátából.
  2. Az illető koordinátát bejártnak tekintjük.
  3. Felderítjük a még nem bejárt szomszédokat.
  4. Egy-egy megoldási szálat indítunk rekurzióval minden még nem bejárt szomszéd irányába.
  5. 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

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade