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
dojoRioEste 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 CompleteE 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/.
.
Escrito por jonatasemidio 
Coding Dojo Rio 