Desafio Php - Número De Erdos

Número de Erdos

O Número de Erdos é uma homenagem prestada ao grande matemático húngaro Paul Erdos, que publicou em toda sua vida mais artigos do que qualquer outro matemático trabalhando com centenas de colaboradores. Este número, que mede a 'distância colaborativa' entre um autor de um artigo e Paul Erdos, é calculado da seguinte maneira:

Erdos possui o número de Erdos igual a 0;

 

Um matemático M possui esse número igual a soma de 1 com o menor número de Erdos dos matemáticos que escreveram um artigo junto com M;

Aquele(a) que nunca escreveu nenhum artigo com Erdos ou com algum matemático que tenha escrito com Erdos ou com um matemático que escreveu com outro que tenha escrito com Erdos, e assim sucessivamente, tem número de Erdos infinito.

Existem 511 matemáticos com número de Erdos igual a 1, ou seja, que escreveram artigos em parceria com Erdos. Os matemáticos que escreveram artigos junto com estes, possuem esse número igual a 2, os que escreveram artigos junto com estes últimos, possuem o número igual a 3, e assim por diante.

Escreva um programa que, dada uma lista de publicações e seus autores, calcule o número de Erdos de cada autor.

Este problema foi adaptado de http://br.spoj.pl/problems/NUMERDOS/. A descrição do problema foi reduzida para agilizar o entendimento

Minha Solução

Eu conseguir realizar este desafio porém o código pode ser bastante melhorado porém funciona. O bacana seria que vocês tentassem fazer sem olha-lo para que sejam gerados códigos diferentes e possamos aprender uns com os outros.

Classes

Publicacao

<?php

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
* Description of publicacao
*
* @author Bruno Quaresma
*/
class Publicacao {

 private $titulo;
 private $autores = array();

 function __construct($titulo,$autores = array()){
 $this->titulo = $titulo;
 $this->autores = $autores;
 }

 function getTitulo(){
 return $this->titulo;
 }

 function getAutores(){
 return $this->autores;
 }
}

?>

Erdos

<?php

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
* Description of erdos
*
* @author Bruno Quaresma
*/
class Erdos {

 private $nome;
 private $numero;
 private $lista;
 private $count;
 private $incidentes = array();
 private $publicacoes = array();

 function __construct($nome_de_erdos, $numero_de_erdos,$publicacoes = array()) {
 $this->nome = $nome_de_erdos;
 $this->numero = $numero_de_erdos;
 $this->publicacoes = $publicacoes;
 $this->lista[$nome_de_erdos] = $numero_de_erdos;
 $this->count = $numero_de_erdos;
 for($i=0;$i<count($publicacoes);$i++){
 $this->reload_list();
 }
 }

 private function reload_list(){
 foreach($this->lista as $autor=>$numero){
 foreach($this->publicacoes as $publicacao){
 $autores_publicacao = $publicacao->getAutores();
 if(in_array($autor, $autores_publicacao)){
 foreach($autores_publicacao as $autor_publicacao){
 if($autor_publicacao != $autor && !(isset($this->lista[$autor_publicacao]))){
 $this->lista[$autor_publicacao] = $this->count+1;
 }
 }
 }else{
 foreach($autores_publicacao as $autor_publicacao){
 $this->incidentes[$autor_publicacao] = 'infinity';
 }
 }
 }
 }
 $this->count++;

 }

 function show(){
 echo '<pre>';
 var_dump(array_merge($this->lista,array_diff_key($this->incidentes,$this->lista)));
 }

}

?>

Arquivo de Entrada

<?

include_once 'class/publicacao.php';
include_once 'class/erdos.php';

$nome_de_erdos = 'Erdos';
$publicacoes = array();

$publicacoes[] = new Publicacao('Publicação 2', array('Paula','Maria','José'));
$publicacoes[] = new Publicacao('Publicação 1', array('Bruno',$nome_de_erdos,'João'));
$publicacoes[] = new Publicacao('Publicação 2', array('Bruno',$nome_de_erdos,'José'));
$publicacoes[] = new Publicacao('Publicação 3', array('Maria','Gabriel','Rony'));
$publicacoes[] = new Publicacao('Maria José é uma #@?$%~',array('Carlos','Eduardo'));

$erdos = new Erdos($nome_de_erdos, 0, $publicacoes);
$erdos->show();

?>