Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!

/r/dailyprogrammer Challenge #114 Easy Solution

By: Unh0ly_Tigg on Dec 7th, 2012  |  syntax: Java  |  size: 2.79 KB  |  views: 129  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileReader;
  4. import java.util.ArrayList;
  5. import java.util.HashSet;
  6. import java.util.ListIterator;
  7. import java.util.Set;
  8.  
  9.  
  10. public class WordLadderEasy {
  11.         public static String wordUrl = "words.txt";
  12.         public static ArrayList<String> words = new ArrayList<String>();
  13.        
  14.         public final static int hamming(String a, String b) {
  15.                 if(a.length() != b.length())
  16.                         return -1;
  17.                 int r = 0;
  18.                 for(int i = 0; i < a.length(); i++)
  19.                         if(a.charAt(i) != b.charAt(i))
  20.                                 r++;
  21.                 return r;
  22.         }
  23.        
  24.         public final static void loadWords() {
  25.                 try {
  26.                         BufferedReader r = new BufferedReader(new FileReader(new File(new File(System.getProperty("user.dir")), wordUrl)));
  27.                         words.clear();
  28.                         while(r.ready())
  29.                                 words.add(r.readLine());
  30.                         r.close();
  31.                 } catch (Exception e) {
  32.                 }
  33.         }
  34.        
  35.         public final static ArrayList<String> ladder(String base) {
  36.                 if(words.size() == 0)
  37.                         loadWords();
  38.                 ListIterator<String> i = words.listIterator();
  39.                 ArrayList<String> r = new ArrayList<String>();
  40.                 while(i.hasNext()) {
  41.                         String s = i.next();
  42.                         int x = hamming(base, s);
  43.                         if(x == 1)
  44.                                 r.add(s);
  45.                 }
  46.                 return r;
  47.         }
  48.        
  49.         public final static ArrayList<String> freqLadder(int freq) {
  50.                 if(words.size() == 0)
  51.                         loadWords();
  52.                 ArrayList<String> r = new ArrayList<String>();
  53.                 ListIterator<String> i = words.listIterator();
  54.                 while(i.hasNext()) {
  55.                         String s = i.next();
  56.                         if(ladder(s).size() == freq)
  57.                                 r.add(s);
  58.                 }
  59.                 return r;
  60.         }
  61.        
  62.         public final static String findLargest() {
  63.                 String current = "";
  64.                 int currentMax = -1;
  65.                 ListIterator<String> i = words.listIterator();
  66.                 while(i.hasNext()) {
  67.                         String s = i.next();
  68.                         int x = ladder(s).size();
  69.                         if(x > currentMax) {
  70.                                 currentMax = x;
  71.                                 current = s;
  72.                         }
  73.                 }
  74.                 return current;
  75.         }
  76.        
  77.         public final static int findLongest(String base, int steps) {
  78.                 Set<String> words = new HashSet<String>();
  79.                 Set<String> seen = new HashSet<String>();
  80.                 words.add(base);
  81.                 for(int i = 0; i < steps; i++) {
  82.                         Set<String> newWords = new HashSet<String>();
  83.                         for(String word : words) {
  84.                                 Set<String> extended = extend(word, seen);
  85.                                 seen.addAll(extended);
  86.                                 newWords.addAll(extended);
  87.                         }
  88.                         words.addAll(newWords);
  89.                 }
  90.                 return words.size();
  91.         }
  92.        
  93.         public final static Set<String> extend(String word, Set<String> seen) {
  94.                 ArrayList<String> w = ladder(word);
  95.                 for(String s : seen)
  96.                         w.remove(s);
  97.                 Set<String> s = new HashSet<String>();
  98.                 s.addAll(w);
  99.                 return s;
  100.         }
  101.        
  102.         public static void main(String[] args) {
  103.                 loadWords();
  104.                 System.out.println(ladder("puma"));
  105.                 System.out.println(freqLadder(33));
  106.                 String max = findLargest();
  107.                 System.out.println(max + " : " + ladder(max).size());
  108.                 System.out.println("Max from \"best\" is " + findLongest("best", 3));
  109.         }
  110. }