Sei que o código, pode não estar pitónico, e pode até ter alguns erros... Mas já pensei bastante sobre ele, e como não estou a conseguir chegar a uma solução, decidi postar aqui o meu código a ver se ele pode ser (e pode de certeza) melhorado para dar a resposta em tempo útil e usando o mínimo de memória possível também (presumo que seja aqui que entra o funcional).
Aqui vai então:
O enunciado do problema é o seguinte:
- Código: Seleccionar Todos
"""
Project Euler Problem 145:
Some positive integers n have the property that the sum [ n + reverse(n) ]
consists entirely of odd (decimal) digits.
For instance, 36 + 63 = 99 and 409 + 904 = 1313.
We will call such numbers reversible; so 36, 63, 409, and 904 are reversible.
Leading zeroes are not allowed in either n or reverse(n).
There are 120 reversible numbers below one-thousand.
How many reversible numbers are there below one-billion (10^(9))?
"""
Está no topo do meu código como uma doc string...
Vou dividir este post em passos, tal como fiz com o código:
1º Passo: Escrever uma função ou funções que me dêem o reverso de um número:
Para este passo, utilizei duas funções:
A primeira função, chamada reverse_as_list, recebe como input um número, converte-o em string e adiciona cada dígito desse mesmo número à lista L.
De seguida, pego nesses elementos e adiciono-os pela ordem inversa, a uma nova lista a que decidi chamar T;
A função está então com este aspecto:
- Código: Seleccionar Todos
def reverse_as_list(number):
L = []
T = []
for s in range(0,len(str(number))):
L.append(str(number)[s:s+1])
j = len(L)-1
while j >= 0:
v = L[j]
T.append(v)
j -= 1
return T
De seguida, escrevi uma outra função, chamada reverse que me dá o reverso do número propriamente dito, usando a função anteriormente definida:
- Código: Seleccionar Todos
def reverse(n):
return int(join(reverse_as_list(n),''))
2º passo: Escrever uma função para testar a condição de reversibilidade de um número (a soma de n com reverse(n) ser apenas formada por dígitos ímpares)
Aqui, usei os idiomas mais comuns para mim, os tradicionais contadores e ciclos for; o que faço é inicializar uma variável, chamada c com o valor 0 que será o meu contador.
Depois uso um ciclo for para percorrer a string toda, testando a divisibilidade de cada elemento da string por 2, com um if, e actualizando o valor do contador sempre que um dígito "passa" na condição de divisibilidade, chamei string_reversibility à função;
- Código: Seleccionar Todos
def string_reversibility(s):
c = 0
for a in range(0, len(str(s))):
if int(str(s)[a:a+1]) % 2 != 0:
c += 1
if c == len(str(s)):
return True
else:
return False
3º passo: Escrever a função reversible propriamente dita, que me diz finalmente, se um número é ou não reversível
Esta função, foi fácil de escrever para mim, dado que, creio eu, fui bastante metódico na escrita das outras funções...
Para esta, só precisei de criar uma variável de nome, res, cujo valor é igual ao da soma de n com reverse(n).
De seguida, apliquei a função string_reversibility ao valor de res, retornando esta função True, caso res seja reversível e False caso contrário;
- Código: Seleccionar Todos
def reversible(t):
res = t + reverse(t)
if string_reversibility(res) == True:
return True
else:
return False
A partir daqui, tinha apenas de fazer um loop ou usar listas por compreensão ou algo do género para obter a resposta... O pior é que o pedaço de código:
- Código: Seleccionar Todos
R = filter(reversible, xrange(1 ,10**9))
print len(R)
dá-me logo MemoryError como é de esperar ao testar tantos valores...
Tendo sido eu tão metódico a questão é, o que é que estou a fazer mal, ou que "salto mental" é que preciso de dar para obter o valor correcto? Penso que a resposta esteja na programação funcional que quero mesmo começar a dominar, mas uma ajuda era de extrema utilidade claro;
Peço desde já desculpa por meter aqui mais um problema do PE, mas só o faço quando preciso mesmo de ajuda,
Bruno
Agora entendo porquê...
Experimentem um dos descendentes da APL, como J ou K, que são linguagens extremamente rápidas (e sucintas, ou não descendessem de APL) construídas propositadamente para manipulação matemática de grandes volumes de dados e com grande precisão.
