// ----------------------------------------------------------------
// Imports
// ----------------------------------------------------------------

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

// ----------------------------------------------------------------
// Phone
// ----------------------------------------------------------------

public class Phone
{
   // ----------------------------------------------------------------
   // The letters associated with each digit on a phone.  Note that in
   // addition to the standard phone letters, we also use "o" for 0
   // and "i" for 1
   // ----------------------------------------------------------------

   public static final String[] LETTERS =
   {
      "o", "i", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
   };

   // ----------------------------------------------------------------
   // lettersForDigit - Return the String from 'LETTERS' that goes
   //                   with the specified 'digit'.  Throw an
   //                   Exception of 'digit' is not in the range
   //                   of 0 -> 9.
   // ----------------------------------------------------------------

   public static String lettersForDigit(int digit)
   {
      if(digit < 0 || digit >= LETTERS.length)
         throw new RuntimeException("Invalid parameter value: " + digit);

      return(LETTERS[digit]);
   }

   // ----------------------------------------------------------------
   // getWords - Return an array of all words from 'fileName' or
   //            throw an Exception if the file could not be read.
   // ----------------------------------------------------------------

   public static String[] getWords(String fileName) throws Exception
   {
      BufferedReader reader = new BufferedReader(new FileReader(fileName));

      ArrayList<String> lines = new ArrayList<String>();

      String line;

      while((line = reader.readLine()) != null)
         lines.add(line);

      reader.close();

      return(lines.toArray(new String[lines.size()]));
   }

   // ----------------------------------------------------------------
   // showWords - Show all words that can be constructed from
   //             the letters in 'remaining' from 'words'.  The
   //             words we've alraedy found are in 'prefix'.
   // ----------------------------------------------------------------

   public static void showWords(
      String prefix, String remaining, String[] words
   )
   {
      for(String word : words)
      {
         if(remaining.startsWith(word))
         {
            String left  = remaining.substring(0, word.length());
            String right = remaining.substring(word.length());

            if(!prefix.equals(""))
               left = prefix + " " + left;

            if(right.equals(""))
               System.out.printf("Solution: %s\n", left);

            else
               showWords(left, right, words);
         }
      }
   }

   // ----------------------------------------------------------------
   // showWords - Show all words from 'words' that can be made from
   //             the letters in 'theString'.
   // ----------------------------------------------------------------

   public static void showWords(String theString, String[] words)
   {
      showWords("", theString, words);
   }

   // ----------------------------------------------------------------
   // findWords - Find and display all word from 'words' that can be
   //             made from the letters that correspond to the
   //             specified 'digits'.
   // ----------------------------------------------------------------

   public static void findWords(int[] digits, String[] words)
   {
      String[] digitLetters = new String[digits.length];
      int[]    sizes        = new int[digits.length];

      for(int i = 0; i < digits.length; i ++)
      {
         digitLetters[i] = lettersForDigit(digits[i]);
         sizes[i]        = digitLetters[i].length();
      }

      Sequence sequence = new Sequence(sizes);
      int[]    indices  = null;

      while((indices = sequence.getNext()) != null)
      {
         String theString = "";

         for(int i = 0; i < indices.length; i ++)
            theString += digitLetters[i].charAt(indices[i]);

         showWords(theString, words);
      }
   }

   // ----------------------------------------------------------------
   // fixNumber - Remove any separator chars (whitespace, '-' and
   //             '.') from 'theNumber' while preserving all
   //             digits.  Throws a RuntimeExeption if 'theNumber'
   //             contains any non-digit, non-separator characters.
   // ----------------------------------------------------------------

   public static String fixNumber(String theNumber)
   {
      String theString = "";

      for(int i = 0, n = theNumber.length(); i < n; i ++)
      {
         char c = theNumber.charAt(i);

         boolean ignore =
            (c == '-' || c == '.' || Character.isWhitespace(c));

         if(!ignore)
         {
            if(!Character.isDigit(c))
            {
               throw new RuntimeException(
                  "Invalid phone number: [" + theNumber + "]"
               );
            }

            theString += c;
         }
      }

      return(theString);
   }

   // ----------------------------------------------------------------
   // numberToDigits - Convert 'theNumber' into an array of int digits
   // ----------------------------------------------------------------

   static int[] numberToDigits(String s)
   {
      String theNumber = fixNumber(s);
      int[] digits     = new int[theNumber.length()];

      for(int i = 0; i < digits.length; i ++)
         digits[i] = (int)(theNumber.charAt(i) - '0');

      return(digits);
   }

   // ----------------------------------------------------------------
   // main
   // ----------------------------------------------------------------

   public static void main(String[] args) throws Exception
   {
      findWords(
         numberToDigits(args.length == 0 ? "864-2676" : args[0]),
         getWords("words.txt")
      );
   }
}