/* Chris Poon
  BHCSI 2005 Algorithms.
   Jumble solution - implementing recursion and binary search
   given a word, check to see if any of its permutaions exist in a
    file.
*/
import java.io.*;
class Dictionary{  //Dictionary object to store file entries
					//and perform binary search on.

	public final static int SIZE=26000; //maximum capacity.
	public int length;
	String entries[]=new String[SIZE];

	private boolean binSearch(String target, int low, int high){
		//the recursive binary search.
		if (low<0 || high>=length || low>high) return false;
		
		int mid=(low+high)/2;

		if (target.compareTo(entries[mid])==0) return true;
		else if (target.compareTo(entries[mid])<0)
			return binSearch(target, low, mid-1);
		else
			return binSearch(target, mid+1, high);
	}
	public boolean isEntry(String target){
		//driver to initiate binary search.
		return binSearch(target, 0, length-1);
	}
	public Dictionary(String dfilename) throws IOException{
		//constructor takes string paramter to load dictionary file.
		//  ignores any word with non alpha characters
		//  also converts all to uppercase.
		BufferedReader infile=new BufferedReader (new FileReader(dfilename));
		length=0;
		while (infile.ready()){
			String dicLine=infile.readLine();
			dicLine=dicLine.toUpperCase();
			boolean goodword=true;
			for (int x=0;x<dicLine.length() && goodword; x++)
				if (dicLine.charAt(x)<'A' || dicLine.charAt(x)>'Z') goodword=false;

			if (goodword) entries[length++]=new String(dicLine);
			
		}
		System.out.println("Dictionary loaded with "+length+" words.");
		infile.close();
	}
}
class Enumerator{
	//Enumerator object that will generate the permutations of a supplied string
	String enumerations[];

	public int length;
	private int fillIndex;
	private int factorial(int n){
		//just a quick factorial method to determine size of enumerations.
		if (n<=1) return 1;
		return n*factorial(n-1);
	}
	private void fillEnumerations(int index, String word, boolean[] used, String built){
		//recursive method to fill the permutation/enumeration table.
		if (index==word.length()) {
			//the base case, here's a word.
			enumerations[fillIndex++]=built;
			return;
		}
		for (int x=0;x<used.length; x++){
			//otherwise, we pick a letter that hasnt been used, add it,
			// and recursively call with the remaining letters.
			if (used[x]) continue;
			else{
				String thisbuilt=new String(built);
				boolean[] thisused=new boolean[used.length];
				System.arraycopy(used, 0, thisused, 0,used.length);
				thisbuilt+=word.charAt(x);
				thisused[x]=true;
				fillEnumerations(index+1, word, thisused, thisbuilt);
			}
		}
	}

	public String getPerm(int i){
		//retrieve a specific permutation.
		if (i<0 ||i>=length) return "";
		return enumerations[i];
	}
	public Enumerator(String word){
		//constructor.
		length=factorial(word.length());
		enumerations=new String[length];
		boolean used[]=new boolean[word.length()];
		for (int x=0;x<used.length;x++) used[x]=false;
		fillIndex=0;
		fillEnumerations(0, word, used, "");
	}
}
public class Jumble 
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
		Dictionary myDictionary=new Dictionary("dictionary.txt");

		System.out.print("Enter jumble >");
		Enumerator jumbled=new Enumerator((stdin.readLine()).toUpperCase());
		for (int x=0;x<jumbled.length; x++){
			if (myDictionary.isEntry(jumbled.getPerm(x)))
				System.out.println("Here's a word: "+jumbled.getPerm(x));
		}

	}
}