package algs41;
import stdlib.*;
import algs35.XIndexSET;
/* ***********************************************************************
 *  Compilation:  javac WordLadder.java
 *  Execution:    java WordLadder word1 word2 < wordlist.txt
 *  Dependencies: Graph.java IndexSET.java In.java BreadthFirstPaths.java
 *
 *  Data files:   http://www.cs.princeton.edu/algs4/41undirected/words5.txt
 *                http://www.cs.princeton.edu/algs4/41undirected/words6.txt
 *                http://www.cs.princeton.edu/algs4/41undirected/words5-knuth.txt
 *
 *  java WordLadder flirt break < words5.txt
 *  length = 11
 *  flirt
 *  flint
 *  fling
 *  cling
 *  clink
 *  click
 *  clock
 *  cloak
 *  croak
 *  creak
 *  break
 *
 *  % java WordLadder allow brown < words5.txt
 *  NOT CONNECTED
 *
 *  % java WordLadder white house < words5.txt
 *  length = 18
 *  white
 *  while
 *  whale
 *  shale
 *  shake
 *  slake
 *  slate
 *  plate
 *  place
 *  peace
 *  peach
 *  poach
 *  coach
 *  couch
 *  cough
 *  rough
 *  rouge
 *  rouse
 *  house
 *
 *  % java WordLadder white house < words5-knuth.txt
 *  length = 9
 *  white
 *  whits
 *  shits
 *  shots
 *  soots
 *  roots
 *  routs
 *  route
 *  rouse
 *  house
 *
 *************************************************************************/

public class XWordLadder {

	// return true if two strings differ in exactly one letter
	public static boolean isNeighbor(String a, String b) {
		assert a.length() == b.length();
		int differ = 0;
		for (int i = 0; i < a.length(); i++) {
			if (a.charAt(i) != b.charAt(i)) differ++;
		}
		return (differ == 1);
	}

	public static void main(String[] args) {
		args = new String[] { "flirt", "break" }; StdIn.fromFile ("data/words5.txt");
		//args = new String[] { "white", "house" }; StdIn.fromFile ("data/words5.txt");
		//args = new String[] { "allow", "brown" }; StdIn.fromFile ("data/words5.txt");
		//args = new String[] { "white", "house" }; StdIn.fromFile ("data/words5-knuth.txt");

		String from = args[0];
		String to   = args[1];
		if (from.length() != to.length())
			throw new Error("Words have different lengths");

		/* *****************************************************************
		 *  Read a list of strings, all of the same length.
		 *  At most 10000 words supported here.
		 *******************************************************************/
		XIndexSET<String> words = new XIndexSET<>();
		while (!StdIn.isEmpty()) {
			String word = StdIn.readString();
			if (word.length() != from.length())
				throw new Error("Words have different lengths");
			words.add(word);
		}
		System.err.println("Finished reading word list");

		/* *****************************************************************
		 *  Insert connections between neighboring words into graph.
		 *  This construction process can be improved from LN^2 to
		 *  L N log N by sorting, where L = length of words.
		 *
		 *  We insert two copies of each edge, but this is easily avoided
		 *  by checking if word1.compareTo(word2) < 0
		 *
		 *******************************************************************/
		Graph G = new Graph(words.size());
		for (String word1 : words.keys()) {
			for (String word2 : words.keys()) {
				if (isNeighbor(word1, word2)) {
					G.addEdge(words.indexOf(word1), words.indexOf(word2));
				}
			}
		}
		System.err.println("Finished building graph");

		/* *****************************************************************
		 *  Run breadth first search
		 *******************************************************************/
		BreadthFirstPaths bfs = new BreadthFirstPaths(G, words.indexOf(from));
		//DepthFirstPaths bfs = new DepthFirstPaths(G, words.indexOf(from));
		if (bfs.hasPathTo(words.indexOf(to))) {
			StdOut.println("length = " + bfs.distTo(words.indexOf(to)));
			for (int v : bfs.pathTo(words.indexOf(to))) {
				StdOut.println(words.keyOf(v));
			}
		}
		else StdOut.println("NOT CONNECTED");
	}
}