"""
 backtrack_class_anagrams.py

 An example of a backtrack search for anagrams,
 using a tiny dictionary, and using the Backtrack generic object.

 $ python backtrack_class_anagrams.py
  in search   []
  in search       ['a']
  in search           ['a', 'c']
  in search               ['a', 'c', 't']
  in search                   ['a', 'c', 't', 'i']
  in search                       ['a', 'c', 't', 'i', 't']
  in search                   ['a', 'c', 't', 't']
  in search               ['a', 'c', 't']
  in search                   ['a', 'c', 't', 't']
  in search                   ['a', 'c', 't', 'i']
  in search                       ['a', 'c', 't', 'i', 't']
  in search       ['c']
  in search           ['c', 'a']
  in search               ['c', 'a', 't']
  in search                   ['c', 'a', 't', 'i']
  in search                       ['c', 'a', 't', 'i', 't']
  in search                   ['c', 'a', 't', 't']
  in search               ['c', 'a', 't']
  in search                   ['c', 'a', 't', 't']
  in search                   ['c', 'a', 't', 'i']
  in search                       ['c', 'a', 't', 'i', 't']
  in search       ['t']
  in search           ['t', 'a']
  in search               ['t', 'a', 'c']
  in search                   ['t', 'a', 'c', 'i']
  in search                       ['t', 'a', 'c', 'i', 't']
  in search       ['i']
  in search           ['i', 't']
  in search               ['i', 't', 'a']
  in search                   ['i', 't', 'a', 'c']
  in search                       ['i', 't', 'a', 'c', 't']
  in search               ['i', 't', 'c']
  in search                   ['i', 't', 'c', 'a']
  in search                       ['i', 't', 'c', 'a', 't']
  in search               ['i', 't', 't']
  in search                   ['i', 't', 't', 'a']
  in search                       ['i', 't', 't', 'a', 'c']
  in search           ['i', 't']
  in search               ['i', 't', 'a']
  in search                   ['i', 't', 'a', 'c']
  in search                       ['i', 't', 'a', 'c', 't']
  in search               ['i', 't', 'c']
  in search                   ['i', 't', 'c', 'a']
  in search                       ['i', 't', 'c', 'a', 't']
  in search               ['i', 't', 't']
  in search                   ['i', 't', 't', 'a']
  in search                       ['i', 't', 't', 'a', 'c']
  in search       ['t']
  in search           ['t', 'a']
  in search               ['t', 'a', 'c']
  in search                   ['t', 'a', 'c', 'i']
  in search                       ['t', 'a', 'c', 'i', 't']
 ['a', 'c', 't', 'i', 't']
 ['a', 'c', 't', 'i', 't']
 ['c', 'a', 't', 'i', 't']
 ['c', 'a', 't', 'i', 't']
 ['t', 'a', 'c', 'i', 't']
 ['i', 't', 'a', 'c', 't']
 ['i', 't', 'c', 'a', 't']
 ['i', 't', 'a', 'c', 't']
 ['i', 't', 'c', 'a', 't']
 ['t', 'a', 'c', 'i', 't'] 

 (Each entry appears twice here because the two 't' characters
 are treated as distinct symbols.)

 Jim Mahoney | cs.marlboro.edu | Apr 2013 | MIT License
"""

class Backtrack(object):
    """ A generic backtrack search.
        To implement a specific problem, you'll need to override
        at least __init__() , is_solution() , and get_moves()
        in a class which inherits from this.
    """

    def __init__(self):
        self.result = []         # the current (partial) solution 
        self.solutions = []      # saved full solutions

    def is_solution(self):
        """ Return True if self.result is a full solution of the problem. """
        return False

    def process_solution(self):
        """ Do something with this solution. """
        # The default is to save each solution as a string.
        self.solutions.append(str(self.result))

    def get_moves(self):
        """ Return list of possible extensions to current result. """
        return []

    def do_move(self, move):
        """ Move down the tree, i.e. extend self.result with move. """
        self.result.append(move)

    def undo_move(self, move):
        """ Move up the tree, i.e. remove last move from self.result. """
        self.result.pop()

    def search(self, verbose=False):
        """ Do the recursive depth-first backtrack tree search. """
        if verbose:
            print " in search   " + "    "*len(self.result) + str(self.result)
        if self.is_solution():
            self.process_solution()
        else:
            for move in self.get_moves():
                self.do_move(move)
                self.search(verbose)
                self.undo_move(move)


class Words(object):
    """ A dictionary of words with lookup methods """

    # Implementation notes:
    #
    #   * I'm using python's built-in set() object, which provides O(1)
    #     membership lookup, e.g. a=set([1,2,3]); if 1 in a: ...
    #     This could also be done with hash tables or (equivalently)
    #     Python dictionaries.
    #
    #   * Both is_anagram() and is_partial_anagram() are called many
    #     times with the same arguments. So to get reasonable efficiency,
    #     they should be memoized - see for example wikipedia's article and
    #     http://stackoverflow.com/questions/1988804/
    #     what-is-memoization-and-how-can-i-use-it-in-python
    #     Memoization is closely related to what is sometimes called
    #     "dynamic programming", and algorithm technique coming up soon.
    #
    #   * Reading in a file of words for the dictionary isn't implemented here
    #     ... but is a straightforward generalization.
    #
    #   * At the moment the output of full match has no spaces,
    #     i.e. actit for 'act it'. Fixing that would be straightfoward
    #     perhaps by writing something similar to is_anagram that returns
    #     a list of the words, and calling that from Anagram.process_solution.

    def __init__(self, words = ['it', 'cat', 'act', 'tacit']):
        self.full_words = set(words)
        self.partial_words = set()
        for word in self.full_words:
            for i in xrange(1, len(word)+1):
                # i.e. if word is 'cat', put 'c', 'a', 't' in partial_words
                self.partial_words.add(word[:i])

    def is_anagram(self, string):
        """ Return True if letters is a sequence of complete words """
        # Implementation:
        #    Suppose full_words is ['cat'] and letters is [c, a, t, c, a, t]
        #    Then the appoarch is to partition the letters into two lists,
        #    e.g. left= [c], right=[a, t, c, a, t], and see if
        #    right is one word, and complete_anagram(left). (Recursive)
        #      If so, we return True: we're done.
        #      If not, we continue the search across other partitions.
        #    Partitions looped over are are e.g. (|cat) (c|at) (ca|t)
        if len(string) == 0:
            return True
        for length in xrange(len(string)):
            left = string[:length]
            right = string[length:]
            if right in self.full_words and self.is_anagram(left):
                return True
        return False

    def is_partial_anagram(self, string):
        """ Return True if string are part of an anagram. For example,
            if full_words is ['cat'] and string is ['c','a'], return True. """
        for length in xrange(len(string)):    # e.g. 0       1      2
            left = string[:length]            # e.g. ''      'c',   'ca'
            right = string[length:]           # e.g. 'cat',  'at',  't'
            if right in self.partial_words and self.is_anagram(left):
                return True
        return False

class Anagram(Backtrack):
    """ Search for anagrams. """

    # The variables in this implementation are :
    #    result        (partial) list of permuted symbols
    #    in_result     list of True/False marking symbols in/out of result[]
    #    move          index (i.e. 0, 1, 2, ...) into self.symbols[]
    #
    # Note that the methods and data structures here are *very* close to
    # the Permute code in backtrack_class_permute.py.
    #

    def __init__(self, phrase='act it', words=Words()):
        super(Anagram, self).__init__()    # Call Backtrack __init__()
        self.symbols = list(phrase.lower().replace(' ',''))
                                           # e.g. ['a', 'c', 't', 'i', 't']
        self.N = len(self.symbols)         # e.g. 5
        self.in_result = [False] * self.N  # e.g. [F, F, F, F, F] with F=False
        self.words = words

    def is_solution(self):
        string = ''.join(self.result)
        return len(self.result)==self.N and self.words.is_anagram(string)

    def do_move(self, move):
        self.result.append(self.symbols[move])  # grow result
        self.in_result[move] = True             # mark symbol used
        
    def undo_move(self, move):
        self.result.pop()                       # shrink result
        self.in_result[move] = False            # mark symbol unused

    def get_moves(self):
        """ Return indices of the symbols that aren't in result yet
            AND that continue to make a partial anagram """
        moves = []
        for i in xrange(self.N):
            string = ''.join(self.result) + self.symbols[i]
            if not self.in_result[i] and self.words.is_partial_anagram(string):
                moves.append(i)
        return moves

def main():
    p = Anagram()
    p.search(verbose = True)
    for s in p.solutions:
        print s

if __name__ == "__main__":
    main()