Ambiguous Codes

An extensive area of research in computer science is the field of communications. With computer networks being part of everyday life of many people, the development of ways for making networks faster, more reliable and secure is constantly needed. This practical need motivates an extensive research activity in the theory behind communications.

The very first thing needed to establish any kind of communication is a common code. A code is a way of changing the form of a piece of information into some other form, in general to make it possible to convey that piece of information from one place to another. Flag codes used by boats and the Morse code used in telegraphy are examples of codes for translating letters into different forms to enable communication over different media.

More formally, a code is a set of strings composed of symbols from one alphabet. Each string defined in the code is called a code word. A message is then composed concatenating a set of code words to convey the information needed. For example, in Morse code the alphabet is composed of the symbols hyphen and dot; letter ``S" is represented by the code word ``...", letter ``O" is represented by the code word ``--", and therefore the distress message ``SOS" in Morse code is ``...--...".

Codes for communication can have many desirable and undesirable properties such as ambiguity, entropy, redundancy, and many more. In this problem we will focus on ambiguity as a key property.

A code is ambiguous when there exists a message using that code that can be partitioned into different sequences of code words. In other words, in an ambiguous code a message may have more than one meaning. For example, consider the binary alphabet, composed of symbols {0,1}. For the code composed of the words {10, 01, 101} the message 10101 can be understood as 10-101 or 101-01 and therefore the code is ambiguous. On the other hand, for the code composed of the words {01, 10, 011} no ambiguous message exists and therefore the code is unambiguous.

As a part of the computer science community, you are required to develop a tester that checks if codes are ambiguous. In case a code is indeed ambiguous, you are also required to report the length (i.e. the number of symbols) of the shortest ambiguous message for that code.

Input

Each test case will consist on several lines. In all test cases the alphabet will be the set of hexadecimal digits (decimal digits plus the uppercase letters ``A" to ``F"). The first line of a test case will contain an integer N (1N100) , the number of code words in the code. Each of the next N lines describes a code word and contains a different and non-empty string of at most 50 hexadecimal digits.

Input is terminated by N = 0 .

Output

For each test case, output a single line with the length of the shortest ambiguous message for the provided code or `-1' if the code is unambiguous.

Sample Input

3
10
01
101
3
AB
BA
ABB
0

Sample Output

5

Solution

/**
 * Exemplo para resolver o problema de AmbiguousCode 
 * Este programa usa uma árvore ordenada priorizada pelos elementos de
 * menor tamanho. Usa um hash para guardar os valores encontrados e se encontrar 
 * outro igual gera uma exception onde a mensagem é a String ambigua.
 * 
 * Não implementei para ler de um arquivo texto, como no enunciado. Isto é muito fácil ;)
 * 
 * 
 * @author Ricardo Alberto Harari - ricardo.harari@gmail.com
 */
package codejam;

import java.util.concurrent.PriorityBlockingQueue;

import com.sun.org.apache.xalan.internal.xsltc.runtime.Hashtable;

/**
 * @author Ricardo A Harari - ricardo.harari@gmail.com
 * 
 */
public class AmbiguousCode {

 private final String[] array = new String[] { "01", "AB", "BA", "ABB", "10", "101" };
 //private final String[] array = new String[] { "AB", "BA", "ABB" };

 private final Hashtable ht = new Hashtable();

 /**
  * 
  * @param pq
  * @throws Exception
  */
 private void process(PriorityBlockingQueue pq) throws Exception {
  if (pq.size() == 0) throw new Exception("-1");
  Node father = pq.poll();
  for (int j = 0; j <>
   Node child = new Node();
   child.father = father;
   child.step = child.father.step + 1;
   child.valueFull = child.father.valueFull;

   String s = array[j];
   Node check = child.father;
   boolean found = false;
   while (!found && check != null) {
    found = check.value.equals(s);
    check = check.father;
   }
   if (!found) {
    child.value = s;
    child.valueFull += s;
    if (ht.get(child.valueFull) != null) throw new Exception(child.valueFull);
    ht.put(child.valueFull, child.valueFull);
    pq.add(child);
   }
  }
 }

 /**
  * 
  * @param args
  */
 public static void main(String[] args) {
  AmbiguousCode c = new AmbiguousCode();
  c.start();
 }

 /**
  * inicio do processo
  */
 private void start() {
  try {
   PriorityBlockingQueue pq = new PriorityBlockingQueue(array.length * array.length);
   pq.clear();
   // adiciona os primeiros elementos na priorityqueue
   for (int i = 0; i <>
    Node n = new Node();
    n.value = array[i];
    n.valueFull = n.value;
    if (ht.get(array[i]) != null) throw new Exception(array[i]);
    ht.put(n.value, n.value);
    pq.offer(n);
   }
   // enquanto tiver elementos, processar
   while (pq.size() > 0) {
    process(pq);
   }
   System.out.println("-1");
  } catch (Exception e) {
   System.out.println(e.getMessage().length());
  }
 }

 /**
  * nó
  * 
  * @author Ricardo Alberto Harari - ricardo.harari@gmail.com
  * 
  */
 class Node implements Comparable {
  Node father = null;
  String value = null;
  String valueFull = null;
  int step = 0;

  /*
   * o segredo esta em comparar o tamanho da string 
   * 
   * desta forma as menores serão processadas primeiro.
   * 
   * (non-Javadoc)
   * 
   * @see java.lang.Comparable#compareTo(java.lang.Object)
   */
  public int compareTo(Node arg0) {
   int l1 = valueFull.length();
   int l2 = arg0.valueFull.length();
   return l1 - l2;
  }
 }

}