4
\$\begingroup\$

The user puts in a starting word and an ending word. My code creates a ladder between these words of words that are different by one letter.

Start: gain

End: fire

Output:

gain
gait
wait
wart
ware
wire
fire

I created a linked list of linked lists and a hash map that uses the word length as a key so that it checks only possible words that can be in the wordladder.

public class PathDictionary {

private static final int MAX_WORD_LENGTH = 4;
private static final int MIN_WORD_LENGTH = 2;
private static final int MAX_PATH_LENGTH = 7;

private static HashSet<String> words                           = new HashSet<>();
private static ArrayList<String> wordList                      = new ArrayList<>();
private static HashMap<Integer, ArrayList<String>> wordLengths = new HashMap<>();
private static ArrayList<LinkedList<String>> adjDictionary     = new ArrayList<>();

public PathDictionary(InputStream inputStream) throws IOException {
    if (inputStream == null) {
        return;
    }

    BufferedReader in = new BufferedReader(new InputStreamReader(inputStream));
    String line = null;
    Log.i("TAGGER", "Loading dict");

    while((line = in.readLine()) != null) {
        String word = line.trim();
        if (word.length() > MAX_WORD_LENGTH && word.length() < MIN_WORD_LENGTH) {
            continue;
        }

        words.add(word);
        wordList.add(word);

        int size = word.length();

        if(wordLengths.containsKey(size) == false){
            ArrayList<String> newTemp = new ArrayList<>();
            newTemp.add(word);
            wordLengths.put(size, newTemp);
        } else {
            ArrayList<String> addToTemp = wordLengths.get(size);
            addToTemp.add(word);
            wordLengths.put(size, addToTemp);
        }

    }

    for(int i = 0; i < wordList.size(); i++){
        // add into path
        String input = wordList.get(i);

        LinkedList<String> neighbours = neighbours(input);
        adjDictionary.add(new LinkedList<String>());
        adjDictionary.get(i).add(input); // adds root node

        String display = "";
        for(int j = 0; j < neighbours.size(); j++){
            adjDictionary.get(i).add(neighbours.get(j)); // adds neighbors to the root node

            display += " " + neighbours.get(j);
        }
      //  Log.d("TAGGER", "Vertice: " + adjDictionary.get(i).get(0) + " Edges: " + adjDictionary.get(i));


    }


}

public boolean isWord(String word) {
    return words.contains(word.toLowerCase());
}

private LinkedList<String> neighbours(String word) {

    int size = word.length();
    LinkedList<String> neighbours = new LinkedList<>();
    ArrayList<String> possibleNeighbours  = wordLengths.get(size);

    for(String validWord: possibleNeighbours){
        int count = 0;

        // the root
        if(validWord.equals(word)) continue;

        for(int i = 0; i < size; i++){

            if(!validWord.contains("" + word.charAt(i))){
                count++;
            }
        }

        if(!(count > 1)) neighbours.add(validWord);
    }


    return neighbours;
}

public String[] findPath(String start, String end) {
    ArrayDeque pathsExplored = new ArrayDeque();
    ArrayList<String> path   = new ArrayList<String>();
    int pathSize = 0;

    path.add(start);
    pathsExplored.add(path);

    while(!pathsExplored.isEmpty()){
        pathSize++;

        if(pathSize > MAX_PATH_LENGTH) return null;

        //While the queue is not empty, get the path from the head of the queue and consider all of its neighbours.
        ArrayList<String> tempPath = (ArrayList) pathsExplored.remove();
        int lastElementInPath = tempPath.size();
        String currentWord    = tempPath.get(lastElementInPath - 1);

        int root = wordList.indexOf(currentWord);
        LinkedList<String> neighbors = adjDictionary.get(root);

        //If the neighbour is the desired end, return the corresponding path.
        if(neighbors.contains(end)){
            String [] pathFound = new String [path.size()];
            Log.i("TAGGER", "PATH FOUND!");
            return tempPath.toArray(pathFound);
        }

        //Otherwise, create new paths representing the current path plus each of the neighbours (avoiding loops) and add them to the queue.
        for(String word: neighbors){
            //stops loops last word in should not be considered
            if(word.equals(tempPath.get(tempPath.size() - 1))){
                continue;
            }

            //create new paths with all neighbors using old path
            ArrayList<String> newPath = new ArrayList<>(tempPath);
            newPath.add(word);
            pathsExplored.add(newPath);

        }



    }

    return null;
   }
}

My code is really messy; it feels like I'm doing too much, but it gets the job done. I'm only using a "sample.txt" file with only words to test the path from gain to fire. When I use a bigger/better dictionary file (65,000 words) my code runs for a very long time simply trying to initialize all the words into the graph. I'd like some refactoring advice and if possible help on how best to tackle this.

Unit 7: Graph Traversal (Android Studio)

\$\endgroup\$
2
\$\begingroup\$

Well, the runtime of your code can be maybe improved a bit by cleaning up the current code a bit, but the main bottleneck is the inefficient algorithm, so I will not comment on your particular code and style, and I will focus on the algorithm only (if you still insist on code clean-up of current version, let me know in comments, I may try to rewrite few bits of it more to my style to show you a thing or two, but I think reviewing better algorithm would make more sense).

Also I would focus on the search algorithm, not on the init. I'm afraid with huge word list even init can be very costly, and worth optimization, but the initial data may be preprocessed ahead, so you then read not only word list, but complete definition of graph with edges between them. You should have posted, if the init itself is important for you as well (can be worth of effort for application where input word list changes often, so graph has to be rebuilt often).

Imagine the words as nodes of graph, with edges between words different only in single letter (obviously words of different length form a completely disconnected sub graph, but even with words of the same length the graph can have several disconnected sub-groups).

If a starting word has a ladder to the ending one, both should belong to the same sub group of graph.

So first optimization may be to store each sub group separately (for example: having for 4-letter words two or more graphs). Then in O(subgroup_size*letters) you can tell if starting word belongs to the group under scrutiny. (with global hash map of words containing index to subgroup and index within subgroup the O(...) can get even lower, depends on hash map search implementation, but the initialization will get longer).

Now the ending word must belong to the same subgroup, otherwise the ladder path does not exist at all, so another search of word ( O(subgroup_size*letters) ) will tell you, if the solution does exist. And also you will have both nodes (starting and ending word).

Now you should do a "path between nodes" search, I'm not sure if the shortest one is required, or any will do. For these situations something like A* path-finding algorithm can be used.

I didn't check A* lately, so just from my head some idea about such algorithm, basically searching the graph from both ends, in a deep/wide way by word_distance:

You have to create some int distance[subgroup_size] = { -1 }; and set distance[start_node_index] = distance[end_node_index] = 0;. distance will be distance (number of nodes) from starting point. Also set int color[subgroup_size] = { -1 }; and color[start_node_index] = 0; color[end_node_index] = 1; color marks whether distance belongs to the starting node, or to the ending node.

Put both indices in the deque.

Now till the deque is not empty, pick the index out of it and it's color.

For all it's neighbours:

  • first check if the neighbour has already distance set for different color. If yes, you have found some path (a node somewhere between starting and ending node). If you don't need shortest one, you can start building the answer by searching from current node for it's color neighbour with distance - 1, and from the different color neighbour search it's distance - 1 neighbour (till you find both start and end nodes on each end.
  • if you need shortest path, you should store as best_found the current middle node, with the total distance (distance of current node + distance of neighbour) - if already set best_found is not shorter, then continue.
  • if neighbour distance is already set, but with same color, either continue (any path), or check if you came here with better distance (for shortest path search). If better distance can be achieved, reset the distance to new one, and put the neighbour again into deque.
  • distance of neighbour not set yet case:
  • color the neighbour (with same color as current node)
  • set distance to current distance + 1.
  • calculate word_distance from opposite color word (= how many letters the neighbour word share with ending word (for color 0), or with starting word (color 1)), insert the node into deque ahead of all words with worse word_distance (as you have 4 letter words, it would make sense to use 5 deques for each possible word_distance, actually just 4 of them, because having 4 letters same means you have found the ending word, so that case is not possible).

Continue with other neighbours of current node, then go back to loop by fetching next current node from deque (if you have 4 of them, then empty the one with best word_distance first), till the (shortest) path is found.

The word_distance is supplying some orientation in the path finding (absolute coordinate distance in A* when used with geometric coordinates) - it's more likely you will find shorter path with words which are becoming closer to the other end of path.

I will end here, as it already took some time to write this, unfortunately I will not provide you with working source.


Hmm... ok, one bit of source just to make it look a bit less like "wall of text" (although I'm afraid it's too late for that :D ).

private LinkedList<String> neighbours(String word) {
    int size = word.length();
    LinkedList<String> neighbours = new LinkedList<>();
    for(String validWord: wordLengths.get(size)){
        if (validWord.equals(word)) continue;
        int differentLetterCount = 0;
        for(int i = 0; i < size; i++) {
            // In original source you have "contains" test.
            // So is "tire" neighbour with "rate"?!
            // I think this is bug, and you wanted this:
            if ((word.charAt(i) != validWord.charAt(i)) &&
                (2 == ++differentLetterCount)) {
                break; // early exit optimization
            }
        }
        if (1 == differentLetterCount) neighbours.add(validWord);
    }
    return neighbours;
}

I was thinking whether searching for neighbours for new word can be optimized by searching only trough "neighbours of neighbours of first-found-neighbour", but after short tinkering with it I think this is not valid, this would maybe work for all 4-letter permutations forming complete graph, not for regular words when plenty of possible 4 letter permutations are not available.


I found another bug in your source: if (word.length() > MAX_WORD_LENGTH && word.length() < MIN_WORD_LENGTH) { will be always false.

Unrelated to your bug, I have read an advice somewhere to always use only "<", "<=", "==" and "!=" in comparisons. It felt strange for few weeks, but once you get used to it, it really makes easier to read sources, as you know the values should only increase from left to right, if the expression is true.

So I would write your expression as: if (word.length() < MIN_WORD_LENGTH || MAX_WORD_LENGTH < word.length()) {.


Example implementation of those ideas in this post and comments: ped.7gods.org/WordLadder.zip

Meanwhile, lured by the fun of figuring out algorithm, and writing the code, I completely went off the path of reviewing your code instead. Sorry Jonathan.

And to make it even worse, my source is not as clean as to be proper example in every possible way, but I have it now for few days sitting on disc and can't get to cleaning it up more, so I'm releasing it at least for the sake of algorithm example, as is.

\$\endgroup\$
  • \$\begingroup\$ I would love to implement this new strategy as it would definitely make finding paths faster, but right now my code is a working a solution only because it is handling a small file of words. The main file is actually 65,000 words, I thought it was 10,000 I just edited it, and the initialization runs past about 30 minutes. I'm afraid if I try this strategy it will not change the issue. Oh and thanks for finding that bug! Yes, I did not intend for "tire" to be a neighbor with "rate". I really want to try this; would changing my data structure and still using the hashmap fix this? \$\endgroup\$ – Jonathan Portorreal Jul 8 '16 at 18:33
  • 1
    \$\begingroup\$ I don't know now, I didn't check your init very much (from O(..) complexity view), so I have no idea if there's easy fix (better algorithm) or your init is basically good, and has to be sped up (much more difficult, to get from 30min anywhere). Although 30min for 65k words sounds a bit too much, even in Java, so there's probably some good room for improvement. I may take a look on it, but not sure when (if I wouldn't respond for a week or so, try to post another comment here under answer - to see whether I was busy or not in mood at all). Hashmap is not magic fix for everything, but may help. \$\endgroup\$ – Ped7g Jul 8 '16 at 18:43
  • 1
    \$\begingroup\$ One of them may be to word lists per [size of word, letter of alphabet (is this ASCII only?!)] for first character and second character. Then to get all possible potential neighbours is to fetch those lists for first and second character for input word (only one can differ), so any neighbour must belong to one list at least (can be in both!). If the word is not in either of the lists, it differs by two letters at least, so it can not be neighbour. Not sure if this will speed up init, as it requires creation of many helper lists (for those first/second characters), but sounds promising to me. \$\endgroup\$ – Ped7g Jul 8 '16 at 19:00
  • 1
    \$\begingroup\$ BTW, it looks like the lecture requires quite some understanding of graph theory and being creative in figuring out non-brute-force algorithms. Your coding skill is far from perfect, but you look to be lacking more in theory field, and logical thinking. So maybe you check that lecture for further materials on Graph theory and also do some more logical/algorithmic exercises to hone your skills further. Also don't jump into coding too fast, take a paper and pencil first and think a bit what are your data, what you want to calculate, and what is a good way to achieve that. Start code after. \$\endgroup\$ – Ped7g Jul 8 '16 at 19:08
  • 1
    \$\begingroup\$ @JonathanPortorreal I tried to write it, I'm missing the final search yet, but read of file and init neighbours lists is done. I found ~350k English word list from Internet: to prepare graph data for words of lengths from 2 to 6 it takes ~1.5s. When I include lengths up to 15, it takes ~16s. (it's useless, as with length 6 the average size of subgroup is only ~4 words, from 7+ length most of the words doesn't have any neighbour, or just one). I'm not posting code, as search is missing. Also it's quite long, not sure if I should post it here after I finish it. Try harder,there's lot of reserve. \$\endgroup\$ – Ped7g Jul 10 '16 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.