0

I'm working on a scrabble-like-app. Given up to 15 letters it finds all possible valid words made from that letters. I decided to store dictionary in a Trie structure. My previous code was making possible combinations and then looking in a Trie if they are valid words. To make it faster, i want to implement John Pirie's suggestion posted here.

I'm using fast_trie gem. Comes with couple of useful methods.

After many hours of trying to implement John Pirie's solution i can't wrap my head around backtracking part of the code. Recursive algorithms seem to be rarely used in ruby - i'm struggling to find any help.

How to make program to go back to previous node, check if there are possible paths not taken before, search them through and go back again? 

    require 'trie'
    trie = Trie.read("local_copy_of_my_trie")
    input = "helloworld"
    rack = input.chars
    $words = [] # after recursive search it conains all possible words made from input
    start_node = trie.root

    def search_from(node, rack)
      current_node = node
      current_rack = rack
      $words.push(node.full_state) if node.terminal?
      search_from(choose_next_node(current_node, current_rack),    update_rack(current_rack)) # choose next node backtracks if possible
    end

    def choose_next_node(node, rack)
      possible_paths = []
      rack.each { |l| possible_paths.push(l) if $trie.has_children?(node.full_state+l) }
      # must backtrack if there are no possibilities
      # how to mark path as already taken?
      # can i return both node and rack to search_from ?
    end

    def update_rack(rack)
      # how to update rack not knowing the result of choose_next_node here?
    end

  search_from(start_node, rack)
Community
  • 1
  • 1
Tomasz Bubała
  • 2,093
  • 1
  • 11
  • 18
  • I hope you get some good answers, but consider yourself very lucky if you do. Firstly, those unfamiliar with the `fast-tree` gem are not likely to prepare answers. Those familiar with the gem will recognize that a very substantial investment of time would be required to work up an answer, which will further discourage participation. It might help to remove the requirement that `fast-tree` be used. Good solution that don't use that gem may still provide useful insights to the structure of the required recursion. – Cary Swoveland Feb 18 '17 at 22:49
  • Thanks for suggestion. Even pointing me in the right direction would be nice. I'm starting to understand recursive functions, but I still don't know how to bring backtracking to life. – Tomasz Bubała Feb 18 '17 at 22:59

0 Answers0