18.06.08
Posted in C, Dojo
at 6:12 pm
by marivb
Esse relato foi escrito pelo Yoshi, estreando como escriba no blog. Legal!!
Tiramos a carta “Venda seu peixe”. Nada mais próprio para um dia onde, numa situação inédita, os problemas eram exatamente os mesmo do dojo anterior, mas com um porém: Se repetísse-mos “Overlapping areas”, continuaríamos do ponto que paramos – para melhor ou para pior. E isso só seria possível por que todos os presentes estavam… Presentes na sessão anterior.
Eram então os problemas: Eternal Truths, Water Flow e Overlapping Areas.
O Yoshi resolveu abraçar a causa da carta e vender a idéia de, finalmente, terminar um problema no Dojo. Como isso, sugeriu Water Flow – incontestavelmente o problema para a situação.
Aberta a votação, ficou evidente que ninguém estava interessado em procurar pela verdade eterna nos labirintos sagrados. A votação então ficou empatada, aguardando o voto da Mari para a decisão. Visivelmente o Yoshi vendeu seu peixe, uma vez que o empate só se deu por que ele traiu seus persuadidos e votou no outro problema, após ser persuadido pelo Thiago a votar no Retorno de “Overlapping Areas”. (Pode isso? Vai entender…) Frente a esse quadro, a Mari resolveu por escolher um outro inédito: repetir um problema no dojo. (Teria ela também sido persuadida pelo Thiago? Ou pelo Yoshi, que virou a casaca dele mesmo? Enfim…)
Como o problema era conhecido, buscamos sua ToDo-List para recomeçar. Lembrávamos de um problema com o qsort, mas não estava claro qual. Como os testes feitos na sessão anterior passaram prontamente, pareceu que estava tudo sobre controle… Ledo engano.
Nosso novo alegre Dojo Unit, agora colorido, não estava com um assert_same funcional. Percebemos isso quando ele disse ok para um teste que… Não estava ok. Demos um svn revert nele e migramos para o velho e sóbrio dojo unit do dojo 40.
Superados os problemas de recomeçar, logo nos deparamos novamente com o estranho problema do quicksort, e este foi resolvido. Moral da hstória? Macros são úteis, mas… COLOQUE PARÊNTESES! Avançamos mais um pouco no problema: começamos a criar os eventos em X para verificar quais retângulos cruzam a linha de varredura. Com isso, ao soar o gongo para nossa retrospectiva, nosso ToDo-List ficou assim:
- Estrutura de Dados para armazenar os retâgulos
- Ordenar os retângulos pelo eixo x (varrer coordenadas ‘x’ dos retângulos)
- Guardar os retângulos que cruzam a linha de varredura
- Calcular quantos retângulos interessam e guardar o máximo.
- Calcular a área
Retrospectiva
Coisas Legais:
- O algoritmo Scanline, apesar de sua complexidade, despertou o interesse de muitos.
- Continuar o problema também teve uma unisitada popularidade.
- Dojo Unit colorido ficou mó legal!
- O quick sort e seus ponteiros tambem tiveram seu destaque, tanto pela notação quanto pelo seu funcionamento.
- Macros são legais, mas… USE PARENTESES!
- Alternativa simples para listas ligadas com alocação dinâmica de data ***vetor
Coisas não legais:
- Retomar do ponto de parada não é fácil
- Mesmo retomando, não terminamos
- Dojo Unit colorido estava bonitinho, mas ainda não pudemos usa-lo
- Estrutura de dados do scanline é complexa
- Ainda não sabemos testar malloc e free…
- Fim de semestre: muito cansaço e poucas pessoas
Durante a (espera pela) pizza, discutimos algumas coisinhas:
Por que não usar o == ao invés de assert_same? Infelizmente não estamos em C++ e, portanto não podemos sobrecarregar o operador. Um uso ingênuo de == não compararia toda a estrutura e, portanto, não daria o resultado esperado…
Para aproveitar melhor o parking lot, devemos distribuir os postits brancos no começo. Assim podermos anotar as dúvidas on-line e não deixar nada de lado!
Permalink
07.06.08
Posted in C, Dojo
at 11:10 pm
by adolfo
- Data: 04/06/2008
- Participantes: Thiago, Mari, Hugo, Yoshi, Breno e Adolfo
- Randori: Overlapping Areas em C, com o Dojo Unit Test
A sessão começou com o sorteio da carta “Have Something at Stake”. Depois da leitura da carta e de uma breve história de pescadores contada pelo Yoshi (embora tudo leve a crer, acho que não era mentira), fomos à tradicional votação. Os 7 votos do Eternal Truths e os 3 do Water Flow não foram suficientes para vencer os 8 votos do Overlapping Areas. Escolhido o predador pro nosso aquário, começamos a discutir o problema.
A encrenca consiste, resumidamente, em determinar a soma das áreas das regiões em que há maior sobreposição de retângulos. No exemplo acima, teríamos que somar a área batizada de “E3″ com a “G3″.
A nossa discussão foi mais longa do que as que temos usualmente. O Yoshi surgiu com uma boa idéia para resolvermos o problema. Depois de algumas explicações e um debate, a Mari nos explicou um algoritmo, usado no Archimedes, que chamamos de “Scan Line”. Misturamos as idéias do Yoshi, o algoritmo da Mari, os pitacos de todo mundo e conseguimos a nossa lista de atividades para serem feitas:
ToDo List:
- Estrutura de Dados para armazenar os retâgulos
- Ordenar os retângulos pelo eixo x (varrer coordenadas ‘x’ dos retângulos)
- Guardar os retângulos que cruzam a linha de varredura
- Calcular quantos retângulos interessam e guardar o máximo.
- Calcular a área
Hora de codar: começamos a implementar o que havíamos discutido e as idéias e observações interessantes não pararam de se manifestar. O andamento das coisas estava tão envolvente que quase não percebemos a chegada da retrospectiva.
Retrospectiva (em resumo)
O que podemos melhorar?
- O problema era longo. Só conseguimos chegar ao segundo item da nossa lista de atividades e, ainda assim, não foi possível resolver um problema com a função QSort.
- Gastamos muito tempo na discussão do problema e tivemos pouco tempo para codar (embora tenhamos conseguido fazer o rodízio de todos os participantes).
- Um teste falhando deixou todo mundo com uma pulga atrás da orelha. Todos estávamos curiosos para entender o comportamento inesperado quando o gongo da retrospectiva tocou.
- Precisamos ser mais pontuais. A sessão começou às 20:20, quando deveria ter sido iniciada às 20:00.
O que foi legal?
- Muitas pessoas gostaram do problema. Tecemos elogios às discussões surgidas, aos desenhos e à dinâmica que a sessão teve com um problema diferente. Nos divertimos.
- A Dojo Unit não dá mais problema de make. A nossa biblioteca de testes está ficando bem legal.
- A sessão foi dinâmica, estamos percebendo que está ficando mais rápido de codar (os 7 minutos estão sendo respeitados)
- Gostamos de aprender a respeito do “Scan Line”
- Elogios à função QSort do C
- Bastantes pessoas, o que significa que o Dojo de quarta continua. Esta discussão surgiu por conta do Dojo que agora também acontece aos sábados.
- SSH not so safe no Debian
Encafifamentos
Durante a pizza, discutimos alguns assuntos:
- Não devemos fazer testes para evitar erros conhecidos? Em alguns momentos forçamos o teste. Qual o seu propósito? Os testes pegam erros não previstos.
- Conversamos sobre a Dojo Unit, que agora está com as features implementadas pelo Hugo.
- Novamente falamos a respeito da questão “terminar a resolução do problema ou focar nas discussões, na melhor implementação, nas práticas do Dojo, etc”.
- Por fim, falamos um pouco sobre as diferenças entre TDD e BDD.
Bom, depois desta sessão empolgante, acho que podemos dizer que o predador no aquário realmente aumentou a nossa motivação. Até a próxima, portanto!!!
Permalink
26.05.08
Posted in C, Dojo
at 3:57 pm
by marivb
- Data: 14/Maio/2008
- Participantes: Breno Franco, Fabricio Sousa, Hugo Corbucci, Jacqueline Marchetti, Leandro Lameiro, Mariana Bravo, Thiago Colucci, Yoshi
- Kata: Ponteiros Dançantes e Coloração em Grafos, Parte A em C, com o Dojo Unit Test
- Fonte: http://dojo_sp.googlegroups.com/web/38-pcg.zip
- Fotos: http://picasaweb.google.com/fabriciosn/Dojo14052008
A sessão começou com uma descrição do problema proposto da disciplina de Estruturas de Dados do BCC-IME-USP. O exercício consistia de 3 partes, mas o objetivo da apresentação era resolver a primeira parte apenas (que já é, por si só, bastante interessante e complicada).
Em resumo, o programa recebe um conjunto de elementos principais e secundários e uma série de subconjuntos dele, e quer determinar qual combinação desses subconjuntos permite cobrir os elementos principais, podendo ou não cobrir os secundários, mas sem repetição. Um rápido exemplo:
Elementos: A B C D E (principais) | E F G (secundários)
Subconjuntos: {A, B, F}, {A, C, G}, {B, E}, {D, F, G} e {D}
- Os subconjuntos {A, B, F} e {A, C, G} causam uma repetição do elemento A, isso não é permitido.
- Os subconjuntos {D, F, G}, {A, C, G} e {B, E} formam {A, B, C, D, E, F, G, G}, cobrindo todos os principais mas repetindo um secundário. Isso também não é uma resposta válida.
- Os subconjuntos {A, C, G}, {B, E} e {D} formam {A, B, C, D, E, G} e são uma resposta válida.
O algoritmo a ser implementado usa uma estrutura de matriz esparsa maluca em que cada coluna representa um elemento e cada linha representa um subconjunto. A célula pode assumir os valores 0 ou 1 se o elemento da coluna está ou não no conjunto da linha. A descrição do algoritmo está no enunciado, assim como a descrição da estrutura da matriz.
Após a explicação do problema e da idéia por trás da estrutura, começou a sessão de código, guiada pelo apresentador do Kata, o Thiago. A implementação avançou em pequenos passos, mas em algum momento o apresentador não lembrava como fazer um determinado teste passar, de forma que todos os participantes começaram a dar sugestões. As sugestões e tentativas realizadas pareceram um passo grande demais e o grupo não conseguiu corrigir o erro até o fim da sessão.
Então veio a…
Retrospectiva
Os principais assuntos discutidos na retrospectiva foram:
- Usamos a nova versão da Dojo Unit, e ela está melhor. O que falta? Algumas das sugestões discutidas podem ser vistas em azul no canto esquerdo superior desta foto.
(A versão mais recente da Dojo Unit encontra-se no nosso repositório do github e a versão usada no Dojo 38 pode ser tirada do código fonte da sessão)
- O pessoal gostou de ter um Kata (fazia tempo que ninguém tomava a iniciativa), mas reconheceu que é bom o apresentador treinar e rever os passos da solução antes de apresentar.
- O problema que enfrentamos no final do Dojo era por conta do uso de
strtok e strsep. Um dos participantes sugeriu que eles não devem ser usados de maneira recursiva, pois isso causa problemas. Depois da retrospectiva, o apresentador lembrou que usou scanf na solução, ao invés desses métodos.
- De novo tivemos problemas com o ambiente – seja por conta do teclado, do editor, do debugger. Discutimos como seria possível ter um ambiente mais amigável a todos, sem chegar em nenhuma solução, mas algumas sugestões.
- Tivemos também uma discussão sobre testes exploratórios: quando devem ser feitos, devem ou não ser apagados? Podemos fazer quando não conhecemos o ambiente, por exemplo (como foi o caso com as rotinas strtok e strsep). No Dojo certamente não queremos apagar, pois o código mostra para outras pessoas um pouco da evolução do que fizemos na sessão.
Também levantamos itens de ação (lado superior direto da mesma foto), que já foram cumpridos.
(Nota do escriba: foi mal pelo atraso… não deixem de ler o post do Adolfo, sobre o Dojo 39, ficou bem legal!)
Permalink
24.05.08
Posted in C, Dojo
at 2:38 pm
by adolfo
- Data: 21/05/2008
- Participantes: Fabs, Jac, Breno, Adolfo, Rodox (o salvador), Hugo e Mari
- Randori: A Pile of Boxes em C, com o Dojo Unit Test (sem as últimas features implementadas pelo Hugo)
- Problema: http://acm.uva.es/problemset/v9/946.html
- Código: http://dojo_sp.googlegroups.com/web/39-pob.tar.bz2
Naquela agradável noite de quarta-feira, o Breno nos apresentou três problemas: “Overlapping Areas”, “Water Flow” e “A Pile of Boxes” *. Como o pessoal não estava muito interessado em polígonos nem em sistemas hidráulicos, a votação foi massacrante:
- A Pile of Boxes – 4 votos
- Water Flow – 2 votos
- Overlapping Areas – nenhum voto, coitado
Definido o problema, partimos diretamente para os testes de uma pilha com somente uma caixa. Sabendo que caixa sozinha não faz verão nem a nossa alegria, seguimos, com passos de bebê, testando e codificando (é, exatamente nesta ordem) até um cenário com três caixas. Neste ponto em que as coisas ficaram interessantes, o tempo da sessão de codificação se expirou. Por este motivo, o mistério de um teste que deveria ter falhado mas não o fez ficou pairando no ar. O enigma só seria explicado no momento da pizza.
Desta vez não tivemos problemas com a manipulação de strings.
Retrospectiva e Pizza
O que podemos melhorar?
- Menos gente do que o usual (feriadão chegando)
- O início da sessão atrasou bastante porque não tínhamos um computador funcionando. A chegada do Rodox com um notebook livrou o Fabs da vergonha de não conseguir hackear o Mac Mini
- Não fizemos o rodízio completo dos participantes durante a fase de codificação
- Alguém sentiu falta de maçã e reclamou que já estava se acostumando com o Mac
- Não utilizamos o Dojo Unit Test mais recente (não lembramos que estava no Git)
- O mistério do teste que deveria ter falhado mas passou
O que foi legal?
- O problema foi bom
- Tinha gente nova, e ainda carregava um note na mochila
- A sessão fluiu bem
- Os 7 minutos de programação foram respeitados
Durante a pizza, o Breno explicou o mistério do teste que se recusou a falhar. Tivemos uma breve discussão a respeito de como agir nestes casos em que o inesperado acontece. Chegamos à conclusão de que, se alguém souber o porquê, este deve explicar o fenômeno aos outros participantes.
Ah, um outro ponto positivo apontado na retrospectiva foi o texto na camiseta do Breno dizendo que ele nunca
* Ficou curioso pra saber mais sobre os outros problemas? Visite: http://groups.google.com/group/dojo_sp/web/fontes-de-problemas?hl=pt-BR
Permalink
06.05.08
Posted in C, Dojo
at 2:12 pm
by marivb
- Data: 30/Abril/2008
- Participantes: Breno Franco, Cecilia Fernandes, Fabricio Sousa, Hugo Corbucci, Jacqueline Marchetti, Leandro Lameiro, Mariana Bravo, Yoshi
- Randori: Número de Erdos em C, com o Dojo Unit Test
- Fonte: http://dojo_sp.googlegroups.com/web/36-erdos.zip
Escolhemos o problema de uma lista de 3 opções, e já saímos codando. Depois do primeiro turno, percebemos que faltava explicar melhor o problema e fazer a lista de “To-Dos” pois os testes estavam indo em uma direção estranha. Ok, diminuímos a velocidade e anotamos as tarefas:
- Adicionar artigo
- Guardar autores
- Guardar relações
- Calcular número de Erdos
Seguimos com a implementação, adicionando artigos (relações), mas guardando apenas os nomes dos autores. Tivemos dificuldades ao lidar com strings – ou melhor, char*‘s – em C. Depois de armazenar os autores, um dos participantes sugeriu de tentar calcular o número de Erdos com base em uma estrutura de Union-Find, evitando a necessidade de armazenar todas as relações. Por isso, pulamos direto para a última tarefa, mas sem discutir muito como seria essa abordagem. Não fomos muito longe, no entanto, porque o tempo acabou.
Retrospectiva
Para a retrospectiva, adotamos um formato diferente usando 3 cores de post-its: amarelo para “O que aprendemos?”, vermelho para “O que nos atrapalhou?” e cinza para “Encafifamentos – coisas que queremos discutir”. Alguns dos assuntos e pontos levantados foram:
- C com TDD esta começando a fluir bem
- O problema e a solução proposta parecem interessantes
- Temos voluntários e interessados em organizar Dojos de sábado (acompanhem na lista mais sobre esse assunto)
- Respeitamos o turno de 7 minutos, o Dojo fica mais dinâmico
- Nossa conversa no vermelho: melhorou, mas pode melhorar
- Nosso Makefile ainda tem problemas
- O Dojo Test não mostra resultado colorido e nem avisa quando todos os testes passam
- Em C, ainda nos faltam estruturas básicas como listas e mapas. Podemos usar algo pronto ou implementar as nossas próprias (essa opção parece mais legal)
- Tentamos evitar de lidar com char*, strings em C é ruim, não estamos acostumados
- Ainda não sabemos balancear discussão e código, por essas e outras parece que não chegamos na parte legal dos problemas
Permalink
