Google Code Jam 2011: QR_B - Magicka

O segundo problema da rodada de qualificação foi um pouco mais difícil que o primeiro, principalmente se você tentar fazer uma solução mais sofisticada e cometer erros primários (o meu caso).

O Problema

O enunciado oficial, como de costume, possui uma historinha que podemos ignorar. O que o nosso programa precisa fazer é processar uma sequência de letras (A a Z) segundo dois conjuntos de regras. A sequencia de entrada e as regras são a entrada do programa. A sequência de entrada deve ser processada em ordem, letra a letra. À media que as letras vão sendo processadas vai sendo montada uma lista de saída. A saída do programa é o valor final desta lista.

As regras operam somente sobre uma parte das letras (os elementos base na historinha): Q, W, E, R, A, S, D, F.

O primeiro conjunto de regras (composição) determina que determinados pares consecutivos de letras devem ser substituídos por uma outra letra que será colocada na lista. Esta nova letra não é um elemento base e portanto não irá disparar nenhuma regra.

O segundo conjunto de regras (oposição) determina que a lista deve ser esvaziada se contiver (em qualquer posição) uma letra oposta à letra que está sendo processada.

Todas as regras são simétricas (isto é, as duas letras envolvidas podem ser trocadas entre si). As regras de composição devem ser processadas antes das de oposição. Se a letra sendo processada não disparar nenhuma regra ela deve ser anexada ao final da lista.

Considere o seguinte exemplo do enunciado:

• temos uma regra de composição: E E -> Z
• temos uma regra de oposição: Q E limpa a lista
  
• a sequência de entrada é QEEEERA

Processando as letras de entrada uma a uma e montando a lista de saída:

Q [Q]
E [] oposição
E [E]
E [Z] composição
E [Z E]
R [Z E R]
A [Z E R A]

Minha Solução

O problema pode ser resolvido facilmente simulando diretamente as regras, porém eu decidi otimizar o meu processamento.

As regras de composição podem ser armazenadas de forma simples e eficiente como uma tabela bidimensional, onde a linha e coluna são as letras a serem combinadas e o valor na tabela é o resultado da combinação.

As regras de oposição são mais complicadas. Para evitar pesquisas na sequência e nas regras, resolvi montar um mapa de bits para indicar quais letras estão presentes, tanto nas regras de oposição como na lista. Como são 26 letras, este mapa de bits pode ser guardado em um inteiro de 32 bits. Desta forma, o teste das regras de oposição pode ser feito através de uma simples operação lógica de AND. Se nenhuma letra presente estiver nas regras o resultado será zero; um resultado diferente de zero indica que a lista de saída deve ser esvaziada.

A parte complicada é manter o mapa de bits que represente a lista de saída. Inicialmente (e quando a lista for esvaziada por uma oposição) o mapa está zerado. Quando uma letra é colocada na lista o bit correspondente deve ir para um. Quando uma letra é retirada da lista (por uma combinação) o bit correspondente deve ser zerado somente se não exister mais desta letra na lista. A forma que usei para implementar esta lógica foi manter uma contagem das letras na saída.

Um detalhe é que o programa poderia considerar somente as letras correspondentes aos elementos base nos mapas de bit e contagem. Entretanto, achei mais simples e eficiente controlar todas as letras já que isto não atrapalha. Desta forma o programa independe de quem são os elementos base; a única premissa é que as letras geradas pelas combinações não disparam novas regras.

O código é uma reprodução direta destas ideias:

char combine[27][27];
unsigned int opposed[27];

char list[100];
int size;
int qty[27];
unsigned int present;

void main (void)
{
 int iCase, nCases;
    int i, C, D, N;
    char c1, c2, c3;

 scanf ("%d\n", &nCases);
 for (iCase = 1; iCase <= nCases; iCase++)
 {
        scanf ("%d ", &C);
        memset (combine, 0, sizeof(combine));
        for (i = 0; i < C; i++)
        {
            scanf ("%c%c%c ", &c1, &c2, &c3);
            c1 -= '@';
            c2 -= '@';
            c3 -= '@';
            combine [c1][c2] = c3;
            combine [c2][c1] = c3;
        }
        scanf ("%d ", &D);
        memset (opposed, 0, sizeof(opposed));
        for (i = 0; i < D; i++)
        {
            scanf ("%c%c ", &c1, &c2);
            c1 -= '@';
            c2 -= '@';
            opposed [c1] |= (1 << c2);
            opposed [c2] |= (1 << c1);
        }
        scanf ("%d ", &N);
        size = 0;
        present = 0;
        memset (qty, 0, sizeof(qty));
        for (i = 0; i < N; i++)
        {
            scanf ("%c", &c1);
            c1 -= '@';
            if (size == 0)
            {
                // list is empty
                list[size++] = c1;
                qty[c1] = 1;
                present |= (1 << c1);
            }
            else
            {
                c2 = list[size-1];
                c3 = combine[c1][c2];
                if (c3 == 0)
                {
                    if (present & opposed[c1])
                    {
                        // opposed is present, list is cleared
                        size = 0;
                        present = 0;
                        memset (qty, 0, sizeof(qty));
                    }
                    else
                    {
                        // append element
                        list[size++] = c1;
                        present |= (1 << c1);
                        qty[c1]++;
                    }
                }
                else
                {
                    list[size-1] = c3;  // combined
                    if (--qty[c2] == 0)
                        present &= ~(1 << c2);
                }
            }
        }
        scanf ("\n");
        printf ("Case #%d: [", iCase);
        for (i = 0; i < size; i++)
        {
            if (i != 0)
                printf (", ");
            printf ("%c", list[i]+'@');
        }
        printf ("]\n");
 }
}