python - reversed - Número de problema de Euler#4

reverse python

Question

Usando Python, estoy tratando de resolver el problema # 4 de los problemas de Project Euler . ¿Puede alguien decirme qué estoy haciendo incorrectamente? El problema es encontrar el palíndromo más grande hecho con el producto de dos números de 3 dígitos . Esto es lo que tengo hasta ahora.

import math

def main(): 
    for z in range(100, 1000):
        for y in range(100, 1000):
            for x in range(1, 1000000):
                x = str(x)
                if x == x[::-1] and x == z*y:
                    print x 

if __name__ == ''__main__'':
    main()

Answer 1

Intente calcular x del producto de zey en lugar de verificar cada número de 1 a un millón. Piénselo: si le pidieron que calcule 500 * 240, ¿cuál es más eficiente, multiplicándolo o contando desde 1 hasta que encuentre la respuesta correcta?

Answer 2

Algunos problemas de eficiencia:

1. comenzar en la parte superior (ya que podemos usar esto para omitir muchos cálculos)
2. no doblemente

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        for y in xrange(x, 99,-1):  # so we don''t double count   
            if x*y < max_seen: continue  # since we''re decreasing, 
                                # nothing else in the row can be bigger
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

Answer 3

Aquí hay algunas optimizaciones generales para tener en cuenta. El código publicado maneja todo esto, pero estas son reglas generales para aprender que podrían ayudar con problemas futuros:

1) si ya ha marcado z = 995, y = 990, no necesita marcar z = 990, y = 995. Greg Lind maneja esto correctamente

2) Calcula el producto de z * y luego ejecuta x en un rango amplio y compara ese valor con y * z. Por ejemplo, acaba de calcular 900 * 950, y luego ejecuta x de 1000 a 1M y ve si x = 900 * 950. ¿Ves el problema con esto?

3) Además, ¿qué ocurre con el siguiente código? (Esta es la razón por la cual su código no devuelve nada, pero no debería estar haciendo esto de todos modos)

x = str(100)
y = 100
print x == y

4) Si descubres (3), estarás imprimiendo mucha información allí. Necesita encontrar una forma de almacenar el valor máximo y solo devolver ese valor al final.

5) Aquí hay una buena forma de medir tus problemas de Euler:

if __name__ == "__main__":
    import time
    tStart = time.time()
    print "Answer = " + main()
    print "Run time = " + str(time.time() - tStart)

Answer 4

Esto es lo que hice en Java:

public class Euler0004
{
    //assumes positive int
    static boolean palindrome(int p)
    {
        //if there''s only one char, then it''s
        //  automagically a palindrome
        if(p < 10)
            return true;

        char[] c = String.valueOf(p).toCharArray();

        //loop over the char array to check that
        //  the chars are an in a palindromic manner
        for(int i = 0; i < c.length / 2; i++)
            if(c[i] != c[c.length-1 - i])
                return false;

        return true;
    }


    public static void main(String args[]) throws Exception
    {
        int num;
        int max = 0;

        //testing all multiples of two 3 digit numbers.
        // we want the biggest palindrome, so we
        // iterate backwards
        for(int i = 999; i > 99; i--)
        {
            // start at j == i, so that we
            //  don''t calc 999 * 998 as well as
            //  998 * 999...
            for(int j = i; j > 99; j--)
            {
                num = i*j;

                //if the number we calculate is smaller
                //  than the current max, then it can''t
                //  be a solution, so we start again
                if(num < max)
                    break;

                //if the number is a palindrome, and it''s
                //  bigger than our previous max, it
                //  could be the answer
                if(palindrome(num) && num > max)
                    max = num;
            }
        }

        //once we''ve gone over all of the numbers
        //  the number remaining is our answer
        System.out.println(max);

    }
}

Answer 5

La pregunta dice:

What is the largest prime factor of the number 600851475143?

Lo resolví usando C #, pero el algoritmo mismo es independiente del lenguaje.

1. Crea un método para determinar si un número es primo o no. Esto puede ser fuerza bruta (en lugar de usar un algoritmo de tamizado mucho más eficiente) y se ve así:

private static long IsPrime(long input)
        {
            if ((input % 2) == 0)
            {
                return 2;
            }
            else if ((input == 1))
            {
                return 1;
            }
            else
            {
                long threshold = (Convert.ToInt64(Math.Sqrt(input)));
                long tryDivide = 3;
                while (tryDivide < threshold)
                {
                    if ((input % tryDivide) == 0)
                    {
                        Console.WriteLine("Found a factor: " + tryDivide);
                        return tryDivide;
                    }
                    tryDivide += 2;
                }
                Console.WriteLine("Found a factor: " + input);
                return -1;
            }
        }

2. Una vez que tengo una función para determinar la primalidad, puedo usar esta función para encontrar el factor primo más alto

private static long HighestPrimeFactor(long input)
{
    bool searching = true;
    long highestFactor = 0;
    while (searching)
    {
        long factor = IsPrime(input);
        if (factor != -1)
        {
            theFactors.Add(factor);
            input = input / factor; 
        }
        if (factor == -1)
        {
            theFactors.Add(input);
            highestFactor = theFactors.Max();
            searching = false;
        }
    }
    return highestFactor;
}

Espero que esto ayude sin dar demasiado.

Answer 6

Si su programa se está ejecutando lento, y ha anidado bucles como este:

for z in range(100, 1000):
    for y in range(100, 1000):
        for x in range(1, 1000000):

Entonces, una pregunta que debe hacerse es: "¿Cuántas veces se ejecutará el cuerpo del ciclo interno?" (el cuerpo de tu ciclo más interno es el código que comienza con: x = str(x) )

En este caso, es fácil de entender. El ciclo externo se ejecutará 900 veces. Para cada iteración, el ciclo medio también se ejecutará 900 veces, lo que hace 900 × 900 u 810,000 veces. Luego, para cada una de esas 810,000 iteraciones, el ciclo interno ejecutará 999,999 veces. Creo que necesito un tiempo para calcular eso:

>>> 900*900*999999
809999190000L

En otras palabras, estás haciendo tu prueba de palíndromo casi 810 mil millones de veces. Si desea ingresar al límite recomendado por Project Euler de 1 minuto por problema, quizás desee optimizar un poco :-) (vea el comentario de David)

Answer 7

comparando cadena con un entero en

x == z*y

también hay errores lógicos

comience en el range(999, 99, -1) orden inverso range(999, 99, -1) . eso será más eficiente. eliminar el tercer ciclo y la segunda comparación por completo.

Answer 8

en lugar de enumerar todos los productos de números de 3 dígitos (~ 900 ^ 2 iteraciones), enumere todos los diagramas de 6 y 5 dígitos (esto lleva ~ 1000 iteraciones); luego, para cada síndrome, decida si se puede representar mediante un producto de dos números de 3 dígitos (si no puede, debe tener un factor primo de 4 dígitos, por lo que es fácil de probar).

también, usted está preguntando sobre el problema # 4, no # 3.

Answer 9

El otro consejo aquí es genial. Este código también funciona. Comienzo con 999 porque sabemos que la combinación más grande posible es 999 * 999. No es python, sino un pseudo código hecho rápidamente.

public static int problem4()
    {       
    int biggestSoFar=0;
        for(int i = 999; i>99;i--){
            for(int j=999; j>99;j--){
                if(isPaladrome(i*j))
                   if(i*j>biggestSoFar)
                        biggestSoFar=i*j;
            }
        }
        return biggestSoFar;    
    }

Answer 10

Aquí está mi solución:

polindroms = [(x, y, x * y) for x in range(100, 999) for y in range(100, 999) if str(x * y) == str(x * y)[::-1]]
print max(polindroms, key = lambda item : item[2])

Answer 11

Esto agrega un par de optimizaciones a la buena solución de @ GreggLind, reduciendo el tiempo de ejecución a la mitad:

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        # Optim. 1: Nothing in any row from here on can be bigger.
        if x*x < max_seen: break  

        for y in xrange(x, 99,-1):  # so we don''t double count   
            # Optim. 2: break, not continue
            if x*y < max_seen: break  # since we''re decreasing, 
                                # nothing else in the row can be bigger

            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

La línea

if x*x < max_seen: break

significa que una vez que llegamos al punto donde x es menor que sqrt del palíndromo más grande visto hasta ahora, no solo no necesitamos investigar más factores en esa fila; ni siquiera necesitamos investigar más filas, ya que todas las filas restantes comenzarían desde un número menor que el valor actual de x.

Esto no reduce el número de veces que llamamos is_palindrome() , pero significa muchas menos iteraciones del bucle externo. El valor de x que rompe es 952, por lo que hemos eliminado la comprobación de 853 filas (aunque las más pequeñas, gracias a la otra break ).

También noté que

if x*y < max_seen: continue

debiera ser

if x*y < max_seen: break

Estamos tratando de cortocircuitar toda la fila, no solo la iteración actual del ciclo interno.

Cuando ejecuté este script usando cProfile , el tiempo acumulado para el biggest() fue de aproximadamente 56 mseg en promedio, antes de las optimizaciones. Las optimizaciones lo redujeron a unos 23 mseg. O bien la optimización sola proporcionaría la mayor parte de esa mejora, pero la primera es ligeramente más útil que la segunda.

Answer 12

Aquí hay una solución que podrías considerar. Podría ser mucho más eficiente, pero solo toma un poco de tiempo para funcionar.

largest = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        c = a * b
        if str(c) == ''''.join(reversed(str(c))):
            largest = max(largest, c)
print(largest)

Answer 13

Aquí hay una solución general eficiente (~ 5 veces más rápida que otras que he visto):

def pgen(factor):
    '''''' Generates stream of palindromes smaller than factor**2 
        starting with largest possible palindrome ''''''
    pmax = str(factor**2)
    half_palindrome = int(pmax[0:len(pmax)/2]) - 1
    for x in xrange(half_palindrome, 0, -1):
        yield int(str(x) + str(x)[::-1])

def biggest(factor):
    '''''' Returns largest palindrome and factors ''''''
    for palindrome in pgen(factor):
        for f1 in xrange(factor/11*11, factor/10, -11):
            f2 = palindrome/f1
            if f2 > factor:
                break
            if f2*f1 == palindrome:
                return palindrome, f1, f2

>>> biggest(99)
(9009, 99, 91)
>>> biggest(999)
(906609, 993, 913)
>>> biggest(9999)
(99000099, 9999, 9901)
>>> biggest(99999)
(9966006699L, 99979, 99681L)
>>> biggest(9999999)
(99956644665999L, 9998017, 9997647L)
>>> biggest(99999999)
(9999000000009999L, 99999999, 99990001L)
>>> biggest(999999999)
(999900665566009999L, 999920317, 999980347L)

Answer 14

Vaya, este enfoque mejora bastante con respecto a otras implementaciones en esta página, incluida la mía .

En lugar de

• caminando por los factores de tres dígitos fila por fila (primero haga todo y para x = 999, luego todo y para x = 998, etc.),

nosotros

• caminar por las diagonales: primero haz todo x, y tal que x + y = 999 + 999; luego haz todo x, y tal que x + y = 999 + 998; etc.

No es difícil probar que en cada diagonal, cuanto más cerca estén xey entre sí, mayor será el producto. Entonces podemos comenzar desde el medio, x = y (o x = y + 1 para diagonales impares) y aún hacer las mismas optimizaciones de cortocircuito que antes. Y debido a que podemos comenzar desde las diagonales más altas, que son las más cortas, es probable que encontremos el palíndromo calificador más alto mucho antes.

maxFactor = 999
minFactor = 100

def biggest():
    big_x, big_y, max_seen, prod = 0, 0, 0, 0

    for r in xrange(maxFactor, minFactor-1, -1):
        if r * r < max_seen: break

        # Iterate along diagonals ("ribs"):

        # Do rib x + y = r + r
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i, r-i, prod

        # Do rib x + y = r + r - 1
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i - 1)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i,r-i-1, prod

    return big_x, big_y, max_seen

# biggest()
# (993, 913, 906609)

Una mejora de un factor de casi 3

En lugar de llamar a is_palindrome () 6124 veces, ahora solo lo llamamos 2228 veces. ¡Y el tiempo total acumulado ha pasado de aproximadamente 23 milisegundos a aproximadamente 9!

Todavía me pregunto si existe una forma perfectamente lineal (O (n)) de generar una lista de productos de dos conjuntos de números en orden descendente. Pero estoy bastante contento con el algoritmo anterior.