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 :)

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.

Recuperando valores com Javascript passados pela URL

Uma coisa chata do Javascript é que não é tão simples pegar valores passados via GET (pela URL) como é, por exemplo, no PHP. Para facilitar a vida fiz uma função simples, mas que resolve o problema:

/**
 * Created by: http://gustavopaes.net
 * Created on: Nov/2009
 * 
 * Retorna os valores de parâmetros passados via url.  
 **/
function _GET(name)
{
	var url   = location.href.replace(location.href.split("?")[0] + "?", "");
	var itens = url.split("&");

	for(n in itens)
	{
		if( itens[n].match(name) )
		{
			return unescape(itens[n].replace(name+"=", ""));
		}
	}
	return null;
}

document.write( _GET("titulo") );

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.