Project 4: Solvle

Okay, so I'm pretty proud of myself for this one. Using the methods from my previous project, I added the ability to, given a particular arrangement of letters from a game of Boggle, find all the words possible according to the rules of the game.

This is accomplished by the same basic method that a human would use while playing the same game: starting with a letter, move on to the adjacent or diagonal tiles to find any English words. I used the ENABLE word list which is a free text-based Scrabble dictionary in exactly the format I needed.

The first working version of the search took a good 90 seconds on my computer, which seemed way too long for practical use. It was searching literally EVERYTHING, though, even after it would be impossible to find additional words. In other words, if searching on a path yielded "ASDF", which isn't a substring of anything, it would keep on searching all possible subpaths which would all yield nothing. One line of code later, and the search results are visible by the time the mouse button has been lifted up.

It works great, as verified by a few games of Noggin (I'm not a habitual cheater, I just wanted to test it out). The only words I didn't get were verified as not being in my dictionary file. Aside from those, Solvle found every single word on the list in a fraction of a second. Fun.

One thing I did differently this time is I tried to fully document the code as I was doing it. It's a good habit to encourage, so I'll make myself do it even though for most of this stuff I'll be the only person to see it. Still, the code could certainly use some tidying up, and some optimizations here and there. I'll take a look at it later.

With regards to what's coming next, I've been talking with somebody about moving on to Scrabble. That would be WAY more complicated, however, and I might want to do something a little lighter for the moment. My wired Xbox controller should be here soon, so I'll get to work a little more with XNA. I'm looking forward to that.

Source:
Solvl.cs
Solvl.Designer.cs
Solvl.resx

Project Update: Dictofunk

I've updated Dictofunk to add searching to the tree. It's fast enough that it updates in the time between keystrokes while typing a word. I'll post screen shots, details, and the updated source code when I get home.

Second update:
I've gone ahead and made the Boggle Solver program in the past couple of days based on the tree stuff done already. I'll pretty it up a big (both visually and in code) and post it later today.

Project 3: Dictofunk

My newest project had the objective of loading a word list from a text file and converting the words into a tree.

In other words:

act
arc
art

would become

a->c->t
.->r->c
....->t

This is one of those sort of important, school-y types of things that people should learn, and I wanted to do it for the Boggle Solver program (given a Boggle board and a list of valid words, find all possible words within the rules of Boggle) I had talked with somebody about a couple of months ago.

The basic process involved is this:
1. Read a word from a file.
2. Starting out with an empty tree, search the top level of the tree for the first letter in the word.
3a. If you find it, make that spot the top of the new tree.
3b. If you don't, add the letter to the tree, make that letter the top of the new tree.
4. Chop off the first letter of the word and start over at 2 with your new subtree.

Finally, when the word is done, it sticks a "." at the end so it knows it's a complete word (so that you know, for instance, while "act" and "actual" are words, "actu" and "actua" aren't--they won't have a "." in their subtrees).

Here's the same algorithm in C# form:

public void insertWord(TreeNode thisNode, Char[] chars)
{
bool found = false;
String charString = new String(chars);

if (charString.Length > 0)
{
charString = charString.Substring(1);

foreach (TreeNode branch in thisNode.Nodes)
{
if (branch.Text == chars[0].ToString())
{
found = true;
insertWord(branch, charString.ToCharArray());
}
}
if (!found)
{
insertWord(thisNode.Nodes.Add(chars[0].ToString()), charString.ToCharArray());
}
}
}


And that's pretty much that. The actual algorithm is fast (as seen in the screen shot, with the test dictionary of over 70,000 words it was going through about 13,000 words per second). Loading the tree into the Windows Form, however, takes a good 60-90 seconds. That's not a major concern, however, since the graphical display (yet another great thing that C# does that makes life so easy) is essentially pointless except for visually verifying that the algorithm works. I was kind of shocked that this was even included as a basic display type. Oh, the future.

Oh, also, C# in general was a huge help in doing this in that it I didn't have to worry about constructing a tree class of my own. I was able to spend my time actually figuring out the algorithm I needed, which, while I've certainly read about tree insertions before, I did last night and this morning on my own. Once again, this is totally freshman programming class stuff, but it feels good to know I did it more or less on my own.

Source
Dictofunk.cs