import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.Queue;

/*
DISTRIBUTION OF DICTIONARY:
Read the words...88984
1       1
2       48
3       601
4       2409
5       4882
6       8205
7       11989
8       13672
9       13014
10      11297
11      8617
12      6003
13      3814
14      2173
15      1169
16      600
17      302
18      107
19      53
20      28
Elapsed time FAST: 2.8 vs 3.8
Elapsed time MEDIUM: 50.9 vs 50.5
Elapsed time SLOW: 95.9 vs 96.1 (H vs T)
**/

public class WordLadder
{
	public static List<String> readWords( BufferedReader in ) throws IOException
	{
		String oneLine;
		List<String> lst = new ArrayList<String>( );
		
		while( ( oneLine = in.readLine( ) ) != null )
			lst.add( oneLine );
		
		return lst;
	}	
	
	// Returns true is word1 and word2 are the same length
	// and differ in only one character.
	private static boolean oneCharOff( String word1, String word2 )
	{
		if( word1.length( ) != word2.length( ) )
			return false;
		
		int diffs = 0;
		
		for( int i = 0; i < word1.length( ); i++ )
			if( word1.charAt( i ) != word2.charAt( i ) )
				if( ++diffs > 1 )
					return false;
					
		return diffs == 1;
	}
	
	private static <KeyType> void update( Map<KeyType,List<String>> m, KeyType key, String value )
	{
		List<String> lst = m.get( key );
		if( lst == null )
		{
			lst = new ArrayList<String>( );
			m.put( key, lst );
		}
		
		lst.add( value );
	}
	
	// Computes a map in which the keys are words and values are Lists of words
	// that differ in only one character from the corresponding key.
	// Uses a quadratic algorithm (with appropriate Map).
	public static Map<String,List<String>> computeAdjacentWordsSlow( List<String> theWords )
	{
		Map<String,List<String>> adjWords = new HashMap<String,List<String>>( );
		
		String [ ] words = new String[ theWords.size( ) ];
		
		theWords.toArray( words );	
		for( int i = 0; i < words.length; i++ )
			for( int j = i + 1; j < words.length; j++ )
				if( oneCharOff( words[ i ], words[ j ] ) )
				{
					update( adjWords, words[ i ], words[ j ] );
					update( adjWords, words[ j ], words[ i ] );
				}
		
		return adjWords;
	}
	
	// Computes a map in which the keys are words and values are Lists of words
	// that differ in only one character from the corresponding key.
	// Uses a quadratic algorithm (with appropriate Map), but speeds things up a little by
	// maintaining an additional map that groups words by their length.
	public static Map<String,List<String>> computeAdjacentWordsMedium( List<String> theWords )
	{
		Map<String,List<String>> adjWords = new HashMap<String,List<String>>( );
		Map<Integer,List<String>> wordsByLength = new HashMap<Integer,List<String>>( );
		
		  // Group the words by their length
		for( String w : theWords )
			update( wordsByLength, w.length( ), w );
		
		  // Work on each group separately
		for( List<String> groupsWords : wordsByLength.values( ) )
		{
			String [ ] words = new String[ groupsWords.size( ) ];
		
			groupsWords.toArray( words );	
			for( int i = 0; i < words.length; i++ )
				for( int j = i + 1; j < words.length; j++ )
					if( oneCharOff( words[ i ], words[ j ] ) )
					{
						update( adjWords, words[ i ], words[ j ] );
						update( adjWords, words[ j ], words[ i ] );
					}
		}
		
		return adjWords;
	}
	
	
	// Computes a map in which the keys are words and values are Lists of words
	// that differ in only one character from the corresponding key.
	// Uses an efficient algorithm that is O(N log N) with a TreeMap, or
	// O(N) if a HashMap is used.
	public static Map<String,List<String>> computeAdjacentWords( List<String> words )
	{
		Map<String,List<String>> adjWords = new HashMap<String,List<String>>( );
		Map<Integer,List<String>> wordsByLength = new HashMap<Integer,List<String>>( );
	
		  // Group the words by their length
		for( String w : words )
			update( wordsByLength, w.length( ), w );

		  // Work on each group separately
		for( Map.Entry<Integer,List<String>> entry : wordsByLength.entrySet( ) )
		{	
			List<String> groupsWords = entry.getValue( );
			int groupNum = entry.getKey( );
			
			// Work on each position in each group
			for( int i = 0; i < groupNum; i++ )
			{
				// Remove one character in specified position, computing representative.
				// Words with same representative are adjacent, so first popular
				// a map
				Map<String,List<String>> repToWord = new HashMap<String,List<String>>( );
				
				for( String str : groupsWords )
				{
					String rep = str.substring( 0, i ) + str.substring( i + 1 );
					update( repToWord, rep, str );
				}
				
				// and then look for map values with more than one string
				for( List<String> wordClique : repToWord.values( ) )
					if( wordClique.size( ) >= 2 )
						for( String s1 : wordClique )
							for( String s2 : wordClique )
								if( s1 != s2 )
									update( adjWords, s1, s2 );
			}
		}
		
		return adjWords;
	}
				
	// Find most changeable word: the word that differs in only one
	// character with the most words. Return a list of these words, in case of a tie.
	public static List<String> findMostChangeable( Map<String,List<String>> adjacentWords )
	{
		List<String> mostChangeableWords = new ArrayList<String>( );
		int maxNumberOfAdjacentWords = 0;
		
		for( Map.Entry<String,List<String>> entry : adjacentWords.entrySet( ) )
		{
			List<String> changes = entry.getValue( );
			
			if( changes.size( ) > maxNumberOfAdjacentWords )
			{
				maxNumberOfAdjacentWords = changes.size( );
				mostChangeableWords.clear( );
			}
			if( changes.size( ) == maxNumberOfAdjacentWords )
				mostChangeableWords.add( entry.getKey( ) );
		}
		
		return mostChangeableWords;
	}	
	
	public static void printMostChangeables( List<String> mostChangeable,
			                                 Map<String,List<String>> adjacentWords )
	{
		for( String word : mostChangeable )
		{
			System.out.print( word + ":" );
			List<String> adjacents = adjacentWords.get( word );
			for( String str : adjacents )
				System.out.println( " " + str );
			System.out.println( " (" + adjacents.size( ) + " words)" );
		}
	}	
	
	public static void printHighChangeables( Map<String,List<String>> adjacentWords,
			                                 int minWords )
    {
		for( Map.Entry<String,List<String>> entry : adjacentWords.entrySet( ) )
		{
			List<String> words = entry.getValue( );
			
			if( words.size( ) >= minWords )
			{
				System.out.print( entry.getKey( ) + " )" + words.size( ) + "):" );
				for( String w : words )
					System.out.print( " " + w );
				System.out.println( );
			}
		}
    }	
	
	// After the shortest path calculation has run, computes the List that
	// contains the sequence of word changes to get from first to second.
	public static List<String> getChainFromPreviousMap( Map<String,String> prev,
			                                            String first, String second )
	{
		LinkedList<String> result = new LinkedList<String>( );
		
        if( prev.get( second ) != null )
            for( String str = second; str != null; str = prev.get( str ) )
                result.addFirst( str );
		
		return result;
	}
	
	// Runs the shortest path calculation from the adjacency map, returning a List
	// that contains the sequence of words changes to get from first to second.
	public static List<String> findChain( Map<String,List<String>> adjacentWords, String first, String second )			
	{
		Map<String,String> previousWord = new HashMap<String,String>( );
		Queue<String> q = new LinkedList<String>( );
		
		q.add( first );
		while( !q.isEmpty( ) )
		{
			String current = q.element( ); q.remove( );
			List<String> adj = adjacentWords.get( current );
			
			if( adj != null )
				for( String adjWord : adj )
					if( previousWord.get( adjWord ) == null )
					{
						previousWord.put( adjWord, current );
						q.add( adjWord );
					}												
		}
		
		previousWord.put( first, null );
		
		return getChainFromPreviousMap( previousWord, first, second );
	}
	
	// Runs the shortest path calculation from the original list of words, returning
	// a List that contains the sequence of word changes to get from first to
	// second. Since this calls computeAdjacentWords, it is recommended that the
	// user instead call computeAdjacentWords once and then call other findChar for
	// each word pair.
	public static List<String> findChain( List<String> words, String first, String second )
	{
		Map<String,List<String>> adjacentWords = computeAdjacentWords( words );
		return findChain( adjacentWords, first, second );
	}
	
	public static void main( String [ ] args ) throws IOException
	{
		long start, end;
		
		FileReader fin = new FileReader( "dict.txt" );
		BufferedReader bin = new BufferedReader( fin );
		List<String> words = readWords( bin );
		System.out.println( "Read the words..." + words.size( ) );
		Map<String,List<String>> adjacentWords;
		
		start = System.currentTimeMillis( );
		adjacentWords = computeAdjacentWords( words );
		end = System.currentTimeMillis( );
		System.out.println( "Elapsed time FAST: " + (end-start) );

		start = System.currentTimeMillis( );
		adjacentWords = computeAdjacentWordsMedium( words );
		end = System.currentTimeMillis( );
		System.out.println( "Elapsed time MEDIUM: " + (end-start) );
	
		
		start = System.currentTimeMillis( );
		adjacentWords = computeAdjacentWordsSlow( words );
		end = System.currentTimeMillis( );
		System.out.println( "Elapsed time SLOW: " + (end-start) );

		
		// printHighChangeables( adjacentWords, 15 );
		
		System.out.println( "Adjacents computed..." );
		List<String> mostChangeable = findMostChangeable( adjacentWords );
		System.out.println( "Most changeable computed..." );
		printMostChangeables( mostChangeable, adjacentWords );
		
		BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
		
		for( ; ; )
		{
			System.out.println( "Enter two words: " );
			String w1 = in.readLine( );
			String w2 = in.readLine( );
			
			List<String> path = findChain( adjacentWords, w1, w2 );
			System.out.print( path.size( ) + "..." );
			for( String word : path )
				System.out.print( " " + word );
			System.out.println( );	
		}
	}
}