import java.util.*;
import java.io.*;

/*
   Implementation of the Ladders program
   November 15, 2004
   Greg Nichols
   Modified by Sriram Pemmaraju. 2/3/2007
*/

public class LaddersBFS{

	// returns true if the words are different by only one letter
	public boolean differentByOne( String a, String b )
	{
		int diffCount = 0;

		// make sure the two strings are both 5 letters long
		if( a.length() != 5 || b.length() != 5 )
			return false;

		// check the letters of the strings
		for( int i = 0; i < a.length(); i++ )
		{
			if( a.charAt(i) != b.charAt(i) )
			if( ++diffCount > 1 )
				return false;
		}

		return (diffCount == 1);
	}
	
	
	public LaddersBFS()
	{
		String[] wordList;
		myGenericListGraph<String> mg;

		mg = new  myGenericListGraph<String>();
		wordList = new String[5800];
		int counter = 0;
		
		try
		{
			BufferedReader in = new BufferedReader(new FileReader("words.dat"));
			String word;

        		// read all the words from the file                
			System.out.println( "Reading words.dat..." );
			while( (word = in.readLine()) != null )
			{
				// make a new vertex w/ this word
				mg.addVertex( word );

				// see what words it's one letter different from
				for( int i = 0; i < counter; i++ )
					if( differentByOne(word, wordList[i]))
						mg.addEdge( word, wordList[i]);

				wordList[counter++] = word;
			}
			in.close();
		}
		catch (IOException e) {}

		System.out.println("Done constructing the graph....");
		mg.printAdjacencyList("house");
		
                // Finding a vertex of maximum degree and a vertex of minimum degree
                int maxIndex, maxDegree, minIndex, minDegree, currentDegree;
                maxDegree = -1;
                minDegree = counter;
                maxIndex = minIndex = -1;
                for(int i = 0; i < counter; i++)
                {
                        currentDegree = mg.degree(wordList[i]);
                        if(currentDegree > maxDegree)
                        {
                                maxDegree = currentDegree;
                                maxIndex = i;
                        }

                        if(currentDegree < minDegree)
                        {
                                minDegree = currentDegree;
                                minIndex = i;
                        }


                }


                System.out.println("A word with maximum degree is " + wordList[maxIndex]);
                System.out.println("Its degree is " + maxDegree);
                System.out.println("Its neighbors are...");
                GenericLinkList<String> neighbors = mg.getNeighbors(wordList[maxIndex]);
		neighbors.displayList();

                System.out.println("A word with minimum degree is " + wordList[minIndex]);
                System.out.println("Its degree is " + minDegree);
                if(minDegree > 0)
                {
                        System.out.println("Its neighbors are...");
                        neighbors = mg.getNeighbors(wordList[minIndex]);
			neighbors.displayList();	
                }

		System.out.println("We are doing BFS from the word: house");
		int[] distances = mg.breadthFirstSearch("house");

		// Find the maximum distance
		int maxDistance = -1;
		for(int j = 0; j < distances.length; j++)
			if(distances[j] > maxDistance)
				maxDistance = distances[j];


		// Print words organized by their distance from "house"
		for(int i = 1; i <= maxDistance; i++)
		{
			System.out.println("Here are vertices at distance " + i);
			for(int j = 0; j < distances.length; j++)
				if(distances[j] == i)
					System.out.println(wordList[j]);
		}

		// Print words that are unreachable from "house"
		System.out.println("Here are vertices unreachable from house");
		for(int j = 0; j < distances.length; j++)
			if(distances[j] == -1)
				System.out.println(wordList[j]);
		
	}

	public static void main(String args[])
	{
		new LaddersBFS();	
	}

}