   Optimizing a certain "programming challenge"
  This is the challenge:Here is my current solution:import java.util.*;import java.io.*;/** * @author null */public class Main{private static ArrayList<String> words;private static class ScoredNode implements Comparable<ScoredNode>{public int score;public int node;public ScoredNode parent;public ScoredNode(int score, int node){this.score = score;this.node = node;parent = null;}public int compareTo(ScoredNode rhs){// order by score, then by word// same score & same word = same scored node, regardless of pathif (score == rhs.score){return words.get(node).compareTo(words.get(rhs.node));}return score - rhs.score;}}private static boolean connected(String a, String b){if (a.length() != b.length())return false;int dif = 0;for (int i = 0; i < a.length(); ++i)if (a.charAt(i) != b.charAt(i))dif++;return dif == 1;}public static void main(String[] args) throws Exception{Scanner in = new Scanner(new File("input.txt"));words = new ArrayList<String>(); // words is a globalHashMap<String, Integer> indices = new HashMap<String, Integer>();// indices map gives us word -> node IDwhile (true){String line = in.nextLine();if (line.equals(""))break;indices.put(line, words.size());words.add(line);}int numWords = words.size();// i wish java had a stack -_-int maxConnections = 32;int[] numConnections = new int[numWords]; // default 0, java got ONE thing rightint[][] connections = new int[numWords][maxConnections];// this loop definitely isn't N^2, but i'm not sure what it is// (for every M, we iterate N-M more times)// either way, should be faster than the old methodfor (int i = 0; i < numWords - 1; ++i){for (int j = i + 1; j < numWords; ++j){if (connected(words.get(i), words.get(j))){connections[numConnections++] = j;connections[j][numConnections[j]++] = i;}}}boolean first = true; // so that we don't have trailing '\n'outer: while (in.hasNext()){String startWord = in.next();String endWord = in.next();if (startWord.length() != endWord.length()){System.out.print((first ? "" : "\n") + "No solution.");first = false;continue outer;}Integer start = indices.get(startWord);Integer end = indices.get(endWord);if (start == null || end == null){System.out.print((first ? "" : "\n") + "No solution.");first = false;continue;}// standard Dijkstra, weight is the distance to the current wordTreeSet<ScoredNode> open = new TreeSet<ScoredNode>();open.add(new ScoredNode(0, start));HashSet<String> closed = new HashSet<String>(); // already visited words with best pathwhile (!open.isEmpty()){ScoredNode best = open.first();open.remove(best);String bestWord = words.get(best.node);if (closed.contains(bestWord)) continue;closed.add(bestWord);if (bestWord.equals(endWord)){// solutionif (!first)System.out.println();first = false;LinkedList<String> list = new LinkedList<String>();for (; best != null; best = best.parent)list.add(0, words.get(best.node));for (String str : list)System.out.println(str);continue outer;}// neighbor loopfor (int i = 0; i < numConnections[best.node]; ++i){int neighbor = connections[best.node];ScoredNode next = new ScoredNode(best.score + 1, neighbor);next.parent = best;if (closed.contains(words.get(neighbor)))continue;open.add(next);}}// if we got here then there's no solution (inner will 'continue' outer if we found a solution)System.out.print((first ? "" : "\n") + "No solution.");first = false;}}}This solution works perfectly fine for the sample input.However, the problem arises when I test it on some input with a 24k word dictionary - it takes about 7-15 seconds to parse the dictionary.  However, the path-finding itself is instantaneous.I cannot find the judge's solution for this problem.  Does anyone have any ideas on how to optimize it?Unrelated:Um...[Edited by - nullsquared on May 17, 2010 7:45:50 PM]
  Your graph building looks O(n^2) or there abouts. It's got a /2 in there, but that'll only affect k, really.One way to speed it up would be to make up a couple of hashes that'll alias on most of the word.Say one using the first couple of letters, and another one using the next couple of letters. It's best to take letters from the front of the word to better handle the shorter words. Say letter positions (1 and 3) and (2 and 4). Pad the word with space or something when you're calculating the hash.The swizzle is to try get a nicer hash from short words (1, 2, and 3 letters).Check all words that alias with the "current one" in the 2 hashes.Still looks like n^2 to me, but k gets to be a load smaller. Looks like /32k for a perfect fit with the hash.You'll need 2 hashes in case they don't alias in the hash but still should connect.If the dataset is hidden, I'd suggest you make a few different hashes and use the best pair (in case all words start with the same letter or some other trickery).As a side note, I'm not sure if there is a way for connected words to differ in length. You'll have to adjust as appropriate. I noticed that your connected function don't allow words of differing lengths to get connected, but the challenge didn't specify what to do in those cases. Should "car" and "care" be connected? I think you can just pad with space, and just modify the connect function.Eh.. Hope it makes sense..-Morten-   ;  Probably the first and easiest thing to do is to split the dictionary based on word length -- in other words have one dictionary each for words of length 2, 3, ... 16 (the maximum defined by the problem statement) -- I guess you'll have to have a dictionary for words of length 1 too (although the difference will always be 1 step, we have to make sure the word is actually in the dictionary.)After that, you probably need to think of a custom data structure, or a combination of off-the-shelf data structures that models the data more efficiently, which is a fairly large undertaking.   ;  @MortenB: Yeah, I thought about hashing pieces of the words, but I wasn't sure if the extra overhead might actually be worse than going directly through the list.  And I'm not sure if an extra letter counts as a valid connection, the problem is ambiguous.  I wish the judge's solution was posted somewhere.@Ravyne: My original approach actually split the words based on length, but it wasn't too much faster.  I'll try it again, perhaps I was doing something wrong.  Also, that would only work assuming that words of differing length cannot be connected.   ;Quote:Original post by nullsquaredUnrelated:Um...Yea... it was WA, so I deleted it... The UVa site isn't loading for me right now, so I can't really test it with large set.   ;  @Ravyne: OK, with the words-length optimization it got down to about 3-4 seconds on a 24k word dictionary.Quote:Original post by AntheusQuote:Original post by nullsquaredUnrelated:Um...Yea... it was WA, so I deleted it... The UVa site isn't loading for me right now, so I can't really test it with large set.Heh, it's all good, I just found it a little funny [grin].   ;  From the looks of the question, I would say that words of different lengths are not to be considered matches -- look at the input dictionary and the second test case -- If we allow differently sized words to match, then the dictionary should be considered sufficient. Solving the problem in such a way that allows differently-sized words to match seems like it would be an exponentially harder problem, so it would be unlikely to be within the scope of the solution that was intended.   ;  You're definitely right, and that was my intuition as well.Edit: Also, connected() can be optimized by early-break when dif >= 2.  This way the longer words that differ in the beginning letters are quickly disregarded.  Current parsing time is at about 2 seconds, which is quite an improvement from the original 7+   ;  I feel like you're wasting cycles by building a graph of all the words. The problem only requires you to return one answer, so why not use a more naive approach and op out early. Here's my attempt (in python). Based on my poor man profile runs in about 1/100 of a second on command line being interpreted by python. [source = "python"]def connected(l, r):if len(l) != len(r):return -1differences = 0for i in range(len(l)):if l != r:differences += 1if differences >= 2:return differencesreturn differencesdef search(inputPair, distance = connected):leftDoublet = []rightDoublet = []results = []for word in dictionary:# levenshteindistance is broken for the word "a"if word == "a":continueif distance(inputPair[0], word) == 1:for r in rightDoublet:if distance(word, r) == 1:return [inputPair[0], word, r, inputPair[1]]leftDoublet.append(word)elif distance(inputPair[1], word) == 1:for l in leftDoublet:if distance(l, word) == 1:return [inputPair[0], l, word, inputPair[1]]rightDoublet.append(word)# Theoritically we should never get herefor l in leftDoublet:for r in rightDoublet:if distance(l, r) == 1:return [inputPair[0], l, r, inputPair[1]]start = time.time()results = search(["lover", "doves"])print "time with connected: " + str(time.time() - start)print resultsI don't have time to really explain it, but hopefully it should be self-explanatory. Feel free to have me explain my approach a bit more, and I will when I can (tomorrow)P.S. This is with a dictionary word list of ~52,000   ;  You can also avoid the O(n^2) cost by having containers of words indexed by the word minus one of the letters (you'll need 16 of these containers). The type of container you need is what in C++ is called a multimap: Something that can store a set of values for a given key. Insert the word "horse" in C[0] at "orse", in C[1] at "hrse", in C[2] at "hose", in C[3] at "hore" and in C[4] at "hors". Make connections to all the words that are present in those containers for those keys already.