¿Cómo hacer el Proyecto Euler 32 en Python Faster? -- python campo con performance campo con programming-challenge camp codereview Relacionados El problema

How to make Project Euler 32 in Python faster?


4
vote

problema

Español

Deciremos que un número N-Digit es pandigital si hace uso de todos los dígitos 1 a n exactamente una vez; Por ejemplo, el número de 5 dígitos, 15234, es de 1 a 5 pandigital.

El producto 7254 es inusual, como la identidad, 39 × 186 = 7254, que contiene multiplicando, multiplicador y producto es de 1 a 9 pandigital.

Encuentre la suma de todos los productos cuyo multiplicand / multiplicador / producto La identidad se puede escribir como un pandigital de 1 a 9.

Sugerencia: algunos productos se pueden obtener en más de una manera, así que asegúrese de Solo inclúyalo una vez en su suma.

Necesito ayuda para hacer de este código más rápido. En este momento estoy usando doble anidado para los bucles; ¿Hay alguna forma en que puedo cambiar eso?

  from timeit import default_timer as timer  start = timer() products = set() for a in range(12, 100):     for b in range(102, 1000): # to get 9-digit: 2-digit * 3-digit         product = a * b         digits = list(str(a) + str(b) + str(product))         digits = [int(x) for x in digits]         if sorted(digits, key = int) == range(1, 10):             products.add(product)  for a in range(1, 10):     for b in range(1023, 10000): # other option is 1-digit * 4-digit         product = a * b         digits = list(str(a) + str(b) + str(product))         digits = [int(x) for x in digits]         if sorted(digits, key = int) == range(1, 10):             products.add(product)  ans = sum(list(products)) elapsed_time = (timer() - start) * 1000 # s --> ms  print "Found %d in %r ms." % (ans, elapsed_time)   
Original en ingles

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 xc3x97 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

I need help on making this code faster. Right now I'm using double nested for-loops; is there a way I can change that?

from timeit import default_timer as timer  start = timer() products = set() for a in range(12, 100):     for b in range(102, 1000): # to get 9-digit: 2-digit * 3-digit         product = a * b         digits = list(str(a) + str(b) + str(product))         digits = [int(x) for x in digits]         if sorted(digits, key = int) == range(1, 10):             products.add(product)  for a in range(1, 10):     for b in range(1023, 10000): # other option is 1-digit * 4-digit         product = a * b         digits = list(str(a) + str(b) + str(product))         digits = [int(x) for x in digits]         if sorted(digits, key = int) == range(1, 10):             products.add(product)  ans = sum(list(products)) elapsed_time = (timer() - start) * 1000 # s --> ms  print "Found %d in %r ms." % (ans, elapsed_time) 
        

Lista de respuestas

8
 
vote
vote
La mejor respuesta
 

Dado que usted sabe que todos los dígitos que no son cero deben estar presentes en la respuesta, puede omitir la mayoría de los números en el rango. Es decir, no tiene sentido hacer una multiplicación de prueba de 22 * ​​3333 porque aquellos que ambos repitan dígitos.

Entonces, lo que se necesita es una forma eficiente de ejecutar todas las permutaciones de dígitos rápidamente, y afortunadamente, el 99887765555554443316 proporciona exactamente eso.

  Stack7  

La forma en que funciona es elegir permutaciones 5 dígitos a la vez y luego grupo como 2 y 3 o como 1, 4 como lo ha hecho. Hay otros refinamientos que uno puede hacer, como saltar cada número que termina en un 5 (porque 5 * n siempre terminará en 0, lo que no está en el rango, o 5, que sería un dígito duplicado), pero yo ' LL dejará tales refinamientos a usted.

Como se representa, este código funciona casi 8 veces más rápido que el original.

 

Since you know that all of the non-zero digits must be present in the answer, you can skip most of the numbers in the range. That is, it's pointless to do a test multiplication of 22*3333 because those both repeat digits.

So what is needed is an efficient way to run through all of the permutations of digits quickly, and fortunately, Python's itertools provides exactly that.

import itertools start = timer() products = set() def makeint(n):     return int(''.join(map(str,n)))  target = range(1,10) d = itertools.permutations(target, 5) for a in d:     product = makeint(a[:2])*makeint(a[2:])     if sorted(list(a)+map(int,str(product))) == target:         products.add(product)     product = makeint(a[:1])*makeint(a[1:])     if sorted(list(a)+map(int,str(product))) == target:         products.add(product)  ans = sum(list(products)) 

The way this works is to pick off permutations 5 digits at a time and then group as 2 and 3 or as 1, 4 as you have done. There are other refinements one can make, such as skipping every number which ends in a 5 (because 5*n will always end in either 0, which is not in the range, or 5 which would be a duplicate digit), but I'll leave such refinements to you.

As it stands, this code runs almost 8x faster than the original.

 
 
3
 
vote

En cuanto a conocer los problemas del Proyecto Euler, un enfoque de fuerza bruta simplemente no funciona. Por lo tanto, no deberíamos codificar el código, sino una revisión de un algoritmo.

Una cosa inmediata que viene a la mente es que usted prueba demasiadas combinaciones a sabiendas imposibles de Stack8 y Stack9 . Ellos se deben componer de diferentes dígitos, que puede probar antes de la multiplicación.

Mi sugerencia sería crear un número de suministro de iterador compuesto por diferentes dígitos (a partir de un conjunto dado: para Deque0 El conjunto de dígitos no incluye los dígitos utilizados en Deque1 ), y pruebe el producto que se está compuesto por lo que queda.

que puede darle una velocidad significativa. Puede ser, se requiere más información sobre matemáticas.

PS: Una vez que se seleccionan los dígitos para Deque2 , puede limitar el rango en el que puede caer un producto, que a su vez limita el rango posible para Deque3 .

 

As far as I know Project Euler problems, a brute force approach just doesn't work. So, we shouldn't code code, but rather an algorithm review.

An immediate thing coming to mind is that you test too many knowingly impossible combinations of a and b. They together must be composed of different digits, which you may test prior to multiplication.

My suggestion would be to create an iterator supplying numbers composed by different digits (from a given set - for b the digit set doesn't include digits used in a), and test the product being composed by what's left.

That may give you a significant speedup. May be, more math insight is required.

PS: once digits for a are selected, you may limit the range in which a product may fall, which in turn limits the possible range for b.

 
 

Relacionados problema

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

61  Uso de funciones separadas para Project Euler 1  ( Using separate functions for project euler 1 ) 
Comencé a programar con Java y C ++, así que estoy acostumbrado a tener una función "principal" que llama a otras funciones que realizan el trabajo real. En l...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

6  Proyecto EULER # 7: 10001ST PRIME  ( Project euler 7 10001st prime ) 
Esta es mi implementación de Project Euler # 7 . ¿Lo he exagerado de nuevo? ¿Hay algo más que debería o no debo hacer? Se ejecuta en 9 milisegundos en mi com...

1  Codificación de Google Jam: Tienda Credit Java Solution  ( Google code jam store credit java solution ) 
Sería genial si pudiera obtener este código revisado. Me encantaría consejos sobre cómo podría mejorar mi código. problema Recibirá un crédito C en una...

5  Cuatro cuatro para obtener cualquier número  ( Four fours to get any number ) 
Decidí resolver un problema de Código Golf llamado los cuatro cuatro . Descripción del problema: El Puzzle Four Fours es un popular rompecabezas matemát...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos