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));
}
}