Dojo@Centro 5/06/2013 – Pintando árvores

Olá, pessoas queridas. Tudo bem?

No dojo@centro da última quarta feira, o problema que tentamos resolver foi o seguinte:

Dada uma árvore binária, só podemos pintar o nó se o nó pai já estiver pintado. Cada nó possúi um valor correspondente e a ordem da pintura é multiplicada ao valor do nó, correspondendo ao tempo de pintar o nó. Sabendo disso, qual é o menor tempo para pintar todos os nós da árvore?

Com isso, temos um conjunto de nós pintados e um conjunto de nós candidatos a serem pintados e temos que encontrar a ordem dos nós que resulta no menor tempo de pintura. O problema original pode ser visto aqui

No tópico do dojo deste dia, foi postada uma consideração sobre o problema:

É um problema de job scheduling. Parto do princípio que a maior tarefa existente, quando for possível fazer (i.e. o pai já tiver sido colorido), necessariamente vai trazer o maior ganho imediato *e global*. Isso significa, em outras palavras, que a maior tarefa precisa ser executada necessariamente logo depois da tarefa pai dela. Assim, eu posso mesclar os dois nós em uma tarefa só (pois elas sempre precisam ser executadas juntas). Mas, para isso, precisei generalizar o problema.

No problema original, as tarefas tem um tempo para ficarem prontas (inicialmente todas tem tempo 1) e a penalidade é dada pelo tempo do final (não pelo do início). Mudei para o tempo ser calculado a partir do início da tarefa pela função linear at + b. Então, inicialmente, todas as tarefas, que tinham penalidade a*t, passam a ter penalidade a*t + a, onde a é a penalidade da tarefa como descrita pelo problema. Toda vez que mesclo duas tarefas cujas penalidades são a*t + b e c*t + d, onde a primeira precisa ser executada antes da segunda, tenho que a nova penalidade é:

penalidade(A+B) = (a + c)*t + (b + d) + c*duração(A)

duração(A+B) = duração(A) + duração(B)

O “c*duração(A)” é porque enquanto A está executando, a tarefa B está acumulando penalidades proporcionais ao tempo perdido executando A.

Se a maior tarefa não tem nenhum pai na árvore (ou seja, ela pode ser executada imediatamente), executo e incremento o tempo. Senão, vou reduzindo a árvore efetuando esses merges.

Mantenho a lista de tarefas ordenadas usando set (e não uma heap, principalmente porque preciso poder remover uma tarefa no meio da lista), e para simplificar as operações na árvore, mesclo duas tarefas usando union-find (para evitar ter que percorrer as tarefas filhas atualizando seus pais).

A solução que conseguimos está no repositório Github do dojoRio

Este dojo também teve uma versão de brigadeiro feito pela Cissa Belém para comemorar o aniversário do Elias Tandel. Os dojos de aniversário estão com problemas muito bons, creio que em honra ao aniversariante :), mas além disso, o Elias trouxe uma notícia que explodiu várias cabeças: CSS 3 é Turing Complete

E os participantes que se lambuzaram de tinta foram :

• Thiago Belem
• Juan Lopes
• Otávio Cardoso
• Andre Oliveira
• Álvaro Justen
• Elias Tandel
• Carlos Cunha
• Jacqueline Abreu
• Diego Volpato

E as pinturas bonitinhas que a galera curtiu foi:

• Problema “profundo” – o falso problema simples, aquele que tem enunciado com aparência de fácil, que só revela a complexidade na hora de implementar +++++++
• Novatos e o retorno de  participantes antigos ++
• Novatos
• Menos bullying com as linguagens
• Nova versão de brigadeiros bel[eé]m +++++++
• A vinda da Val Parajara, do Diego Volpato, do Júlio Marins e do Leonardo Alberto (Leobeto)
• Aniversário do Elias Tandel +
• Comida +++
• CSS 3 Turing Complete +++
• Ruby +++
• Retorno ao dojo
• Árvore (Estrutura de Dados)
• Rule 110

E as manchas no chão que teremos que limpar foram:

• Falatório ++++++
• Ar condicionado não está funcionando direito ++++
• Israel e Claudio Berrondo não puderam vir +
• Fonte de dojotimer não estava ok
• Entender um pouco mais de ruby
• Webdings +++
• CSS 3 não deveria ser turing complete (está fazendo mais do que deve)
• O dojo começou tarde ++
• Explicar várias vezes o problema atrasa o andamento do dojo
• [] != NIL
• Bel[eé]m fêmea, vulgo Cissa, não participou
• Receber ligações telefonicas na hora em que está pilotando
• O problema pareceu não estar muito adequado a ser feito seguindo a lógica do TDD. A implementação da solução foi muito exaustiva
• Poucas bebidas
• Apesar de menor, ainda teve momentos de bullying com as linguagens
• Não consegui participar ++

E este foi o dojo@Centro desta semana e semana que vem tem mais. Se você quer mostrar para a sua namorada ou namorado que programação também pode ser feita em grupo e divertida, pode levar a pessoa ao próximo dojo :).

A Íparos agora está se tornando o espaço #CurtoCircuito. Para saber mais, leia o post da @CissaBelem sobre ele – é uma versão bastante simplificada sobre o espaço, veja outras informações na fan page do espaço e também veja o http://curto-circuito.org/ :D.

E se você gostou de tudo isso, esteja conosco na próxima 4º feira, na  Av Treze de Maio, 13 – 6° andar – Cinelândia, entre 18:30 e 19:00. Só não tem dojo@Centro se a 4º feira for dia de feriado . Qualquer dúvida, é só mandar email para o  grupo (google groups) do dojo, alguém do grupo sempre responde as dúvidas conforme for possível ou um tweet com a hashtag #dojoRio.

Você é muito bem vindo, de verdade :D.

Até a próxima o/.

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 😀