El Proyecto Euler: Problema 4

6/02/2009

El Proyecto Euler es una serie de problemas de programación, si quieres enterarte de que va esto, lee la introducción.

Debo notar que he cambiado las reglas. Ahora me voy a preocupar mas por sacar la solución -menos cochina posible- que porque mi “algoritmo sea lo mas eficiente posible”. Esto es porque simplemente no me puedo dar el tiempo para ello y quiero avanzar con los ejercicios algún día. Espero me ayuden en los comentarios a mejorar las soluciones :-)

Problema 4

Un número capicúa se lee de la misma manera en ambas direcciones. El capicúa mas grande resultante del producto de dos números de dos dígitos es 9009 = 91 x 99.

Encuentra el mayor capicúa resultante del producto de dos números de tres dígitos.

Aquí tenemos dos variables cuyo valor puede ir desde 100 hasta 999 -todos los números de 3 dígitos-, es un rango realmente pequeño así que iremos con el viejo y sucio conocido método de fuerza bruta y probaremos cada una de las opciones.

Es decir; Un par de bucles para probar que cada resultado de las multiplicaciones de números de 3 dígitos, sea o no un número capicúa. Si el resultado es positivo entonces verificamos que sea el más grande que hemos encontrado hasta el momento y lo guardamos.

main()
{
	int i, j, x, r = 0;
 
	for ( i = 999; i > 99; i-- )
	{
		for ( j = 999; j > 99; j-- )
		{
			x = i * j;
 
			if ( is_palindrome(x) ) {
				r = x > r ? x : r;
			}
		}
	}
 
	printf("%d", r);
	return 0;
}

Para la función que verifica que el número sea capicúa podemos asumir -debo decir, suciamente- que el resultado que buscamos va a estar compuesto de 6 dígitos, así que nuestro objetivo sera descomponer el número a probar en un arreglo que tenga 6 elementos.

A notar que con la operación mod 10 podemos tomar el último dígito de un número y haciendo una división sobre 10 podemos eliminar dicho dígito del número, porque ya lo hemos guardado.

Al ya tener los 6 dígitos guardados podemos comparar cada uno de los índices opuestos para ver que sean iguales.

int is_palindrome(int number)
{
	int i = MAX - 1, digits[MAX];
 
	while ( i >= 0 )
	{
		digits[i] = number % 10;
		number = number / 10;
		i--;
	}
 
	if ( digits[0] != digits[5] || digits[1] != digits[4] || digits[2] != digits[3] ) {
		return 0;
	}
 
	return 1;
}

Voila! Esto ya resuelve nuestro problema y lo hace en un tiempo razonable. Pero.. siempre hay un pero..

Si te sientes sucio utilizando una función que depende de que nuestro número contenga exactamente 6 dígitos, entonces podemos sustituirla por una función que simplemente toma un numero y lo devuelve al revés para poder checarlo directamente con el original.

Esta función se basa en el mismo principio que utilizamos antes con el operador mod y las divisiones. Extraer y eliminar el último dígito, solo que ahora lo vamos acumulando en otra variable -agregando nuevos dígitos al multiplicar por 10- para regresarlo de revés.

int reversed(int number)
{
	int reversed = 0;
 
	while (number > 0)
	{
		 reversed = reversed * 10;
		 reversed = reversed + number % 10;
		 number = number / 10;
	}
 
	return reversed;
}

Y entonces podemos sustituir la llamada de la is_palindrome por reversed

11
12
13

			if ( reversed(x) == x ) {
				r = x > r ? x : r;
			}

La primera función es un poco más rápida, pero la diferencia son apenas un par de milésimas. Ambas me parece que terminan en un tiempo aceptable.

real 0m0.070s
user 0m0.068s
sys 0m0.008s

Mejoras

Creo que el mayor problema con esta solución es el bucle a fuerza bruta, no es necesario probar cada combinación ya que por lo menos creo que dos cosas se deben de poder evitar:

No repetir multiplicaciones. 999 x 555 = 555 x 999. Actualización: Victor Bracco ayudó con esta solución en los comentarios, los tiempos de ejecución se cortan por la mitad :-)
Se deberían de evitar las multiplicaciones de números en que ambas variables sean con números bajos. Con solo calcular cual es la mínima combinación que nos resulta en productos de 6 dígitos nos evitaría operaciones innecesarias. Actualización: Victor dio con esta solución también, con ambas mejoras el programa tarda apenas 0.002s :-)

Actualización: Victor dio ahora una solución que mejora los ciclos externos necesitados :-)

«Anterior | Siguiente»

Hay 17 comentarios:

6/02/2009Iñaki Soria dice:

Y empezar por 999*999? Te aseguras que el primer resultado es el mejor ;)
6/02/2009nibblesmx dice:
Hola!
yo tambien estuve haciendo estos ejercicios hace algun tiempo. Deberias considerar utilizar python, te facilita mucho las cosas. Este es el codigo que alguna vez escribi para resolver este mismo problema:
1 2 3 4 5 6 7
number = 999**2 while number > 100: str_number = str(number) if (str_number == str_number[::-1]): print str_number break number -= 1
Es mucho mas sencillo :D Suerte!!!

6/02/2009Gunnar Wolf dice:

Recomendación en el mismo sentido que nibblesmx… Pero bueno, veo que tú usas C – Yo no domino el lenguaje, pero podría ser una función similar a:

int es_palindrome (int number) {
    char* num_orig;
    char* num_reverse;
    int str_size;
    int res;
 
    /* Seguro hay maneras más elegantes... Pero bueno, yo repito el cálculo de la cadena */
    str_size = strlen(sprintf("%d", number)
    num_orig = (char*) malloc(str_size * sizeof(char)) ;
    num_reverse = (char*) malloc(str_size * sizeof(char));
    *num_orig = sprintf("%d", number);
    for (int i=0; i < str_size-1; i++) {
         num_reverse[i] = num_orig[str_size-i];
    }
    /* No estoy seguro de que este sea el manejo correcto de la terminación de cadena... */
    num_reverse[str_size] = 0;
    res = strcmp(num_orig, num_reverse);
    free(num_orig);
    free(num_reverse);
    return res; 
}

De nuevo, nomás como se asomó a mi cabeza, sin experiencia escribiendo en C desde hace cosa de 10 años :)

6/02/2009Manuelinux dice:

Este lo resolvi hace algun tiempo, mi solucion esta aqui:
http://manuelinux.info/blog/view/47/euler-problema-4
6/02/2009El Proyecto Euler | Pablasso dice:

[...] Problema 4 – Encuentra el mayor producto capicúa de dos números de tres dígitos. «Anterior | Siguiente» Temas SimilaresEl Proyecto Euler: Problema 1 [...]
6/02/2009pablasso dice:

@Iñaki Soria: Ya comienza desde 999×999. Lo mismo pensé yo, pero el primer resultado no es el capicúa mas grande. Saldrían antes combinaciones como 995 x 517, antes del correcto 993 x 913. Se tendría que construir el bucle de diferente forma para esto.

@nibblesmx: Gracias! uno de los objetivos es hacer esto en ANSI C, ya que nunca lo use realmente fuera de la escuela y esto me obliga a crear mis propias funciones en lugar de utilizar las facilidades de un lenguaje de scripting. Pero siempre es bueno ver las soluciones en otros lenguajes para comparar.

@Gunnar, @Manuelinux: Gracias! Muy buenas sus soluciones convirtiendo a cadenas.
9/02/2009codeplasticlesthack » Blog Archive » El proyecto de Euler dice:

[...] conocía este proyecto pero debido a mi curiosidad y a un post que vi, entre para ver de que se trataba. El proyecto de Euler son una serie de problemas [...]
9/02/2009Michoacano dice:

Este problema esta chido, no se como optimizarlo jajajajaa.

12/02/2009Victor Braco dice:

trabajando un poquito con tu código sobre la primera recomendacion, que era de no repetir las multiplicaciónes, esto queda sencillo cambiando el valor con el que empieza el bucle interno. En vez de 999, que comienze con el valor del indice i.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
main()
{
	int i, j, x, r = 0;
 
	for ( i = 999; i > 99; i-- )
	{
		for ( j = i; j > 99; j-- )
		{
			x = i * j;
 
			if ( is_palindrome(x) ) {
				r = x > r ? x : r;
			}
		}
	}
 
	printf("%d", r);
	return 0;
}

12/02/2009pablasso dice:

Genial Victor! Esto baja el tiempo de ejecución promedio desde los .070s hasta los .035, justo por la mitad.
13/02/2009Victor Braco dice:
Jeje, tengo otra…creo para la segunda recomendación:
No se si es exactamente igual en C, si fuera PHP seria break; cualquier cosa tu lo retocas.

Podemos evitar hacer multiplicaciones innecesarias, cortando el bucle interno una vez que la multiplicacion de los 2 numeros es menor al menuro guardado en r, es decir, por ejemplo si r=987789 y la multiplicaciones de X y Y es un número menor a ese, no tiene sentido seguir bajando Y porque siempre van a ser menores a ese.
9 10
x = i * j; if (x < r) break;
13/02/2009pablasso dice:

Excelente Victor!

Ahora el programa solo hace poco mas de 6000 iteraciones internas, cuando antes hacia mas de 400,000 y originalmente mas de 900,000. Ahora no se me ocurre que otra cosa mejorarle, tarda apenas 0.002s :-)

13/02/2009Victor Braco dice:

Ahora no estoy seguro de esto, le veo sentido pero no estoy totalmente seguro que sea del todo correcto. Se trata de cortar el bucle externo, haciendo uso de este ejemplo:

Si se tiene que la multiplicacion 995 x 517 es un capicua, entonces habria que guardar el 517 en una variable para hacer que el bucle más grande, no baje de ese número, porque ya sabriamos que los resultados van a ser números más pequeños.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
main()
{
	int i, j, h, x, r = 0;
 	h=99;
	for ( i = 999; i > h; i-- )
	{
		for ( j = i; j > 99; j-- )
		{
			x = i * j;
                        if (x < r) break;
 
			if ( is_palindrome(x) ) {
				if(x > r){
					r = x;
					h=j;
				}
			}
		}
	}
 
	printf("%d", r);
	return 0;
}

13/02/2009pablasso dice:

Que buena, así reduces muchísimo las iteraciones externas, aquí se van de 900 iteraciones hasta 86 (y el consecuente ahorro en iteraciones internas)

El tiempo que me tarda en ejecutar es el mismo, pero es una gran mejora.
13/02/2009pecesama dice:

Que interesante se puso este ejercicio, todo un buen ejemplo didáctico sobre optimización.
13/02/2009 El Proyecto Euler: Problema 4 by Pecesama.Net [weblog] dice:

[...] estan interesados en el Proyecto Euler, Pablo tiene un excelente post sobre el problema 4, además en los comentarios Victor a dado muy buenos aportes para optimizar la solución. Si no han [...]
15/02/2009Proyecto Euler | Buanzolandia dice:

[...] unos días en un post de Pablo, me quedé super enganchado con los problemas del Proyecto Euler. Para los que no tengan idea de [...]

Escribe tu comentario:

Los mas frikis pueden suscribirse a los comentarios por RSS.