DojoRio@Centro 03/04/2013 – Go!! Counting Boolean Parent… o que?

Salve Jogadores!

Para os que não foram e ainda não sabem. Neste dojo de (03/04/2013) tivemos duas
novidades:
1 – Go: Liguagem de programação open source criada pela Google. http://golang.org/
2 – Rodolfo: Que veio da china comemorar o dia 1 de abril no Brasil. OBS – “Não foi só por isso
que o cara veio, mas é divertido pensar desta forma”.

A casa estava cheia, um tremendo de um carnaval, mas como de costume não faltou muita
codificação, diversão e papo NERD.
Neste dia o problema selecionado foi o Counting Boolean Parenthesizations, mas é claro que
esse não foi o nome do projeto no GIT, pois sempre que alguém chegava e perguntava qual era
o problema só lembrávamos a sigla “CBP” rsrsr.
O objetivo deste problema é Contar o número de formas possíveis de se organizar o código
alterando os parênteses de maneira que os mesmos retornassem verdadeiro, lembrando que a
entrada é uma sequencia de booleanos em forma de uma String.
Porem já que eu sei que não expliquei muito bem… segue o link do problema com um vídeo
explicativo: http://people.csail.mit.edu/bdean/6.046/dp/ . no item 9.
O código esta no git do DojoCentro.
Para os mais curiosos segue um link do tour do Go lang, um tutorial em forma de handsOn :
http://tour.golang.org/#1

Jogadores do Dia:

Flávio Amieiro
Aleksandra Kwoka
Israel Teixeira
Rodolfo Henrique Carvalho
Eduardo Stalinho
Otávio Cardoso
Carlos Cunha
Juan Lopes
Jonatas Emidio

Caras Felizes:

Mate
Voltei após muito tempo+
GO+++++
Niteroi
Muita gente+++
Rodolfo 1º de Abril / Rodolfo in Rio+++
Chineses
Poloneses
Problema++++
Morango+
Presenças Ilustres
Cubo mágico
Frutas++
Berrondo voltou a ser praticante regular
Pessoas+

Tentativa de mudança de linguagem
Discussão sobre árvores++
Caqui
Ola
Retornos+
Aprendi como funciona um cubo mágico
Não caiu nenhum prédio ate agora

Caras Tristes:

Problema
Conversa no vermelho+
Frutas
Go++
Go legal mas não cabe no dojo
Demora para começar++++
Quadro pequeno+
Ambiente não preparado previamente+
Sintaxe do map
Faltou brigadeiro
Discussão
Porta fechada
Não programei+
Alguns não programaram
Demorei a entender
Fui atropelado
Galera dispersa++++++
Problema mal definido++
Pouca comida+
Pessoas saindo no meio+
Biscoito de castanha?
Niterói
Fome
Go test

Sempre terá dojo nas 4º feiras, começando entre 18:30 – 19:00 e se você gostou, é só chegar na  Íparos – Av Treze de Maio, 13 – 6° andar – Cinelândia. Qualquer dúvida, é só mandar email para a lista do dojo google groups, que sempre tem alguém para responder, por isso, não se acanhe, pode vir que a casa é totalmente livre para quem quiser ensinar e aprender conosco 

Até a próxima o/

 

DojoRio@Centro 27/03/2013 – No Brasil, é esquibunda na areia

No dia 27 de março foi véspera do feriado mais doce do ano, a Páscoa e não fizemos problema temático desta vez. No lugar disso, fizemos um problema que rendeu boas risadas com as alterações que fizemos para que ele tivesse mais a cara do nosso país com calor das profundezas <insira o inferno da sua fé aqui>.

Queríamos resolver o seguinte: existe um carinha (no problema é o Michael)  que gosta muito de snowboard e também temos uma montanha, com suas altitudes  representadas por uma matriz. Sabendo que só podemos ir do ponto mais alto até o mais baixo da montanha, qual é a maior distância percorrida na montanha informada ?

Pelo fato de que moramos no Rio de Janeiro (com 42º a sombra, não tem nem 1 mês atrás) , num estado dentro de um país tropical, também conhecido como Brasil, durante as trocas de piloto e co-piloto com os presentes foi falado que snowboard não tem nada a ver com onde moramos e que o mais próximo de montanha para deslizar que temos são as dunas de Natal e lá se faz é esquibunda. Neste momento de bastante risadas, nós rebatizamos o esporte e o problema passou a ser tupiniquim 🙂

Este dojo manteve a sequência de problemas com Programação Dinâmica, mas no lugar de focarmos em programação dinâmica somente, este problema nos levou a um contexto que aplicava programação dinâmica na sua resolução.  O contexto do desafio temos vários pontos a serem visitados, sendo que temos que sempre ir da altitude maior para a altitude menor, ou seja, não tem como voltar. Isso nos permite observar o todo como um DAG – Grafo Acíclico Dirigido. Nosso objetivo é achar o maior caminho possível no grafo (montanha) dado e Programação Dinâmica é indicada para resolver este tipo de problema, inserindo as altitudes visitadas num array e manipulando-o conforme a implementação escolhida para Programação Dinâmica.

A solução deste dojo divertido foi esta.

E os pontos positivos que conseguiram chegar até o final da duna sem rolar no meio:

• Problema ++++
• Pessoas
• Comida variada
• sensação de que as pessoas entenderam mesmo o problema
• Lucas Martins, Otávio Cardoso e Thiago Bel[e]m voltaram
• Comida suficiente
• Python +
• A solução foi obscura no início, mas durante o dojo consegui entender
• A troca do esporte do problema de esqui para esquibunda ++
• Participação
• Evolução da solução
• PD e Grafos
• Pessoal veio mesmo com chuva e véspera de feriado
• Solução (parcial)

Os pontos negativos que nem deu o friozinho na barriga da adrenalina:

• Cadê os novatos? +
• A troca dos termos para a retrospectiva de “Carinha Feliz/Carinha Triste” para “O que quero mais/ O que não quero mais” não deu certo
• Não avançamos muito na solução ++
• Falatório no vermelho ++
• O dojo começou tarde ++
• Armadilha da coca cola – alguém agitou a coca cola e quando esta coca cola foi aberta, praticamente estourou.
• Pessoas não programaram
• Demorei para entender o problema
• Testes com nomes ruins
• Python
• “Roubamos ” muito e poderíamos ter evoluído mais depressa se partissemos para a solução mais correta um pouco antes
• O ex novato (Júlio Marins) não veio.

Sempre terá dojo nas 4º feiras, começando entre 18:30 – 19:00 e se você gostou, é só chegar na  Íparos – Av Treze de Maio, 13 – 6° andar – Cinelândia. Qualquer dúvida, é só mandar email para a lista do dojo google groups, que sempre tem alguém para responder, por isso, não se acanhe, pode vir que a casa é totalmente livre para quem quiser ensinar e aprender conosco 😀

Até a próxima o/

DojoRio@Centro 20/03/2013 – Amigos, amigos, bagagens à parte

Olá, pessoas queridas. Tudo bem com vocês?

No dia 20 de março, fizemos um problema com características clássicas. Um grupo de amigos está planejando uma viagem e precisam decidir como dividirão as malas. Dado um conjunto de malas com um determinado peso e 2 carros, é possível dividir as malas para que todos os carros sempre carreguem o mesmo peso?

Um ponto que deve ser atentar  é que por mais que o peso possa ser divisível por 2 (temos 2 carros), nem sempre será possível dividir as malas por 2, já que as malas são inteiras. Por exemplo, 4 malas com pesos de 1, 2, 5, 4 – O peso total é 12, este peso é divisível por 2 carros e conseguimos arrumar as malas de forma que as malas de peso 2 e 4 fiquem num carro e as malas de peso 1 e 5 fiquem em outro. Agora suponha as mesmas 4 malas para serem divididas pelos mesmos 2 carros, só que com pesos diferentes de 1, 1, 1, 9 – por mais que 1 + 1 + 1 + 9 = 12 e 12 seja divisível por 2, a distribuição do peso não é possível, pois 3 < 9 e não podemos dividir a mala de peso 9 para que seu excedente em relação a metade do peso total das malas seja carregado em outro carro.

O desafio abordado é uma variação de um problema famoso, conhecido como Problema de Partição. Programação dinâmica é bastante utilizada para resolver problemas deste tipo.

A técnica da Programação Dinâmica possui algoritmos de resolução de alguns problemas, entre eles a Mochila. É possível visualizar esta variação do problema da partição como uma Mochila. Existem diversos tipos de mochilas e várias definições diferentes. Uma definição de um tipo de mochila (dada pela wikipedia) é:

“Dado um conjunto de artigos, cada um com um peso e um valor, determinar o número de cada item de incluir em um conjunto de modo que o peso total é inferior a ou igual a um determinado limite e o valor total é tão grande quanto possível. Ela deriva seu nome do problema enfrentado por alguém que está limitado por uma mochila de tamanho fixo e deve preenchê-la com os itens mais valiosos.”

A definição dada acima é para Mochilas  problemas de otimização: maximizar, minimizar, encontrar valores, etc. Outras Mochilas são aplicadas em problemas de decisão – retorna true ou false. Durante o dojo, este problema foi citado como pertencente à classe dos NP Completo.

A Mochila que estamos utilizando neste caso é de decisão, pois temos que decidir se é possível ou não dividir as malas de forma a igualar os pesos entre os carros.

As malas foram divididas por presenças ilustres e seus respectivos óculos. Um parabéns para o Luan e seus óculos gigantescos que roubaram a cena durante o dojo :). Decidimos bagagens com óculos dinâmicos com este código.

E as frases de efeito das bagagens que foram divididas com sucesso e foram para lugares maneiríssimos:

• Problema ++++++
• Novatos ++
• Pessoas ++
• Programação Dinâmica (PD) +++
• Biscoito de castanhas (Padaria)
• Explicação
• Cissa Bel[é]m presente +
• Retrospectiva
• “Jac Abreu jornalista” (Jac anotando para o post do dojo)
•  Ambiente legal
• Recursão
• Explicação bem detalhada (sobre o problema e sobre PD)
• Não sou mias novato (desabafo do Júlio Marins 😛 )
• Interatividade
• Desenvolvimento de ideias
• Retorno ao dojo +
• Pessoas permanecendo no dojo
• Problema acessível e ainda aplicando mochila (PD)
• Pessoal empolgado 😀

As malas que ficaram em casa também tem o que dizer:

• Thiago Be[e]m não veio ++
• Otávio Cardoso não veio +
• Flávio Amieiro não veio +
• O dojo começou tarde +
• Teclado com mofo =(
• Pouca comida +++
• Chegar atrasado ao dojo
• Patota
• Cadê a cadeira do “cabuuumm” 😛

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 da gente? O dojo@Centro é realizado na Íparos – Av Treze de Maio, 13 – 6° andar – Cinelândia, entre 18:30 e 19:00 de todas as quartas feiras (menos feriados) . 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. Você é muito bem vindo 😀

Até a próxima 

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 😀