import java.io.*;
import java.util.Enumeration;
import rpi.goldsd.container.*;
import rpi.goldsd.graph.*;

public class Ladders
{
  public static void main( String[] args )
  {
    int numWords = 0;
    String strings[] = new String[5757];

    try
    {
      FileInputStream istream = new FileInputStream( "words.dat" );
      BufferedReader in = new BufferedReader( new InputStreamReader( istream ) );

      while ( in.ready() )
      {
        String s = in.readLine();
        if ( s.charAt( 0 ) != '*' && s.length() > 5 && s.charAt( 5 ) == '*' )
//        if ( s.charAt( 0 ) != '*' )
          strings[numWords++] = new String( s.substring( 0, 5 ) );
      }

      System.out.println( "Encountered " + numWords + " words." );
      in.close();
    }
    catch( IOException e )
    {
      System.err.println( e );
      System.exit(0);
    }


    int LEN = 5;
    Graph G = new Graph( "Ladders Graph" );
    Vertex V[] = new Vertex[numWords];
    LadderStr strs[][] = new LadderStr[numWords][LEN];

    for ( int i = 0 ; i < numWords ; i++ )
    {
      V[i] = new Vertex( strings[i] );
      G.add( V[i] );
      for ( int j = 0 ; j < LEN ; j++ )
        strs[i][j] = new LadderStr( strings[i], j, V[i] );
    }


    Table tables[] = new Table[LEN];
    for ( int i = 0 ; i < LEN ; i++ )
      tables[i] = new Table( 127 );

    for ( int i = 0 ; i < strs.length ; i++ )
    {
      for ( int j = 0 ; j < LEN ; j++ )
      {
        Enumeration e = tables[j].elements( strs[i][j].hash() );

        while ( e.hasMoreElements() )
        {
          LadderStr LS = (LadderStr)e.nextElement();
          if ( LS.similar( strs[i][j] ) )
          {
            Edge E = new Edge( V[i], LS.associatedVertex, 1.0 );
            G.add( E );
          }
        }

        tables[j].add( strs[i][j] );
      }

      // Display the progress ...
      if ( i % 100 == 0 )
        System.out.println( "Processed word #" + i );
    }

    System.out.println( "GENERATED GRAPH HAS " + G.numEdges() + " EDGES!" );

    BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) );

    while ( true )
    {
      String startWord = "", endWord = "";

      try
      {
        String userInput = "";
        boolean found = false;
        while ( ! found )
        {
          System.out.println( "Please enter starting word:" );
          userInput = stdin.readLine();
          if ( userInput.length() != 5 )
            System.out.println( "Starting word must be 5 letters long." );
          else
          {
            startWord = new String( userInput.substring( 0, 5 ) );
            if ( G.contains( new Vertex( startWord ) ) )
              found = true;
            else
              System.out.println( startWord + " not found -- please try again." );
          }
        }

        found = false;
        while ( ! found )
        {
          System.out.println( "Please enter ending word:" );
          userInput = stdin.readLine();
          if ( userInput.length() != 5 )
            System.out.println( "Ending word must be 5 letters long." );
          else
          {
            endWord = new String( userInput.substring( 0, 5 ) );
            if ( G.contains( new Vertex( endWord ) ) )
              found = true;
            else
              System.out.println( endWord + " not found -- please try again." );
          }
        }
      }
      catch( IOException e )
      {
        System.err.println( e );
        System.exit(0);
      }

      System.out.println();
      System.out.println( "Attempting to construct word ladder from " );
      System.out.println( startWord + " to " + endWord + "." );

      Vertex startVertex = G.mapToVertex( new Str( startWord ) );
      Vertex endVertex = G.mapToVertex( new Str( endWord ) );
      boolean pathExists = true;
      Path P = null;

      try
      {
        P = Algorithms.findShortestPath( startVertex, endVertex );
      }
      catch( PathDoesNotExistException E )
      {
        System.out.println( "Sorry, a path does not exist ..." );
        pathExists = false;
      }

      if ( pathExists )
      {
        System.out.println();
        System.out.println( "Found Path with " + P.length() + " edges:" );
        System.out.println( P );
      }
    }
  }
}



class LadderStr extends Str
{
  private int omitPosition;
  public Vertex associatedVertex;

  public LadderStr()
  {
    super();
    omitPosition = -1;
    associatedVertex = null;
  }

  public LadderStr( String s, int omitPosition, Vertex V )
  {
    super( s );
    this.omitPosition = omitPosition;
    this.associatedVertex = V;
  }

  public int hash()
  {
    int result = 0;
    char[] chars = string.toCharArray();

    for ( int i = 0 ; i < chars.length ; i++ )
      if ( i != omitPosition )
        result += chars[i] - 'a';

    return result;
  }

  public boolean similar( LadderStr s )
  {
    char[] chars1 = string.toCharArray();
    char[] chars2 = s.string.toCharArray();

    for ( int i = 0 ; i < chars1.length ; i++ )
      if ( i != omitPosition && chars1[i] != chars2[i] )
        return false;

    return true;
  }
}