#Set filename to the path of the input file
FILENAME = "/Users/Zack/Desktop/words2.txt"
#filename = "/Users/Zack/Desktop/test_words.txt"

#abort the search if our result hasn't improved after this number of itterations
NO_PROGRESS_CUTOFF = 10

#set this to true to find a path the ALWAYS follows the pattern
#set to false to prefer pattern matching, but match anything
PURE_PATTERN_MATCHING = true

#set to true to prompt for the starting word
#set to false to search over all words
PROMPT_FIRST_WORD = true

#Optional: set the starting word (requires PROMPT_FIRST_WORD = true)
START_WORD = "zero"


#------------------------------------------------
# parse text file, convert to string array
#------------------------------------------------
def parse_textfile(filename)
  word_list = []

  File.open(filename) do |file|
    while(line = file.gets)
      tokens = line.split(",")
      tokens.collect! {|token| token.strip}
      tokens.each do |token|
        token.strip!
        word_list << token if(token.length == 4)
      end
    end
    puts "Parsed #{word_list.length} words..."
  end
  
  word_list
end

#------------------------------------------------
# DfsNode - contains the search history of a sequrnce of words
#------------------------------------------------
class DfsNode
  attr_accessor :word_list, :path, :wildchar_index
  def initialize(word_list)
    @word_list = word_list.clone    # a list of all unused words
    @path = []                      # a list of the chosen words to get to this point
    @wildchar_index = []            #the index of the letter that changed for the path (chosen words)
  end
  
  def clone
    node = DfsNode.new(@word_list)
    node.path = @path.clone
    node.wildchar_index = @wildchar_index.clone
    node
  end
  
  def dfs_search()
    child_nodes = []
    last_word = @path.last
   
    #make regexp's for the last items in wildchar_index
    indexes = [0,1,2,3]
    used = []

    #get a list of the changed indexes of the last few words, unless we've just finished a whole word (4 changes)
    if(@wildchar_index.length % 4 != 0)
      if(@wildchar_index.length < 3)    #when we have processed less than 3 nodes (startup condition)
        @wildchar_index.each {|val| used << indexes.delete(val)}
      else                              #when we have processed 3 or more nodes
        (1..3).each { |val| used << indexes.delete(@wildchar_index[@wildchar_index.length - val]) }
      end

      if(not PURE_PATTERN_MATCHING)
        #we are combining the used an unused indexes into a list such that 
        # we will search the unused index first (preferentially), but then continue on to
        # search the used indexes, but search them last
        used.each {|val| indexes << val if not val.nil?}
      
        #the dfsnode list processes from the end, so reverse the list here such that for any new nodes
        #nodes of the prefered type are at the end of the list and thus get processed first
        indexes.reverse!
      end
    end
    
    indexes.each do |ix|
      #make a regular rexpression for each char index (i.e. HACK-> /.ACK/, /H.CK/, /HA.K/, /HAC./)
      rx = make_regex(last_word, ix)
      next_words = @word_list.select {|word| rx.match(word)}  #get a list of all words that match the regex
      
      #for each matching word, make a new dfs node with the selected word as the next step in the search
      next_words.each do |word|
        node = self.clone
        node.word_list.delete word
        node.path << word
        node.wildchar_index << ix
        
        #append the new dfs node to the end of the list
        child_nodes << node
      end
    end
    
    #return the list of all new dfsnodes
    child_nodes
  end
  
  #private method to make a regexp from a word and a character wildcard index
  def make_regex(word, wildchar_index)
    puts "word error: ''#{word}'" if(word.length != 4) #debugging check
    word = String.new(word)
    word[wildchar_index] = '.'
    Regexp.new(word)
  end
end
#---//end DfsNode class

#------------------------------------------------
# Main DFS Search entry point
#------------------------------------------------
def search(node_list)
  best_node = nil       #the best solution we've found so far
  iteration = 0         #the number of iterations through the while loop (below)
  prev_itr_count = 0    #the number of times we've had the same solution length
  prev_itr_size = 0     #the previous iteration's solution length
  while(node = node_list.pop)
    iteration = iteration + 1
    
    #print out status information,
    #check to see if we've hit a local maximum
    if(iteration % 1000 == 0)
      puts "Pass #{iteration}, Best Path: #{best_node.path.length}, Stack Size: #{node_list.length}" if(iteration % 1000 == 0)
      STDOUT.flush
      if(best_node.path.length > prev_itr_size)
        prev_itr_size = best_node.path.length
        prev_itr_count = 1
      else
        prev_itr_count = prev_itr_count + 1
      end
      if(prev_itr_count >= NO_PROGRESS_CUTOFF)
        puts "Search Ended - No Progress for #{NO_PROGRESS_CUTOFF} iterations"
        return best_node
      end
    end

    #check to see if we've exhausted the search
    if(node.word_list.length == 0)
      puts "Search Ended - Success"
      return node
    else
      best_node = node if best_node.nil?
      best_node = node if node.word_list.length < best_node.word_list.length
      child_nodes = node.dfs_search
      #add the new dfsnodes to the end of the processing list
      node_list.concat child_nodes
    end
  end
   puts "Search Ended - incomplete"
   best_node 
end


#------------------------------------------------
# start processing
#------------------------------------------------
start_time = Time.now

#process text file
word_list = parse_textfile(FILENAME)

#collection of dfsnodes
node_list = []

if(PROMPT_FIRST_WORD)
  input = START_WORD.upcase
  valid_word = word_list.include? input
  puts "Enter the word that should start the sequence:"
  while(not valid_word)
    input = gets.upcase.chomp
    if(word_list.include? input)
      valid_word = true
    else
      puts "That word isn't in the list, please try again"
    end
  end
  
  #create the dfsnode off of the chosen word
  node = DfsNode.new(word_list)
  node.word_list.delete(input)
  node.path << input
  node_list.push(node) 
    
else  #for each word, create a dfsnode with the search starting at that word
  word_list.each_index do |ix|
    node = DfsNode.new(word_list)
    word = node.word_list.delete_at(ix)
    node.path << word
    node_list.push(node) 
  end
end

puts "Initial search set size: #{node_list.length}"

#do the dfs search
#the return value is the best solution found
node = search(node_list)

puts "Total Time: #{(Time.now - start_time)/60} minutes"

#print the solution set
# path - the sequence of words
# wildchars - the index of the changed letter for successive words
# remaining - the list of unused words
puts "---------------Solution----------------"
print "Path (#{node.path.length}): "
node.path.each {|word| print "#{word}, "}
print "\n"
print "Wildchars (#{node.wildchar_index.length}): "
node.wildchar_index.each {|val| print "#{val}, "}
print "\n"
print "Remaining words (#{node.word_list.length}): "
node.word_list.each {|word| print "#{word}, "}
print "\n"