Google Code Jam - Alien Numbers e Always Turn Left

6/25/2008 6:35:00 PM 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.

Covariância e Contravariância em C#, Parte Dez: Lidando Com Ambiguidades

6/24/2008 2:01:00 PM By Felipe Pessoto

Suponha que fizemos IEnumerable covariante em T. O que este código deve fazer?

class C : IEnumerable<Girafa>, IEnumerable<Tartaruga>
{
    IEnumerator<Girafa> IEnumerable<Girafa>.GetEnumerator()
    {
        yield return new Girafa();
    }
    IEnumerator<Tartaruga> IEnumerable<Tartaruga>.GetEnumerator()
    {
        yield return new Tartaruga();
    }
    // [etc.]
}
 
class Program
{
    static void Main()
    {
        IEnumerable<Animal> animais = new C();
        Console.WriteLine(animais.First().GetType().ToString());
    }
}

Opções:

1) Erro em tempo de compilação.
2) Erro em tempo de execução.
3) Sempre enumera Girafas.
4) Sempre enumera Tartarugas.
5) Escolha entre Girafas e Tartarugas em tempo de execução.
6) Nenhuma das opções acima.

Se você escolheu outra opção além da 1, deveríamos ter um warning em tempo de compilação?

Covariância e Contravariância em C#, Parte Nove: Criando Incompatibilidades

6/24/2008 1:02:00 PM By Felipe Pessoto

Nesta parte vamos discutir quais incompatibilidades teremos ao adicionar este recurso.

Simplesmente adicionando variância às regras de conversão nunca deveria causar nenhuma incompatibilidade. Entretanto, a combinação de se adicionar variância às regras de conversão e fazer alguns tipos terem parâmetros variantes causa uma potencial quebra de compatibilidade.

Geralmente as pessoas sabem que não se deve fazer isso:

if (x is Animal) 
  DoSomething();
else if (x is Girafa) 
  DoSomethingElse(); // nunca executa

porque a segunda condição é totalmente englobada pela primeira. Mas hoje no C# 3.0 é perfeitamente normal escrever:

if (x is IEnumerable<Animal>) 
  DoSomething();
else if (x is IEnumerable<Girafa>) 
  DoSomethingElse();

porque não há qualquer conversão sendo usada entre IEnumerable<Animal> e IEnumerable<Girafa>. Se nós adicionarmos covariância no IEnumerable<T> e o programa compilado contendo o fragmento acima usar a nova biblioteca então o comportamento quando dado um IEnumerable<Girafa> irá mudar. O objeto passará a ser atribuível à IEnumerable<Animal>, e por isso o "is" irá retornar "true", mudando a lógica do programa.

Há também a questão de mudar a semântica dos códigos fonte existentes ou tornar programas compiláveis em programas com erros de compilação. Por exemplo, a resolução da sobrecarga pode falhar onde deveria ser usada com sucesso. Se nós temos:

interface IBar<T>{} // Vindo de outro assembly
...
void M(IBar<Tigre> x){}
void M(IBar<Girafa> x){}
void M(object x) {}
...
IBar<Animal> y = qualquer;
M(y);
Então a resolução da sobrecarga pega a versão que recebe um object porque é a única escolha aplicável. Se nós mudarmos a definição de IBar para

interface IBar<-T>{}


e recompilar então teremos um erro de ambiguidade porque agora todos os três são aplicáveis e não há uma única melhor escolha.

Sempre queremos evitar incompatibilidades se possível, mas as vezes novos recursos são suficientemente atraentes e as incompatibilidades são tão raras que vale a pena. Acho que criando a variância em interfaces e delegates vamos permitir muito mais cenários interessantes do que incompatibilidades.

Será que este recurso irá trazer tantos benefícios que vale a pena gastar tempo desenvolvendo-o pra uma futura versão do C#?

Covariância e Contravariância em C#, Parte Oito: Opções de Sintaxe

6/23/2008 6:13:00 PM By Felipe Pessoto

Como discutimos anteriormente, nós introduzimos variância de interface e delegate em uma hipotética futura versão do C#, então precisamos de uma sintaxe para ela. Aqui estão algumas possibilidades.

Opção 1:

interface IFoo<+T, -U> { T Foo(U u); }

A CLR usa a convenção que estamos usando em toda a série de "+ sendo covariante e - contravariante”. Embora isto tenha algum valor mnemónico (porque + quer dizer "é compatível com um tipo maior"), muitas pessoas (incluindo membros da comissão de design do C#!) têm dificuldades em se lembrar o que é exatamente.

Esta convenção também é utilizada pela linguagem de programação Scala.

Opção 2:

interface IFoo<T:*, *:U> {x

Este indica mais graficamente "alguma coisa que é extendida por T" e "alguma coisa a qual extende U". É similiar as keywords Java, onde elas dizem "extends U" ou "super T".

Embora isto não seja terrível, penso que isto funde um pouco as noções de extensão e compatibilidade de atribuição. Eu não quero implicar que IEnumerable<Animal> é a base de IEnumerable<Girafa>, mesmo que Animal seja a base de Girafa. Em vez disso, quero dizer que IEnumerable<Girafa> é convertível para IEnumerable<Animal>, ou a atribuição é compatível. Eu não quero exceder os conceitos o mecanismo de herança. Isto é ruim, nós estamos unindo classes base com interfaces base.

Opção 3:

interface IFoo<T, U> where T: covariant, U: contravariant {

Novamente, nada mal. O perigo aqui é similar ao dos sinais mais e menos: que ninguém se lembra o que "contravariante" e "covariante" significa. Este tem a vantagem de que pelo menos você pode buscar pelas palavras e achar alguma explicação.

Opção 4:

interface IFoo<[Covariant] T, [Contravariant] U>  {

Similar à opção 3.

Opção 5:

interface IFoo<out T, in U> {

Estamos tomando um rumo diferente com essa sintaxe. Nas opções anteriores nós estávamos descrevendo como o usuário da interface pode trata-lá, respeitando as regras do sistema de conversão de tipos para conversão implícita – que é, quais são as variâncias válidas nos tipos dos parâmetros. Em vez disso, aqui nós estamos descrevendo como o implementador da interface tem a intenção de usar os tipos dos parâmetros.

A desvantagem é que, como discutido em artigos anteriores, você acaba em situações como essa:

delegate void Meta<out T>(Action<T> action);

onde o "out" T seja claramente utilizada em uma posição de entrada.

Google Code Jam

6/20/2008 6:35:00 PM 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.