Google Code Jam 2009 - Alien Language

Neste post vou discutir o primeiro problema da rodade de qualificação do Google Code Jam 2009. Se você não quiser ver a solução (ou preferir tentar resolver primeiro), pare de ler por aqui e vá para a página oficial.

O Problema

O enunciado completo está, é claro, na página oficial. Segue um resumo:

• É fornecido um conjunto (dicionário) de D palavras, todas com exatamente L letras minúsculas ('a' a 'z'). No pior caso (large input) D pode ser 5000 e L 15.
• Devem ser resolvidos N casos de teste. No large input N pode chegar a 500.
• Em cada caso de teste é preciso responder quantas palavras do dicionário atendem a um determinado padrão.
• O padrão contem L partes, cada uma correspondendo a uma letra da palavra. Uma parte pode ser uma letra isolada (indicando que somente ela pode ser aceita nesta posição) ou uma sequência de letras cercada por parenteses (indicando que pode ser aceita qualquer uma destas letras nesta posição).
  

Por exemplo, considerando L = 3, D = 5 e o dicionário

aaa
abc
baa
bbb
xyz

o padrão (ab)a(ac) é atendido por duas palavras (aaa e baa).

Minha Solução

Adotei uma solução "força-bruta", gerando as combinações correspondente ao padrão e procurando-as, uma a uma, no dicionário. Para otimizar a busca no dicionário, ele é ordenado (usando o qsort da biblioteca do C) e feita uma busca binária. Cheguei a pensar em algo mais sofisticado, mas o dicionário é relativamente pequeno (5000 itens requerem no máximo 13 comparações na busca binária).

Minha primeira versão, que gerava todas as combinações, estava muito lenta. Para acelerar, eu passei a testar as combinações parciais e deixei de gerar combinações cujo começo já não estivessem no dicionário. Isto é útil na medida em que o tamanho das palavras aumenta e poucas palavras atendam ao padrão. Não é maravilhoso, mas conseguiu resolver o large input dentro do tempo estipulado (com boa folga).

O meu código ficou assim (qualquer semelhante com a minha solução do primeiro problema do ano anterior é mero cut-and-paste)

//
// Google CodeJam 2009 - Qualification Round, Problem A
// DQuadros
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Dictionary
#define MAX_WORDS 5000
#define MAX_L     15
int nW = 0;
char Words [MAX_WORDS][MAX_L+1];
int order [MAX_WORDS];

// Compare words for qsort
int compWord (const void *elem1, const void *elem2)
{
  int i1 = *((int *) elem1);
  int i2 = *((int *) elem2);
  int dif = strcmp (Words[i1], Words[i2]);
  return dif;
}

// Find a partial Word
// (good old binary search)
int FindWordN (char *w, int n)
{
  int first, last, mid, dif;

  first = 0;
  last = nW-1;
  while (last >= first)
  {
      mid = (last+first)/2;
      dif = memcmp (Words[order[mid]], w, n);
      if (dif == 0)
          return mid;
      else if (dif < 0)
          first = mid + 1;
      else
          last = mid - 1;
  }
  return -1;  // not found
}

void main (void)
{
  int iCase, nCases;
  int L, D;
  char word [16];
  int nHits;
  char query [26*15+1];
  char qt [15] [27];
  int pos [15];
  int i, j, k;

  scanf ("%d %d %d\n", &L, &D, &nCases);

  // Read the dictonary
  for (nW = 0; nW < D; nW++)
  {
   gets (word);
      strcpy (Words[nW], word);
      order[nW] = nW;
  }
  qsort (order, nW, sizeof(int), compWord);

  for (iCase = 1; iCase <= nCases; iCase++)
  {
      // Process the query
  gets (query);
      nHits = 0;
      for (i = j = 0; query[i] != 0; i++, j++)
      {
          if (query[i] == '(')
          {
              i++;
              for (k = 0; query[i] != ')'; i++, k++)
                  qt [j][k] = query[i];
              qt [j][k] = 0;
          }
          else
          {
              qt [j][0] = query [i];
              qt [j][1] = 0;
          }
      }

      i = 0;
      pos[0] = 0;
      word[L] = 0;
      while (1)
      {
          word[i] = qt[i][pos[i]];
          if (FindWordN (word, i+1) != -1)
          {
              if (i == (L-1))
              {
                  nHits++;
              }
              else
              {
                  i++;
                  pos[i] = -1;
              }
          }
          pos[i]++;
          while (qt[i][pos[i]] == 0)
          {
              i--;
              if (i < 0)
                  break;
              pos[i]++;
          }
          if (i < 0)
              break;
      }

      printf ("Case #%d: %d\n", iCase, nHits);
  }

}

Uma Solução Melhor

Uma das coisas legais no Code Jam é que o código fonte dos participantes fica disponível para download, o que permite garimpar soluções interessantes. No caso eu "encontrei ouro" logo na solução de quem ficou em primeiro (que se identifica como 'liszt1990').

Ao invés de gerar as combinações, o que ele faz é testar cada palavra do dicionário contra o padrão. Isto é melhor, pois ele utiliza uma forma muito eficiente para testar se uma palavra atende ao padrão. Cada parte do padrão é expandida para um vetor de 26 posições, cada uma indicando se a letra correspondente é aceita. O teste de uma posição se resume assim a uma indexação.

O código abaixo é a minha implementação desta ideia (o código original de liszt1990 pode ser baixado do site).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Dictionary
#define MAX_WORDS 5000
#define MAX_L     15
int nW = 0;
char Words [MAX_WORDS][MAX_L+1];

void main (void)
{
  int iCase, nCases;
  int L, D;
  int nHits;
  char query [28*15+1];
  char qt [15] [26];
  int i, j;

  scanf ("%d %d %d\n", &L, &D, &nCases);

  // Read the dictonary
  for (nW = 0; nW < D; nW++)
   gets (Words[nW]);

  for (iCase = 1; iCase <= nCases; iCase++)
  {
      // Process the query
      gets (query);
      memset (qt, 0, sizeof(qt));
      for (i = j = 0; query[i] != 0; i++, j++)
      {
          if (query[i] == '(')
          {
              i++;
              for (; query[i] != ')'; i++)
                  qt [j][query[i]-'a'] = 1;
          }
          else
          {
              qt [j][query[i]-'a'] = 1;
          }
      }

      // Check words in dictionary
      nHits = 0;
      for (i = 0; i < nW; i++)
      {
          for (j = 0; j < L; j++)
              if (qt [j] [Words[i][j]-'a'] == 0)
                  break;
          if (j == L)
              nHits++;
      }

      printf ("Case #%d: %d\n", iCase, nHits);
  }

}