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

Chores

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?

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?

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!