André Carlucci

Skeptic .net development

Coding4fun na Way2

Na Way2 a gente passa tanto tempo desenvolvendo software para web que as vezes esquecemos o quanto é desafiador ter que resolver um problema com algoritmos complexos.

Estamos prontos para criar código testável, inverter o controle injetando dependências, fazer mágicas com javascript e domar o hibernate como ninguém, mas tenho notado um certo delay nas poucas tasks que envolvem criação de algoritmos mais sofisticados. O problema é justamente esse, no tipo de software que a gente produz temos poucas situações onde isso é necessário, mas são os pontos mais importantes na diferenciação de nossos produtos.

Para manter nossas habilidades em algoritmos e ao mesmo tempo sanar nossa vontade de resolvê-los, criamos uma nova prática na Way2 que chamamos de “Coding4fun” (sim, o nome é cópia descarada do Channel9).

Como funciona?

A cada sprint a gente define alguns algoritmos para resolver. Cada um cria um gist com suas versões e discutimos as diferentes maneiras de resolver os problemas.

Esse primeiro sprint fizemos os três primeiros problemas do Project Euler, só para esquentar os motores.

Por exemplo: “Add all the natural numbers below one thousand that are multiples of 3 or 5.”

O Bassani resolveu usando linq. Achei que ficou bem elegante:

Já o Marcel fez com Ruby, o que já dá outra cara:

[ruby]
limit = 1000

sum = 0
(1…limit).each { |v| sum += v if v%3 == 0 || v%5 == 0 }

puts sum
[/ruby]

A Dri já usou uma abordagem mais procedural:

A próxima rodada já vai ser diferente, vamos fazer um único algoritmo (mais difícil) e cada um vai resolvê-lo em c# (nossa linguagem do dia-a-dia) e em outra linguagem de sua escolha. Vai ser bem interessante ver em quanto a linguagem vai nos influenciar na maneira de resolver o problema.

E você, gosta de algoritmos? Como resolveria esse aí?

  • Faria do último modo, uma vez que só conheço esse:D Estou no caminho de C++…
    Posta o resultado do segundo C4Fun!
    Ruby é muito diferente do usual, wow.

  • Acredito que o metodo do Bassani seja o mais performatico, mas just for fun eu fiz um com yield return…

    class Program
    {
    public static IEnumerable Multiplos3or5(int inicio, int quantidade)
    {
    foreach (var n in Enumerable.Range(inicio, quantidade).Where(n => (n % 3 == 0) || (n % 5 == 0)))
    yield return n;
    }

    static void Main(string[] args)
    {
    var soma = 0;
    foreach (int i in Multiplos3or5(3, 997))
    soma += i;

    Console.WriteLine(soma);
    Console.ReadLine();
    }
    }

  • Fernando Bassani

    @Gabriel, meu método não é o mais performático. Se você observar a IL gerada, vai perceber que ele gera uma série de chamadas extra (se comparado a abordagem procedural da Dri), além de possuir uma infraestrutura muito grande por detrás daqueles métodos. Se o range de números fosse maior, *talvez* a minha solução tirasse real proveito do paralelismo (que entrou ali só pela brincadeira), e ainda assim o ganho seria questionável nesse problema.
    A sua solução produz quase a mesma coisa que a minha, já que Enumerable.Range e Enumerable.Where retornam IEnumerable, sendo ‘lazy’ por natureza. Talvez o compilador possa gerar exatamente a mesma IL ao perceber que o seu código está apenas adicionando uma indireção.

    Minha solução preferida continua sendo em F# (quase igual a do C#):

    [1 .. 999]
    |> Seq.filter(fun i -> i % 3 = 0 || i % 5 = 0)
    |> Seq.sum

  • André,

    Primeiro parabéns pela iniciativa! Certa vez tentei algo parecido na empresa em que trabalho, mas a galera não se interessou muito e não foi para frente. Vou tentar puxar isso novamente usando o exemplo da Way2.

    Continuando, seria legal você apresentar ao pessoal, agora que já resolveram o problema, a questão levantada pelo Juan Lopes:

    “Desenvolva uma solução que rode em tempo satisfatório para valores bem maiores que 1000. Não há limite esperado. Qual o máximo que a sua solução resolveria em, digamos, menos de 1 minuto?”

    http://juanlopes.net/2016/project-euler-1/

    O Juan já postou a resposta também, mas é um exercício interessante!

    Abraço!

    • Anonymous

      Valeu Diogo. Manda ver, tente fazer o pessoal usar linguagens diferentes, fica bem mais divertido. Vi a solução do Juan lá, muito boa a solução.

  • André,

    Primeiro parabéns pela iniciativa! Certa vez tentei algo parecido na empresa em que trabalho, mas a galera não se interessou muito e não foi para frente. Vou tentar puxar isso novamente usando o exemplo da Way2.

    Continuando, seria legal você apresentar ao pessoal, agora que já resolveram o problema, a questão levantada pelo Juan Lopes:

    “Desenvolva uma solução que rode em tempo satisfatório para valores bem maiores que 1000. Não há limite esperado. Qual o máximo que a sua solução resolveria em, digamos, menos de 1 minuto?”

    http://juanlopes.net/2016/project-euler-1/

    O Juan já postou a resposta, mas é um exercício interessante!

    Abraço!

  • Anonymous

    De tempos em tempos pego um problema do Project Euler pra resolver. Gosto muito deles porque exigem mais raciocínio lógico e matemático do que conhecimento de algoritmos em si.

    Também gosto muito do UVa online judge (http://uva.onlinejudge.org/). Mas esse é pra treinar algoritmos mesmo. Os problemas são bem direcionados e geralmente no formato do ICPC.

    Quanto a solução para o problema, a minha versão, em O(1).

    https://github.com/juanplopes/euler/blob/master/001.boo

    • Anonymous

      Excelente, nem passou pela minha cabeça resolver usando P.A.!
      Vou dar uma olhada no UVa, valeu pela dica.
      []’s!

  • Suenny Boos

    Olá André, qual é seu e-mail??

  • Danimar Ribeiro

    Existem versões tupiniquins também.

    http://br.spoj.pl/
    http://www.urionlinejudge.com.br

    O bom desses é que você pode testar a velocidade de execução do seu algoritmo, dá até pra fazer competições internas. :)