Scrabble Word Finder

• Download source - 38.1 KB

Introduction

I recently knew that I had a valid 8 letter word (my 7 letters plus a letter on the board) -- Word With Friends word finder told me I could write the 8 letter word -- but I didn't know what the word was.

I had these letters to work with, including the 's' on the board:

List<char> myLetters = new List<char>() { 't', 'r', 'o', 'i', 'l', 'b', 's', 's' };

Using the More Words site with the search "8 letter words starting with s" I got 3480 words that fit that criteria. But which one matched?

First Pass

Given that I knew the word began and ended with an 's', I did this:

string[] words = File.ReadAllLines("words.txt");
var f1 = words.Where(w => w[0] == 's' && w[7] == 's');

var f2 = (from word in f1
where myLetters.All(c => word.Any(wc => wc == c))
select word).ToList();

f2.ForEach(w => Console.WriteLine(w));

Presto, there's my word: "strobils" -

1. A cone of a gymnosperm or of a seedless vascular plant such as a horsetail or a club moss.
2. Any of various similar structures, such as the female inflorescence of a hop plant, which is composed of small flowers obscured by overlapping green bracts.

But I was pre-filtering the entire word list knowing the beginning and ending letters. If I didn't use that filter:

var f2 = (from word in <font color="#FF0000">words</font>
where myLetters.All(c => word.Any(wc => wc == c))
select word).ToList();

I got this list:

sorbitol
strobila
strobile
strobili
strobils

Notice that there are words with duplicate letters and words that have other letters that I don't have.

Second Pass

So how I do match exactly on the letters that are available? Well, count them and make sure that the count of each letter in a possible word matches the count of letters I have available to me. This gives me a count of my letters:

var occurences = myLetters.Select(c => new { letter = c, count = myLetters.Count(o => o == c) });

Notice that we have two entries for 's'. Let's clean that up:

var occurences = myLetters.Distinct().
  Select(c => new { letter = c, count = myLetters.Count(o => o == c) });

Similarly, we do the same thing for each possible word (the ToList() makes the debugger readable):

var wordLetterCounts = words.Select(word =>
 new
 {
   word = word,
   counts =
     word.GroupBy(c => c).Select((a, b) =>
     new
     {
       letter = a.Key,
       count = word.Count(c => c == a.Key)
     }).ToList()
 });

The first two words in the list of words:

Now we can match counts of letters in the test word with the letters available to me:

var matches = wordLetterCounts.Where(wlc => 
  wlc.counts.All(letterCount => 
    occurences.Single(o => o.letter == letterCount.letter).count == letterCount.count));

var listOfMatches = matches.ToList();

Oops:

The problem here is that my list of occurrences (elephant, I misspelled "occurrences" in the code) of each letter may not contain the letter in the test word.

Third Pass

Null continuation and null coalescing operators to the rescue (fixed the spelling error too):

var matches = wordLetterCounts.Where(wlc => 
  wlc.counts.All(letterCount => 
    (occurrences.SingleOrDefault(o => 
       o.letter == letterCount.letter)?.count ?? 0) == letterCount.count));

Success!

Alternate Implementation

An alternate Linq statement that is "simpler" combines the pieces together without creating the temporary anonymous type wordLetterCounts:

var matches = words.Select(word =>
{
  return new { word = word, matches =
  word.GroupBy(c => c).Select((a, b) => new { letter = a.Key, count = word.Count(c => c == a.Key) })
  .All(q => (occurrences.FirstOrDefault(o => o.letter == q.letter)?.count ?? 0) == q.count) };
}).Where(word => word.matches);

A Simple UI

using System;
using System.Data;
using System.Linq;
using System.Windows.Forms;

namespace WordFinderUI
{
  public partial class Form1 : Form
  {
    public Form1()
    {
      InitializeComponent();
      tbWordList.MaxLength = Int32.MaxValue;
    }

  private void btnFind_Click(object sender, EventArgs e)
  {
    var myLetters = tbMyLetters.Text.ToList();
    var occurrences = myLetters.
       Distinct().
       Select(c => new { letter = c, count = myLetters.Count(o => o == c) });
    var words = tbWordList.Text.Split(new char[] { '\r' }).Select(w=>w.Trim());

    var matches = words.Select(word =>
    {
      return new
      {
        word = word,
        matches =
        word.GroupBy(c => c).
          Select((a, b) => new { letter = a.Key, count = word.Count(c => c == a.Key) })
        .All(q => (occurrences.FirstOrDefault(o => o.letter == q.letter)?.count ?? 0) == q.count)
      };
    }).Where(word => word.matches);

    tbMatches.Text = matches.Count() == 0 ? 
      "No Matches!" : String.Join("\r\n", matches.Select(m => m.word));  }
  }
}

The only thing of interest to note here is:

tbWordList.MaxLength = Int32.MaxValue;

The default length of a TextBox is 32767 characters, and some of these word lists are a lot longer. This gives you 2GB of characters!

Conclusion

Now I can "cheat" when I'm trying to find 7 letter words!