Google Code Jam - Saving the Universe

07/17/2008 22:52:00 By Felipe Pessoto

Infelizmente meus planos de participar do Google Code Jam já eram. Marquei pra competir no dia 26(Sábado), até ai tudo ok, mas pra ajudar fizeram as eliminatórias HOJE, numa quinta-feira. Claro, como a maioria das pessoas estava trabalhando, quando cheguei ja tinha acabado o tempo...
De qualquer forma fiz o primeiro desafio, em C#, vou postar o código fonte pra vocês.

O desafio é salvar o Universo =). Segundo o Google, se você buscar pelo nome de um buscador nele mesmo(Ex.: Buscar Google, no Google) o universo vai implodir. Você recebe uma lista de Buscadores e a lista de Palavras à buscar(que vai ser sempre o nome de um dos buscadores). Então tem que gerar um algoritmo que faça que a busca, sem buscar a Palavra no Buscador com mesmo nome(pra nao implodir o Universo). Até aí nada demais, seria só um if pra fazer o switch entre qual buscador vai usar cada vez.

O desafio é fazer esse switch da forma mais otimizada possível, dizendo qual o número mínimo de switchs em cada caso, exemplos:

5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

O primeiro número indica a quantidade de Buscadores, seguido pelos nomes dos mesmo, depois o número de Searchs e as respectivas Buscas.

No caso acima, devemos retornar:

Case #1: 1
Case #2: 0

Segue o código:

class Saving_the_Universe
{
    const string CaminhoEntrada = @"C:\Documents and Settings\Felipe\Meus documentos\Visual Studio 2008\Projects\CodeJam\CodeJam\Saving_the_Universe_Entrada.txt";
    const string CaminhoSaida = @"C:\Documents and Settings\Felipe\Meus documentos\Visual Studio 2008\Projects\CodeJam\CodeJam\Saving_the_Universe_Saida.txt";
 
    static List<string> Buscadores = new List<string>();
    static List<string> Querys = new List<string>();
 
    static void Main(string[] args)
    {
        StreamReader Entrada = new StreamReader(CaminhoEntrada);
        if (File.Exists(CaminhoSaida))
            File.Delete(CaminhoSaida);
 
        StreamWriter Saida = new StreamWriter(CaminhoSaida);
 
        int CasoAtual = 1;
        int CasosTotais = int.Parse(Entrada.ReadLine());
 
        string Temp = "";
 
        while (CasoAtual <= CasosTotais)
        {
            Buscadores.Clear();
            Querys.Clear();
 
            Temp = Entrada.ReadLine();
            for (int i = 0; i < int.Parse(Temp); i++)
            {
                Buscadores.Add(Entrada.ReadLine());
            }
 
            Temp = Entrada.ReadLine();
            for (int i = 0; i < int.Parse(Temp); i++)
            {
                Querys.Add(Entrada.ReadLine());
            }
 
            Saida.WriteLine("Case #{0}: {1}", CasoAtual, Algoritmo());
 
            CasoAtual++;
        }
 
        Entrada.Close();
        Saida.Close();
        Console.ReadKey(true);
    }
 
    static int Algoritmo()
    {
        Dictionary<string, int> QuerysContadas = new Dictionary<string, int>();
        //Pra cada buscador, conta quantas Querys existem chamando eles
        foreach (var item in Buscadores)
        {
            QuerysContadas.Add(item, Querys.Count<string>(p => p == item));
        }
 
        if (QuerysContadas.Values.Min() == 0)
            return 0;
 
 
        int UltimoIndice = 0;
        List<string> PalavraBuscadasNaOrdem = new List<string>();
 
        for (int i = 0; i < Querys.Count; i++)
        {
            if (PalavraBuscadasNaOrdem.Count == 0 || Querys[i] == PalavraBuscadasNaOrdem[PalavraBuscadasNaOrdem.Count - 1])
            {
                foreach (var NomeBuscador in Buscadores)
                {
                    if (Querys.IndexOf(NomeBuscador, i) == -1)
                        return PalavraBuscadasNaOrdem.Count;
 
                    if (UltimoIndice < Querys.IndexOf(NomeBuscador, i) && (PalavraBuscadasNaOrdem.Count == 0 || NomeBuscador != Querys[i]))
                        UltimoIndice = Querys.IndexOf(NomeBuscador, i);
                }
                PalavraBuscadasNaOrdem.Add(Querys[UltimoIndice]);
            }
        }
 
        return 1;
    }
}

Google Code Jam - Alien Numbers e Always Turn Left

06/25/2008 14:35:00 By Felipe Pessoto

Conseguir fazer os dois primeiros testes do primeiro concurso, o Alien Numbers e Always Turn Left. É possível também baixar o código dos vencedores, que são na maioria em C++.

Queria saber se alguem mais fez em C#, pra trocar umas idéias sobre o algoritmo. O meu ficou bem grande, 460 linhas, fiz orientado a objetos e tudo comentando e separado em métodos, talvez por isso tenha ficado tão grande.

Esse fim de semana vou participar do concurso e quem sabe da pra ganhar uns trocados...

Ah, o primeiro colocado do primeiro concurso que levou U$10000,00 é algum tipo de gênio, o que só levou vinte e poucos minutos pra fazer cada um dos 4 testes, levei 2h pra fazer o primeiro e 3h pro segundo. Do segundo colocado em diante demoraram várias dezenas de horas.

Quem quiser o código fonte é só pedir. Não vou postar pelo tamanho do mesmo.

Google Code Jam

06/20/2008 14:35:00 By Felipe Pessoto

O desafio mundial da Google aos melhores programadores do mundo e que consiste em resolver quatro problemas de algoritmos no menor tempo possível está com inscrições abertas até o próximo dia 17 de julho. A finais regionais acontecerão em Belo Horizonte, em outubro.

Os 500 melhores classificados ganharão uma viagem com tudo pago para as semifinais na capital mineira, de onde serão selecionados os 100 primeiros para a grande final na sede da Google em Mountain View. Além da viagem, também há prêmios em dinheiro:

· 1º lugar: US$ 10 mil

· 2º lugar: US$ 5 mil

· 3º lugar: US$ 2,5 mil

· 4º - 10º lugares: US$ 1,5 mil cada

· 11º - 30º lugares: US$ 1 mil cada

· 31º - 50º lugares: US$ 750 cada

· 51º - 75º lugares: US$ 500 cada

· 76º - 100º lugares: US$ 250 cada

Citando o comunicado da imprensa:

Uma novidade do Google Code Jam 2008 é a inserção de ferramentas próprias que permitem que os participantes programem em qualquer linguagem. Essas ferramentas foram criadas por uma equipe de funcionários que dedica 20% do seu horário de trabalho a projetos inovadores de seu interesse, e que é formada também por vencedores de Code Jams passados.



Nada mal, faturar um trocado, ter seu nome estampado com glória em sites geek pelo mundo afora e conseguir uma vaguinha em Montain View. Mas não pense que a coisa é fácil... em 2006, para se ter uma idéia, o vencedor latino-americano foi o carioca Fábio Dias Moreira, com um total de 753,4 pontos. Já o campeão mundial foi o russo Petr Mitrichev, com 972,02!

Via: Meio Bit

Nota: Fiz o primeiro teste prático(Alien Numbers). E não é fácil, mas também não é impossível. Demorei 2 horas pra criar o algoritmo, ficaria um pouco atrás do segundo colocado neste teste. Recomendo pra quem quiser praticar um pouco de lógica.