Introducing Boggle

Earlier this week, I had a technical interview and was given an interesting question to solve.

My technical question would be based off the board game Boggle and was as follows. Suppose we have a 4x4 Boggle board (for detailed rules on Boggle, check out this helpful WikiHow article). A user playing Boggle wants to know whether a particular word is on the board. What we need to do is to write an algorithm to determine whether a word is on the board. If the given word is on the board, “true” will be returned, and if the word is not on the board, “false” will be returned.

During my interview, I figured out all the logic that would need to be implemented for the solution, and talked through the problem with my interviewer, and began writing code. However, due to time constraints I wasn’t able to finish it… but this problem was so interesting that I decided to finish it at home- which I did!

The Sample Board

Please note: this 4x4 quadrant of letters will serve as the example Boggle board being referred to in all our code.

Step 1: Creating the Class & Initialization

First things first, I decided to created a class called FindString, which would house all of my methods and which would later allow me to create objects. The first thing I did was to create an initialize method for use in creating new objects and gave it two arguments to implement upon instantiation; “board” and “string.” I also gave the FindString class an attr_accessor for both board and string, to give us getter and setter methods which could later be accessed in our code.

Step 2: Does the first letter of the word exist?

Before we focus on nodes and whether the word given to us exists, we have to establish something more fundamental, namely “does the first letter in the word given to us exist?” In order to determine this, I created a method called letter_exists. I gave this method two arguments, board and letter for use in our method. I began by iterating through the board by using the each_with_index method, and passed it row and index in the block. Then I created a column variable and called index on the row to establish where the column was. Then I set out to find the “x” and “y” coordinates for the particular letter on the board, and if letter existed in a column I shoveled it into an array called result. If the letter did not exist, “nil” would be returned. Does this code work? Let’s take a look!

Yes it does! The letter “c,” which is on the board, has its coordinates returned in a hash [{:x=>1, :y=>3}], whereas the letter “x” which is not on the board, is returned as “nil.”

Step 3: Does the next letter exist?

After establishing that the initial letter exists, we need to determine whether the subsequent letter in the string also exists. In order to figure this out, we’ll create a method called connected_nodes?. This method will take two arguments; the first_letters and the subsequent_letters. We see our methods building off each other as we’ll be calling our previously created letter_exists method, pass in both arguments, and assign them to the variables initial_letters and subsequent_letters. Then, we want to see if two of these nodes (ie “letters”) are connected. In order to do so, we create a conditional to weed out faulty letters: if either initial_letters or subsequent_letters returns nil, we immediately know a letter doesn’t exist and “false” will be returned.

However, if “false” is not returned, we’ll proceed in our code and iterate over each letter, first the initial_letter and then the subsequent_letter. We’ve established that these two letters exist on the board, but are they connected? If “true” is returned we know they’re connected, otherwise we’re returned “false.”

Does our method work? Let’s go to our terminal again to test it out.

Yep! We see “true” is returned for letters “c” and “g” because they exist and are connected on the board, whereas “c” and “s” return “false” because even though they both exist on the board, they’re not connected.

The connected_node? method

After establishing that the previous nodes exist, this method checks for a particular order, based on the node’s coordinates. To put it simply, if there are duplicates of letters on our board, how do we know which specific letter we’re referring to? We do this by utilizing the “x” and “y” coordinates to determine where the letter is and the nodes surrounding it. If the nodes are in the expected position we return “true,” and if not, “false.”

Adding a Helper Method

We’ll also create a helper method called letter_exists? to make our code a little less cluttered, and for use in our upcoming word_exists method.

Step 4: Does the given word exist?

Everything we’ve done up to this point was solely for the creation of this method, word_exists. This method is so important because it answers what we set out to do in the beginning; determine whether the given word exists.

The first thing we’ll do here is call string.length and store it in a variable we’ll call word_length. Then we call another method on the string, string.split(“”) which will return us an array of each individual letter of the given word, and store it in the variable word_array. Now that we have this word_array array, we can iterate through it and call the each_with_index method on it, and we’ll pass in letter and index as the block’s arguments. Then we’ll call our helper method letter_exists? to again see if the letter exists. If the letter exists, we can then invoke our previously created connected_nodes? method to see if the letters in the word_array are connected to one another. If the letters are fully connected, it’s a valid word and we’re returned “true.” Otherwise, “false” will be returned.

Now let’s put our code to use!

Sample Board

Above is the sample board we’ve been working with. Below are four objects I created, and I gave each of them a different word. Then I proceeded to call our key method, word_exists, on each of them. If the word could be found on the Boggle board we’ll be returned “true,” and if it’s not on the board we’ll be returned “false.”

Will our code work? Let’s see..

It worked! We see for word_one(starts) and word_four(big) we’re returned “true” since both of these words are found on the board. For word_two(phish) and word_three(wombat) we’re returned “false” since neither of these words can be found on our board.

We figured out the solution! Let’s celebrate!

Conclusion:

There we have it in all it’s glory, the Boggle solution. In case you’d like to see the code all in one shot, here’s a link to the GitHub repository or feel free to look below at the code in it’s entirety.