How do I search for a 'blank tile' in a scrabble application? (PHP)

Question

I created this application a couple of months ago: http://www.mondofacto.com/word-tools/scrabble-solver.html

The application lets the user enter the set of letters they are given, and echos back what valid words they can use, along with what score they will get for using those letters.

Basically, what I want to do is extend the application so users can enter a 'blank tile' - that being one which can qualify as any of the 26 letters of the alphabet, and to echo back words that are valid.

Below is a screenshot of the database structure.

http://i37.tinypic.com/28v6a8h.png

You might need to copy that ^ into your browser.

The query run on this data when a user enters, for example, 'aardvark' - is as follows:

SELECT * FROM scrabble WHERE a <= 3 AND b <= 0 AND c <= 0 AND d <= 1 AND e <= 0 AND f <= 0 AND g <= 0 AND h <= 0 AND i <= 0 AND j <= 0 AND k <= 1 AND l <= 0 AND m <= 0 AND n <= 0 AND o <= 0 AND p <= 0 AND q <= 0 AND r <= 2 AND s <= 0 AND t <= 0 AND u <= 0 AND v <= 1 AND w <= 0 AND x <= 0 AND y <= 0 AND z <= 0 AND length <= 8 ORDER BY scrabble DESC

If you want to see the results type a word into the link I posted at the top.

Right,

So does anybody have any idea how to approach doing this? I have started with the following code, which appends each alphabet character onto the end of the string entered by the user, if they put spaces in (spaces being the blank tile).

 if (preg_match('/[\s]/', $string)) { 

     $wild_string = $string;

     foreach (range('a','z') as $i) { 

        $wild_string = $string;
        $wild_string .= $i; 

        }

The $wild_string variable is the one which each letter is appended to on loop. By resetting it to the initial string on every loop it stops the code from adding all 26 letters onto the entered string.

I hope somebody can help, and sorry if I have waffled :)

Andy.

Answer 1

The only method I can think of is to run your query above 26 times, each time adding 1 to a different letter of the alphabet, as well as 1 to the length limit, and then eliminating the duplicates.

Answer 2

My proposal is the following:

Let's say the user input is: ab* where * is the wildcard. Count all the known letters and the wildcards and create an array where element 0 is the number of wildcards and every other element key is a known letter with a value the number of times it is given in the user input:

function GetArrayLetters($userInput) {
  ...
  // produces something like $letters = ( 0 => 1, 'a' => 1, 'b' => 1);
  return $letters;
}

Using that array modify your query by adding the number of wildcards in each letter and at the word's length:

# with only one wildcard, the query will become:
SELECT * FROM scrabble WHERE a <= 2 AND b <= 2 AND c <= 1 ....
    ... AND length <= 3

Now put the results somewhere (an array) and examine each word in turn. Go through each letter and subtract one for each known letter from your $letters array; If the value of a known letter is zero, subtract from element 0 instead (the wildcard). If you get a negative value for the wildcard, then discard the word:

foreach ($result_set AS $word) {
  $letters = GetArrayLetters($userInput);
  for ($i = 0; $i < str_len($word); $i++) {
    $letter = substr($word, $i, 1);
    if ( array_key_exists( $letter, $letters )) {
      if ($letters[$letter]) > 0 {
        $letters[$letter] -= 1;
      } else {
        $letters[0] -= 1; // else subtract from the wildcard
      }
    } else {
      $letters[0] -= 1;
    }

    if ($letters[0] < 0) {
      // if wildcard falls bellow zero, discard the word
    }
  }
}

Answer 3

I would use an asterisk to mark a blank tile and do the following if the input was DOR*:

SELECT * FROM scrabble WHERE d + o + r + $number_of_wildcards >= length

If I understood your database structure correctly, this should return door, dorm, dork, odor, etc.

EDIT: This version should also match shorter words like do, rod and so on.