CODEWITHSUNDEEP
javascriptjquery
Bango Skank
Bango Skank

Reputation: 73

Create valid words from random letters

This is a bit of a puzzle - I have created a small game for my kids that is not dissimilar to the likes of Bookworm and Wordsworth. 49 letters are chosen at random from the alphabet (stored in an array), and the kids click adjacent letters to make words. There is a check to match the words to a dictionary file (also in an array), and if the word is valid the chosen letters are replaced in the grid with more random letters. All fine so far.

What I would like to do next is to check the grid to see if there are any valid words left in it, a kind of game over if you like. The problem is that I have no idea where to actually start!

The letters in the grid can be dropped into an array easily enough, but I lack the skills to work out the jQuery or javascript code that can check the grid to for valid words (remembering that the letters have to be adjacent to each other). Letters are displayed in DIV elements as opposed to a table.

So far I have simply managed to lock up the browser in a multitude of loops with the problem only exacerbated because the code needs to run every time a word is correctly found and letters in the grid replaced.

I understand that this is more of a problem solving experiment than a coding question as such, so my apologies if this post breaks any rules here, but does anyone have any idea how best to go about this?

Cheers BS

Upvotes: 0

Views: 1996

Answers (1)

Drathier
Drathier

Reputation: 14519

Start by getting all letters of a row. Then copy the first letter into a string and compare it to the dictionary. Next you take the two first letters and do the same. When you've reached 7 character length you take the 6 last letters and compare it to the dictionary. When you've done all checks in that row, move on to the next row. When all rows are completed do the same for collumns.

psuedo code: 

for ($currentCollumn=1; $gridWidth > $currentCollumn; $currentCollumn++) {
    $collumn = get collumn as string
    for ($i=1;$i!=7;$i++) {
        get first $i characters of $collumn and compare to dictionary
        }
    for ($i=1;$i!=7;$i++) {
        get last $i characters of $collumn and compare to dictionary
        }
}

for ($currentRow=1; $gridHeight > $currentRow; $currentRow++) {
    $row = get row as string
    for ($i=1;$i!=7;$i++) {
        get first $i characters of $row and compare to dictionary
        }
    for ($i=1;$i!=7;$i++) {
        get last $i characters of $row and compare to dictionary
        }
}

EDIT: Version 2, since I didn't realize the words weren't limited to straight lines.

start at every possible location. 

// define variables:
booleanArray path[x][y] = false;  
p = pointerlocation;  
stack[] = p;  
currentString = "";

p.up/.down/.left/.right checks path[][] where y+1, y-1, x+1, x-1 respectively. If it's outside the bounds it will return false.

The stack[] works like an x86 stack. Last in, first out.
push() adds a new object onto the stack
pop() gets the last object added to the stack and removes it from the stack 

function getAllTheStrings(p.x, p.y) {
    while (p) {
        path (p.x, p.y) = true;
        currentString += p.getCharacter();
        // check neighbors
        if (p.up) {
           stack.push(p.up, path, currentString);
        } 
        if (p.down) {
           stack.push(p.down, path, currentString);
        } 
        if (p.left) {
           stack.push(p.left, path, currentString);
        } 
        if (p.right) {
           stack.push(p.right, path, currentString);
        }
        // add current string to list possible words
        foundWords.push(currentString);

        // pop next item from stack
        overwrite variables with stored values of: p, path, currentString

        if (stack is empty) {
        p = false; // end loop
        }
    }
}

And that would be called by:

function getWords() {
    for ($y=1; $gridHeight > $y; $y++) {
        for ($x=1; $gridWidth > $x; $x++) {
            getAllTheStrings(x,y);
        }
}

This function scales very badly with grid size since it has to check every single combination of possible paths. A 1x1 grid would take one test. A 2x2 would take 28 tests. At 3x3 I lost count at about 270 tests.

After the loop is finished foundWords would be checked word for word against the whole dictionary. 5 found words and 100 words in the dictionary would give 500 comparisons. In reality the dictionary would have at least a thousand words.

Upvotes: 1

Related Questions