Dojo@Centro 13/03/2013 – Dê 1 moeda e ganhe 3 moedas

Olá, pessoal queridão.

Tudo bem com vocês?

No dojo do dia 13 de março, nós procuramos problemas numa fonte recente e bastante divertida, o dailyprogrammer do reddit. Estavamos procurando um problema com algo a mais e na indecisão, resolvemos inovar: tinham 3 problemas que a solução de um influenciava no início do seguinte e por quê não fazer os 3?

Com o apoio de todos, o problema do dia escolhido foi sobre as moedas de um país bizarro (e meio dado a estelionado XD). O contexto é o seguinte:

Em um país chamado Bytelandian, e existe uma moeda para cada número inteiro não negativo (incluindo 0 – sim, existe uma moeda de valor ZERO) e também existe uma máquina muito da estranha que se você inserir uma moeda nela ela te retornará seu dinheiro em 3 moedas – valor inserido/2 + valor inserido/3 + valor inserido/4. – Caso a divisão retorne um valor não inteiro, ele arredonda o valor para baixo.

Sabendo disso, temos os problemas:

Esse problema aplicamos uma técnica de resolução de problemas bastante conhecida, a Programação dinâmica. Uma definição utilizada para inicializar a explicação desta técnica no material da USP:

“A programação dinâmica é um nome fantasia para [recursão] com uma tabela. Vez de resolver subproblemas recursivamente, resolvê-los seqüencialmente e armazenar suas soluções em uma tabela. O truque é resolvê-los na ordem correta para que sempre que a solução de um subproblema é necessário, já se encontra disponível na tabela. Programação dinâmica é particularmente útil em problemas para os quais dividir para conquistar parece produzir um número exponencial de subproblemas, mas há realmente apenas um pequeno número de subproblemas repetida muitas vezes de forma exponencial. neste caso, faz sentido para calcular cada uma das soluções pela primeira vez, e guardá-la em uma tabela para uma utilização posterior, em vez de recomputar cada vez que é necessário”  Ian Parberry, Problems on Algorithms

Dentre as possibilidades que a programação dinâmica oferece, foi utilizado o memoization. Memoization utiliza fortemente a recursão. Não confundam com outra forma de implementar, conhecida como Botom-up, que utiliza programação de forma imperativa.  Enquanto memoization calcula valores conforme for necessário, a forma bottom-up calcula todas as possibilidades primeiro para depois retornar os valores.

Exemplo de memoization (C++) – Dada uma mochila(um termo que denota uma das abstrações de programação dinâmica), o código abaixo deverá informar se é possível formar uma mochila com os valores informados (1) ou não (0) :

Notem que a implementação acima é praticamente a aplicação direta da recorrência demostrada na wikipedia salvadora 0-1 knapsack problem:

  • m[i,\,w]=m[i-1,\,w] if w_i > w\,\! (the new item is more than the current weight limit)
  • m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i) if w_i \leqslant w.

Exemplo da implementação do mesmo caso abordado acima utilizando bottom-up:

Uma referência de uma explicação muito simples para programação dinâmica é este post abordando um pouco sobre programação dinâmica com bottom-up

E a solução que obtivemos foi essa aqui. Uma outra referência abordada na solução foi o design pattern Decorator

E as moedas que renderam mais dinheiro ainda foi:

  • Python
  • Curto Café +++
  • Memoization (PD) ++
  • Novas estruturas sendo exploradas (memoization)
  • Muito bem impressionada com um problema que parecia ser muito bobo ++++
  • Discussão sobre a persistência/como fazer TDD quando não sabemos a resposta esperada – Se foi provado por indução, foi provado por indução – Seu Carlos Flores +
  • Volta do Carlos Flores Cunha/Cunha Flores
  • Presença do Claudio Berrondo
  • Ex novato voltou
  • Recursão
  • Decorator ++++
  • Reddit – boa fonte de problemas -> http://www.reddit.com/r/dailyprogrammer/
  • Bom número de pessoas
  • Indução
  • Salgados
  • Functools ++
  • Teen town ++

Moedas que só deram prejuízo:

  • Casal bel[eé]m não veio +++
  • Ligações
  • Pouca comida +
  • Atraso
  • Pouco tempo para a retrospectiva
  • Stalinho sumiu no meio do dojo
  • Pouca gente
  • Ex-novato (vulgo Júlio Marins) ainda não ficou a vontade para ir pilotar
  • Não fomos até o final do problema proposto – ou seja, fazer os 3 problemas.

E não importa o que acontecer, sempre terá dojo nas 4º feiras, começando em torno das 18:30 – 19:00 em algum lugar do Rio de Janeiro.

Gostou do problema? Gostou da ideia do dojo? Então venha estar conosco, pois todos são muito bem vindos :D. Qualquer dúvida, é só mandar email para o  grupo (google groups) do dojo, sempre terá alguém para responder qualquer pergunta. Nós estamos na  Íparos – Av Treze de Maio, 13 – 6° andar – Cinelândia. O dojo começa entre 18:30 – 19:00. É vir, ensinar e aprender em/com grupo o/

Até a próxima 😀

Anúncios

One Response to Dojo@Centro 13/03/2013 – Dê 1 moeda e ganhe 3 moedas

  1. […] técnica da Programação Dinâmica possui algoritmos de resolução de alguns problemas, entre eles a Mochila. É possível visualizar […]

%d blogueiros gostam disto: