CodeKata #5: Número de Erdős

Tempo de leitura: menos de 1 minuto

E aí, vai encarar?

Fala aí galera, como vão vocês? Já estavam com saudades dos Codekatas, né? É eu sei, varia pessoas me cobraram novos desafios, fico muito feliz por isto.

O CodeKata #4: Jogo de dominó foi um dos mais desafiadores que já postei, não sei dizer ao certo qual foi o mais complexo, pois o CodeKata #2: Caixa Eletrônico também foi foda. Acho que a complexidade foi o motivo do baixo número de participantes, foram apenas 2 na edição passada: Flávio Pimenta e Junior Capra. Obrigado ao Pimenta e Junior pela participação.

Com a baixa participação, Pimenta e Junior puderam melhorar suas posições do ranking. Por falar nisso, Pimenta encostou definitivamente no líder Fernando Silva. Se cuida Fernando, seu posto no ranking está ameaçado!

Regras

O desafio será dado, e qualquer leitor poderá participar.
O participante terá 15 dias para dar uma solução para o problema.
A solução deverá ser escrita em Java ou Groovy.
A solução deverá ser enviada por e-mail.
As soluções e seus autores serão divulgados em um post no dia previamente fixado.
Pontuação para o ranking:
- 100 dividido pela quantidade de cenários de teste, será a pontuação dada ao cenário que ficar verde, os cenários que falharem não pontuam.
  - Pontuação por acerto (cenário verde) = 100/n° cenários
- Cenário cujo objetivo seja testar as restrições terá penalização de – 0,5 por cenário que ficar verde.
- Performance (válidos apenas para cenários que passarem, ficarem verdes):
  - Bonificação (Média para baixo): + 0,5 por cenário;
  - Penalização (Acima da média): – 0,5 por cenário; por performance
  - Adicional de 2,0 pontos para o participante que entregar a solução com maior performance (O vencedor será conhecido quando a solução dada por ele executar todos os cenários mais rapidamente que seus oponentes).

Desafio: Número de Erdős

Enviar a solução até: 24/05/2016
Divulgação do resultado até dia: 27/05/2016

O matemático húngaro Paul Erdős (1913-1996), um dos mais brilhantes do século XX, é considerado o mais prolífico matemático da história.

Erdős publicou mais de 1500 artigos, em colaboração com cerca de outros 450 matemáticos. Em homenagem a este gênio húngaro, os matemáticos criaram um número, denominado “número de Erdős“.

Toda pessoa que escreveu um artigo com Erdős tem o número 1. Todos que não possuem número 1, mas escreveram algum artigo juntamente com alguém que possui número 1, possuem número 2. E assim por diante, por tanto o número do próprio Erdős é 0.

Quando nenhuma ligação pode ser estabelecida entre Erdős e uma pessoa, diz-se que esta possui número de Erdős infinito.

Por exemplo:

O número de Erdős de Albert Einstein é 2.
E talvez, surpreendentemente, o número de Erdős de Bill Gates é 4.

Tarefa

Sua tarefa é escrever um programa que a partir de uma lista de autores de artigos, determine o número de Erdős dos autores.

Premissas

Será disponibilizada uma lista contendo os autores dos artigos;
Cada item da lista corresponderá a um artigo;
Cada artigo pode possuir de 1 à 10 autores;
Cada autor tem seu nome inicial abreviado (uma letra mais .) seguindo do seu último nome, exemplo:
- P. Erdos ou E. Leite;
Caso o artigo tenha mais de um autor, seus nomes serão separados por vírgula, exemplo:
- P. Erdos, E. Leite, F. Pimenta;
Dada a lista de autores, será solicitado o número de Erdős de um autor da lista, conforme descrição a cima.

Exemplo 1:

Entradas:
1. Lista de autores:
  P. Erdos, A. Selberg.
  P. Erdos, J. Silva, M. Souza.
  M. Souza, A. Selberg, A. Oliveira.
  J. Ninguem, M. Ninguem.
  P. Duarte, A. Oliveira.
2. Qual o número de Erdős do autor: A. Oliveira
Saída: 2

Exemplo 2:

Entradas:
- Lista de autores:
  Z. Silva, P. Erdos.
  Z. Souza.
- Qual o número de Erdős do autor: Z. Souza
Saída: -1 (Infinito)

Restrições

Número de artigos: 1 à 100;
Nome do autor deve ter no máximo 15 caracteres;
Número autores por artigo: 1 à 10;

Interface a ser implementada

Essa vez o retorno é muito simples, basta retornar um inteiro, dispensando assim a necessidade de um TO específico.

Implemente a interface:

[code language=”java”]
public interface INumeroErdosService {
/**
* Método responsável por descobrir o número de Erdos de um dado autor.
* Esse número deverá ser descoberto, considerando a lista de
* autores de uma dada lista de artigos.
* Exemplo de lista de autores de artigos:
* – P. Erdos, A. Selberg.
* – P. Erdos, J. Silva, M. Souza.
* – M. Souza, A. Selberg, A. Oliveira.
* – J. Ninguem, M. Ninguem.
* – P. Duarte, A. Oliveira.
* @param pNomeAutor nome de um autor qualquer. Ex: "A. Selberg".
* @param pAutoresArtigos cada item da lista corresponde a algo como isso: "P. Erdos, A. Selberg".
* @return é esperado um número inteiro representando o Número de Erdos do autor.
*/
public Integer descobrirNumeroErdosDoAutor(String pNomeAutor,
List<String> pAutoresArtigos) throws IllegalArgumentException;
}
[/code]

Nota: Projeto disponível no GitHub, junto também estou disponibilizando a Test Table para facilitar a adição de cenários de teste na construção da solução.

Espero que gostem!!

Participe e convide seus amigos a participarem do CodeKata #5.

Enquete: Qual o nível de dificuldade do CodeKata #5?

[polldaddy poll=9412005]

Formulário de envio

[contact-form][contact-field label=’Nome’ type=’name’ required=’1’/][contact-field label=’Email’ type=’email’ required=’1’/][contact-field label=’Solução’ type=’textarea’ required=’1’/][/contact-form]

Abraços