import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.ListIterator;
import java.util.Set;


public class WordLadderEasy {
	public static String wordUrl = "words.txt";
	public static ArrayList<String> words = new ArrayList<String>();
	
	public final static int hamming(String a, String b) {
		if(a.length() != b.length())
			return -1;
		int r = 0;
		for(int i = 0; i < a.length(); i++)
			if(a.charAt(i) != b.charAt(i))
				r++;
		return r;
	}
	
	public final static void loadWords() {
		try {
			BufferedReader r = new BufferedReader(new FileReader(new File(new File(System.getProperty("user.dir")), wordUrl)));
			words.clear();
			while(r.ready())
				words.add(r.readLine());
			r.close();
		} catch (Exception e) {
		}
	}
	
	public final static ArrayList<String> ladder(String base) {
		if(words.size() == 0)
			loadWords();
		ListIterator<String> i = words.listIterator();
		ArrayList<String> r = new ArrayList<String>();
		while(i.hasNext()) {
			String s = i.next();
			int x = hamming(base, s);
			if(x == 1)
				r.add(s);
		}
		return r;
	}
	
	public final static ArrayList<String> freqLadder(int freq) {
		if(words.size() == 0)
			loadWords();
		ArrayList<String> r = new ArrayList<String>();
		ListIterator<String> i = words.listIterator();
		while(i.hasNext()) {
			String s = i.next();
			if(ladder(s).size() == freq)
				r.add(s);
		}
		return r;
	}
	
	public final static String findLargest() {
		String current = "";
		int currentMax = -1;
		ListIterator<String> i = words.listIterator();
		while(i.hasNext()) {
			String s = i.next();
			int x = ladder(s).size();
			if(x > currentMax) {
				currentMax = x;
				current = s;
			}
		}
		return current;
	}
	
	public final static int findLongest(String base, int steps) {
		Set<String> words = new HashSet<String>();
		Set<String> seen = new HashSet<String>();
		words.add(base);
		for(int i = 0; i < steps; i++) {
			Set<String> newWords = new HashSet<String>();
			for(String word : words) {
				Set<String> extended = extend(word, seen);
				seen.addAll(extended);
				newWords.addAll(extended);
			}
			words.addAll(newWords);
		}
		return words.size();
	}
	
	public final static Set<String> extend(String word, Set<String> seen) {
		ArrayList<String> w = ladder(word);
		for(String s : seen)
			w.remove(s);
		Set<String> s = new HashSet<String>();
		s.addAll(w);
		return s;
	}
	
	public static void main(String[] args) {
		loadWords();
		System.out.println(ladder("puma"));
		System.out.println(freqLadder(33));
		String max = findLargest();
		System.out.println(max + " : " + ladder(max).size());
		System.out.println("Max from \"best\" is " + findLongest("best", 3));
	}
}