Euler 4 (Python)

Posted on 12 de junio, 2009 by Juanjo

Enunciado 4

Un número palíndromo se lee igual en ambos sentidos. El mayor palíndromo construido a partir del producto de dos números de dos dígitos es 9009 = 91 × 99.

Encontrar el mayor palíndromo que se puede construir como el producto de dos números de tres dígitos.

Solución

La solución fue obtenida en el intérprete interactivo de Python 3.0rc1+. Necesitaba Python 3 para utilizar itertools.combinations:

juanjo@fenix:~$ python3
Python 3.0rc1+ (py3k, Oct 28 2008, 09:23:29) 
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from itertools import combinations
>>> tri = range(999, 99, -1)
>>> mults = []
>>> for a,b in combinations(tri, 2):
...     s = str(a*b)
...     if s == s[::-1]:
...             mults.append(int(s))
... 
>>> max(mults)
906609

Python tips

  • combinations genera la combinación con los elementos de la lista argumento tomados de a n, si se especifica el parámetro n.
  • En Python 3 print deja de ser una sentencia para convertirse en una función, por lo que siempre debe ser llamado con parámetros.
  • unString[::-1] es un idiom usado para invertir una cadena de texto (en el ejemplo, unString). Se lee: los elementos de unString, desde el principio al final, con paso -1.

About Juanjo

Mi nombre es Juanjo Conti, vivo en Santa Fe y soy Ingeniero en Sistemas de Información. Mi lenguaje de programación de cabecera es Python; lo uso para trabajar, estudiar y jugar. Como hobby escribí un libro de cuentos que se puede descargar gratuitamente.
This entry was posted in Aprendiendo Python, Problemas and tagged , . Bookmark the permalink.
  • http://patriciogomez.com.ar patricio

    JJ Conti!

    Muy buen hack para determinar la “palindromidad” de un string!

    Para los que no usamos py3, conocés la diferencia de performance entre usar combinations y dos for anidados?

    Otra cosa, en lugar de almacenarlos en una lista, no te conviene ir guardando el mayor, preguntar en cada producto y recién ahí fijarte si son palíndromos?

    Saludos

  • Juanjo

    Lo que combinations te evita es crear una mega lista en memoria. A medida que vas necesitando elementos, estos se van generando.

  • http://patriciogomez.com.ar patricio

    Aca va mi versión, sin itertools, claro!
    Con cálculo de tiempo incorporado también.

    import time
 
digitos = 999
max = 0
 
t1 = time.time()
for i in range(1,digitos):
    for j in range(1,digitos):
        prod = (i*j)
	if prod > max:
	    s = str(prod)
	    if s == s[::-1]:
	        max = prod
t2 = time.time()
 
print max
print t2 - t1
  • Juanjo

    La verificación temprana de si prod > max está buena! Ahorra buscar palíndromos innecesarios.