Objectives

By the end of this workshop you will:

• Create a word game called Word Ladder in Android Studio.

Aim

This workshop's app will be a game called Word Ladder. This game was invented by Lewis Carroll (the author of Alice in Wonderland) and appears in some newspapers along with the crossword puzzles.

It looks like this:

The game gives the players two starting words of the same length (gain and fire in this example) and a number of blank spaces in between. The objective of the game is to fill each blank space with a word that differs from the word above and the word below it by a single letter. For example, one solution (there may be several) to the above puzzle is:

gain
gait
wait
wart
ware
wire
fire

Timing

In total, this workshop activity should take you around 3-4 hours to complete.

Tour of code

Starter Code

The starter code is made up of two Java classes:

• WordSelectionActivity: This is the activity that is shown when the application is launched:
• onCreate: boilerplate plus code to load the word list
• onStart: handler for the "Start" button. You will have to add code to launch another activity here.
• onCreateOptionsMenu and onOptionsItemSelected: boilerplate
• PathDictionary: This is a custom class that stores the list of words and provides functionality to find paths between words:
• PathDictionary: Constructor that reads the words list. You'll need to store the words in some convenient data structures.
• isWord: Implementation is provided.
• neighbours: Private helper to find all the words that differ from the given word by one letter.
• findPath: Returns an array of strings that form a path between two strings. For example, given start = "cold" and end = "warm", it will return ["cold", "cord", "card", "ward", "warm"].

Milestone 1: PathDictionary

The given implementation of WordSelectionActivity is almost complete so we'll start by implementing PathDictionary. The given code stores each word in a HashSet to allow fast checking of word validity but we will need to also store the words in another data structure. Conceptually, we want to store the words in a graph where each node is a word and each edge connects two words that differ by only one letter (we'll call such words 'neighbours').

One approach to this would be to create a HashMap where the keys are the words and the values are all of the keys neighbors. The down side of this is that populating this HashMap is time consuming and memory-intensive as you end up storing multiple copies of each string.

Info

You are free to implement the above approach but there is a myriad of ways to represent a graph of strings. This may be a good time to do some thinking (and possibly doing some web research) about other potential strategies that may be more efficient for this problem.

Once you have chosen how to store the word graph, populate it in PathDictionary's constructor and implement neighbours to return all the neighbours of a given word.

Milestone 2: findPath

Once neighbours is working, you can implement findPath. Conceptually, findPath checks all of start's neighbours to see if any of them is the end. If not, it checks all of its neighbours' neighbours and so forth until it finds a path (or gives up). This is just breadth-first search (BFS) over a graph. So you'll need to:

• Create a queue to store the paths explored so far. You can use any of the Java classes that implement the Queue interface. ArrayDeque is a good choice for this as it is faster than a LinkedList. The path can be represented as an ArrayList of the words in the path.
• Create an ArrayList and add start to it. Add that array list to the queue.
• While the queue is not empty, get the path from the head of the queue and consider all of its neighbours. If the neighbour is the desired end, return the corresponding path. Otherwise, create new paths representing the current path plus each of the neighbours (avoiding loops) and add them to the queue.
• In addition, add some logic to stop looking once the paths grow past a certain length. You can start off with a depth or 4-5 and experiment with deeper searches as you optimize your solution.

Info

Optionally, keep track of words that you have already reached and avoid enqueueing paths that are longer than an already considered path.

Milestone 3: SolverActivity

Once you've verified that findPath is working, you can implement a second activity that will be used by the user to solve the puzzle (as shown in the screenshot above):

• Go back to WordSelectionActivity.onStart and implement the code to create an intent to launch the new Activity (call it SolverActivity). Don't forget to pass the words array to the activity using the intent's extra.
• Implement SolverActivity by implementing:
• onCreate:
  • Create the basic UI (you can use the provided activity_display_solver.xml to jump-start that process)
  • Get the word list from the intent that created this activity
  • Set the start text and end text in the TextView fields
  • Programmatically create the appropriate number of EditText fields and insert them in between the start and end
• onSolve: The handler for the "Solve" button which populates the textFields with the solution to the puzzle

Finally, experiment with increasing MAX_WORD_LENGTH and the depth of your search to see what your code and device will support (Android will start warning that your thread is taking too long when you near the limit).

Extensions

• You can enable much deeper searches in your word graph (and faster searches when the path is short) by doing a double BFS. This means doing a BFS from both the start and end point simultaneously until you find a node that can be reached from either side.
• The default UI for the solver is not as user-friendly as it could be. Improve it by checking the words that the user enters and coloring them green if they are both valid dictionary words and neighbors of the words above and below them (if specified). Otherwise, color them red.
• Add support for multiple, equal-length solutions. When the user hits "Solve" show the solution that is most similar to the partial answer that the user has provided.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.