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 – patAGata – 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 ÍparosAv 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/

Anúncios

Os comentários estão desativados.

%d blogueiros gostam disto: