onecharaway-tree.js

1-readme.md

This algorithm collects the words of a dictionary identical to a given words, one letter excepted.

To achieve a faster speed, the dictionnary is transformed into a tree of nodes containing the words letter by letter, as such:

{
  "a": {
    "b": {
      "c": {
        "d": {
          "e": {
            "f": {
              "asWord": "abcdef"
            },
            "z": {
              "asWord": "abcdez"
            }
          },
          "z": {
            "f": {
              "asWord": "abcdzf"
            },
            "z": {
              "asWord": "abcdzz"
            }
          }
        },
        "z": {
          "e": {
            "f": {
              "asWord": "abczef"
            },
            "z": {
              "asWord": "abczez"
            }
          },
          ...

onecharaway-tree.js

var LETTERS = 'abcdefghijklmnopqrstuvwxyz'.split('');


//----------------------------------------------------------
// generate a dictionary that contains "abcdef"-like words
//----------------------------------------------------------

var dict = [];
for(var w = 250; w--;) {
  var dict_word = Array(6);
  for(var l = 6; l--;) {
    if(Math.random()<0.75) {
      dict_word[l] = LETTERS[l];
    } else {
      dict_word[l] = LETTERS[25];
    }
  }
  dict.push(dict_word.join(''));
}

 
//----------------------------------------------------------
// convert the dictionary into a tree
//----------------------------------------------------------
 
function DicNode() {
  this.a = undefined; this.b = undefined; this.c = undefined; this.d = undefined; this.e = undefined; 
  this.f = undefined; this.g = undefined; this.h = undefined; this.i = undefined; this.j = undefined;
  this.k = undefined; this.l = undefined; this.m = undefined; this.n = undefined; this.o = undefined;
  this.p = undefined; this.q = undefined; this.r = undefined; this.s = undefined; this.t = undefined;
  this.u = undefined; this.v = undefined; this.w = undefined; this.x = undefined; this.y = undefined;
  this.z = undefined; this.asWord = undefined;
}
 
var tree = new DicNode(); dict.forEach(function(entry) {
                
  var currentNode = tree;
  for(var i = 0; i<entry.length; i++) {

    var nextNode = currentNode[entry[i]];
    if(!nextNode) { nextNode = currentNode[entry[i]] = new DicNode(); }
    currentNode = nextNode;

  }
  currentNode.asWord=entry;
                
});


//----------------------------------------------------------
// accept close words based on a tree
//----------------------------------------------------------

function acceptCloseWords(baseWord, tree) {
  
  var beforeDiffNodes = [tree];
  var afterDiffNodes = [];
  
  //
  // for each letter of the base word, one by one
  //
  for(var i = 0; i<baseWord.length; i++) {
    var currentLetter = baseWord[i];
    
    //
    // get the nodes of the dict-tree which may contain valid words up to this letter
    //
    var next_beforeDiffNodes = [];
    var next_afterDiffNodes = [];
    
    //
    // those nodes are still a perfect match 
    // (there should be only one in fact)
    //
    for(var j = beforeDiffNodes.length; j--;) {
      var node = beforeDiffNodes[j];

      //
      // all children nodes under this one will be admissible
      //
      for(var l = LETTERS.length; l--;) {
        var letter = LETTERS[l];
        
        var nextNode = node[letter];
        if(!nextNode) continue;
        
        if(letter == currentLetter) {
          
          //
          // we may continue to be a perfect match
          //
          next_beforeDiffNodes.push(nextNode);
          
        } else {
          
          // 
          // or we may differ for the first time
          // 
          next_afterDiffNodes.push(nextNode);
          
        }
        
      }
      
    }
    
    //
    // those nodes have a difference already
    // from here, they must be perfect matches till the end
    //
    for(var j = afterDiffNodes.length; j--;) {
      var node = afterDiffNodes[j];
      var nextNode = node[currentLetter];
      if(!nextNode) continue;
        
      next_afterDiffNodes.push(nextNode);
        
    }
    
    //
    // move to the next letter
    //
    beforeDiffNodes = next_beforeDiffNodes;
    afterDiffNodes = next_afterDiffNodes;
    
  }
  
  //
  // convert the nodes into words, if possible
  //
  var results = Array(afterDiffNodes.length), cr = 0;
  for(var j = afterDiffNodes.length; j--;) {
      var node = afterDiffNodes[j];
    if(node.asWord) results[cr++] = node.asWord;
  }
  results.length = cr;
  return results;
  
}


//----------------------------------------------------------
// to understand how it works, uncomment this
//----------------------------------------------------------

//console.log(JSON.stringify(tree,null,'  '));
//console.log(acceptCloseWords("abcdef", tree));


//----------------------------------------------------------
// performance testing
//----------------------------------------------------------
 
time("start");

for(var i = 1000; i--;) { logArray(acceptCloseWords("abcdef", tree)); }
time("algoTree(cold)");
 
for(var i = 1000; i--;) { logArray(acceptCloseWords("abcdef", tree)); }
time("algoTree(hot)");
 
for(var i = 1000; i--;) { logArray(acceptCloseWords("abcdef", tree)); }
time("algoTree(hot)");

for(var i = 1000; i--;) { logArray(acceptCloseWords("abcdef", tree)); }
time("algoTree(hot)");