How to Take the Fun out of a Word Game

Some time back I created a word game to play with the kids on long car rides. The objective of the game is to agree on two words and then see who can first come up with a series of changes starting from the first word that get you to the second.  The changes allowed are the removal, addition or replacement of a single letter.  Additionally you are allowed to rearrange the letters with each of these changes.  Each change must result in another real word along the way.

For example: WATER to FIRE

1. Start with WATER
2. Replace A with I and rearrange to WRITE
3. Remove T and rearrange to WIRE
4. Replace W with F and arrive at FIRE

I’ve at times thought about writing software to solve this problem for any two arbitrary words. After considering the problem as really a graph theory problem it occurred to me that I could leverage a non relational graph database to do this. These sorts of NO SQL databases are something I understood the principle of but never actually used in practice.

For those that aren’t familiar, a normal (relational) databases consist of tables and each table consists of rows and columns. A table may hold a specific data entity like a Customer table where every row in that table represents a different Customer and information describing them would be in columns like Name, Email, etc.  There may be a Customer ID on that table that uniquely identifies that Customer and that ID can exist on other tables like an Orders table where each order placed by that customer is defined and it in turn references a Item table that contains all the Items in that Order.  This allows for data to be normalized across a relational data structure.

A Graph Database functions quite differently and while not a new concept it has really only started to grow in prominence in the age of big data as we try to define and identify relationship across large swathes of connected data.  The structure of a Graph database is based on the graph theory concept of Nodes and Relationships.   A classic use case for a Graph database is to solve the Six Degrees of Kevin Bacon problem by defining a database of Person and Movie nodes and connecting them with Relationships that define that Person’s involvement with that movie:

This sort of database is optimal for identifying paths between nodes:

So in order to sap all the fun out of this word game, I created a piece of software that consumed a dictionary and created a Graph Database containing a node for every word and connecting them with relationships to every other word they can be transformed into under the rules of the game!  The graph database I chose by the way was NEO4J which worked well and their Cypher Text query language I thought was pretty intuitive to learn.

This database consists of 276,643 words and 4,228,645 relationships!

And now, I can enter any two words and find the shortest paths between them instantly!  Such as Encyclopedia to Balloon!

• Encyclopedia
  • Encyclopedias
  • Encyclopaedist
  • Conceptualised
  • Conceptualiser
  • Inoperculates
  • Reinoculates
  • Secretional
  • Tolerance
  • Tolerances
  • Realtones
  • Stoneable
  • Stonable
  • Bonsella
  • Ballones
• Balloon

Here is Michael to Laboratories where you can see the Cypher Text and the graphical output that the NEO4J browser provides:

I can also grab a single word and explode out all the words it can connect to, but this can seriously degrade my system if it is a word with more than a dozen or so nodes connected to it:

I have another word game I invented that I might tackle ruining another day, but on to a different project already so it will have to wait 🙂