Google Treasure Hunt 3: Busca em Profundidade (Depth-First Search)

Esse é outro problema do Google Treasure Hunt que eu resolvi. Esse foi o mais fácil de todos, e realmente não era necessário nenhum conhecimento de programação. Tenha-se em mente apenas que o não uso de programação para resolvê-lo não é de modo algum divertido! Tente ensinar seu computador a fazê-lo por você… O problema que eu obtive no Google foi o seguinte:

“Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host P with a destination of 4.229.231.150. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)”

O diagrama para o modelo da rede acima foi fornecido na forma da tabela de roteamento a seguir:

“

A 26.40.28.17 75.174.216.140 => 126.186.188.58 26.40.28.17 => 17.100.195.84 4.229.231.0/24 => 75.174.216.140 13.157.234.26

B 13.157.234.26 76.246.145.72 => 53.12.68.161 126.186.188.58 => 75.174.216.140 53.12.68.0/24 => 26.40.28.17 17.100.195.84

C 53.12.68.161 75.174.216.140 => 219.88.219.35 229.23.61.42 => 13.157.234.26 17.100.195.0/24 => 103.19.57.145 126.186.188.58

D 103.19.57.145 86.60.122.237 => 86.60.122.237 117.146.177.141 => 53.12.68.161 229.23.61.0/24 => 219.88.219.35 212.222.1.12

E 4.229.231.150 4.229.231.150 => 103.19.57.145 54.35.7.207 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 229.23.61.42

F 54.35.7.207 4.229.231.150 => 229.23.61.42 13.157.234.26 => 199.223.210.72 26.40.28.0/24 => 4.229.231.150 86.60.122.237

G 86.60.122.237 229.23.61.42 => 54.35.7.207 13.157.234.26 => 103.19.57.145 103.19.57.0/24 => 212.222.1.12 219.88.219.35

H 212.222.1.12 126.186.188.58 => 219.88.219.35 75.174.216.140 => 86.60.122.237 103.19.57.0/24 => 103.19.57.145 229.23.61.42

I 229.23.61.42 4.229.231.150 => 4.229.231.150 117.146.177.141 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 212.222.1.12

J 199.223.210.72 53.12.68.161 => 229.23.61.42 4.229.231.150 => 54.35.7.207 219.88.219.0/24 => 219.88.219.35 4.229.231.150

K 219.88.219.35 4.229.231.150 => 199.223.210.72 17.100.195.84 => 212.222.1.12 126.186.188.0/24 => 86.60.122.237 103.19.57.145

L 117.146.177.141 4.229.231.150 => 219.88.219.35 117.146.177.141 => 126.186.188.58 26.40.28.0/24 => 76.246.145.72 75.174.216.140

M 75.174.216.140 199.223.210.72 => 13.157.234.26 4.229.231.150 => 117.146.177.141 126.186.188.0/24 => 17.100.195.84 26.40.28.17

N 17.100.195.84 4.229.231.150 => 26.40.28.17 219.88.219.35 => 13.157.234.26 17.100.195.0/24 => 75.174.216.140 76.246.145.72

O 76.246.145.72 4.229.231.150 => 17.100.195.84 86.60.122.237 => 126.186.188.58 13.157.234.0/24 => 53.12.68.161 117.146.177.141

P 126.186.188.58 13.157.234.26 => 53.12.68.161 4.229.231.150 => 76.246.145.72 103.19.57.0/24 => 26.40.28.17 117.146.177.141

”

Como você talvez tenha suposto, o primeiro símbolo é o ID do nó de rede, seguido por seu número IP. A seguir, você tem uma sequência de 3 regras de roteamento, o nó pode ver se essa regra em específico serve para o pacote entrante (incoming packet, ou pacote de rede no estágio de ingresso ao roteador). O ultimo número IP nos dá a rota padrão (“default route”), apenas no caso em que esse nó não encontrou nenhuma regra de roteamento que coubesse para um dado pacote (a rota padrão é como um “else” após uma sequência de “IF”s...).No caso do pacote chegar à rota padrão, esse pacote será direcionado para o host definido pelo endereço IP na última coluna da tabela acima.

Criei uma solução em C++, que usa um método de busca em profundidade para buscar por um caminho válido saindo de um dado nó para outro no modelo de rede do problema. Minha idéia foi fazer a função de busca em profundidade (em ingles, “depth-first search”) andar de nó em nó (nós são rotulados como: A, B, C, etc.), iterando sobre cada uma das regras da tabela de roteamento, e procurando por cada uma dessas regras que possa rotear adequadamente o pacote através da rede. A função abaixo é auto-explicável:

“

bool RoutingTable::routeTo( string node, string* resp )

{

bool do_it_again = true;

RoutingEntry rentry = findRouteEntry( node );

if ( rentry.doneThis() )

return false;

resp->append( rentry.getId() );

if ( rentry.getAddress().compare(getFinalDestination()) == 0 ) {

return false;

}

vector<RoutingRule> routing_rules = rentry.getRules();

vector<RoutingRule>::iterator i;

rentry.markThis(true);

// go through each of the routing rules

for ( i = routing_rules.begin(); ( i != routing_rules.end() ) &&

do_it_again; i++ )

{

if ( (*i).canRoute(getFinalDestination()) ) {

do_it_again = routeTo( (*i).getRedirection(), resp );

} // if

} // for

rentry.markThis(false);

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

return do_it_again;

}

”

Nessa solução usei apenas a STL do C++, ou C++ Standard Template Library (STL). Todos os nós são armazenados em estruturas como elementos de um vector, e são localizadas por símbolos de ID (A, B, C, etc.), ou por números IP (método findRouteEntry()). Cada nó tem a sua própria estrutura “Rules” (que você pode obter chamando getRules()). Uma vez processadas, cada uma dessas regras pode apontar para um outro nó da tabela, e a função routeTo pode atuar de forma recursiva sobre uma dada regra. Se nenhuma regra suficiente para combiner com o pacote for encontrada, a função routeTo é chamada sobre o nó retornado pela chamada a “getDefaultRoute”:

“

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

“

As chamadas para a função markThis() são para evitar recursões infinitas (iterar sobre os mesmos nós, de uma forma circular e muitas vezes irreversível, levando ao esgotamento de recursos computacionais). A semântica é simples: markThis(true), quando o código precisar entrar numa “regão crítca”, e markThis(false) quando tiver saído da região crítica.

Você conseguiria encontrar a diferença entre o método de roteamento que eu formulei para o que é implementado por roteadores de rede de verdade (de fabricantes como Cisco)? Talvez meus posts anteriores com questões da certificação CCNA da Cisco possam ajudar...

Google Treasure Hunt 4

O Google resolveu disponibilizar uma espécie de competição, onde são propostos problemas e pede-se a solução deles, cujas respostas sugerem (na verdade, praticamente obrigam) a aplicação de algum recurso computacional. Até onde eu sei, os problemas são únicos para cada candidato, o que inviabiliza qualquer tentativa de “trabalho em conjunto”. Chama-se de “Google Treasure Hunt 2008” [http://treasurehunt.appspot.com/]. O conjunto de problemas apresentado (atualmente, contando com apenas 4) assemelha-se aos vistos em outros campeonatos de programação, como o International Collegiate Programming Contest (ICPC), da Association for Computing Machinery (ACM) [www.acm.org]. Resolvi o último desses problemas (o quarto), e detalho aqui como cheguei à solução.

O problema proposto foi o seguinte:

“Find the smallest number that can be expressed as

the sum of 11 consecutive prime numbers,

the sum of 25 consecutive prime numbers,

the sum of 513 consecutive prime numbers,

the sum of 1001 consecutive prime numbers,

the sum of 1129 consecutive prime numbers,

and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as

the sum of 3 consecutive primes (11 + 13 + 17 = 41) and

the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).”

Para solucionar o problema proposto, resolvi utilizar a linguagem de programação C++, pelos recursos que a STL oferece (estruturas como set’s, vector’s, operações sobre conjuntos, etc.). Antes de tudo, o grande problema foi o de gerar os números primos. De modo que o problema não se refere a um limite razoável para a quantidade de números primos que a solução envolva, gerar uma tabela com todos os números primos até o limite considerável de 100.000, por exemplo, resolvi obter uma listagem pronta com o todos os números primos abaixo de 100 mil [http://members.aol.com/MICRO46/primes_1.zip], um total de exatamente 78498 primos. A razão de usar uma tabela pronta foi que o método que eu estava usando para gerar essa lista de primos demorava algo em torno de 4 minutos... Posteriormente, otimizei o procedimento para durar menos de 0,5 segundos, e gerei o resultado em disco. Contudo, quem não tiver afim de gerar essa quantidade de primos, esses arquivos prontos são uma mão na roda. Com o conjunto de primos em mãos, apliquei o procedimento seguinte:

1) Calcular as somas dos números primos em cada um dos intervalos (11, 25, 513, 1001, 1129) – isso implica em somar os primos em todos os subintervalos de tamanho 11, por exemplo, dentro do conjunto de primos, o que gerou uma seqüência de 78488 intervalos de tamanho 11, até 77.370 subintervalos de tamanho 1129;

2) Fazer uma intersecção de conjuntos, 2 a 2, com os conjuntos resultantes da operação acima (por exemplo, as somas de todos os subintervalos de tamanho 11 geram um conjunto) – o objetivo é obter as somas que são comuns entre esses conjuntos de somatórios de primos;

3) Ordenar o conjunto intersecção resultante e mostrar o primeiro valor (ou seja, o menor).

Para as etapas 1 e 2, o método que usei foi o seguinte:

void

sum_subintervals(const vector<long>& primes, unsigned long max,

set<long>* pivot)

{

unsigned long soma = 0, j = 0, old_sum = 0;

set<long> sums;

for (j = 0; j <>

{

soma += primes.at(j);

} // for

sums.insert(soma);

while ( (j <>

{

old_sum = soma;

soma = old_sum - primes.at(j-max) + primes.at(j);

++j;

sums.insert(soma);

}

set<long> s;

if (pivot->size() != 0)

{

set_intersection(sums.begin(), sums.end(), pivot->begin(),

pivot->end(), inserter(s, s.end()) );

pivot->clear();

copy(s.begin(), s.end(), inserter(*pivot, pivot->begin()));

}

else

{

copy( sums.begin(), sums.end(), inserter(*pivot, pivot->end()) );

}

}

O código é pouco óbvio, mas eu explico: o que ele faz é pegar intervalos de um certo tamanho (11, 25, 513, etc.) e somar os elementos nesse intervalo. Uma solução bastante elementar seria tentar somar diretamente todos os valores, e fazer isso para cada intervalo. Computacionalmente, no entanto, esse método repete desnecessariamente operações de soma (a maior parte dos elementos seriam somados duplicados entre subintervalos consecutivos). Foi exatamente nessas somas supérfluas que o algoritmo que eu fiz gerou otimizações. Por exemplo, o primeiro subintervalo de tamanho 11 é o seguinte:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

O próximo subintervalo é assim:

{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}

Qual a diferença entre os 2? No segundo, inseriu-se o 37 e removeu-se o 2. De forma geral, cada subintervalo adiciona à seqüência anterior o próximo elemento primo, e remove o primeiro elemento da sequência anterior do resultado. Aplicando esse método iterativamente, foi possível reduzir a complexidade da solução de uma exponencial (em função do quadrado do conjunto de primos) para uma solução linear, com o esforço de execução variando apenas sobre o tamanho da tabela de primos.

Pra finalizar, a parte mais simples do código apenas mostra o algoritmo acima rodando em cima de cada constante do problema:

set<long> all_sums;

int nums[5] = { 11, 25, 513, 1001, 1129 };

int i;

for (i = 0; i < 5; i++)

{

sum_subintervals(primes, nums[i], &all_sums);

}

if (all_sums.size() > 0)

cout << "Solution: " << *(all_sums.begin()) << endl;

Nem precisei ordenar o conjunto resultante, porque a classe template “set” da Standard Template Library já adiciona os elementos em ordem na estrutura. Quando tudo dá certo, na submissão aparece isso:

Correct answer: XXXXXXXXXX
Your answer was: Correct

Your answer was correct! Congratulations, you're part-way there.
There will more questions over the coming weeks, and the first person to answer them all correctly will win a prize, so keep trying!

Boa sorte!