001package algs41;
002import stdlib.*;
003import algs35.XIndexSET;
004/* ***********************************************************************
005 *  Compilation:  javac WordLadder.java
006 *  Execution:    java WordLadder word1 word2 < wordlist.txt
007 *  Dependencies: Graph.java IndexSET.java In.java BreadthFirstPaths.java
008 *
009 *  Data files:   http://www.cs.princeton.edu/algs4/41undirected/words5.txt
010 *                http://www.cs.princeton.edu/algs4/41undirected/words6.txt
011 *                http://www.cs.princeton.edu/algs4/41undirected/words5-knuth.txt
012 *
013 *  java WordLadder flirt break < words5.txt
014 *  length = 11
015 *  flirt
016 *  flint
017 *  fling
018 *  cling
019 *  clink
020 *  click
021 *  clock
022 *  cloak
023 *  croak
024 *  creak
025 *  break
026 *
027 *  % java WordLadder allow brown < words5.txt
028 *  NOT CONNECTED
029 *
030 *  % java WordLadder white house < words5.txt
031 *  length = 18
032 *  white
033 *  while
034 *  whale
035 *  shale
036 *  shake
037 *  slake
038 *  slate
039 *  plate
040 *  place
041 *  peace
042 *  peach
043 *  poach
044 *  coach
045 *  couch
046 *  cough
047 *  rough
048 *  rouge
049 *  rouse
050 *  house
051 *
052 *  % java WordLadder white house < words5-knuth.txt
053 *  length = 9
054 *  white
055 *  whits
056 *  shits
057 *  shots
058 *  soots
059 *  roots
060 *  routs
061 *  route
062 *  rouse
063 *  house
064 *
065 *************************************************************************/
066
067public class XWordLadder {
068
069        // return true if two strings differ in exactly one letter
070        public static boolean isNeighbor(String a, String b) {
071                assert a.length() == b.length();
072                int differ = 0;
073                for (int i = 0; i < a.length(); i++) {
074                        if (a.charAt(i) != b.charAt(i)) differ++;
075                }
076                return (differ == 1);
077        }
078
079        public static void main(String[] args) {
080                args = new String[] { "flirt", "break" }; StdIn.fromFile ("data/words5.txt");
081                //args = new String[] { "white", "house" }; StdIn.fromFile ("data/words5.txt");
082                //args = new String[] { "allow", "brown" }; StdIn.fromFile ("data/words5.txt");
083                //args = new String[] { "white", "house" }; StdIn.fromFile ("data/words5-knuth.txt");
084
085                String from = args[0];
086                String to   = args[1];
087                if (from.length() != to.length())
088                        throw new Error("Words have different lengths");
089
090                /* *****************************************************************
091                 *  Read a list of strings, all of the same length.
092                 *  At most 10000 words supported here.
093                 *******************************************************************/
094                XIndexSET<String> words = new XIndexSET<>();
095                while (!StdIn.isEmpty()) {
096                        String word = StdIn.readString();
097                        if (word.length() != from.length())
098                                throw new Error("Words have different lengths");
099                        words.add(word);
100                }
101                System.err.println("Finished reading word list");
102
103                /* *****************************************************************
104                 *  Insert connections between neighboring words into graph.
105                 *  This construction process can be improved from LN^2 to
106                 *  L N log N by sorting, where L = length of words.
107                 *
108                 *  We insert two copies of each edge, but this is easily avoided
109                 *  by checking if word1.compareTo(word2) < 0
110                 *
111                 *******************************************************************/
112                Graph G = new Graph(words.size());
113                for (String word1 : words.keys()) {
114                        for (String word2 : words.keys()) {
115                                if (isNeighbor(word1, word2)) {
116                                        G.addEdge(words.indexOf(word1), words.indexOf(word2));
117                                }
118                        }
119                }
120                System.err.println("Finished building graph");
121
122                /* *****************************************************************
123                 *  Run breadth first search
124                 *******************************************************************/
125                BreadthFirstPaths bfs = new BreadthFirstPaths(G, words.indexOf(from));
126                //DepthFirstPaths bfs = new DepthFirstPaths(G, words.indexOf(from));
127                if (bfs.hasPathTo(words.indexOf(to))) {
128                        StdOut.println("length = " + bfs.distTo(words.indexOf(to)));
129                        for (int v : bfs.pathTo(words.indexOf(to))) {
130                                StdOut.println(words.keyOf(v));
131                        }
132                }
133                else StdOut.println("NOT CONNECTED");
134        }
135}