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:

• problema 1 é Quantas moedas de valor 0 obtemos com uma moeda de valor 1000??
• problema 2 é Dada uma moeda de valor N, qual é o maior valor que conseguimos obter com ela?
  
• problema 3 não foi feito é Duas máquinas diferentes – dada 1 moeda n , a 1º máquina retorna n/2 + n/3 + n/4 moedas e a 2º máquina retorna n+1. Qual é o menor valor de N que através de diversas trocas entre as máquinas, conseguimos uma outra moeda do valor n inserido e uma moeda de valor 1? 

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) :

	#include <iostream>
	#include <cstring>
	#define MAX 1000
	using namespace std;
	//Testar com 5 10 /n 1 2 3 4 5 e 5 10 /n 3 3 3 3 3
	int W[MAX];
	bool V[MAX][MAX];
	bool M[MAX][MAX];
	bool K(int n, int w) {
	if (w==0) return true;
	if (w<0 || n==0) return false;
	if(V[n][w]){
	return M[n][w];
	}else{
	V[n][w] = true;
	return M[n][w] = K(n-1, w) || K(n-1, w-W[n-1]);
	}
	}
	int main() {
	int n, w;
	while(cin >> n >> w) {
	memset(V, false, sizeof(V));
	for(int i=0; i<n; i++)
	cin >> W[i];
	cout << K(n, w);
	}
	}

view raw

memoization_example.cpp

hosted with ❤ by GitHub

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

•  if  (the new item is more than the current weight limit)
•  if .

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

	#include <iostream>
	#include <cstring>
	#define MAX 1000
	using namespace std;
	int W[MAX];
	bool M[MAX][MAX];
	int main() {
	int n, w;
	while(cin >> n >> w) {
	for(int i=0; i<n; i++)
	cin >> W[i];
	for(int j=0; j<=w; j++)
	M[0][j] = false;
	for(int i=0; i<=n; i++)
	M[i][0] = true;
	for(int i=1; i<=n; i++) {
	for(int j=1; j<=w; j++) {
	M[i][j] = M[i-1][j] || M[i-1][j-W[i-1]];
	}
	}
	cout << M[n][w] << endl;
	}
	}

view raw

bottomUpDynamicProgramingExample.cpp

hosted with ❤ by GitHub

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 😀