Warning - what follows is a complete waste of time. Do not spend time reading this blog post. Still here? Of course you are. For the past few days I've been addicted to a cool little game called WordBrain. It is a simple idea. You're presented with a grid of letters and must find two words within it by drawing a 'path' from one letter to the next. I like word games, but oddly have never really played any on my mobile devices before. Now I know why - they're incredibly addictive. While playing a few days ago I found myself stuck on one particular puzzle.

device1mod

I've obscured the hints in case you want to try to figure it out yourself before reading on. The obscured area though does provide you with a clue. You get the length of each word. In this case, the first word is five letters long and the second one is four letter.

One thing you run into very early in the game is that there will almost always be valid words that don't match. So looking at the puzzle above you'll see FONT, PINT, PITA, and possibly more words. They are valid, but not what the puzzle wants.

As I stared at this puzzle and got more and more frustrated, I naturally thought - I bet I could cheat at this! I'm absolutely pro-cheating in games. Heck, I learned to program because I wanted to cheat. I figured out hex so I could edit my Bard's Tale characters (and it worked, so hah).

Given that we know the length of a word, and we can figure out a 'path' through the grid, and assuming we can find an English word list, in theory, it should be possible to figure out all the possible words, right?

Heck yes!

I began by finding a good English word list: The English Open Word List. The web site describes the data like so:

The EOWL currently contains about 128,985 words. To make EOWL more usable for computer word games there are no words longer than 10 letters, and no proper nouns or words requiring diacritical symbols, hyphens, or apostrophes.

Sounds perfect, right? The source data consists of one file per letter, so I combined them into one big text file with a word per line:

aa
aah
aal
aalii
aardvark
aardvarks
aardwolf
aardwolves
aargh
aarrghh
aasvogel
aasvogels
and so one for a long, long, time

While some of the words were a bit questionable (like that last one), I figured it would be a good source set. I didn't want to keep all of this data in memory, so I decided I'd used IndexedDB to store the words. Here is how the application starts up:

//globals
var db;
var $wordLength;
var $wordGrid;

$(document).ready(function() {
	if(!("indexedDB" in window)) {
		alert("This will not work for you. Your browser must support IndexedDB.");	
		return;
	}
	
	$wordLength = $("#wordLength");
	$wordGrid = $("#wordGrid");
	
	loadDatabase();
		
});

function loadDatabase() {
	var words;

	var openDB = indexedDB.open("words2", 1);
	openDB.onupgradeneeded = function(e) {
		
		var thisDB = e.target.result;
		
		if(!thisDB.objectStoreNames.contains("words")) {
			var store = thisDB.createObjectStore("words", {keyPath:"word"});
			store.createIndex("length, word", ["length","word"]);
		}

	}
	
	openDB.onerror = function(e) {
		console.log("Error opening/setting up db");
		console.dir(e);	
	}
	
	openDB.onsuccess = function(e) {
		db = e.target.result;
		if(!localStorage["dataloaded"]) {
			console.log("begin loading the db, first, we XHR the data.");
			seedData(startUI);
		} else {
			startUI();
		}
	}
	
	
	var seedData = function(cb) {
		$.get("allwords.txt").then(function(res) {
			words = res.split("\n");
			console.log("Going to load "+words.length + " words.");
		
			console.log("seeding data");
			var transaction = db.transaction(["words"], "readwrite");
			var store = transaction.objectStore("words");
			
			for(var i=0;i<words.length;i++) {
				if(i%250 == 0) console.log("250 done");
				if(words[i].length > 0) store.add({word:words[i].toLowerCase(),length:words[i].length});
			}
		
			transaction.onerror = function(e) {
				console.log("transaction error");
				console.dir(e);
			}
			
			transaction.oncomplete = function(event) {
				console.log("I think I'm done now. Yeah probably");
				localStorage["dataloaded"] = 1;
				cb();	
			}
		});

	}
}

Taking it from the top, and ignoring globals variables and the such, I start off with a call to open up and setup my IndexedDB. This is fairly boiler plate, but I will point out the compound index was based on an initial idea I had for getting the solution. I ended up not using it. The seedData function just does an XHR and loads the word list. The file is 1.1 megs which is large, but not horribly so, and we only need to load it one time. I loop over the words and store each value in my IndexedDB object store. (And again, I'm storing the length because of some plans I had originally that changed while I was working. I'll detail that in a sec.)

So at this point, I've got a database of words. Now I need to ask the user for the length of the word they want to find and have them input the grid. I could have made something fancy, but I just used form fields:

shot1

How in the heck do we solve this? Considering we have a grid, we can iterate over every letter, and find every possible N-lengthed path from there. The game allows a path of any direction and you can't go over a previously used square. My initial thought was this:

  • Start at the upper left and find the paths from there.
  • We'd have: RF, RN, and RO.
  • We can search the IDB for words that are N characters long that begin with RF, etc. If any match, then find paths from RF.

In theory, using the data above, RF and RN would "die" as possibilities but RO would not. I began to work down this path but had difficulty with the asynch nature. I thought about using promises, but... it just didn't click. To be honest, someone smarter could probably figure it out. I decided to take another approach.

  • For each letter, get all the N length paths possible.
  • Given a monster list of N length words, check to IDB to see if it is a valid word.
  • Profit

Here is my ugly, incredibly ugly, solution. Note I probably have multiple unused variables and bad practices here. Also, I just output to console. Oh, and I also assume a 3x3 grid. I'm pretty sure I could make the 'find paths' portion handle any square sized grid, but for now, I'm keeping it (somewhat) simple.

/*
Given position X, and a possibly null history, I return paths you can go
*/
function getPaths(position, size, history) {
	if(!history) history = [];
	var paths = [];
	//console.log('entered getPaths('+position+','+size+',['+history+'])');
	//check all 8 directions

	//up
	if(position > 2 && history.indexOf(position-3) == -1) {
		var newPath = history.slice(0);
		newPath.push(position-3);
		paths.push(newPath);			
	}

	//ne
	if(position>2 && position!=5 && position!=8 && history.indexOf(position-2) == -1) {
		var newPath = history.slice(0);
		newPath.push(position-2);
		paths.push(newPath);
	}
	
	//e
	if(position!=2 && position!=5 && position!=8 && history.indexOf(position+1) == -1) {
		var newPath = history.slice(0);
		newPath.push(position+1);
		paths.push(newPath);
	}
	
	//se
	if(position<6 && position!=2 && position!=5 && history.indexOf(position+4) == -1) {
		var newPath = history.slice(0);
		newPath.push(position+4);
		paths.push(newPath);
	}
	
	//s
	if(position<6 && history.indexOf(position+3) == -1) {
		var newPath = history.slice(0);
		newPath.push(position+3);
		paths.push(newPath);
	}
	 
	//sw
	if(position<6 && position!=3 && position!=0 && history.indexOf(position+2) == -1) {
		var newPath = history.slice(0);
		newPath.push(position+2);
		paths.push(newPath);
	}
	
	//w
	if(position!=0 && position!=3 && position!=6 && history.indexOf(position-1) == -1) {
		var newPath = history.slice(0);
		newPath.push(position-1);
		paths.push(newPath);
	}
	
	//nw
	if(position>2 && position!=3 && position!=6 && history.indexOf(position-4) == -1) {
		var newPath = history.slice(0);
		newPath.push(position-4);
		paths.push(newPath);
	}
	
	//console.log('before if, i have '+paths.length+' paths and my size is '+paths[0].length+' and it is '+paths[0]);
	//console.dir(paths);
	if(paths.length && paths[0].length < size) {
		var newPathResults = [];
		for(var i=0;i<paths.length;i++) {
			var thisPath = paths[i];
			//console.log('inner call with tip '+thisPath[thisPath.length-1]+' size='+size+' thisPath: '+thisPath);
			var newPathsInner = getPaths(thisPath[thisPath.length-1], size, thisPath);
			//console.log('newPathsInner has results len of '+newPathsInner.length);
			for(var x=0;x<newPathsInner.length;x++) {
				newPathResults.push(newPathsInner[x]);
			}
		}
		//console.log("newPathResults");
		//console.dir(newPathResults);
		return newPathResults;
	} else {
		//console.log('returning from getPaths with '+JSON.stringify(paths));
		return paths;
	}
}

function getPhrase(path) {
	var grid = $wordGrid.val();
	var gridArray = grid.split(",");
	var phrase = "";
	for(var i=0;i<path.length;i++) {
		phrase += gridArray[path[i]];	
	}
	return phrase;
}

function doSearch() {
	var wordlen = $wordLength.val();
	if(wordlen === '') return;
	wordlen = Number(wordlen);

	var grid = $wordGrid.val();
	/*
	grid is A,B,C,D,E,F,G,H,I
	
	A B C
	D E F
	G H I
	
	Right now we assume 3x3
	*/

	var gridArray = grid.split(",");

	var paths = [];
		
	for(var i=0;i<9;i++) {
		var letter = gridArray[i];
		//console.log("position "+i+" letter "+letter);
		//first, based on position, get initial paths
		var pathsForPos = getPaths(i,wordlen,[i]);
		//console.log("i found "+pathsForPos.length+" valid paths");
		for(var x=0;x<pathsForPos.length;x++) {
			paths.push(pathsForPos[x]);
		}
	}
	console.log("we have "+paths.length+" total words to check");
	//console.dir(paths);

	//now convert them all to words to check
	var wordsToCheck = [];
	for(var i=0;i<paths.length;i++) {
		wordsToCheck.push(getPhrase(paths[i]).toLowerCase());
	}
	//console.dir(wordsToCheck);

	var wordStore = db.transaction(["words"], "readonly").objectStore("words");  
	var matches = [];
	
	wordsToCheck.forEach(function(word) {
		wordStore.get(word).onsuccess = function(e) {
			if(e.target.result) {
				var word = e.target.result.word;
				if(matches.indexOf(word) == -1) {
					console.log(word);
					matches.push(word);	
				}
			}
			//console.dir(e.target.result);	
		};
	});

}

Got all that? Nice and simple, right? FYI, I could have used a oncomplete for my transaction to tell the user when I'm done, but since I'm simply spitting out to the console, it doesn't matter. Also, since my code fires asynch, my "don't repeat words" code could fail too. Again, using an oncomplete would let me handle that better. Who cares! Let's see the results:

shot2

Woot! Cool, right? I went through the words and then discovered something weird - none of them worked. So... I gave up and used the hints system the game doles out at certain times. I discovered that the 4 letter word was RAF. Obviously that's RAFT, right? But looking at the screen shot, you can see they don't hook up. Then I remembered - when you find a word, the letters disappear and the others 'fall' down. At this point, I kid you not - I immediately saw the 5 letter word. No kidding, I figured it out in seconds. But for the heck of it, I tried my tool:

shot4

The answer was PIANO. Selecting that left RAFT. And that's that. Want to run it yourself? Keep in mind you'll need an IDB-compatible browser and this code is very brittle. Here it is: https://static.raymondcamden.com/wordbrainsolver/