import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Set;
import java.util.TreeSet;

/**
 * A word reduction is a list of words obtained by removing one
 * letter each time until the word contains a single letter.  This
 * program finds all reducible words and prints them.
 * 
 * @author Scot Drysdale, 1/14/2011
 */
public class WordReduction {

	/** 
	 * Reads a dictionary of words and puts all of ones that contain
	 * either an "a" or an "i" into lists by length.
	 * Assumes that the words are one per line.
	 * 
	 * @param fileName the name of the file containing the dictionary.
	 */
  public static ArrayList<Set<String>> readWords(String fileName) {
  	try {
  		FileReader reader = new FileReader(fileName);
  		Scanner in = new Scanner(reader);
  		ArrayList<Set<String>> wordSets = new ArrayList<Set<String>>();
  		
  		while(in.hasNextLine()) {
  			String word = (in.nextLine()).toLowerCase();
  			if(word.contains("a") || word.contains("i")) {
  				// Add lists for missing sizes
  				while(word.length() > wordSets.size()) {
  					wordSets.add(new TreeSet<String>());
  				}
  				
  				wordSets.get(word.length()-1).add(word);  // Add word to correct list 					
  			}
  		}		
    	return wordSets;
  	}
  	catch (IOException exception) {
  		System.out.println("File processing error: " + exception);
  	}
  	return null;  // In case of an exception still need to return.
  }
  
  /**
   * Go through the wordSet and add any reducible words to goodWords.
   * Assumes that all good words shorter than the current word are
   * already in goodWords.
   * 
   * @param wordSet list of words of a given length
   * @param goodWords set of all good words of shorter length
   */
  public static void addGoodWords(Set<String> wordSet, Set<String> goodWords) {
  	for(String word : wordSet)
  	  for(int pos = 0; pos < word.length(); pos++)
  	  	if(goodWords.contains(dropLetter(word, pos)))
  	  		goodWords.add(word);	  	
  }
  
  /**
   * Returns the given word with letter in position pos dropped
   * 
   * @param word the word to shorten
   * @param pos the position of the character to drop
   * @return word with letter in position pos dropped
   */
  public static String dropLetter(String word, int pos) {
  	return word.substring(0, pos) + word.substring(pos+1, word.length());
  }
  
  /**
   * Prints the reduction chain starting with word
   * @param word the word to reduce
   * @param goodWords set of good words
   */
  public static void printReduction(String word, Set<String> goodWords) {
  	String shortened;  // The word with a letter dropped
  	System.out.print(word + "  ");
  	if(word.length() > 1) {
  		for(int pos = 0; pos < word.length(); pos++) {
  			shortened = dropLetter(word, pos);
      	if(goodWords.contains(shortened)) {
      		printReduction(shortened, goodWords);
      		return;
      	}     		
  		}
  		System.err.println("Cannot reduce " + word);
  	}
  }
  
  
	public static void main(String[] args) {
		Set<String> goodWords = new TreeSet<String>();
		goodWords.add("i");
		goodWords.add("a");
		
		ArrayList<Set<String>> wordSets = readWords("/usr/share/dict/words");
    System.out.println(wordSets.size());
    
		for (Set<String> wordSet : wordSets) 
			addGoodWords(wordSet, goodWords);
		
		String longestWord = "";
		for (String word : goodWords) {
			if(word.length() > longestWord.length())
				longestWord = word;
		  System.out.print(word + ": ");
		  for(int pos = 0; pos < word.length(); pos++) {
		  	String shortened = dropLetter(word, pos);
	    	if(goodWords.contains(shortened))
	  	   	System.out.print(shortened + " ");
		  }
		  System.out.println();
		}
		
		System.out.println("Number of good words = " + goodWords.size());
		System.out.print("Longest word reduction: ");
		printReduction(longestWord, goodWords);
		System.out.println();
	}
}