Scrabble and .NET

I love games; some of you may know that about me. I love reading and try to dabble with writing every now and then. A game that combines both of these passions is Scrabble. Scrabble is a word game. You get a certain number of tiles, each with a letter on it. Each of these letters counts a particular point value. Difficult letters are worth more than others. In the game, you continuously add letters onto existing letters to form a word to score points. It gets pretty difficult if you do not have a pocket dictionary by your side, or a huge vocabulary. Even if you have a decent vocabulary, you will struggle some times because the tiles and the letters do not work in your favor.

My aim today is to improve your vocabulary a bit! I will show you how to traverse through dictionary files in search of a certain word. The same principle gets applied with Scrabble games to verify matching words. Who knows, perhaps in a second installment I will delve a bit deeper into creating the game engine. So for now, let’s call this Part 1.

There is a ton of work, so let’s get started right away!

Our Project

Before you begin with creating the project, you first need a dictionary. Luckily, the Internet is huge and you can just about find anything on it. Navigate to this dictionary and download the files. Remember the location of the files; you will need the location a bit later, because you will read through all these files to find your matching word and all its variants.

Create a new Windows Forms application in C# or VB.NET. Once the project has been created, design it to resemble Figure 1.

Design
Figure 1: Design

Create a new class and name it something descriptive, such as clsRecursion. The recursion class will be used to iterate through the dictionary files one by one. If you do not know what Recursion is, here is a very helpful link.

To be honest, I did not create this class, but it is probably the best recursion class that can be found out there. Add the class now.

C#

using System;
using System.Collections.Generic;

namespace Scrabble_C
{
   /*
    * The "Recursion" class below, is written in C# by
    * Gary Stafford
   * who references
   * Algorithm Source: A. Bogomolny, Counting And Listing
   * All Permutations from Interactive Mathematics Miscellany
   *    and Puzzles
   * http://www.cut-the-knot.org/do_you_know/AllPerm.shtml,
   * Accessed 11 June 2009
   * who references

   * 1. A. Levitin, Introduction to The Design & Analysis of
       * Algorithms,
       * Addison Wesley, 2003
   * 2. E. W. Dijkstra, A Discipline of Programming,
       * Prentice-Hall,
   * 3. R. Sedgewick, Algorithms in C, Addison-Wesley,
       * 3rd edition (August 31, 2001)
   */
   public class clsRecursion
   {

      private int lvlElement = -1;
      private int intElements;
      private int[] intPermutationVal = new int[0];

      private string strList = "";
      private LinkedList<string> lstList = new
         LinkedList<string>();

      private char[] chrInput;
      public char[] InputSet
      {

         get
         {

            return chrInput;
         }

         set
         {

            chrInput = value;

         }

      }

      private int intCountPermutation = 0;
      public int PermutationCount
      {

         get

         {

            return intCountPermutation;
         }

         set
         {

            intCountPermutation = value;
         }

      }

      public char[] CreateCharArray(string strInput)
      {

         char[] charString = strInput.ToCharArray();


         Array.Resize(ref intPermutationVal, charString.Length);
         intElements = charString.Length;

         return charString;

      }

      public void CalcPermutation(int intIndex)
      {

         lvlElement++;

         intPermutationVal.SetValue(lvlElement, intIndex);

         if (lvlElement == intElements)
         {

            OutputPermutation(intPermutationVal);

         }

         else
         {

            for (int i = 0; i < intElements; i++)
            {

               if (intPermutationVal[i] == 0)
               {

                  CalcPermutation(i);

               }

            }

         }

         lvlElement--;

         intPermutationVal.SetValue(0, intIndex);

      }

      private void OutputPermutation(int[] intVal)
      {

         string strWord = "";

         foreach (int i in intVal)
         {

            strList += (chrInput.GetValue(i - 1));
            strWord += (chrInput.GetValue(i - 1));

         }

         strList += "\r\n";

         if (lstList.Contains(strWord))
         {

         }

         else
         {

            lstList.AddLast(strWord);

         }

         PermutationCount++;

      }

      public LinkedList<string>GetList()
      {

         return lstList;

      }

   }

}

VB.NET

Imports System
Imports System.Collections.Generic

Public Class clsRecursion

   Private lvlElement As Integer = -1

   Private intElements As Integer

   Private intPermutationVal As Integer() = New Integer(-1) {}

   Private strList As String = ""

   Private lstList As LinkedList(Of String) = New _
      LinkedList(Of String)()

   Private chrInput As Char()

   Public Property InputSet As Char()

      Get

         Return chrInput

      End Get

      Set(ByVal value As Char())

         chrInput = value

      End Set

   End Property

   Private intCountPermutation As Integer = 0

   Public Property PermutationCount As Integer

      Get

         Return intCountPermutation

      End Get

      Set(ByVal value As Integer)

         intCountPermutation = value

      End Set

   End Property

   Public Function CreateCharArray(ByVal strInput As String) _
         As Char()

      Dim charString As Char() = strInput.ToCharArray()
      Array.Resize(intPermutationVal, charString.Length)

      intElements = charString.Length

      Return charString

   End Function

   Public Sub CalcPermutation(ByVal intIndex As Integer)

      lvlElement += 1

      intPermutationVal.SetValue(lvlElement, intIndex)

      If lvlElement = intElements Then

         OutputPermutation(intPermutationVal)

      Else

         For i As Integer = 0 To intElements - 1

            If intPermutationVal(i) = 0 Then

               CalcPermutation(i)

            End If

         Next

      End If

      lvlElement -= 1
      intPermutationVal.SetValue(0, intIndex)

   End Sub

   Private Sub OutputPermutation(ByVal intVal As Integer())

      Dim strWord As String = ""

      For Each i As Integer In intVal

         strList += (chrInput.GetValue(i - 1))
         strWord += (chrInput.GetValue(i - 1))

      Next

      strList += vbCrLf

      If lstList.Contains(strWord) Then

      Else

         lstList.AddLast(strWord)

      End If

      PermutationCount += 1

   End Sub

   Public Function GetList() As LinkedList(Of String)

      Return lstList

   End Function


End Class

This class gets a list of strings and loops through it continuously until all the strings have been traversed. On the form, add the necessary namespaces.

C#

using System.IO;
using System.Text.RegularExpressions;

VB.NET

Imports System.IO
Imports System.Text.RegularExpressions

The System.IO namespace allows you to work with files and folders. System.Text.RegularExpressions enables you to make use of Regular Expressions in your text. Regular Expressions are a great way to filter input strings. Here is more information on Regular Expressions.

Add the following member variables to your form class.

C#

      private LinkedList<string> lstDictionary = new
         LinkedList<string>();

      public static LinkedList<string> lstCombinations = new
         LinkedList<string>();

VB.NET

   Private lstDictionary As LinkedList(Of String) = New _
      LinkedList(Of String)()

   Public Shared lstCombinations As LinkedList(Of String) = New _
      LinkedList(Of String)()

lstDictionary will contain all the dictionary items that match your input word. lstCombinations will contain all possible combinations of that word. Each of these will be stored inside a LinkedList generic list object.

Add the following code behind the button.

C#

      private void btnGetWords_Click(object sender, EventArgs e)
      {
         lstCombinations.Clear();
         txtPossibles.Clear();

         char[] Letter = {
            'A','B','C','D','E','F','G','H','I','J','K','L','M',
            'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'
         };

         if (lstDictionary.Count == 0)
         {

            for (int i = 0; i < Letter.Length; i++)
            {

               StreamReader srWords;
               srWords = File.OpenText("C:\\scrabble\\dictionary\\
                  gcide_" + Letter[i] + ".xml");

               string strFullList = "";

               strFullList = srWords.ReadToEnd();
               srWords.Close();

               Regex rgPattern = new Regex(@"<p> (.*?) </p>",
                  RegexOptions.Singleline);

               MatchCollection mcMatch =
                  rgPattern.Matches(strFullList);

               MatchCollection mcWords = Regex.Matches(strFullList,
                  @"<hw> (.*?) </hw>",
                  RegexOptions.Multiline);

               for (int j = 0; j < mcWords.Count; j++)
               {

                  lstDictionary.AddLast(Regex.Replace(mcWords[j]
                     .ToString().ToLower(), "<hw>|</hw>|\\
                     .|\\]|\\[|,|\\?|:|\\(|\\)|;|-|!|\\*|\"|`", "")
                     .ToString().Trim().ToLower());

               }

            }

         }

         string strInput = txtInput.Text;

         GetSubPermutations(strInput);

         LinkedList<string> strCombo = new LinkedList<string>();
         clsRecursion rcRecursion = new clsRecursion();

         foreach (string strComb in lstCombinations)
         {

            rcRecursion.InputSet = rcRecursion.CreateCharArray
               (strComb);
            rcRecursion.CalcPermutation(0);

            strCombo = rcRecursion.GetList();

         }

         lblDictionary.Text = "Dictionary: " + lstDictionary.Count;
         lblCombination.Text = "Combination: " + strCombo.Count;

         foreach (var word in strCombo)

         {

            txtPossibles.Text += word.ToUpper();

            txtPossibles.Text += Environment.NewLine;
            txtPossibles.Text += Environment.NewLine;

         }

      }

VB.NET

   Private Sub btnGetWords_Click(ByVal sender As Object, _
         ByVal e As EventArgs)

      lstCombinations.Clear()
      txtPossibles.Clear()

      Dim Letter As Char() = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, _
         "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, _
         "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, _
         "Y"c, "Z"c}

      If lstDictionary.Count = 0 Then

         For i As Integer = 0 To Letter.Length - 1

            Dim srWords As StreamReader

            srWords = File.OpenText("C:\scrabble\dictionary\ _
               gcide_" & Letter(i) & ".xml")

            Dim strFullList As String = ""
            strFullList = srWords.ReadToEnd()
            srWords.Close()

            Dim rgPattern As Regex = New Regex("<p> (.*?) _
               </p>", RegexOptions.Singleline)

            Dim mcMatch As MatchCollection = _
               rgPattern.Matches(strFullList)

            Dim mcWords As MatchCollection = _
               Regex.Matches(strFullList, "<hw> (.*?) _
               </hw>", RegexOptions.Multiline)

            For j As Integer = 0 To mcWords.Count - 1

               lstDictionary.AddLast(Regex.Replace(mcWords(j) _
                  .ToString().ToLower(), "<hw>|</hw>|\ _
                  .|\]|\[|,|\?|:|\(|\)|;|-|!|\*|""|`", "") _
                  .ToString().Trim().ToLower())

            Next

         Next

      End If

      Dim strInput As String = txtInput.Text

      GetSubPermutations(strInput)

      Dim strCombo As LinkedList(Of String) = New _
         LinkedList(Of String)()
      Dim rcRecursion As clsRecursion = New clsRecursion()

      For Each strComb As String In lstCombinations

         rcRecursion.InputSet = _
            rcRecursion.CreateCharArray(strComb)
         rcRecursion.CalcPermutation(0)

         strCombo = rcRecursion.GetList()

      Next

      lblDictionary.Text = "Dictionary: " & lstDictionary.Count
      lblCombination.Text = "Combination: " & strCombo.Count

      For Each word In strCombo

         If lstDictionary.Contains("" & word) Then

            txtPossibles.Text += word.ToUpper()

            txtPossibles.Text += Environment.NewLine
            txtPossibles.Text += Environment.NewLine

         End If

      Next

   End Sub

Here, you set up the “Letter array” that contains every letter of the alphabet. You did this because you will need to loop through each of the dictionary files that you downloaded earlier. You then specified the location for your dictionary files. Remember your location, as stated earlier.

Now, these files contain a lot of jargon. They not only contain words, but they also contain their definitions as well as some unnecessary (well, to me at least) comments. You need to sift through these files to get only the words that potentially can match the entered word. In comes Regular Expressions. As you can see: Regular Expressions allow you to set up a filter once, and it gets applied to all the strings that need to be filtered. Lastly, add the getSubPermutations Sub procedure that adds all combinations to the LinkedList object.

C#

      public static void GetSubPermutations(string strPerm)
      {

         if (lstCombinations.Contains(strPerm))
         {

         }

         else
         {

            lstCombinations.AddLast(strPerm);

         }

         if (strPerm.Length > 2)
         {

            for (int i = 0; i < strPerm.Length; i++)
            {

               if (lstCombinations.Contains(strPerm.Remove(i, 1)))
               {

               }

               else
               {

                  lstCombinations.AddLast(strPerm.Remove(i, 1));

               }

               GetSubPermutations(strPerm.Remove(i, 1));

            }

         }

      }

VB.NET

   Public Shared Sub GetSubPermutations(ByVal strPerm As String)

      If lstCombinations.Contains(strPerm) Then

      Else

         lstCombinations.AddLast(strPerm)

      End If

      If strPerm.Length > 2 Then

         For i As Integer = 0 To strPerm.Length - 1

            If lstCombinations.Contains(strPerm.Remove(i, 1)) Then

            Else

               lstCombinations.AddLast(strPerm.Remove(i, 1))

            End If

            GetSubPermutations(strPerm.Remove(i, 1))

         Next

      End If
   End Sub

GitHub C# Source

GitHub VB.NET Source

Conclusion

Now that you have made the word interpretation engine, creating a decent user interface for a game such as Scrabble should not be too complicated. Hopefully, I will post a second part for this game soon. But first, I need a much deserved holiday. See you afterwards.

Hannes DuPreez
Hannes DuPreez
Ockert J. du Preez is a passionate coder and always willing to learn. He has written hundreds of developer articles over the years detailing his programming quests and adventures. He has written the following books: Visual Studio 2019 In-Depth (BpB Publications) JavaScript for Gurus (BpB Publications) He was the Technical Editor for Professional C++, 5th Edition (Wiley) He was a Microsoft Most Valuable Professional for .NET (2008–2017).

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read