El Proyecto Euler: Problema 4

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.

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.