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 24/10/2012

Olá, pessoas queridas 😀

O problema desta quarta, data estrelar dia 24 de outubro de 2012 foi uma releitura do cláaassico problema do Troco. Para quem não conhece, o problema do troco consiste em: de que forma(s) posso dar o troco para um determinado valor, dada x valores de moeda. Este problema é bastante versátil e a leitura feita foi retirarmos as moedas de centavos e tentamos encontrar o troco com a menor quantidade de moedas.

A linguagem escolhida foi PHP e ela encaixou muito bem com o problema, para a alegria de todos.

O código fonte do deste dojo pode ser encontrado no repositório (github) do dojo-rio

E os participantes foram:

• Jonatas Emidio
• Thiago Belem
• Renan Augusto
• Otavio Cardoso
• Juan Lopes
• Israel Teixeira
• Flávio Amieiro
• Valéria Parajara
• Carlos Cunha
• Cecília Belém
• André Pfeiffer
• Jacqueline Abreu

Os pontos positivos – Carinhas Felizes foram :

• Nova leitura do problema
• Continuamos resistindo a python (e estamos utilizando mais outras linguagens)
• Discussão sobre algoritmos foi excelente +
• Pessoas antigas voltaram
• Todas as meninas presentes no dojo participaram pilotando
• Participação do André Pfeiffer  +
• Evolução do problema
• Pessoas mais novas no dojo programando
• Cissa Belém programando +++++
• Biscoito Belem (Cissa, coloco acento na marca do biscoito 😛 ?) +++++++
• PHP+++
• Comida++++++
• Participação da Valéria Parajara+
• Dojo começou cedo+
• Participação do Claudio Berrondo (sumido)+
• Problema+++
• Juan Math
• Programação Dinâmica (PD)
• Menos conversa paralela
• Ambiente gostoso
• Várias pessoas pilotando
• Sem “Bullyng” com outras linguagens
• Presença feminina+
• A quantidade de presenças “fixas” – costumam vir frequentemente ao dojo – tem aumentado +
• Let’s / Try
• Problema ficou muito bom de ser programado em php
• A solução utilizando recursão
• Galera

Os pontos negativos – Carinhas Tristes foram 😦 :

• O problema ficou complicado com o decorrer dos testes
• Muita coca cola
• Participação ainda incompleta ao dojo
• Não concentração
• Muito sono, atrapalhou a presença
• Falei no vermelho
• Provas
• System Crash
• O problema – Troco, por mais que seja uma releitura, está virando fizz buzz
• Ainda tem muita conversa
• Nem todo mundo programou
• Cheguei tarde
• Distração
• Pessoas falando no vermelho +
• Loop infinito
• Baguncei muito o dojo na minha chegada (cumprimentando pessoas)
• Não cheguei a tempo de comer o biscoito Belem

OBS: Sra Dona Cissa Belém está de parabéns pelos biscoitos – que ela mesma faz, quem não está vindo, está perdendo 😛

E pessoal, nesta quarta tem mais dojo Centro, mas durante a semana, não deixem de prestigiar os outros dojos que estão surgindo. Isso é muito legal e esperamos que continue, em especial o dojo@Barra, que está começando e espero sinceramente que seja um dojo permanente.

O dojo@Centro está ocorrendo na Íparos, na Av Treze de Maio, 13 – 6° andar – Centro – Rio de Janeiro – RJ. O pessoal começa a chegar as 18:30 e qualquer dúvida, entra no grupo Coding Dojo Rio e manda sua pergunta para nós :D. Sempre tem alguém para responder, estejam certos disso \o/ 😀

Dojo@Centro 16/05/2012

Olá pessoal.

Faz muito tempo que não postamos sobre os temas e as nossas impressões sobre os dojos realizados, mas se alguém quiser saber sobre a solução que chegamos, pode dar uma olhada em https://github.com/dojorio/dojo-centro – tem todas as soluções desde 2008 – veja o quanto se pode aprender lendo e/ou tentando reproduzir estas códigos :D, além de estar sempre com o código da semana corrente fresquinho esperando por todos para ser melhorado/apreciado/etc.

Neste dia, o problema abordado consistia numa conta de luz que você recebia, sendo que o consumo indicado não era somente o seu, mas também o do seu vizinho. Sabendo os parâmetros de cobrança e sabendo que sempre a sua fatura era menor que seu vizinho, indique o seu qtd consumida/valor da conta.

Para quem quiser saber mais, veja busca binária (também conhecida como Pesquisa Binária).

Apesar de ter sido um dia bastante chuvoso, tivemos bastante pessoas presentes (presenças internacionais, inclusive :D). Elas foram:

• Eduardo Stalinho
• Flávio Amieiro
• Carlos Cunha
• Leandro Thimóteo
• Jean Pacheco
• Vera Osokina
• Luiz Peralba
• Jacqueline Abreu
• Israel Teixeira
• Juan Lopes

E na retrospectiva deste dojo tivemos como:

Pontos Positivos – Carinha feliz 😀

• Comida(+)
• Pessoas novas (Vera e Jean) e pessoal da myfreecomm presente
• Problema (+++)
• Pessoas novas (++++)
• Pessoas com interesse e opiniões interessantes para compartilhar
• Lembrar de trazer comida

Pontos Negativos – Carinha triste 😦

• Falta de pontualidade
• Dispersão neste dojo
• Problema
• Pessoas falando no vermelho
• Falta de concentração
• Demora para escolher o problema
• Não conseguimos finalizá-lo durante o dojo
• Dificuldade das pessoas em entenderem o problema, apesar do problema ser simples
• O problema ser interessante, mas aparentemente não muito viável de ser feito com um grupo grande
• Muitas opiniões diferentes e falta de focar numa única vertente para chegar a solução
• Esquecer de apertar o play
• Chuva
• Dispersão(+)
• Apesar do problema ser muito legal e do pessoal (aparentemente) ter entendido o que fazer, mesmo assim ficamos travados
• Problema
• Bagunça(+)
• Travamos

Este dia foi curioso, pois muita gente gostou e ao mesmo tempo desgostou do problema, mas acreditamos fortemente que todo mundo saiu dali aprendendo alguma coisa e que olhará para uma situação parecida com outros olhos :D.

Esperamos todos que vieram, os que não vieram e todos os que quiserem nos visitar, as 4º feiras (QUARTAS FEIRAS), às 18:30 (tentaremos chegar nesta hora, é o nosso compromisso semanal), na Av Treze de Maio, 13 – 6° andar – Cinelândia – Rio de Janeiro – RJ, também conhecida como Íparos.

Traga seu problema interessante, o seu biscoito, refrigerante ou qualquer outra coisa para comer – se quiser, mas venha,  ensine e aprenda conosco 😀 😀