Open Source Bananagrams Solver in JavaScript, PHP & MySQL

I had some free time and decided to find a programmatic solution to a game of Bananagrams… yeah, why not :)… So, I’ve built a variety of MySQL dictionaries from Aspell, HTML and CSS were used to style the page, then coded the backend in PHP and placed a solver logic into JavaScript web worker. Here is a short outline of the entire process along with a web site and YouTube demo.

 

BANANAGRAMS INTRODUCTION

Bananagrams is a word game similar to Scrabble, invented by Abraham Nathanson in 2006.  From a bag of 144 lettered tiles, each player randomly picks the predetermined number of tiles (usually 21 letters). The goal of the game for each player is to use all of the given letters by creating the word grid of intersecting or interlocking letters that form valid English words. Players can rearrange their grid as many times they like. The player that uses up all of their tiles first, wins the game. The major skill that is required for this game is the ability to create anagram words formed by rearranging the letters by using all the original letters exactly once.

In general, the unwritten strategy for the game usually follows the following two simple rules:

  • Build the longest possible initial word
  • Keep the open layout structure, don’t cram the letters into a small grid

That’s the strategy I also use whenever I play the games. However, Saahil Agrawal and David Kwok of Stanford University in a paper named Bananas for Bananagrams offered another interesting idea on how to approach the problem. Their strategy suggested the use of a heuristic method of assigning a score for each of the words based on its component letters. Essentially they propose to give the less frequent English letters a higher number of points with a notion that starting the grid with letters that are more difficult to play, allows for the more flexible use of letters that are easier to play. Something similar is a strategy employed by Scrabble players, who create words with the highest possible combined letter value.

 

DEMO

The finished version of the Bananagrams Solver is online at: http://www.BananagramSolve.com

Here is a minute long video demo:

Looking at the final solution, it is not exactly ideal, has a long way to go, but

SOURCE CODE

Source Code for this little app is released under GNU Affero General Public License v3.0 on GitHub: https://github.com/JozefJarosciak/Bananagrams_Solver

 

 

 

 

Create MySQL English Word Dictionary

I decided to code the solution by using HTML, CSS, JavaScript on the frontend, PHP in the backend & MySQL as storage and word search engine.

Creating MySQL Dictionary of English Words

First I needed a good dictionary. To build one, I’ve converted a text file containing over 466k English words (found on https://github.com/dwyl/english-words) into MySQL database. I’ve also played with a dictionary of English words that I created from Aspell, here is a short article that describes How to dump and convert Aspell dictionary to wordlist or searchable MySQL/MariaDB database.

Once I had the database of English words in MySQL, I realized, that both dictionaries contain way too many words, some of them so unusual that they would likely never be regularly played by any human player. I needed to be able to select and search only among the words that are recognizable by most people. To resolve the problem, I implemented another database column, that added to each of the words their rank value based on the frequency in which the word occurs in a typical English text. You can read more about a word frequency on https://www.wordfrequency.info, who also show some examples of frequency lists based on the COCA corpus.

Once done, I had a list of English words and their associated frequency rank, which I could search by using SQL queries.

The following is my ‘dictionaries’ database and ‘en_english479k’ table definition:

CREATE TABLE `en_english479k` (
	`id` INT(11) NOT NULL AUTO_INCREMENT,
	`word` VARCHAR(50) NULL DEFAULT NULL,
	`description` VARCHAR(255) NULL DEFAULT NULL,
	`rank` INT(11) NULL DEFAULT NULL,
	PRIMARY KEY (`id`),
	UNIQUE INDEX `word_2` (`word`),
	INDEX `rank` (`rank`),
	FULLTEXT INDEX `word` (`word`)
)
COLLATE='utf8_general_ci'
ENGINE=MyISAM
;

Here is a SQL Dump in case someone wants to replicate it: 484k English Words with Frequency Rank.zip (3.8 MB Zip)

Search Query

MySQL Search – Search the longest possible initial word

The initial goal was to create a SQL query that would allow me to search the entire database for a word that contains as many of the letter tiles that I’ve randomly picked from the bag of lettered tiles. It’s somewhat of a tricky exercise because the query must also be capable of selecting words in situations where certain letters occur more than once, yet capable of finding words that might or might not contain any of the letters.

Ultimately, I’ve settled on using REGEX and combination of filters that used a MySQL BETWEEN condition, with order based on ranking the words by their total length (longer the better) and English word frequency rank. This is what the final SQL query looks like for a randomly selected letter sequence:

‘ANNEAGANRIT‘.

5 STEP MySQL Query

  1. First, build a Regex (1) based on the given lettered tiles.
  2. Then filter letters by using BETWEEN condition (2) for each character, defining the minimum and the maximum number of times a character can occur in the word. This part of the SQL will need to be generated programmatically, by counting the letter occurrence in the word.
  3. Select the allowed minimum and maximum gate for word frequency rank. In this case, I decided to only search my words among the top 50 thousand English words.
  4. Set the minimum word length. We want to solve the Bananagrams board only by using English words that are at least 3-letter long. I found that those solutions are the most readable.
  5. And finally closing the SQL by leveraging ORDER (3), sorting the words based on the descending word length and ascending frequency rank.

Let’s run the query on the randomly selected tiles ‘ANNEAGANRIT’:

As we can see the best result and the longest English word for the randomly selected tiles ‘ANNEAGANRIT’, is the word: ‘ARGENTINA‘.

Note: The importance of using the English word frequency rank is quite obvious when doing a search without the frequency rank, where the solution to randomly selected tiles ‘ANNEAGANRIT’ tiles is a quite obscure English word: ‘ANTENNARIA‘. While ‘Antennaria’ might be a valid English word, most of us would agree that it’s hardly recognizable and not really fit for purposes of building a human-like version of the Bananagrams solver. BTW. I had to look it up :) – Antennaria is a genus of herbaceous perennial plants.

PHP – Function to Find the Longest Word +Remainder of Characters

Now that we have a working SQL that can find the longest recognizable English words based on the given set tiles, we should wrap the SQL query into a PHP function that can be reused.

Let’s create PHP API endpoint that can be called from the JavaScript (or any other type of frontend UI), something like this:

  1. Input: Takes two URL variables, the sequence of characters and search offset.
  2. Result: Provide the longest found English word for the combination of submitted characters as well as the remainder of characters that could be used.

The API for finding words could look like this, where ‘q’ is the sequence of characters and ‘offset’ is the given results with 0 being the first/best word.

api.php?q=ANNEAGANRIT&offset=0

Here is the api.php file I’ve created to meet these requirements:

<?php
// ---------------------------------
//error_reporting(E_ALL); ini_set('display_errors', 1);
mb_internal_encoding("UTF-8");

// get MYSQL credentials ($username,$password) from credentials.php (you must create the file
include("credentials.php");

// ---------------------------------

// Connect to MySQL DB
$mysqli = new mysqli("localhost", $username, $password, "dictionaries");
$mysqli->query("SET NAMES 'utf8'");
$mysqli->query("SET CHARACTER SET utf8");
$mysqli->query("SET SESSION collation_connection = 'utf8_unicode_ci'");

// Set some of the variables

$shortestWord = htmlspecialchars(mb_strtolower(($_GET["shortestWord"])));
$longestWord = htmlspecialchars(mb_strtolower(($_GET["longestWord"])));
$dictionary = htmlspecialchars(mb_strtolower(($_GET["dictionary"])));
$characters = htmlspecialchars(mb_strtolower(($_GET["q"])));
$first = htmlspecialchars(mb_strtolower(($_GET["first"])));
$characters = preg_replace('/(\?+)/', '', $characters);
$characters = strtoupper(preg_replace('/(\+)/', '', $characters));
$remainingCharacters = $characters;
$characters_length = mb_strlen($characters, "UTF-8");
$offset_position = htmlspecialchars(mb_strtolower(($_GET["offset"])));
//$shortestWord = 2;


if ($longestWord >= 100) {
    $randomNumb = rand($shortestWord,strlen($characters));
    $longestWord = strlen($characters);
    //echo "1 - " . $randomNumb;
} else {
    $randomNumb = rand($shortestWord,$longestWord);
    //echo "0 - " . $randomNumb;
}



if (($characters_length < 1) || ($offset_position < 0)) {
    exit;
}




// Define Arrays
$characters_Array = str_split($characters);
$chars_UniqueOnlyArray = array_unique($characters_Array);


// SEARCH THE DICTIONARY + FIND REMAINING CHARACTERS
if ($characters_length <= 100) { // Do not allow search over 100 characters long
    // Build SQL Query
    $sql = buildSQLQuery($characters, $characters_Array, $chars_UniqueOnlyArray, $offset_position, $shortestWord, $longestWord,$dictionary,$randomNumb,$first); //echo $sql."<BR>";

    // Search Database
    $result = mysqli_query($mysqli, $sql);
    $row = mysqli_fetch_array($result);
    $foundWord = strtoupper($row['word']);
    $foundDescription = $row['description'];
    echo $foundWord;

    // find remaining characters
    $foundWord_Array = str_split($foundWord);
    for ($i = 0; $i < sizeof($foundWord_Array); ++$i) {
        $remainingCharacters = str_replace_first($foundWord_Array[$i], '', $remainingCharacters);
    }
    echo "|" . $remainingCharacters . "|" . $foundDescription ;
}

// Close MySQL Connection
mysqli_close($mysqli);


// *****************
// *** FUNCTIONS ***
// *****************

// SQL Query Builder
function buildSQLQuery($characters, $characters_Array, $chars_UniqueOnlyArray, $offset_position, $shortestWord, $longestWord,$dictionary,$randomNumb,$first)
{
    $finchar = strtolower($characters);
    $sqlQuery = "SELECT word,description FROM ".$dictionary." WHERE binary(lower(word)) REGEXP '^[$finchar]*$'";
    //$sqlQuery = "SELECT word,rank FROM en_english20k WHERE LOWER(word) REGEXP '^[$finchar]*$'";
    for ($i = 0; $i < sizeof($characters_Array); ++$i) {
        $countCharOccurence = substr_count($characters, $chars_UniqueOnlyArray[$i]);
        if ($countCharOccurence > 0) {
            $sqlQuery .= ' AND (CHAR_LENGTH(binary(lower(word))) - CHAR_LENGTH(REPLACE(binary(lower(word)), \'' . strtolower($chars_UniqueOnlyArray[$i]) . '\', \'\')) BETWEEN 0 AND ' . $countCharOccurence . ') ';
        }
    }




    //$sqlQuery .= ' AND rank BETWEEN 1 AND 20000 AND CHAR_LENGTH(word)>' . ($shortestWord - 1) . ' AND CHAR_LENGTH(word) <=' . $longestWord . ' ORDER BY length(word) DESC, rank ASC LIMIT ' . $offset_position . ',1';
    //$sqlQuery .= ' AND CHAR_LENGTH(word)>=' . ($shortestWord) . ' AND CHAR_LENGTH(word) <=' . $longestWord . ' ORDER BY length(word) DESC LIMIT ' . $offset_position . ',1';

    if ($first==='1') {
        $sqlQuery .= ' AND CHAR_LENGTH(word)>=' . $shortestWord . ' AND CHAR_LENGTH(word) <=' . $longestWord . ' ORDER BY length(word) DESC LIMIT ' . $offset_position . ',1';
        }
    else {
        $sqlQuery .= ' AND CHAR_LENGTH(word)>=' . $shortestWord . ' AND CHAR_LENGTH(word) <=' . $longestWord . ' ORDER BY length(word) DESC LIMIT ' . $offset_position . ',1';
        //$sqlQuery .= ' AND CHAR_LENGTH(word)>=' . $shortestWord . ' AND CHAR_LENGTH(word) <=' . $randomNumb . ' ORDER BY length(word) DESC LIMIT ' . $offset_position . ',1';
    }

    return $sqlQuery;
}

// Replace First Occurance of String within another String
function str_replace_first($from, $to, $content)
{
    $from = '/' . preg_quote($from, '/') . '/';
    return preg_replace($from, $to, $content, 1);
}

?>

EXAMPLES:

Let’s test it on an example, by getting the best word for the random characters: ANNEAGANRIT

We’ll call the API like this: api.php?q=ANNEAGANRIT&offset=0

The result: ANNEAGANRIT|AN

This is what happened:

 

If we need to get the 2nd best word, we simply increase the offset by one:

We’ll call the API like this: api.php?q=ANNEAGANRIT&offset=1

The result: EARING|AANT

You get the point. PHP API lets us control which result we want to display, allowing us to control the dictionary search the way we want, which will be especially useful when we start to look for Bananagrams solution.

 

PHP – GRID SIZE

In terms of the starting grid size, I am not sure if there is an optimal grid based calculation for n-letters, but I assume for a single direction placement, we shouldn’t need height x width grid ratio larger than the total length of initially provided characters. However, that assumption changes, if we start placing tiles in the exact middle of the grid and stretch the board/grid in all directions (up, down, left, right).

For example, if we start with a 4 characters ‘STBE’, and we can construct the word from all 4 of them, then the X and Y axis in all directions would look like this:

The answer to grid size is not the quadruple (8×8) as one would assume, but rather (7×7) as shown above… At least I think :)

The formula should be:

(n2 -1)  x  (n2 -1)

Thus (n2 -1)  x  (n2 -1) is also the total number of tile combinations that will need to be constantly checked during the letter placement.

 

Finding the middle of the board should be the crucial part of the exercise, as the two-dimensional JavaScript array cannot extend below zero.

In JavaScript, the grid can be constructed by using a two-dimensional associative array, where X will be the nth element in the outer array and Y will be the nth element in the inner array:

grid[X][Y];

For example, if the initially given letters are ‘BEST’, then to start placing letters into the exact middle of the grid, we should use X: (n -1)  and Y: (n -1)

In our case start at position X:3 and Y:3

grid[3][3] = “B”;
grid[4][3] = “E”;
grid[5][3] = “S”;
grid[6][3] = “T”;

The final placing on the grid with all other unset positions would then look something like this:

 

 

JAVASCRIPT – GRID CHECK LOGIC

The grid checking is the most active part of the Bananagrams solver. Essentially, as we’re adding words into the grid, with each iteration, we need to check all rows and columns to ensure that each results in a valid English word. If there are multiple words on the row or in the column, we need to ensure they are separated by space(s). If the grid doesn’t pass the test, the word can’t be placed and a different word combination must be tried. We must try all combinations until there are no words left (Bananagrams doesn’t have a solution), or until we find a solution when there are no remaining letter tiles.

Thinking about the process, this is how I’d like to execute it, the following is an approximate idea of the algorithm logic:

 

 

I had the option to develop this logic either on the server side or on the client side, each having certain benefits. On the client side, I can get better messaging as to the state of each iteration, I didn’t want to be calling backend every single time. On the client side, having a single thread available in the browser is a nightmare to deal with, especially because of the browser UI locking. But that can be easily fixed by using the second web worker thread. Web workers as we know, don’t have access to DOM, but they can receive and also post messages from and to the main javascript.

So instead of placing the logic into PHP, I decided to code the login into a web worker script, which I called search.js:

// Define global variables
var grid = new Array([]);
var inputCharacters = "";
var originputCharacters = "";
var remainingCharacters = "";
var foundWordsArray = new Array([]);
var counterRepeater = 1;
var longestWord = 100;
var maxIterations = 10;
var dictionary = "";
var finished = false;
var finalWordsArray = new Array([]);


this.onmessage = function (e) {
    if (e.data.addThis !== undefined) {
        inputCharacters = e.data.addThis.inputCharacters;
        originputCharacters = e.data.addThis.inputCharacters;
        shortestWord = e.data.addThis.shortestWord;
        longestWord = e.data.addThis.longestWord;
        maxIterations = e.data.addThis.maxiterations;
        dictionary = e.data.addThis.dictionary;
        console.log("Worker received inputCharacters: " + e.data.addThis.inputCharacters + " | longestWord:" + longestWord);
    }

    gridSolver(counterRepeater);
}

function gridSolver(itt) {

    finalWordsArray = new Array([]);
    grid = new Array([]);
    //  inputCharacters = "";
    remainingCharacters = "";
    foundWordsArray = new Array([]);

    if (!itt) {

        if (counterRepeater === 0) {
            itt = 0;
        }

    }

    inputCharacters = originputCharacters;
    console.log("---------------------------------------------------------");
    console.log("STARTING ITERATION: " + itt);
    console.log("---------------------------------------------------------");


    //  inputCharacters = document.getElementById("input").value.toString();
    console.log(inputCharacters + " | Length: " + inputCharacters.length);

    // initialize Grid array
    fill2DimensionsArray(grid, (inputCharacters.length * 3), (inputCharacters.length * 3) );

    // FIRST WORD PLACEMENT


    var xhr = new XMLHttpRequest();
    xhr.open("GET", "../api/api.php?q=" + inputCharacters + "&offset=" + itt + "&shortestWord=" + shortestWord + "&longestWord=" + longestWord + "&dictionary=" + dictionary+ "&first=1", false);  // synchronous request
    xhr.send(null);

    var firstWord = xhr.responseText.split('|');
    inputCharacters = firstWord[0];
    remainingCharacters = firstWord[1];

    finalWordsArray.push(firstWord[0] + "|" + firstWord[2]);

    placeFirstWord(inputCharacters);
    showGrid(inputCharacters.length, inputCharacters.length);

    //console.log("Placed 1st word:" + inputCharacters + " on the grid! | Remainder:" + remainingCharacters);
    console.log("Found: " +inputCharacters.toUpperCase() + " | Remainder: " + remainingCharacters.toUpperCase());
    //console.log("Description: " + firstWord[2]);
    //this.postMessage({result: "Placed 1st word:" + inputCharacters + " on the grid! | Remainder:" + remainingCharacters});
    this.postMessage({result: "<br>Iteration <b>" + itt + "</b>. Starting with word: <b>" + inputCharacters.toUpperCase() + "</b><br><br>"});


    // 2ND WORD CHECK
    ///////////////////
    ///// START 1 /////
    ///////////////////
    // remainingCharacters = foundWordsArray[0].remainder;
    if (remainingCharacters === "") {
        endProgramSolutionFound();
    } else {


        // if remainder exists we need to try letters on the board + remainder
        setFoundArray();
        finished = false;

        for (var x = 0; x < foundWordsArray.length; ++x) {
            // if you find the word in the array of found words that has no remainder, place it on the grid
            if (foundWordsArray[x].remainder === "") {
                finished = true;
                addWordToGrid(x);
                showGrid(inputCharacters.length, inputCharacters.length);
                break; // no need to continue
            }
        }


        if (finished === false) {
            addWordToGrid(0);
            showGrid(inputCharacters.length, inputCharacters.length);
        } else {
            endProgramSolutionFound();
        }


        // 3RD+ WORDs CHECK
        ///////////////////
        ///// START 3 /////
        ///////////////////

        remainingCharacters = foundWordsArray[0].remainder;
        if (remainingCharacters === "") {
            // showGrid(inputCharacters.length,inputCharacters.length);
            this.postMessage({end: "end"});
        }

        while (remainingCharacters.length !== 0) {

            try {
                remainingCharacters = foundWordsArray[0].remainder;
               // console.log("Remaining: '" + remainingCharacters + "'");
            } catch (e) {
                this.postMessage({grid: "."});
                this.postMessage({buttonName: "Solve"});
            }

            if (!remainingCharacters) {
                showGrid(inputCharacters.length, inputCharacters.length);
                break;
            }

            // if remainder exists we need to try letters on the board + remainder
            setFoundArray();
            finished = false;
            for (var x = 0; x < foundWordsArray.length; ++x) {
                // if you find the word in the array of found words that has no remainder, place it on the grid
                if (foundWordsArray[x].remainder === "") {
                    finished = true;
                    addWordToGrid(x);
                    showGrid(inputCharacters.length, inputCharacters.length);
                    endProgramSolutionFound;
                    //  showGrid(inputCharacters.length,inputCharacters.length);
                    break; // no need to continue
                }
            }

            if (finished === false) {
                addWordToGrid(0);
                showGrid(inputCharacters.length, inputCharacters.length);
            } else {
                if (remainingCharacters === "") {
                    //    showGrid(inputCharacters.length,inputCharacters.length);
                    endProgramSolutionFound();
                    break;
                    //exit;
                }
                endProgramSolutionFound();
                break;
            }
        }


    }

    this.postMessage({buttonName: "Solve"});
    //document.getElementById("button").value = "Solve";


}

function endProgramSolutionFound() {


    var placedCharacters = 0;
    for (var yy = 0; yy < (grid[0].length) - 1; ++yy) {
        for (var xx = 0; xx < (grid[0].length) - 1; ++xx) {
            if (grid[xx][yy]) {
                placedCharacters++;
            }
        }
    }


    if (originputCharacters.length === placedCharacters) {
        this.postMessage({result: "<hr><h3>Bananagram Solved!</h3> All " + originputCharacters.length + " tiles were successfully placed:<br><br>"});
        this.postMessage({buttonName: "Solve"});
        //console.log("1: " + finalWordsArray[1]);
        //console.log("2: " + finalWordsArray[2]);
        //console.log("3: " + finalWordsArray[3]);
        this.postMessage({description: finalWordsArray});
    } else {
        this.postMessage({result: "<hr><h3>Sorry, I am not able to solve this Bananagram!</h3>"});
        this.postMessage({grid: "."});
    }


}

function addWordToGrid(selectedItem) {
    //  console.log("Common Letter: " + grid[foundWordsArray[selectedItem].x][foundWordsArray[selectedItem].y]);
    //find where we can place the word: Top to bottom, or Left to right
    var commonCharacter;
    var commonLetterFirstPosition;

    try {
        var word = foundWordsArray[selectedItem].word;
        //console.log("Placing on grid word: " + word + " - Remainder:" + foundWordsArray[selectedItem].remainder);

        console.log("Found: " + word.toUpperCase() + " | Remainder: " + foundWordsArray[selectedItem].remainder.toUpperCase());
        commonCharacter = grid[foundWordsArray[selectedItem].x][foundWordsArray[selectedItem].y];
        commonLetterFirstPosition = word.indexOf(commonCharacter);


        //console.log("Common Letter: " + commonCharacter + " - at position: " + commonLetterFirstPosition);
        finished = false;

        for (var yy = 0; yy < (grid[0].length) - 1; ++yy) {

            for (var xx = 0; xx < (grid[0].length) - 1; ++xx) {
                if (grid[xx][yy]) {

                    if (commonCharacter === grid[xx][yy]) {


                        if (finished === false) {
                            var topToBottomOccupied = false;
                            for (var scanY = (yy - commonLetterFirstPosition) - 1; scanY < (yy + word.length) + 1; ++scanY) {
                                if (scanY !== yy) {
                                    //this.postMessage({progressCell: xx.toString()+"x"+scanY.toString()});
                                    if (grid[xx][scanY]) {
                                        topToBottomOccupied = true;
                                    }
                                } else {
                                    // console.log("+grid["+xx+"]["+scanY+"] = " + grid[xx][scanY]);

                                }
                            }

                            for (var scanY1 = (yy - commonLetterFirstPosition); scanY1 < (yy + word.length); ++scanY1) {
                                if (scanY1 !== yy) {
                                    if (grid[xx - 1][scanY1]) {
                                        topToBottomOccupied = true;
                                    }
                                    if (grid[xx + 1][scanY1]) {
                                        topToBottomOccupied = true;
                                    }
                                } else {
                                    // console.log("+grid["+xx+"]["+scanY+"] = " + grid[xx][scanY]);
                                }
                            }

                            //console.log("topToBottomOccupied = " + topToBottomOccupied);
                            if (topToBottomOccupied === false) {
                                var pos = 0;
                                for (var scanYY = (yy - commonLetterFirstPosition); scanYY < (yy + word.length); ++scanYY) {
                                    grid[xx][scanYY] = word.charAt(pos).toUpperCase();;
                                    pos++;
                                }
                                //console.log("Successfully Placed: " + foundWordsArray[selectedItem].word + " on the grid top to bottom!");


                                console.log("Successfully Placed Word: " + foundWordsArray[selectedItem].word.toUpperCase() + " on the grid top to bottom!");
                                //console.log("Description: " + foundWordsArray[selectedItem].description);
                                finalWordsArray.push(foundWordsArray[selectedItem].word + "|" + foundWordsArray[selectedItem].description);

                                finished = true;

                                break;
                            }
                        }


                        if (finished === false) {
                            var leftToRightOccupied = false;
                            for (var scanX = (xx - commonLetterFirstPosition) - 1; scanX < (xx + word.length) + 1; ++scanX) {
                                if (scanX !== xx) {
                                    if (grid[scanX][yy]) {
                                        leftToRightOccupied = true;
                                    }
                                } else {
                                    // console.log("+grid["+xx+"]["+scanY+"] = " + grid[xx][scanY]);
                                }
                            }

                            for (var scanX1 = (xx - commonLetterFirstPosition); scanX1 < (xx + word.length); ++scanX1) {
                                if (scanX1 !== xx) {
                                    if (grid[scanX1][yy - 1]) {
                                        leftToRightOccupied = true;
                                    }
                                    if (grid[scanX1][yy + 1]) {
                                        leftToRightOccupied = true;
                                    }
                                } else {
                                    // console.log("+grid["+xx+"]["+scanY+"] = " + grid[xx][scanY]);
                                }
                            }

                            //console.log("leftToRightOccupied = " + leftToRightOccupied);
                            if (leftToRightOccupied === false) {
                                pos = 0;
                                for (var scanXX = (xx - commonLetterFirstPosition); scanXX < (xx + word.length); ++scanXX) {
                                    grid[scanXX][yy] = word.charAt(pos).toUpperCase();
                                    pos++;
                                }
                                console.log("Successfully Placed Word: " + foundWordsArray[selectedItem].word.toUpperCase() + " on the grid left to right!");
                               // console.log("Description: " + foundWordsArray[selectedItem].description);
                                finalWordsArray.push(foundWordsArray[selectedItem].word + "|" + foundWordsArray[selectedItem].description);
                                finished = true;

                                //  console.log("--------------------------");
                                break;
                            }
                        }


                    }

                }


            }


        }


    }
    catch (err) {

        counterRepeater++;
        console.log("---------------------------------------------------------")
        console.log("DID NOT FIND SOLUTION, TRYING: " + counterRepeater + " TIME")
        console.log("---------------------------------------------------------")


        if (counterRepeater > maxIterations) {
            this.postMessage({result: "I did not find the solution in the first " + maxIterations + " iterations. Try changing the settings!"});
            this.postMessage({grid: "."});
            this.postMessage({buttonName: "Solve"});
            this.postMessage({end: "end"});
        } else {
            counterRepeater++;
            gridSolver(counterRepeater);
        }

    }


    if (finished === false) {
        counterRepeater++;
        console.log("---------------------------------------------------------");
        console.log("COULD NOT FINISH! remaining characters: " + remainingCharacters);
        console.log("---------------------------------------------------------");
        if (counterRepeater > maxIterations) {
            this.postMessage({result: "<font size=\"3\" color=\"red\">Sorry, but solution cannot be found in first " + maxIterations + " iterations. Try changing the settings!</font></p>"});
            this.postMessage({grid: "."});
            this.postMessage({buttonName: "Solve"});
            this.postMessage({end: "end"});

        } else {

            gridSolver(counterRepeater);
        }
    }
}


function setFoundArray() {
    var letterFromBoard = "";
    foundWordsArray = [];
    foundWordsArray.length = 0; // clear array
    for (var y = 0; y < (grid[0].length) - 1; ++y) {
        for (var x = 0; x < (grid[0].length) - 1; ++x) {
            if (grid[x][y]) {
                letterFromBoard = grid[x][y];
                var xhr = new XMLHttpRequest();
                xhr.open("GET", "../api/api.php?q=" + (remainingCharacters + letterFromBoard) + "&offset=0"  + "&shortestWord=" + shortestWord + "&longestWord=" + longestWord + "&dictionary=" + dictionary+ "&first=0", false);  // synchronous request
                xhr.send(null);
                //console.log("X:" +x + " x Y:" + y + " : " + remainingCharacters+ " + " +letterFromBoard);
                var firstWord = xhr.responseText.split('|');
                // console.log(firstWord[0] + " : " + firstWord[1]+ " : " + firstWord[2]);

                if (firstWord[0].indexOf(letterFromBoard) > -1) {
                    foundWordsArray.push({
                        "x": x,
                        "y": y,
                        "word": firstWord[0],
                        "remainder": firstWord[1],
                        "description": firstWord[2],
                        "length": firstWord[0].length
                    });
                }

            }
        }
    }
    // sort found words by length
    foundWordsArray.sort(function (a, b) {
        return parseFloat(b.length) - parseFloat(a.length);
    });
}


function placeFirstWord(inputCharacters) {
    // First word placement
    var firstWordSplit = inputCharacters.split('');
    for (var c = 0; c < firstWordSplit.length; ++c) {
        grid[((inputCharacters.length+2) + c)][(inputCharacters.length+2)] = firstWordSplit[c].toUpperCase();
    }
}

function showGrid(xs, ys) {
    var gridTable = "<table id=\"mytable\">";
    var gridTable2 = "";

    for (var y = 0; y < (ys * 3); ++y) {
        gridTable += '<tr>';
        var gridTable2 = "";
        var itemsInRow = false;
        for (var x = 0; x < (xs * 3); ++x) {
            if (grid[x][y]) {
                gridTable2 += '<td id="decorate">';
                gridTable2 += grid[x][y];
                itemsInRow = true;
            } else {
                gridTable2 += '<td id="' + x.toString() + "x" + y.toString() + '">';
                 // gridTable2 += "<small>"+x + " x " + y + "</small>";
            }
            gridTable2 += '</td>';
        }

        if (itemsInRow === true) {
            gridTable += gridTable2;
        }

        gridTable += '</tr>';
    }

    gridTable += "</table>";


    // POST BACK GRID
    this.postMessage({grid: gridTable});
    //document.getElementById("grid").innerHTML = gridTable;
}


function fill2DimensionsArray(arr, rows, columns) {
    for (var i = 0; i < rows; i++) {
        arr.push([0])
        for (var j = 0; j < columns; j++) {
            arr[i][j] = 0;
        }
    }
}

function upperCase(a) {
    setTimeout(function () {
        a.value = a.value.toUpperCase();
    }, 1);
}

Please note, as I coded the logic, I realized there are some holes in it, especially as I decided to not to use rank, but rather go for the longest word (or whatever is specified as a limit), which seemed like a better choice, but the reality is, I always only check the first word, I don’t go into deeper loops. In any case, the above logic, as much as it can be further improved, seems to be finding the results for me.

Search.js shown above is called from the main javascript.js, where the web worker is initialized:

function removePlaceholder() {
    document.getElementById("input").placeholder = "";
}

function webWorkerThread() {

    if (document.getElementById("input").value.length > 2) {
    document.getElementById("foundwords").innerHTML = "";
    document.getElementById("button").value = "processing...";
    document.getElementById("button").disabled = true;
    document.getElementById("button").style.background = '#787878';
    document.getElementById("shortestWord").disabled = true;
    document.getElementById("longestWord").disabled = true;
    document.getElementById("dictionary").disabled = true;
    document.getElementById("maxiterations").disabled = true;
    document.getElementById("input").disabled = true;
    document.getElementById("random").disabled = true;
    document.getElementById("randLen").disabled = true;



    var worker = new Worker('js/search.js');


    var shortestWord = document.getElementById("shortestWord").value;
    var longestWord = document.getElementById("longestWord").value;
    var maxiterations = document.getElementById("maxiterations").value;
    var dictionary = document.getElementById("dictionary").value;
    // send message to web worker
    var message = {
        addThis: {
           shortestWord: shortestWord,
            longestWord: longestWord,
            maxiterations: maxiterations,
            inputCharacters: document.getElementById("input").value.toString(),
            dictionary: dictionary
        }
    };
    worker.postMessage(message);

    // get message from web worker
    worker.onmessage = function (e) {

        if (e.data.result) {
            //console.log(e.data.result);
            document.getElementById("message").innerHTML = e.data.result;
        }

        if (e.data.grid) {
            // Clean Grid
            var resultGrid = e.data.grid;
            resultGrid = resultGrid.replaceAll("<tr></tr>", "");

            document.getElementById("grid").innerHTML = resultGrid;
            // console.log(resultGrid);
            if (e.data.grid === ".") {
                document.getElementById("grid").innerHTML = "";
            }
        }

        if (e.data.buttonName) {
            document.getElementById("button").value = e.data.buttonName;
            document.getElementById("button").disabled = false;
            document.getElementById("button").style.background = '#008CBA';
            document.getElementById("shortestWord").disabled = false;
            document.getElementById("longestWord").disabled = false;
            document.getElementById("dictionary").disabled = false;
            document.getElementById("maxiterations").disabled = false;
            document.getElementById("input").disabled = false;
            document.getElementById("random").disabled = false;
            document.getElementById("randLen").disabled = false;

            /*
            if (document.getElementById("grid").innerHTML.indexOf("<hr>" < 0)) {
            document.getElementById("grid").innerHTML += "<hr>";
            }
            */

        }

        if (e.data.end) {
            worker.terminate();
        }

        if (e.data.description) {
            //console.log(e.data.description);
            var arrayOfFoundWords = e.data.description;
            var finallist = "<hr><table id=\"resultWords\">";
            for (var i = 1; i < arrayOfFoundWords.length; i++) {
                //console.log(arrayOfFoundWords[i]);
                var finalword = arrayOfFoundWords[i].split("|");

               // document.getElementById("foundwords").innerHTML = "please wait... getting content...";

                // SK
                if (document.getElementById("dictionary").value.indexOf("sk_") > -1) {
                    finallist += "<tr><td id=\"leftcell\"><b><a href=\"http://slovniky.juls.savba.sk/?w=" + finalword[0] + "\" target=\"_blank\">" + finalword[0].toUpperCase() + "</a></b></td>";

                    var remote = $.ajax({
                        type: "GET",
                        url: "/api/getdescription-sk.php?q="+finalword[0],
                        async: false
                    }).responseText;

                    finallist += "<td id='leftcell'><small>   " + remote +"</small></td></tr>";



                }

                // EN
                if (document.getElementById("dictionary").value.indexOf("en_") > -1) {

                    finallist += "<tr><td id=\"leftcell\"><b><a href=\"https://www.merriam-webster.com/dictionary/" + finalword[0] + "\" target=\"_blank\">" + finalword[0].toUpperCase() + "</a></b></td>";

                    var remote = $.ajax({
                        type: "GET",
                        url: "/api/getdescription-en.php?q="+finalword[0],
                        async: false
                    }).responseText;

                    finallist += "<td id='leftcell'><small>   " + remote +"</small></td></tr>";

                }

                if ((document.getElementById("dictionary").value.indexOf("en_") === -1) && (document.getElementById("dictionary").value.indexOf("sk_") === -1)) {
                    finallist += "<tr><td id=\"leftcell\"><b>" + finalword[0] + "</b></td><td id='leftcell'><small>   " + finalword[1]+"</small></td></tr>";
                }

                //finallist += "<tr><td id=\"leftcell\"><b>" + finalword[0].toUpperCase() + "</b></td><td id='leftcell'><small>   " + finalword[1]+"</small></td></tr>";
            }
            finallist += "</table>"
            document.getElementById("foundwords").innerHTML += finallist;
            worker.terminate();
        }


    };

    } else {}


}

function makeRandomString() {
    var text = "";
    var possible =
        "EEEEEEEEEEEE" +
        "AAAAAAAAA"+
        "IIIIIIIII"+
        "OOOOOOOO"+
        "NNNNNN"+
        "RRRRRR"+
        "TTTTTT"+
        "LLLL"+
        "SSSS"+
        "UUUU"+
        "DDDD"+
        "GGG"+
        "BB"+
        "CC"+
        "MM"+
        "PP"+
        "K"+
        "J"+
        "X"+
        "Q"+
        "Z";


    if (document.getElementById("dictionary").value.indexOf("sk_") > -1) {
        console.log(document.getElementById("dictionary").value.indexOf("sk_"));
        possible =
            "AAAAAAAAAAAAAAAAAAOOOOOOOOOOOOOOOOOO" +
            "EEEEEEEEEEEEEEEEIIIIIIIIIINNNNNNNNNNRRRRRRRRSSSSSSSSTTTTTTTTVVVVVVVV"+
            "MMMMMMMMDDDDDDKKKKKKLLLLLLPPPPPP"+
            "JJJJUUUUBBBB"+
            "ÁÁCCHHYYZZ"+
            "ČÍŠÝŽÉĽŤÚĎFGŇÔÄĹÓŔX";
    } else {
        console.log(document.getElementById("dictionary").value.indexOf("sk_"));
    }


    for (var i = 0; i < document.getElementById("randLen").value; i++)
        text += possible.charAt(Math.floor(Math.random() * possible.length));
    document.getElementById("input").value = text;

}



function upperCase(a) {
    setTimeout(function () {
        a.value = a.value.toUpperCase();
    }, 1);
}

String.prototype.replaceAll = function (search, replacement) {
    var target = this;
    return target.replace(new RegExp(search, 'g'), replacement);
};

The HTML file (index.html) for this is somewhat simple:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Bananagrams Solver</title>
    <link rel="stylesheet" href="css/styles.css">
    <script src="js/javascript.js"></script>
    <script src="js/jquery3.3.1.js"></script>
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="description" content="Online Anagram Solver for Bananagrams game."/>
</head>

<body>

<div id="page-wrap">
    <a href="/">
    <img border="0" src="img/bananagrams_logo_new.png">
    </a>
    
    <br>
        <br>

    <table style="max-width: 800px">
        <tr>

            <td style="width: 20%"> Min. Length:<br><select name="shortestWord" id="shortestWord">
                <option value="2">2</option>
                <option value="3">3</option>
                <option value="4">4</option>
                <option value="5">5</option>
                <option value="6">6</option>
                <option value="7">7</option>
                <option value="8">8</option>
                <option value="9">9</option>
                <option value="10">10</option>
            </select></td>


                <td style="width: 20%">Max. Length:<br><select name="longestWord" id="longestWord">
                <option value="100">unlimited</option>
                    <option value="20">20</option>
                    <option value="19">19</option>
                    <option value="18">18</option>
                    <option value="17">17</option>
                    <option value="16">16</option>
                    <option value="15">15</option>
                    <option value="14">14</option>
                    <option value="13">13</option>
                    <option value="12">12</option>
                    <option value="11">11</option>
                    <option value="10">10</option>
                <option value="9">9</option>
                <option value="8">8</option>
                <option value="7">7</option>
                <option value="6">6</option>
                <option value="5">5</option>
                    <option value="4">4</option>
                    <option value="3">3</option>
            </select></td>


            <td style="width: 20%">Max. Iterations:<br><select name="maxiterations" id="maxiterations">
                <option value="10">10</option>
                <option value="20">20</option>
                <option value="30">30</option>
                <option value="40">40</option>
                <option value="50">50</option>
            </select></td>

            <td style="width: 40%">Dictionary:<br><select name="dictionary" id="dictionary">
                <option value="en_collins_scrabble_2015">EN - 2015 Collins Scrabble Dictionary (276k words)</option>
                <option value="en_english20k">EN - Most Common Words (20k words)</option>
                <option value="en_english479k">EN - English Dictionary (484k words). Source: Internet</option>
                <option value="en_aspell">EN - 2018 English Dictionary (119,772 words). Source: Aspell</option>
                <option value="cs_aspell">CS - Czech Dictionary (4,669,280 words). Source: Aspell</option>
                <option value="da_aspell">DA - Danish Dictionary (360,723 words). Source: Aspell</option>
                <option value="de_aspell">DE - German Dictionary (312,001 words). Source: Aspell</option>
                <option value="es_aspell">ES - Spanish Dictionary 2018 (1,250,780 words). Source: Aspell</option>
                <option value="fr_aspell">FR - French Dictionary 2018 (629,568 words). Source: Aspell</option>
                <option value="nl_aspell">NL - Dutch Dictionary 2018 (222,907 words). Source: Aspell</option>
                <option value="pl_aspell">PL - Polish Dictionary 2018 (3,401,773 words). Source: Aspell</option>
                <option value="pt_aspell">PT - Portuguese Dictionary 2018 (460,836 words). Source: Aspell</option>
                <option value="sk_aspell">SK - Slovak Dictionary 2018 (1,694,148 words). Source: Aspell</option>
                <option value="sk_pravidla_slovenskeho_pravopisu_2013">SK - Pravidlá Slovenského Pravopisu 2013 (97,292 slov)</option>
                <option value="sk_slovnik_cudzich_slov_2005">SK - Slovník Cudzích Slov 2005 (36,933 slov)</option>
                <option value="sk_slovnik_slovenskeho_jazyka_1959_1968">SK - Slovník Slovenského Jazyka 1968 (75,681 slov)</option>
                <option value="sk_synonymicky_slovnik_slovenciny_2004">SK - Synonymický Slovník Slovenčiny 2004 (42,285 slov)</option>
            </select></td>


        </tr>
    </table>



    <br>

    <input id="input" autocomplete="off" autocorrect="off" spellcheck="false" onkeypress="return (event.charCode > 64 && event.charCode < 91) || (event.charCode > 96 && event.charCode < 123)" onkeydown="upperCase(this)" type="text" value="" placeholder="Enter Characters" onclick="removePlaceholder()">
<br>
    <select name="randLen" id="randLen">
        <option value="10">10</option>
        <option value="11">11</option>
        <option value="12">12</option>
        <option value="13">13</option>
        <option value="14">14</option>
        <option value="15">15</option>
        <option value="16">16</option>
        <option value="17">17</option>
        <option value="18">18</option>
        <option value="19">19</option>
        <option value="20">20</option>
        <option value="21">21</option>
        <option value="22">22</option>
        <option value="23">23</option>
        <option value="24">24</option>
        <option value="25" selected>25</option>
        <option value="30">30</option>
        <option value="35">35</option>
        <option value="40">40</option>
    </select>
    <input id="random" type="button" class="buttonrandom" value="Generate Random" onclick="makeRandomString();">

    <br>
    <input id="button" type="button" class="button" value="Solve" onclick="webWorkerThread();">




    <div id="message"></div>

    <div id="grid"></div>

    <div id="foundwords"></div>


</div>


<!-- Default Statcounter code for Bananagramsolve.com
http://www.bananagramsolve.com -->
<script type="text/javascript">
    var sc_project=11918478;
    var sc_invisible=1;
    var sc_security="d82429e4";
</script>
<script type="text/javascript"
        src="https://www.statcounter.com/counter/counter.js"
        async></script>
<noscript><div class="statcounter"><a title="web stats"
                                      href="http://statcounter.com/" target="_blank"><img
        class="statcounter"
        src="//c.statcounter.com/11918478/0/d82429e4/1/" alt="web
stats"></a></div></noscript>
<!-- End of Statcounter Code -->


<br><br><br>
<hr style="text-align:right;width:310px;position: fixed;padding:10px;bottom: 0;right: 0;">
<small style="position: fixed;bottom: 0;right: 0;padding:10px;color:grey">
    ©
    <script>document.write(new Date().getFullYear())</script>
    - Jozef Jarosciak - Open Source <a href="https://github.com/JozefJarosciak/BlockPuzzleSolver/blob/master/LICENSE.txt" target="_blank">AGPL-3.0</a> license.
    <br>
</small>

<a href="https://github.com/JozefJarosciak/Bananagrams_Solver"><img style="position: absolute; top: 0; right: 0; border: 0;" src="img/forkme_right_green_007200.png" alt="Fork me on GitHub"></a>

</body>
</html>

 

And so is the CSS stylesheet (styles.css):

#input {
    text-align:center;
    width: 90%;
    max-width: 800px;
    font-weight: bold;
    padding: 10px 20px;
    text-align: center;
    text-decoration: none;
    display: inline-block;
    font-size:20px;
    background: #fefbe8;
    color: #0050a0;
}

td#tdinput{
    width: 90%;
    align-content: center;
}

.buttonrandom {
    color: #787878;
    background-color: #c4c4c4;
    padding: 2px 2px;
    margin: 2px;
    text-align: center;
    text-decoration: none;
    display: inline-block;
    font-size: 16px;
    border: none;
}

#randLen {
    width: 45px;
    background-color: #f8f8f8;
    padding: 2px 2px;
    margin: 0px;
}

/* unvisited link */
a:link {
    color: #1b5fff;
}

/* visited link */
a:visited {
    color: #1b5fff;
}

/* mouse over link */
a:hover {
    color: #0020ff;
}

/* selected link */
a:active {
    color: #1b5fff;
}




img {
    max-width: 100%;
}

hr{
    max-width: 750px;
    border-top: 1px dashed #cecece;
}

#foundwords {
text-align: left;
    padding: 20px;
}

.button {
    background-color: #008CBA;
    border: none;
    color: white;
    padding: 8px 20px;
    margin: 10px;
    text-align: center;
    text-decoration: none;
    display: inline-block;
    font-size: 16px;
    width: 190px;
}



td {
    height: 0px;
    text-align: center;
}

td#leftcell {
    text-align: left;
    border: 1px solid #f6f6f8;
    border-bottom: 2px dotted #787878;
    text-align: left;
    vertical-align: top;
}

td#decorate {
    width: 20px;
    height: 14px;
    text-align: center;
    border: 1px solid #008000;
    background: #fefbe8;
    margin: 5px;
    font-size: 20px;
}

#page-wrap {
    width: 80%;
    margin: 0 auto;
    justify-content: center
}

html {
    text-align: center;
}

#grid {
    text-align: center;
    width:100%;
    height:100%;
}

table {
    margin: 0 auto; /* or margin: 0 auto 0 auto */
}

 

Once everything was done, I’ve built a feature to scrap the word descriptions from online dictionaries. For example, to get a description from Merriam-Webster, I use a simple PHP script: get-description-en.php

<?php
$word = htmlspecialchars(mb_strtolower(($_GET["q"])));
// ---------------------------------
//error_reporting(E_ALL); ini_set('display_errors', 1);
mb_internal_encoding("UTF-8");

// get MYSQL credentials ($username,$password) from credentials.php (you must create the file
include("credentials.php");

// Connect to MySQL DB
$mysqli = new mysqli("localhost", $username, $password, "dictionaries");
$mysqli->query("SET NAMES 'utf8'");
$mysqli->query("SET CHARACTER SET utf8");
$mysqli->query("SET SESSION collation_connection = 'utf8_unicode_ci'");
$sql = "SELECT * FROM en_english479k WHERE word='".$word."'"; //echo $sql."<BR>";

// Search Database
$result = mysqli_query($mysqli, $sql);
$row = mysqli_fetch_array($result);
$foundWord = $row['word'];
$foundDescription = $row['description'];
if (substr($foundDescription, 0, strlen(": ")) == ": ") {
    $foundDescription = substr($foundDescription, strlen(": "));
}

if ($foundDescription===null) {
    $doc = new DOMDocument;
    $doc->preserveWhiteSpace = false;
    $doc->strictErrorChecking = false;
    $doc->recover = true;
    $doc->loadHTMLFile("https://www.merriam-webster.com/dictionary/".$word);
    $xpath = new DOMXPath($doc);
    $query = "//div[@class='vg']";
    $entries = $xpath->query($query);
    $foundDescription = $entries->item(0)->textContent;
    if (substr($foundDescription, 0, strlen(": ")) == ": ") {
        $foundDescription = substr($foundDescription, strlen(": "));
    }

    $foundDescription = preg_replace("/[\r\n]*/","",$foundDescription);
    $foundDescription = preg_replace('/\s+/', ' ',$foundDescription);

    if (strlen($foundDescription)>0) {
        // Connect to MySQL DB
        $servername = "localhost";
        $dbname = "dictionaries";
        $conn = new mysqli($servername, $username, $password, $dbname);
        if ($conn->connect_error) {            die("Connection failed: " . $conn->connect_error);        }


        $stmt = $conn->prepare("UPDATE en_english479k SET description=? WHERE word=?");
        $stmt->bind_param("ss", trim($foundDescription), $word);
        $stmt->execute();
        $stmt->close();

        $conn->close();


        if (substr($foundDescription, 0, strlen(": ")) == ": ") {
            $foundDescription = substr($foundDescription, strlen(": "));
        }
        echo trim($foundDescription);
     }



} else {
    if (substr($foundDescription, 0, strlen(": ")) == ": ") {
        $foundDescription = substr($foundDescription, strlen(": "));
    }
    echo $foundDescription;
}

And I also added multilanguage support, supporting following dictionaries in English, Czech, Danish, German, Spanish, French, Dutch, Polish, Portuguese and Slovak:

Then, registered a $3 .com domain BananagramSolve.com and this is what the result looks like for one of the queries in English:

 

 

 

If you feel like improving the code a bit, give it a try: https://github.com/JozefJarosciak/Bananagrams_Solver

Enjoy!