Solving Boggle with Dart

My friends at work and I have been playing a lot of Scramble with Friends. It's a "tile based word searching game" where you find words on a 4x4 grid of letters. Being a good Dart hacker, I wanted to try writing a small library to find all possible words on the board. Here's how I did it!

Dart, not trad. :)

First off, props to danvk.org and his helpful posts (such as this one) on solving Boggle.

Old 'n busted

My first attend was the naive version. The following code simply tried every possible combination, in a depth-first search. It works, but it's slow. So very slow.

class Solver {  
  final Map _words;  
  final List<List<String>> _grid;  
  final List<List> _visited = new List.generate(4, (_) => new List.filled(4, false));  
  final List _found = new List();  
    
  Solver(this._words, this._grid);  
    
  _solve(int x, int y, [String word = '']) {  
   _visited[x][y] = true;  
     
   final newWord = '${word}${_grid[x][y]}';  
     
   if (_words.containsKey(newWord)) {  
    _found.add(newWord);  
   }  
     
   for (var _x = -1; _x < 2; _x++) {  
    final nX = x + _x;  
    if (nX < 0 || nX > 3) continue;  
    for (var _y = -1; _y < 2; _y++) {  
     if (_x == 0 && _y == 0) continue;  
     final nY = y + _y;  
     if (nY < 0 || nY > 3) continue;  
     if (_visited[nX][nY] == true) continue;  
     _solve(nX, nY, newWord);  
    }  
   }  
     
   _visited[x][y] = false;  
  }  
    
  Iterable<String> findAll() {  
   for (var x = 0; x < 4; x++) {  
    for (var y = 0; y < 4; y++) {  
     _solve(x, y);  
    }  
   }  
     
   return _found;  
  }  
 }  

Some notes for the code above:

• Real classes!
• Use _ to mark names as private to the library.
• Final variables can't be reassigned after they are initialized. This leads to safer code.
• The third parameter to _solve is an "optional positional parameter". It has a default value of an empty string.

Full recursion across all possible combinations?!? Surely we can do better!

New hotness

Enter a data structure called a Trie. A trie is an efficient data structure for dictionaries, because the nodes in the tree are letters that spell words.

From http://en.wikipedia.org/wiki/File:Trie_example.svg

Here is the code I used for the Trie. Thanks to Ladislav Thon for the initial inspiration.

library trie;  
   
 import 'dart:collection';  
   
 class Trie<T> {  
  T value;  
  final Map<int, Trie<T>> map;  
   
  Trie() : map = new Map<int, Trie<T>>();  
   
  T operator [](String key) {  
   var node = this;  
   for (int i = 0; i < key.length; i++) {  
    int char = key.codeUnitAt(i);  
   
    node = node.map[char];  
    if (node == null) {  
     return null;  
    }  
   }  
   return node.value;  
  }  
    
  Trie<T> nodeFor(String character) {  
   return map[character.codeUnitAt(0)];  
  }  
   
  void operator []=(String key, T value) {  
   var node = this;  
   for (int i = 0; i < key.length; i++) {  
    int char = key.codeUnitAt(i);  
   
    var current = node;  
    node = node.map[char];  
    if (node == null) {  
     current.map[char] = node = new Trie<T>();  
    }  
   }  
   node.value = value;  
  }  
 }  

A couple notes about the code above:

• A trie is a tree of strings to values, so I use Dart's generics (aka parameterized types) to clearly annotate that a Trie can hold a specific kind of value T (to be specified by the consumer of this trie).
• Dart classes can define [], the index access operator.
• Dart supports libraries, so I placed this code into its own library.

Here is the new Solver, that uses the Trie:

 library solver;  
   
 import 'dart:math';  
 import 'package:tilebasedwordsearch/trie.dart';  
 export 'package:tilebasedwordsearch/trie.dart' show Trie;  
   
 class Solver {  
  final Trie _words;  
  final List<List<String>> _grid;  
  final List<List> _visited = new List.generate(4, (_) => new List.filled(4, false));  
  final List _found = new List();  
    
  Solver(this._words, this._grid);  
    
  _solve(int x, int y, Trie inProgress) {  
     
   final Trie nextStep = inProgress.nodeFor(_grid[x][y]);  
     
   if (nextStep != null) {  
    if (nextStep.value != null) {  
     // FIXME: add real word  
     _found.add(nextStep.value);  
    }  
   
    _visited[x][y] = true;  
      
    for (var _x = -1; _x < 2; _x++) {  
     final nX = x + _x;  
     if (nX < 0 || nX > 3) continue;  
     for (var _y = -1; _y < 2; _y++) {  
      if (_x == 0 && _y == 0) continue;  
      final nY = y + _y;  
      if (nY < 0 || nY > 3) continue;  
      if (_visited[nX][nY] == true) continue;  
      _solve(nX, nY, nextStep);  
     }  
    }  
   
    _visited[x][y] = false;  
   }  
     
  }  
    
  Iterable<String> findAll() {  
   for (var x = 0; x < 4; x++) {  
    for (var y = 0; y < 4; y++) {  
     _solve(x, y, _words);  
    }  
   }  
     
   return _found;  
  }  
 }  

The real interesting part to me is that the Trie can act as the dictionary as well as the "in progress" tracking. As the solver walks through the tiles on the board, it looks to see if the current node in the tree has a child node for the adjacent tile. If not, the solver simply bails out immediately. No more searching all possible combinations! The new implementation above also does not build the potential word by concatenating strings, character by character. Instead, it just walks the tree until it it finds a word (the word is stored as a value on the left node) or a dead-end.

In action

Here's how I use it in a very simple web app. I was mostly concerned about benchmarks, so there's no UI.

 import 'dart:html';  
 import 'package:tilebasedwordsearch/solver.dart';  
   
 main() {  
  var timeToParseFiles = query("#time-to-parse-file");  
  var numWords = query('#num-words');  
  var resultsWords = query('#results-words');  
  var resultsLength = query('#results-length');  
  var time = query('#time');  
    
  const List<List<String>> grid = const [  
   const ['A', 'B', 'C', 'D'],  
   const ['E', 'F', 'G', 'H'],  
   const ['I', 'J', 'K', 'L'],  
   const ['M', 'N', 'O', 'P']  
  ];
    
  Trie words = new Trie();  
    
  HttpRequest.getString("../assets/dictionary.txt")  
   .then((contents) {  
    var start = window.performance.now();  
    contents.split("\n").forEach((line) => words[line] = line);  
    var stop = window.performance.now();
    var readFilesTime = stop - start; 
      
    var solver = new Solver(words, grid);  
      
    start = window.performance.now();  
    List<String> results = solver.findAll().toList();  
    stop = window.performance.now();
    var findAllTime = stop - start;  
      
    timeToParseFiles.text = '$readFilesTime';  
    resultsWords.text = '$results';  
    resultsLength.text = '${results.length}';  
    time.text = 'Found in $findAllTime ms';  
   })  
   .catchError((e) => print(e));  
 }  

The above Solver and Trie runs in about 1ms on my local machine (finding 33 words in the test board, using my dictionary), which is good enough for me. This is very much a fun weekend project, not meant to be production code. Hopefully it helps you learn a bit of Dart!