Google Code Jam – Alien Language

O legal do Twitter é que você muitas vezes fica sabendo de coisas que normalmente você não ficaria sabendo. Na última semana, enquanto lia as mensagens recentes, vi uma mensagem do @google dizendo que as inscrições para o Google Code Jam iam se encerrar em dois dias.

Cliquei no link que acompanhava a mensagem e descobri o Google Code Jam, um desafio proposto pelo Google com vários “rounds”. Cada etapa funciona da seguinte maneira:

  • São divulgados 3 problemas de lógica que devem ser resolvidos.
  • Há um tempo para resolução destes 3 problemas ( Na qualificação foram 24 horas)
  • Cada problema possui uma descrição do que deve ser feito.
  • Cada problema possui um formato de arquivo que será disponibilizado e será processado pela aplicação. O arquivo contém os dados de entrada para sua aplicação.
  • No final do problema há um exemplo deste arquivo e um modelo de arquivo de saída contendo a solução para o problema proposto.
  • Após desenvolver sua aplicação, você deve fazer o download de apenas um arquivo contendo alguns casos para resolver.
  • Você tem 4 minutos para rodar seu programa com esse arquivo disponibilizado pelo google e postar o arquivo de saída com a solução e seu código fonte, automaticamente eles testam o resultado e informam se está correto ou não. Caso esteja incorreto, ele vai lhe tirar alguns pontos e você pode corrigir seu programa e tentar novamente.
  • Após funcionar com o arquivo com apenas algumas soluções você deve tentar com o arquivo de entrada maior e com mais possibilidades, este arquivo não exibirá se você acertou ou não na hora, somente ao término da rodada.

Alien Language

Após anos de estudo, os cientista dos laboratórios do Google descobriram uma língua extraterrestre sendo transmitida de um planeta distante. Esta língua extraterrestre é unica em cada uma de suas palavras, cada palavra consiste de exatamente L letras minusculas. Também existem exatamente D palavras nesta língua.

Um dicionário com todas as palavras na lingua alienigena foi criado, o próximo passo foi descobrir que os aliens tem transmitido mensagens para terra na década que passou. Infelizmente, esses sinais enfraqueceram devido a distancia entre os dois planetas e algumas palavras foram má-interpretadas.Para ajudar os cientistas a decifrar estas mensagens, eles pediram a você que desenvolva um algoritmo que determine o número possível de interpretações para um dado padrão.

O padrão consiste de exatamente L marcações. Cada marcação é uma única letra minuscula (os cientistas tem certeza desta letra) ou um grupo de letras minusculas entre parenteses ( and). Por Exemplo: (ab)d(dc) significa que a primeira letra pode ser a ou b, a segunda letra deve ser d e a ultima letra pode ser um d ou c. De qualquer maneira, o padrão (ab)d(dc) suporta umas dessas quatro possibilidades: add,adc,bdd,bdc.

O arquivo que eles disponibilizarão está no seguinte formato:

3 5 4

abc

bca

dac

dbc

cba

(ab)(bc)(ca)

abc

(abc)(abc)(abc)

(zyx)bc

A primeira linha contém: L D N

No exemplo acima: 3 5 4

Onde L é a quantidade de letras de cada palavra, no exemplo 3 letras, D é a quantidade de palavras capturadas nas transmissões e N são a quantidade de padrões no arquivo.

No exemplo dado, cada palavra contém no máximo 3 letras, as próximas 5 linhas correspondem as 5 palavras capturadas e em seguida as palavras capturadas estão os padrões a serem seguidos.

Palavras capturadas:

  • abc
  • bca
  • dac
  • dbc
  • cba

Padrões:

  • (ab)(bc)(ca) – Começa com a ou b, seguido de b ou c e termina com c ou a.
  • abc – Deve começar com a seguido de um b e c terminando a palavra.
  • (abc)(abc)(abc) – Pode conter em cada uma das letras a ou b ou c
  • (zyx)bc – Deve começar com z ou y ou z e em seguida um b seguido de um c.

O arquivo de saída deve conter: Para cada um dos padrões, quantas palavras são aceitas pelo padrão, para o exemplo acima deve ser gerado um arquivo contendo:

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

 

 

 

Minha solução

Assim que li o problema, me lembrei de duas coisas, uma que aprendi com os amigos e outra que aprendi na faculdade. Me lembrei de minha professora, explicando sobre a máquina de Turing na aula de Autômatos, matéria que precede Compiladores, explicando que uma Língua é formada de um “Alfabeto” e de suas regras para ser aplicado, lembrei de sua representação através de grafos, etc..etc..

Com a lembrança da faculdade já vi que conseguiria resolver este problema, mas ai lembrei de algo que vi a muito tempo atrás com um dos meus amigos resolvendo um problema semelhante, quando desenvolvemos um software para aplicar regras em uma série de valores alfa-numéricos, e não foi o Smart – Expressões Regulares.

Basicamente o que temos acima são expressões regulares e textos a serem validados pela expressão regular.

Como C# já possui os recursos necessários para trabalharmos com Regular Expressions (System.Text.RegularExpressions).

Para fazer download do meu programa para solucionar, clique no link abaixo.

[download id=”8″]

Para baixar arquivos de entrada para testar sua aplicação:

http://code.google.com/codejam/contest/dashboard?c=90101#

No link acima, você faz o download de um arquivo nos padrões acima e pode postar o aruqivo de saída para que seja conferido pelo Google instantaneamente.

2 Comentários


  1. Esta incorreto.

    funciona soh nesse caso do sample.in

    mas o correto é utilizar (a|z) e nao [az]
    senao com o [az] ele estaria testando qualquer letra de ‘a’ até ‘z’


  2. Mathias, farei alguns testes e obrigado pela dica. Ele também funcionou com mais 3 amostras de arquivos (sample.in) e com o large e small inputs fornecidos pelo Google.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Please leave these two fields as-is:

Protected by Invisible Defender. Showed 403 to 755.891 bad guys.