CodeKata #1: Encontre a sequência [Conclusão]

Tempo de leitura: menos de 1 minuto

Fala galera, ainda falando sobre o CodeKata #1: Encontre a sequência, na segunda-feira dia 08/02, publiquei o resultado do CodeKata, mesmo oficialmente tendo apenas duas pessoas que responderam ao teste, a repercussão das possíveis soluções foi grande aqui no meu time.

Inclusive recebi no fim da noite de segunda-feira a solução do Fernando Silva que trabalha aqui comigo. Ele jurou de pé junto que a solução teria assertividade de 100%, ele também afirmou que não teve acesso aos outros resultados, e realmente isso foi confirmado pela solução dada.

Rodei a bateria de teste para a implementação dele e realmente foi 100%, mas como ele mandou pós data limite, resolvei criar mais um cenário para validar a seguinte afirmação no problema: “As cadeias serão compostas pelos seguintes caracteres: A, B, X, Y.”

Assim criei o seguinte cenário:

p = ABC
t = BXYYBBXABCAYYBBYYA
resultado esperado direta  = vazio ou erro (exception)
resultado esperado reversa = vazio ou erro (exception)

Por tanto seu Fernando, seu código não deu 100%! kkkk
Mas por ter uma solução simples e diferente resolvi postar, ele usou Regex para resolver o problema, veja:

[code language=”java”]
public PosicaoTO encontrar(final String p, final String t) {
PosicaoTO retorno = new PosicaoTO();
Pattern pattern = Pattern.compile(p);
Matcher m = pattern.matcher(t);
while (m.find()) {
retorno.addPosicaoDireta((m.end() – p.length()) + 1);
}
pattern = Pattern.compile(new StringBuffer(p).reverse().toString());
m = pattern.matcher(t);
while (m.find()) {
retorno.addPosicaoReversa((m.end() – p.length()) + 1);
}
return retorno;
}
[/code]

Também vale ressaltar o V2 do Darian. Nela, além de corrigir o problema de reversão da String t, a solução dada foi bem esperta.

A ideia foi a varrer da String “char à char” (i = uma posição da String t), fazendo um substring da posição i até o tamanho de p, depois verificava se a substring é igual a p.

Essa solução funcionaria se não fosse o cenário 11:

p = YYY
t = YYXBXYXAYAYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
resultado esperado direta  = 11;14;17;20;23;26;29;32;35;38;41;44;47;50;53;56;59;62;65;68;71;74;77;80;83;86;89;92;95;98;101;104;107;110
resultado esperado reversa = 11;14;17;20;23;26;29;32;35;38;41;44;47;50;53;56;59;62;65;68;71;74;77;80;83;86;89;92;95;98;101;104;107;110

Como ele varre a String “char à char”, o retorno na implementação dele foi 11;12;13,14;…;112, tanto para direta, quanto para reversa. Veja o código:

[code language=”java”]
public PosicaoTO encontrar(String p, String t) {
final PosicaoTO posicaoTO = new PosicaoTO();
final String pReverse = new StringBuilder(p).reverse().toString();

for (int i = 0; i < t.length(); i++) {
final int endIndex = i + p.length() > t.length() ? t.length() : i + p.length();
final String substring = t.substring(i, endIndex);
if (p.equals(substring)) {
posicaoTO.addPosicaoDireta(i+1);
}
if (pReverse.equals(substring)) {
posicaoTO.addPosicaoReversa(i+1);
}
}
return posicaoTO;
}
[/code]

Já na minha implementação, usei outra abordagem, fiz o split da String t. Veja código:

[code language=”java”]
public PosicaoTO encontrar(final String p, final String t) {
final PosicaoTO posicao = new PosicaoTO();
…
posicao.getListaPosicoesDireta().addAll(procurarPosicoes(p, t));
posicao.getListaPosicoesReversa().addAll(procurarPosicoes(new StringBuffer(p).reverse().toString(), t));
return posicao;
}

private List<Integer> procurarPosicoes(final String p, final String t) {
List<Integer> listaPosicoes = new ArrayList<Integer>();
int anterior = 0;
if (p.equals(t)) {
listaPosicoes.add(1);
}
final String[] partes = t.split(p);
for (String parte : partes) {
int posicaoAtual = anterior + parte.length() + 1;
if (t.length() >= posicaoAtual) {
listaPosicoes.add(posicaoAtual);
anterior += parte.length() + p.length();
}
}
return listaPosicoes;
}
[/code]

A do Rafael é a mais trivial, mas também funciona. Ou seja, 4 soluções diferentes para o mesmo problema.

Concluímos então que existem várias formas de resolver este problema, muitas vezes na hora de implementar até nos perdemos na idéias, um código escrito por nós hoje é lindo, daqui uma semana, um mês o mesmo código é uma “bosta”… Por várias vezes isso já ocorreu comigo, quando isso acontecer meu amigos, quer dizer que você ficou mais experiente, e agora sabe uma nova forma, e com certeza, melhor resolver o mesmo problema.

Nesse sentido o desafio CodeKata nos ajuda bastante a conhecer novas formar de fazer!

Por isso, participem!

No GitHub está disponível o fonte de todas as implementações e cenários de testes.

Abraços.