$(function() {
  function Trie(dictionary) {
    var trie = {};
    
    function insert(word, trie) {
      var word_length = word.length;
      
      if (word_length) {
        var next = trie;
        
        for (var i = 0; i < word_length; i++) {
          var char = word[i];
          
          if (char in next) {
            next = next[char];
          } else {
            var child = {};
            next[char] = child;
            next = child;      
          }
        }
        
        next['|'] = null;
      }
    }
    
    for (var i = 0, length = dictionary.length; i < length; i++) {
      insert(dictionary[i], trie);
    }
  
    // returns true for a word, null for a segment and false otherwise  
    this.test = function(str) {
      var next = trie;
      
      for (var i = 0, str_length = str.length; i < str_length; i++) {
        var char = str[i];
  
        if (char in next) {
          next = next[char];
        } else {
          return null;
        }
      }
      
      return '|' in next;    
    }; 
  }
  
  // main workhorse, depth first
  function start_search(start_x, start_y, length_x, length_y, segment, trie, board, visited, results) {
    var min_y = Math.max(0, start_y - 1), 
        min_x = Math.max(0, start_x - 1),
        max_y = Math.min(length_y - 1, start_y + 1),
        max_x = Math.min(length_x - 1, start_x + 1);
        
    for (var y = min_y; y <= max_y; y++) {
      var visited_y = visited[y],
          board_y = board[y];
          
      for (var x = min_x; x <= max_x; x++) {
        if (!visited_y[x]) {
          var segment_new = segment + board_y[x],
              test = trie.test(segment_new);
          
          if (test === true) {
            results[segment_new] = true;
          }
          
          if (test !== null) {
            visited_y[x] = true;
            start_search(x, y, length_x, length_y, segment_new, trie, board, visited, results);
            visited_y[x] = false;
          }
        }
      }
    }
  }
  
  function search(trie, board) {
    var length_y = board.length,
        length_x = board[0].length;
    
    var visited = [];
    for (var y = 0; y < length_y; y++) {
      visited[y] = [];
      for (var x = 0; x < length_x; x++) {
        visited[y][x] = false;
      }
    }    
      
    var results = {};
    for (var y = 0; y < length_y; y++) {
      var visited_y = visited[y],
          board_y = board[y];
            
      for (var x = 0; x < length_x; x++) {
        visited_y[x] = true;
        start_search(x, y, length_x, length_y, board_y[x], trie, board, visited, results);
        visited_y[x] = false;
      }
    }
    
    var result_array = [];
    for (var word in results) {
      if (results.hasOwnProperty(word)) {
        result_array.push(word);
      }
    }
    
    result_array.sort();
    
    return result_array;  
  }
  
  function solve_boggle(dictionary, callback) {
    $("#solving-boggle").html('<p>Solving</p>');
    
    var board = [
        ["d", "g", "f", "k"],
        ["o", "z", "a", "c"],
        ["b", "w", "k", "e"],
        ["b", "w", "k", "e"]
      ],
      trie = new Trie(dictionary),
      results = search(trie, board);
    
    callback(results);
  }

  function dictionary(callback) {
    if (window.localStorage !== null && window.localStorage.dictionary) {
      solve_boggle(window.localStorage.dictionary.split(","), callback);
    } else {
      function dictionary_load(data) {
        if (window.localStorage !== null) {
           window.localStorage.dictionary = data.join(",");
        }
        solve_boggle(data, callback);
      }
    
      $.getScript("http://goo.gl/8EhgZ");
    }
  }


  $("<a href='#'>Click to run Boggle Solver</a>")
    .appendTo("#solving-boggle")
    .one("click", function() {
      $("#solving-boggle").html('<p>Loading</p>');
      dictionary(function(results) {
        console.log(results);
        
        $("#solving-boggle").html('<span>Results: </span><span class="results"></span>');
        $("#solving-boggle .results").text(results.join(", "));
      });
      return false;
    });
});