// ----------------------------------------------------------------
// Imports
// ----------------------------------------------------------------

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.ArrayList;
import java.io.FileReader;
import java.util.HashSet;
import java.util.Arrays;

// ----------------------------------------------------------------
// Anagrams
// ----------------------------------------------------------------

public class Anagrams
{
   // ----------------------------------------------------------------
   // getWords - Returns an array of Strings, the words extracted
   //            from 'fileName', throws an Exception on error
   // ----------------------------------------------------------------

   public static String[] getWords(String fileName) throws Exception
   {
      BufferedReader reader = new BufferedReader(new FileReader(fileName));

      ArrayList<String> lines = new ArrayList<String>();

      String line;

      while((line = reader.readLine()) != null)
         lines.add(line);

      reader.close();

      return(lines.toArray(new String[lines.size()]));
   }

   // ----------------------------------------------------------------
   // subtract - Return the result of removing 'lookFor' from
   //            'theString', returns null if 'lookFor' was not
   //            contained within 'theString'
   // ----------------------------------------------------------------

   public static String subtract(String theString, String lookFor)
   {
      String result = theString;

      for(char c : lookFor.toCharArray())
      {
         int index = result.indexOf(c);

         if(index == -1)
            return(null);

         String left  = result.substring(0, index);
         String right = result.substring(index + 1);

         result = left + right;
      }

      return(result);
   }

   // ----------------------------------------------------------------
   // removeSpaces - Return 'theString' with all spaces removed
   // ----------------------------------------------------------------

   public static String removeSpaces(String theString)
   {
      return(theString.replaceAll("\\s+", ""));
   }

   // ----------------------------------------------------------------
   // getKey - Form a unique key from 's' by splitting into
   //          words and then alphabetizing those words and
   //          separating them with commas.
   // ----------------------------------------------------------------

   public static String getKey(String s)
   {
      String[] array = s.split("\\s+");

      Arrays.sort(array);

      return(Arrays.toString(array));
   }

   // ----------------------------------------------------------------
   // showAnagrams - Display all anagrams that can be constructed
   //                from the letters in 'remaining', use 'history'
   //                to allow us to only show a set of words once.
   // ----------------------------------------------------------------

   public static void showAnagrams(
      HashSet<String> history,
      String          processed,
      String          remaining,
      String[]        words
   )
   {
      for(String word : words)
      {
         // See what's left if we subtract 'word' from 'remaining'
         // note that 'subtract' returns null if 'word' was not found

         String rNew = subtract(remaining, word);

         if(rNew != null)
         {
            String pNew =
               processed + (processed.isEmpty() ? "" : " ") + word;

            if(rNew.isEmpty())
            {
               String key = getKey(pNew);

               if(!history.contains(key))
               {
                  history.add(key);
                  System.out.printf("Solution: %s\n", pNew);
               }
            }
            else
            {
               showAnagrams(history, pNew, rNew, words);
            }
         }
      }
   }

   // ----------------------------------------------------------------
   // showAnagrams - Display all anagrams of 'theString' using
   //                the word list 'words'
   // ----------------------------------------------------------------

   public static void showAnagrams(String theString, String[] words)
   {
      showAnagrams(
         new HashSet<String>(), "", removeSpaces(theString), words
      );
   }

   // ----------------------------------------------------------------
   // main
   // ----------------------------------------------------------------

   public static void main(String[] args) throws Exception
   {
      String[] words = getWords("words.txt");

      String theString = (args.length > 0 ? args[0] : "star trek");

      showAnagrams(theString, words);
   }
}