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.
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
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.