Solution: Google code jam 2009, Qualification Round:Alien Language

  1 package qualificationround2009;
  2 
  3 import java.io.BufferedReader;
  4 import java.io.IOException;
  5 import java.io.InputStreamReader;
  6 
  7 public class AlienLanguage
  8 {
  9 
 10     private static char[][] _words;
 11 
 12     public static void main(String[] args)
 13     {
 14         try
 15         {
 16             BufferedReader br = new BufferedReader(new InputStreamReader(""
 17                     .getClass().getResourceAsStream(
 18                             "/qualificationround2009/A-large-practice.in")));
 19 
 20             String[] caseArgs = br.readLine().split(" ");
 21             // int wordLength = Integer.valueOf(caseArgs[0]);
 22             int wordsNumber = Integer.valueOf(caseArgs[1]);
 23             int caseNumber = Integer.valueOf(caseArgs[2]);
 24 
 25             _words = new char[wordsNumber][];
 26             for (int i = 0; i < wordsNumber; i++)
 27             {
 28                 _words[i] = br.readLine().toCharArray();
 29             }
 30             // Collections.sort(words);
 31 
 32             String testCase;
 33             for (int i = 0; i < caseNumber; i++)
 34             {
 35                 testCase = br.readLine();
 36                 char[][] words = _words;
 37                 int j = 0;
 38                 int k = 0;
 39                 while (j < testCase.length())
 40                 {
 41                     if (testCase.charAt(j) != '(')
 42                     {
 43                         words = getLast(words, k, testCase.charAt(j));
 44                         j++;
 45                         k++;
 46                     }
 47                     else
 48                     {
 49                         String temp = testCase.substring(j + 1, testCase
 50                                 .indexOf(')', j));
 51                         words = getLast(words, k, temp);
 52                         j += temp.length() + 2;
 53                         k++;
 54                     }
 55                 }
 56                 System.out.println("Case #" + (i + 1) + ": " + words.length);
 57             }
 58         }
 59         catch (NumberFormatException e)
 60         {
 61             e.printStackTrace();
 62         }
 63         catch (IOException e)
 64         {
 65             e.printStackTrace();
 66         }
 67     }
 68 
 69     private static char[][] getLast(char[][] words, int k, String str)
 70     {
 71         char[][] temp = new char[words.length][];
 72         int count = 0;
 73         for (int i = 0; i < words.length; i++)
 74         {
 75             if (str.indexOf(words[i][k]) >= 0)
 76             {
 77                 temp[count++] = words[i];
 78             }
 79         }
 80 
 81         char[][] last = new char[count][];
 82         for (int i = 0; i < count; i++)
 83         {
 84             last[i] = temp[i];
 85         }
 86 
 87         return last;
 88     }
 89 
 90     private static char[][] getLast(char[][] words, int k, char charAt)
 91     {
 92         char[][] temp = new char[words.length][];
 93         int count = 0;
 94         for (int i = 0; i < words.length; i++)
 95         {
 96             if (words[i][k] == charAt)
 97             {
 98                 temp[count++] = words[i];
 99             }
100         }
101 
102         char[][] last = new char[count][];
103         for (int i = 0; i < count; i++)
104         {
105             last[i] = temp[i];
106         }
107 
108         return last;
109     }
110 }
111