title: Word Ladder, Javascript: What algorithm and data structure am I using?
body: <p>I wrote the following algorithm to complete a word ladder. You can find the full program with the jQuery visualization and the json dictionary on my github here: <a href="https://github.com/NateBrady23/algorithms/tree/master/word_ladder" rel="nofollow">https://github.com/NateBrady23/algorithms/tree/master/word_ladder</a></p>
  
  <p>So I have very little knowledge of what the names of the algorithms I'm using are, and the names of the data structures I'm building out other than I'm filling some arrays with each level of Nodes.</p>
  
  <p>I start at a given input word and end word. I eliminate all words in the dictionary that I can't use (the input word and words not the same length as the input word). I build a Node object that holds the jump level it's on, a value, and a prev so I can traverse backward from my endpoint if I find a path.</p>
  
  <p>Starting at level 0, my input word, I find all words that could be created from that word by transforming one letter and save it into a bucket of level 1 wordNodes. Each of those Node objects prev property point back to the level 0 node it was found from. I then delete all of those words from the dictionary. I then go through all the level 1 wordNodes and for each one, find the transformed word from the modified dictionary and store it in level 2 and point back to the word that created it and so on until I find the target word or no new levels can be created (no path to my word).</p>
  
  <p>So given that probably poorly worded summary, is there a name for this type of structure I've built (like a binary search tree?) and the algorithm I used to get there. Also, is there a way to significantly improve the code below without using an entirely different structure/algorithm.</p>
  
  <pre><code>&lt;style&gt;
      span {
          margin: 10px;
      }
  
      .highlight {
          background-color: yellow;
          font-weight: bold;
      }
      span {
          display: inline-block;
      }
  &lt;/style&gt;
  &lt;div id="path"&gt;
  
  &lt;/div&gt;
  
  &lt;script src='js/jquery.min.js'&gt;&lt;/script&gt;
  &lt;script src='js/dictionary.js'&gt;&lt;/script&gt;
  &lt;script&gt;
  // var dict = JSON.parse('{"aa" : true, "aah" : true, "aahed" : true}');
  
      // Build our dictionary array
      // Create a Node object so we can traverse back up the tree
      function Node(value, prev, level) {
          this.prev = prev;
          this.level = level;
          this.value = value;
      }
  
      function getRegex(word) {
          var temp = [];
  
          for(var i = 0; i &lt; word.length; i++){
              temp.push( word.substring(0,i) + '.' + word.substring(i+1) );
          }  
          var re_str = '^(' + temp.join('|') + ')$';
          return new RegExp(re_str, 'i');
      }
  
      function oneOffs(wordNode) {
          var list = [];
          var regex = getRegex(wordNode.value);
  
          if ($('#' + (wordNode.level+1)).length == 0) {
              $('#path').append('&lt;div id="' + (wordNode.level+1) + '"&gt;&lt;/div&gt;');
              $('#' + (wordNode.level+1)).append('&lt;h1&gt;Level: ' + (wordNode.level+1));
          }
          for (var word in dict) {
                  // If we found a match
                  if (dict.hasOwnProperty(word) &amp;&amp; regex.test(word)) {
                      list.push(new Node(word, wordNode, wordNode.level + 1));
                      $('#' + (wordNode.level+1)).append('&lt;span id="' + word + '"&gt;' + word +'&lt;/span&gt;');
                      delete dict[word];
                  }
          }
          return list;
      }
  
      // Get our start and end words
      inputWord = 'boggle';
      endWord = 'shaggy';
  
      $('#path').append('&lt;div id="start"&gt;&lt;h1&gt;Transform Case&lt;/h1&gt;&lt;span&gt;&lt;b&gt;Starting Word:&lt;/b&gt; ' + inputWord + '&lt;/span&gt;&lt;span&gt;&lt;b&gt;Ending Word:&lt;/b&gt; ' + endWord + '&lt;/span&gt;&lt;/div&gt;');
      $('#path').append('&lt;div id="0"&gt;&lt;h1&gt;Level: 0&lt;/h1&gt;&lt;span id="' + inputWord + '"&gt;' + inputWord + '&lt;/span&gt;&lt;/div&gt;');
  
      // Have to remove our inputWord from the dictionary
      delete dict[inputWord];
  
      // Remove all words in dictionary not of proper length
      for (var word in dict) {
          if (dict.hasOwnProperty(word)) {
              if (word.length != inputWord.length) {
                  delete dict[word];
              }
          }
      }
  
  
      // Create input and end nodes
      inputNode = new Node(inputWord, null, 0);
      endNode = new Node(endWord, null, 0);
  
      // Create our initial list of level 1 nodes
      list = oneOffs(inputNode);
  
      for (var node in list) {
          if (list[node].value === endNode.value) {
              endNode.level = list[node].level;
              endNode.prev = list[node].prev;
          }
      }
  
      // Build our tree
      while (list.length &amp;&amp; !endNode.level) {
          newList = [];
          for (var i = 0; i &lt; list.length; i++) {
              newNodeList = oneOffs(list[i]);
              for (var node in newNodeList) {
                  if (newNodeList[node].value === endNode.value) {
                      endNode.level = newNodeList[node].level;
                      endNode.prev = newNodeList[node].prev;
                      break;
                  }
              }
              if (newNodeList.length) {
                  newList = newList.concat(newNodeList);
              }
          }
          list = newList;
      }
  
      // if we found the path, let's traverse back up and print out all the values
      if (endNode.level) {
          curr = endNode;
          $('#' + curr.value).addClass('highlight');
          console.log(curr.value);
          while(curr.prev) {
              $('#' + curr.prev.value).addClass('highlight');
              console.log(curr.prev.value);
              curr = curr.prev;
          }
      } else {
          console.log('No possible path');
      }
  
  
  &lt;/script&gt;
  </code></pre>