Boggler
¶ ↑
Description¶ ↑
Boggler
is a gem that comes with two ways to ‘play’ a simulated version of Boggle.
The first method is to run a game as you would with the tabletop version. Simply run boggler
and a random 4x4 grid will be generated using actual Boggle dice. A 3.5 minute timer is built in. When the time is up, the grid will be pushed off the screen and acceptable answers will be revealed.
The second method is to simply watch Boggler
generate a random grid and immediately show all solutions for it. To do this, simply run boggler_solver
.
Installation¶ ↑
If you have Ruby and Rubygems already installed, then installation is as easy as:
$ gem install boggler
TODO¶ ↑
Features¶ ↑
-
Allow a dictionary file to be specified.
-
Allow the time limit to be specified.
-
Allow grid size to be specified.
-
Allow die selection to be specified.
-
(Perhaps there can be preset dice/size combinations).
-
Find a better dictionary? (This one started from /usr/share/dict/words.)
Chores¶ ↑
-
Cell and Grid classes are not as clean as they should be.
-
The first keys in the dictionary hash can be single letters now.
-
Add specs.
Interesting Bits?¶ ↑
These are some of the bits that I think are interesting.
Dictionary Hash Conversion¶ ↑
This is the only code that currently has specs around it. This was tricky as the hashes need to be merged from the bottom up.
It converts the words ‘foo’, ‘foobar’ and ‘foobz’ into:
{ 'foo' => { '' => true, 'b' => { 'a' => { 'r' => { '' => true, }, }, 'z' => { '' => true, }, }, }, }
Word Construction¶ ↑
Using linked lists that have nodes which know what adjacent nodes are eligible and can iterate over them allow each node to get the next node to try. If all adjacent nodes have been attempted, simply back up the linked list to the last node that still has adjacent nodes to try. If there are no nodes to try given the starting point, move on to the next starting point.
Word construction is halted as soon as there are 3 or more letters in a word that do not have any chance of forming a word.
Thoughts and Things to Ponder¶ ↑
What external resources would help?¶ ↑
The easy answer is a dictionary.
A better answer is a dictionary that is already some kind of hashmap or a dictionary that is in a database that facilitates efficient lookups of partial words.
I reduced the size of my dictionary by removing all words that contained fewer than 3 characters (as they are not valid ‘solutions’ in Boggle).
I believe I removed words with uppercase letters as well. This was due to a number of words that do not seem appropriate in Boggle (such as names of people).
I did leave words with special characters, however. This was done simply to keep the dictionary reasonably large.
What factors impact performance?¶ ↑
-
The size of the dictionary.
-
The size of the grid.
-
NOT short-circuiting the search.
What would you do to improve them?¶ ↑
Convert the dictionary into a hashmap or save it to a database that facilitates efficient lookups of partial words.
Short-circuit word construction as soon as it is known that a valid word can not be formed.
Some form of both of these have been done in this implementation.
What are the key data structures in use here?¶ ↑
-
Arrays for the grid.
-
Hashes for the dictionary.
-
Linked lists for constructing words in the grid.
What makes them more appropriate than alternatives?¶ ↑
An array (or array of arrays) makes the most sense for the grid since there is no reason to do anything other than access adjacent cells.
A hash makes the most sense for the dictionary to improve lookup performance.
Singly linked lists for the grid cells makes navigation to the previous node trivial once all adjacent cells have been ‘visited’.
Can your solution handle words that occur within other words?¶ ↑
Of course.
Credit¶ ↑
I would like to thank HYFN for inspiring me to take on this challenge!