Gustavo Paes

Project Euler: Problema 23

Ontem finalizei o problema 23 do Project Euler. O problema em si é de fácil solução, mas se você não pensar em otimizar ao máximo a execução do seu script, pode levar horas — como o meu levou — ou até mesmo dias, para conseguir o resultado final. E ainda pode conseguir um resultado errado.

O problema 23 explica o que é um número perfeito (aquele que a soma de seus divisores resultado no próprio número), número deficiente (aquele que a soma é menor que o próprio número) e número abundante (aquele que a soma é maior que o próprio número).

Como exemplo de um número perfeito, ele cita o 28, que possui os seguintes divisores:
1 + 2 + 4 + 7 + 14 = 28

E como exemplo de um número abundante, é citado o número 12:
1 + 2 + 3 + 4 + 6 = 16

Dito isso, o problema afirma que todos os números positivos inteiros maiores que 28123 podem ser encontrados através da soma de dois números abundantes. Mas que, de 0 até 28123, não é possível afirmar isso. E o problema pede no fim é que você encontre quais são os números que não podem ser encontrados através da soma de dois números abundantes e some eles. A resposta final essa.

Sabendo de tudo isso, algo que irá mudar sua vida a partir desse ponto, vamos pensar na solução. Primeira coisa que se precisa fazer é achar todos os números abundantes entre 0 e 28123. Para isso é preciso criar uma função que ache os divisores de um determinado número. Com ela, fica fácil descobrir quais são números abundantes e quais não são:

abundantes = []
for n in xrange(1, 28124):
	if sum(divisors(n)) > n:
		abundantes.append(n)

A função divisors retorna True ou False. Para conseguir achar tudo, a função leva cerca de meio minuto.

Com esses números em um array você tem duas opções:

1. Fazer um laço de 1 até 28123 verificando os números que podem ser encontrados através da soma de dois números abundantes;

2. Fazer todas as somas possíveis do números abundantes e guardar em um array para depois ir verificando de 1 a té 28123 qual deles existe nesse array.

A primeira opção foi a que eu escolhi primeiro (não tinha tido a segunda idéia ainda). Fiz o script sem grandes dificuldades mas logo percebi que a execução iria demorar, provavelmente, mais de dia.

Parti então para um segundo script — enquanto o primeiro ia ocupando 100% de um dos processadores — para tentar chegar a uma solução melhor. Foi quando pensei na segunda opção.

Mesmo com a segunda opção, que roda mais rápido que a primeira, o script levou quase 5 horas para encontrar o número final. O script é esse:

from divisors import divisors
import time

start = time.time()

# funcao que verifica se o parametro passado pode ser encontrado
# atraves da soma de algum dos numeros abundantes encontrado
def allSum(arr):
	all_sum = []
	limit = len(arr)

	f_index = 0 # primeiro indice
	s_index = 0 # segundo indice
	
	while f_index  n:
		abundantes.append(n)

print "... encontrados %d numeros" % len(abundantes)
print

print "Somando todos os abundantes entre si..."
all_sum = allSum(abundantes)

print "... encontrado %d resultados" % len(all_sum)
print

# percorre ate o limite
print "Descobrindo numeros que nao podem ser encontrados atraves da soma..."
numbers = []
for x in xrange(1, 28124):
	# apenas para controle no console
	if x%10 == 0:
		print x

	if x not in all_sum:
		numbers.append(x)

print
print
print sum(numbers)

print
print "achado em ", (time.time() - start) , "segundos"

Por sorte consegui chegar no resultado certo, senão seriam 5 horas de processamento jogados no lixo :)

Python versus C: qual é mais rápido?

Para responder à pergunta, usei um código, que fiz inicialmente em Python, para resolver o problema 9 do Project Euler.

O resultado segue abaixo:
Python levou 66 segundos para retornar o resultado.
C levou 16 segundos para retornar o mesmo resultado.

Segue os códigos para comparação.

Código em Python

import time

limit = 1000
start = time.time()

for a in range(1, 500):
  for b in range(1, 500):
    for c in range(1, limit+1):
      if (a**2 + b**2 == c**2) and (a+b+c==limit):
        end = time.time()
        print "%d + %d + %d = %d" % (a, b, c, limit)
        print "Total time: %d" % (end-start)
        exit()

Código em C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int main(int argc, char **argv)
{

  time_t start, end;
  int a, b, c, limit;
	
  limit = 1000;
  start = time(NULL);

  for(a = 1; a < 500; a++)
  {
    for(b = 1; b < 500; b++)
    {
      for(c = 1; c < 500; c++)
      {
        if( (pow(a, 2) + pow(b, 2) == pow(c, 2)) && (a + b + c == limit) )
        {
          end = time(NULL);
          printf("%d + %d + %d = %d\n\a", a, b, c, limit);
          printf("Total time: %d\n\n", end-start);
          system("pause");
          return 0;
        }
      }
    }
  }

  system("pause");
  return 0;

}

Observação: O código em C foi compilado pelo DJGPP

Project Euler - Problema 5

Estava fazendo os problemas do Project Euler e me deparei o quinto problema, que consiste em achar o menor número divisível por todos os número do intervalo de 1 a 20.

Ou seja, o número a ser encontrado deve ser divisível — não ter resto — por 1, 2, 3, 4 … 20. Como exemplo, ele deu o número 2520, que é divisível por 1, 2, 3, 4 … 10.

Fiz um script que não demorou muito para achar esse 2520. Mas para achar o número divisível por todos os números de 1 a 20, levei quase 10 minutos, consumindo 100% de um dos cores do processador. Mas ele conseguiu achar o número certo. Abaixo segue o script em Python:

n = 1
while True:
	div = True
	for x in range(1,21):
		if n % x > 0:
			div = False
			break

	if div:
		print "Numero: %d" % n
		break

	n += 1

Para se ter uma idéia, ele fez mais 4 de bilhões de vezes de iterações. Não é à toa que demorou tanto.

Não tenho dúvidas também que essa não é a melhor forma de se resolver esse problema. Provavelmente, algum fera em Python resolve isso com uma linha.

Navegar recursivamente entre diretórios com Python

O código abaixo, em Python, retorna um Array com todos os arquivos de uma determinada extensão encontrados dentro de um diretório e seus sub-diretórios:

import os, glob, re

class Dir:
  def read(self, dir, extension, files=[]):
    for f in glob.glob( os.path.join(dir, "*") ):

      if os.path.isdir( f ):
        files = self.read( f, extension, files )
      else:
        if f.endswith(".%s" % extension):
          files.append( f )

    return files

O uso é simples:

print Dir().read("C:\Documents and Settings\gustavo\documentos", "txt")

Isso irá exibir na tela o array com os arquivos encontrados. Se o diretório for muito grande, pode demorar um tempo para processar.

Esse código usa o esquema de recursão para conseguir navegar entre os sub-diretórios. Foi bem útil para o que eu precisava.