dojo@centro 16/01/2013 – “Tolkien” e partes de compiladores

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

Na semana passada rolou um problema que foi muito bem recebido por todos e tem um excelente relato. Ia escrever um texto, mas postaram no grupo do Coding Dojo Rio uma excelente explicação, por isso essa explicação será postada e em seguida os participantes mais pontos positivos/negativos:

Post do Juan Lopes

É um problema que escolhemos com uma certa frequência, mas ontem tomamos um caminho bem interessante pra resolver.

Pra quem não esteve lá, é o problema da avaliação de expressões matemáticas. Terminamos o passo de tokenização da expressão, e paramos no meio da análise sintática. Estava bastante ansioso para continuar esse problema em casa, porque nunca havia feito isso “na unha”, sempre com ajuda de parser generators e fiquei surpreso em perceber que muito da teoria por trás de compiladores acaba ajudando na elegância do código final.

Essa gramática para parse de expressões aritiméticas é bem conhecida, podemos definir como:

<add> ::= <mult> (“+” <mult>)*

<add> ::= <mult> (“-” <mult>)*

 

<mult> ::= <primary> (“*” <primary>)*

<mult> ::= <primary> (“/” <primary>)*

<primary> ::= <number>

<primary> ::= “(” <add> “)”

O que achei legal é que se abrirmos mão de algumas práticas mais comuns, podemos implementar essa gramática quase como se lê em python.

A soma, por exemplo:

def add(tokens):

e = mult(tokens)        

while(tokens[0][0] in “+-“):

kind, image = tokens.pop(0) #+-

e = e + mult(tokens) + [kind]

return e

Simplesmente combinando a regra para parsear a soma com a da multiplicação (mostro depois), eu consigo combinar os dois resultados. Por exemplo, se eu tiver a expressão “1*2+3*4”, a primeira chamada de mult, vai ler os tokens 1, * e 2, processar isso e retornar algo como [1, 2, ‘*’], a segunda chamada (dentro do for), vai obter o token ‘+’ (tokens.pop(0)) e vai chamar mult de novo para ler 3*4, no final, ele vai concatenar o resultado da primeira chamada, com o resultado da segunda chamada e vai colocar a operação no final, resultando em:

[1, 2, ‘*’, 3, 4, ‘*’, ‘+’]

A multiplicação tem uma implementação igual (exceto que chama a regra primary, no lugar):

def mult(tokens):

e = primary(tokens)        

while(tokens[0][0] in “*/”):

kind, image = tokens.pop(0) #*/

e = e + primary(tokens) + [kind]

return e

A única regra diferente é a primary, que tem que decidir se produz um número ou inicia uma nova expressão com parenteses, mas isso é só uma questão de verificar o tipo do token antes:

def primary(tokens):

kind, image = tokens[0]

if kind == ‘N’:

tokens.pop(0) #N

return [int(image)]

elif kind == ‘(‘:

tokens.pop(0) #(

e = add(tokens)

tokens.pop(0) #)

return e

E só usando esse parser recursivo, conseguiríamos parsear qualquer expressão contendo as quatro operações básicas e parenteses, respeitando a precedência das operações.

O gist do método parse que passa nos testes do problema de ontem: https://gist.github.com/4556536.

Complementado por Thiago Belem:

Menção honrosa ao BNF que torna isso tudo super fácil de entender 🙂

 

Curti muito o problema e a nossa caminhada até uma possível (e bem plausível!) solução.

 

Claro que a sua explicação do N [+ N]* mudou o rumo da coisa, mas era só questão de identificar isso.

Compiladores foi a matéria que mais gostei (e aprendi algo?) até hoje na faculdade, mas o dojo de ontem valeu mais que um período inteiro! 😀

 

A qualidade e o conteúdo do dojo estão cada vez melhores, fico muito feliz de acompanhar esse progresso e aprender junto.

E como não poderia deixar de ser, Rodolfo contribuiu com:

Lexical Scanning in Go – Rob Pike

https://www.youtube.com/watch?v=HxaD_trXwRE

Slides: https://cuddle.googlecode.com/hg/talk/lex.html

E as pessoas que aprenderam um pouquinho mais de compiladores foram:

• Flávio Amieiro
• Eduardo Stalinho
• Otávio Cardoso
• Thiago Belem
• Carlos Cunha
• Juan Lopes
• Eduardo Vinicius
• Jacqueline Abreu
• Israel Teixeira

Os “tolkiens” positivos foram 😀 :

• “Tolkien +++
• Problema (foi uma excelente releitura do problema, mostrando que podemos dar abordagens diferentes para problemas já feitos) +++
• Polonesa Reversa (com gente achando que era posição sexual O_õ) ++
• Componentes de compilador construído na unha (tem gente que deixará a unha crescer)
• Compiladores apresentados mais formalmente no dojoRio
• Volta de pessoas conhecidas e que estavam sumidas +++
• Jac chegou “cedo” hoje (menos Barra na vida da Jac)
• Cuca da Cissa – Mais um produto Bel[eé]m +
• Rever os participantes do dojoRio #Centro
• Não houve muita reescrita do código do outro – o grupo estava unido e conseguiu avançar a solução dada pela dupla que estava pilotando anteriormente.
• Python
• Casa cheia+
• Muita comida (em especial a Cuca da Cissa) ++++
• Retorno (pessoal) ao dojo
• Chegar cedo
• As pérolas proferidas neste dojo

Os “tolkiens” negativos foram 😀 :

• Pessoas falando no vermelho
• Jac pedindo desculpas demais
• Código do tokenizer pode melhorar
• Problema não foi definido no início e isso causou certo atraso
• Não tinha suco
• Atraso
• Café acabou

 Quem sabe um dia, poderemos ter um compilador totalmente construído no dojoRio. Isso seria demais.

Se você gostou do relato, não deixe de estar conosco na Íparos, Av Treze de Maio, 13 – sala 616 – TODAS as 4º feiras. O pessoal começa a chegar entre 18:30 e 19:00 e para voltar, tem o metrô Cinelândia pertinho  .

Esperamos todos vocês lá \o/

dojo@centro 9/01/2013 – Primeiro dojo de 2013 \o/

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

Para o primeiro dojo do ano, o problema escolhido foi em grande estilo: Qual a maior sequência de palavras na forma “escada” encontramos em uma determinada lista (a lista foi indicada no link do problema) ?.

A forma “escada” pode ser exemplificada por: Rato – Pato – patA – Gata – gatO . Repare que essas palavras compartilham 3 letras e só variam em 1. Continuando a lista Fato – Rato – Pato – patA – Gata – gatO – Fato – elas continuam sendo diferenciadas por apenas 1 letra.  Colocarmos na lista: Fato – Rato – Pato – patA – Gata – gatO – Fato – RaSo – raso não pertence a lista, pois difere das outras palavras da lista atual em 2 letras. Ou seja, queremos palavras que podem ser transformadas em outras palavras mudando apenas 1 letra.

Essa tentativa de explicação da forma “escada” é explicada de verdade pela Distância de Levenshtein. Copiando da Wikipedia, temos:

 A distância Levenshtein ou distância de edição entre dois “strings” (duas sequências de caracteres) é dada pelo número mínimo de operações necessárias para transformar um string no outro. Entendemos por “operações” a inserção, deleção ou substituição de um carácter

No nosso problema, procuramos as palavras que tenham distância de edição igual a 1.

Em PHP, temos uma função muito marota: int levenshtein ( string $str1 , string $str2 ).

O problema foi encontrado no Reddit e foi muito legal utilizarmos mais esta fonte de desafios a serem resolvidos :D.

Nós usamos PHP para construir o código e utilizamos DFS para encontrar uma solução. DFS é sigla de Depth-First Search, ou seja, Busca em Profundidade. O algoritmo de DFS realiza Backtracking para encontrar a resposta: ele começa a busca de um nó raiz e vai até a folha da árvore. Caso ele encontre a solução, ela é retornada. Se não conseguir a solução, o algoritmo retorna até a raiz da árvore e começa novamente a busca – daí o nome de busca em profundidade.

Abordamos o problema desta maneira pela natureza que ele apresenta, dado que temos diversas opções de listagem com distância de Levenshtein igual a 1, mas o objetivo era encontrar o maior conjunto de palavras que estivessem nesse padrão.

E quem começou o ano diretamente no dojoRio foi:

• Jonatas Emidio
  
• Valéria Parajara
• Eduardo Stalinho
• Juan Lopes
• Vinicius Pacheco
• Thiago Belem
• Otávio Cardoso
• Jacqueline Abreu

Dizem que o quem começamos o ano fazemos o ano inteiro – espero mesmo que isso seja verdade ^.^. Neste dojo tivemos até brownie e brigadeiro – por Cissa Belém e Valéria Parajara, adoçando os nossos encontros o/.

E os pontos positivos desta caçada foram 😀 :

• Volta do dojoRio #Centro – 1° dojoRio de 2013 \o/ +++
• Problema +
• Reddit – nova fonte de problemas ++
• Levenshtein – Distancia de Levenshtein +++
• PHP ++
• Chocolate +
• Algoritmo – Estar estudando algoritmos diferentes é muito positivo
• Brigadeiro +
• Brownie Bel[eé]m +
• Galera participativa
• Pessoas novas +
• Pessoal do HoraExtra aceitou o convite (da Val Parajara) e veio ver as mudanças do dojoRio (espero que tenham sido para melhor ^.^)
• As pessoas do #dojoRio
• Grafos

E as migalhas deixadas no chão do dojo (vulgo pontos negativos 😦 ) foram

• Pouca gente
• Não trouxe comida
• Atraso ++
• Backtracking
• Cansaço (será que ainda é da virada do ano??)
• Deixar de acompanhar a resolução na metade.
• Quebra de regras do dojo – piloto e copiloto não participaram do momento de explicação do problema/solução e continuaram programando
• “Seu” Carlos não veio 😦 +
• Muita Conversa +
• Sujamos a sala do dojo +
• Problema
• Muito doce e pouco salgado
• Timeout – durante um teste

E assim, abrimos o ano de 2013, começamos e não pretendemos parar até o natal, mas falta muiiiiiiiiiiiito para ganharmos presente novamente.  Então, não deixe de estar conosco na Íparos, Av Treze de Maio, 13 – sala 616. O pessoal começa a chegar entre 18:30 e 19:00 e para voltar, tem o metrô Cinelândia pertinho  .

Esperamos todos vocês lá \o/

dojo@centro 19/12/2012 – Dojo de Natal && Último dojo de 2012

Olá, pessoas queridas.

O dojo de encerramento de 2012 e o de natal foi uma orgia alimentar com casa cheia \o/.

De panetone até biscoito de gengibre, teve de tudo. Este dojo foi um dojo especial também pela escolha do problema ter a ver com a data. Houve pessoas que pediram que o problema fosse o fim do mundo (é, pessoal, acho que o mundo não acabou no dia 21/12/2012, mas continuem tentando :P), mas o de natal ganhou mesmo

O problema foi:

“Imagine que o segredo do Papai Noel não esteja na velocidade em que ele trabalha para atender as crianças do mundo inteiro, mas no fato de que ele pode duplicar seu trenó em qualquer ponto da viagem para atender outras crianças simultaneamente.

Mas se fosse só isso, ele poderia criar tantos trenós quantas crianças existem e entregar no menor tempo possível. O problema é que o trenó é movido por um pó mágico. Cada trenó que ele cria gasta pó proporcional à distância que ele percorre. E esse pó é muito caro (custa muitas boas ações das crianças). Então, dada uma lista de crianças, o Papai Noel quer saber qual o mínimo de pó que ele precisa para entregar presentes na casa de todas elas. 

Dependendo dessa lista, pode ser uma boa alternativa usar um trenó só, ou duplicar o trenó depois de atender uma certa criança específica, ou até mesmo usar N trenós para as N crianças. Depende muito da lista. ”  – http://goo.gl/AKgYO

Esse é um clássico problema de grafos e a solução se encaminhou naturalmente para uma implementação do algoritmo de Prim

O algoritmo de Prim destina-se a achar as arestas que compõem a árvore geradora mínima (ou seja, uma árvore com todos os vértices, mas ligados pela menor quantidade de arestas)  e tem várias aplicações interessantes :D.

A wikipedia salvadora explica o algoritmo da seguinte forma:

“Um algoritmo genérico para o algoritmo de Prim é dado da seguinte forma:

Escolha um vértice S para iniciar o subgrafo

enquanto há vértices que não estão no subgrafo

selecione uma aresta segura

insira a aresta segura e seu vértice no subgrafo        “

Uma aresta segura, no caso do algoritmo de Prim, é:

“A aresta segura é sempre a aresta de peso mínimo que conecta a árvore a um vértice não presente no conjunto X (subgrafo).”  Fonte: Universidade Federal de Alfenas.

No nosso problema, as casas das crianças são os vértices e o caminho entre as casas são as arestas selecionadas. O peso mínimo significa que escolheremos a casa mais próxima de onde o Papai Noel está, desde que ela não tenha sido visitada antes.  Com isso temos: Enquanto há casas de crianças que não foram visitadas, escolha a casa mais próxima, desde que ela não tenha sido visitada antes.

A solução de até onde conseguimos evoluir está no repositório do dojo no github

E os gulosos foram:

• Thiago Belem
• Juan Lopes
• Eduardo Stalinho
• Otávio Cardoso
• Carlos Cunha
• Henrique Bastos
• Israel Teixeira
• Lucas R. Martins
• Diogo Vincenzi
• Jacqueline Abreu
• Jonatas Emidio

E as carinhas boazinhas (que ganharão presentes lindos), foram :D:

• Comida (panetone +, cachorro quente, biscoitos bel[eé]m de gengibre ++++)
• Pessoas
• Problema+++++++++
• Papai Noel na velocidade da luz (é possível?? Saiba mais no próximo episódio de “O Dojo de Natal – aventura no mundo das conjecturas” XD). ++
• Python +
• Primeira participação no dojoRio o/
• Boa divisão do problema – dividimos o problema em partes (metas) para resolvê-lo melhor, em partes
• Fim do mundo na sexta (acho que não foi, nê…)
• Volta da galera antiga e galera nova aparecendo
• Apelidos fofos sendo revelados – alguém agora ganhou a alcunha de “Xuco-Xuco” +
• Meninas programando
• O twitter do dojoRio voltou – Sigam o @dojoRio  #FF @dojoRio 😀 +
• Participação da Galera – a vergonha dos novatos está diminuindo \o/
• 2012 foi um ano muito legal para o dojoRio
• Partials (Python) +
• Prim
• Casa cheia
• Escolha prévia do problema
• Guardaram biscoito para mim (mim = Jonatas Emidio, Jacqueline Abreu e Valéria Parajara #ProntoFalei e #ObrigadaCissa)
• Espírito Natalino

As carinhas malvadas – essas não ganham presente, foram 😦 :

• Atraso ++
• Não acompanhar a evolução do problema +
• Só abordamos as crianças malvadas
• Muito tempo sem dojoRio
• Não enrolar tanto para começar o dojo
• Atrasos pessoais de 2012
• Bagunça durante os dojos de 2012
• Último dojoRio de 2012

Esse foi o último dojo de 2012 no Centro, mas em 2013 tem mais. O dojoRio – Centro volta com as atividades no dia 9 de janeiro de 2013, por isso, não deixe de estar conosco na Íparos , Av Treze de Maio, 13 – sala 616. O pessoal começa a chegar entre 18:30 e 19:00 e para voltar, tem o metrô Cinelândia pertinho :D.

Esperamos todos vocês lá \o/