Resolviendo el #TuentiContest: Problema 3 – Emirps

21Jun11

El tercer problema fue otro donde toda la información no estaba en el planteamiento. Aquí se los perdono porque al menos te “indicaban” qué buscar.

En este caso pedían la suma de todos los emirps hasta X. Y para empezar ¿qué es un emirp? Mi primer intento fue interpretar que simplemente escribieron “prime” (primo) al revés para fastidiar un poco. Luego con los ejemplos puede verificarse que no era así. Así que tuve que recurrir a Google y Wikipedia para descubrir qué eran.

Esta solución la implementé en Java y usa la Criba de Eratóstenes para calcular los números primos. También puedes ver mis soluciones a los otros problemas.

Análisis del problema

No hay mucho que decir en este, la única decisión es cómo encontrar los números primos. Una opción es ir verificando todo el tiempo si un número es primo o no, la otra es calcularlos todos de antemano y utilizarlos después. Yo decidí la última.

Solución enviada

En vista de que precalcularé todos los primos necesarios, decidí leer todos los casos de prueba y precalcular los primos hasta el mayor de ellos. Una vez obtenida la tabla, el resto era coser y cantar.

import java.util.*;

public class Emirps {
  public static boolean[] criba(int top) {
    int ceros = Integer.toString(top).length();
    StringBuilder tope = new StringBuilder("1");
    for (int i = 0; i < ceros; i++)
      tope.append('0');
    top = Integer.parseInt(tope.toString());

    boolean[] compuestos = new boolean[top];
    compuestos[0] = compuestos[1] = true;

    for (int i = 2; i < (top >> 1) + 1; i++) {
      if (!compuestos[i]) {
        for (int j = i << 1; j < compuestos.length; j += i) {
          compuestos[j] = true;
        }
      }
    }

    return compuestos;
  }

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    LinkedList queries = new LinkedList();
    int max = 0;
    while (scan.hasNext()) {
      int top = scan.nextInt();
      if (top > max) {
        max = top;
      }
      queries.add(top);
    }

    boolean compuestos[] = criba(max);
    for (Integer top : queries) {
      int suma = 0;
      for (int i = 2; i <= top; i++) {
        if (!compuestos[i]) {
          StringBuilder sb = new StringBuilder(String.valueOf(i));
          int emirp = Integer.parseInt(sb.reverse().toString());

          if (!compuestos[emirp] && emirp != i) {
            suma += i;
          }
        }
      }
      System.out.println(suma);
    }
  }

}

Solución mejorada

Como en toda revisión calmada de código, siempre hay espacio para mejorar. En mi caso, he resaltado las líneas que menos me gustan.

La razón de las líneas [5,9] es la de obtener una cota máxima para la criba (aunque no el supremo). El razonamiento fue el siguiente: si para saber si un número es emirp debo invertirlo, entonces la tabla debe considerar todos los números que tengan la misma cantidad de cifras del pedido (para saber si 4999 es emirp, debo saber si 9994 es primo). Aquí me estoy pasando y considero más números de los necesarios, además de que la forma de crear la cota superior es algo ordinaria. Si conoces alguna forma de hacerlo mejor, me gustaría que la mencionaras en los comentarios.

Luego tenemos las líneas 14 y 16 en la que hago iteraciones hasta top/2 cuando en realidad pude haberlas hecho hasta √top y comienzo el loop interno en 2i en vez de i*i. Siempre implemento la versión colegial de la criba, cuando lo fácil solo era sumar y restar. Esta sería la más correcta:

for (int i = 2; i*i < top; i++)
  if (!compuestos[i])
    for (int j = i*i; j < top; j += i)
      compuestos[j] = true;

Para el que sea tacaño con el espacio, también se pueden eliminar los números compuestos de la criba una vez calculada y reducir el orden de la iteración de la suma (Seguirá siendo O(N) pero con una N más pequeña). En ese caso habría que utilizar una vector en vez de un arreglo. Otra cosa es empezar la revisión de emirps en el 13 en vez del 2 pero esto ya son tonterías.

En general, me gusta esta solución. El precálculo de la criba con el máximo posible nos da velocidad de ejecución pues es más rápido obtenerla que verificar desde cero si un número es primo y además solo debemos calcularla una vez.

Y tú ¿en qué lenguaje lo resolviste?

Anuncios


7 Responses to “Resolviendo el #TuentiContest: Problema 3 – Emirps”

  1. 1 Kevin Hernandez

    Tienes razón, lo mejor es calcular la criba primero. Mucho más eficiente.

    Respecto a la cota, creo que no hay mucho que ahorrarse. Me parece que sólo te puedes ahorrar 9 valores en el mejor de los casos.

    En el método que empleaste, puedes ahorrarte tres de forma directa (top -= 3 al final de tu implementación), reconociendo que 10^n nunca es primo (con n entero), que 10^n – 1 es siempre múltiplo de 9 y que 10^n – 2 es siempre par. Así que chequear hasta 999…97 es suficiente.

    Adicionalmente, si el número a chequear comienza con dígito par no puede ser emirp, así que puedes usar i+=2 en vez de i++ en la linea 40 (y cambiar para comenzar en 13 como mencionaste). También quedarán descartados los números que comiencen con dígito par, así que se podría incluir en el chequeo esto y hacer saltos de floor(log(i))+1 cuando sea necesario. No sé cuán costoso es el chequeo de ese primer dígito así que no estoy seguro en cómo afectaría al tiempo de cómputo, pero me parece que vale la pena.

    Otra forma de hacer el salto (menos costoso pero con más líneas de código) sería llevar un contador que lleve cuenta de la cantidad de dígitos y otro de cuántas iteraciones llevas sin dar saltos de los mencionados anteriormente.

  2. 2 Kevin Hernandez

    No terminé de comentar sobre como reducir hasta 9 valores en el tope de la criba en el mejor de los casos (5 si saltas los pares como mencioné antes). Divagué por el lado de la paridad.

    Puedes llevar la criba hasta 999…9Y donde Y es (el primer digito de (Y+1)) – 1… a este valor puedes tambien hacerle el chequeo de paridad y restarle uno. Pero como mínimo llegarías a 99…91

    • ¡Qué grande Kevin!
      Excelente observación la de los saltos de pares y primeros dígitos pares. Con contadores sería la forma más fácil de proceder (más líneas pero bastante legibles). Mientras que es “tontería” simplemente empezar por el 13 y llegar a top-3, estos saltos grandes sí que reducen el orden.
      Lo de ahorrarse valores también pensé que no serían muchos al final. Implementar eso es complicarse la vida por 9 casillas de un arreglo.

  3. 4 Alvaro

    Yo hice una solucion a medias entre la tuya, donde sabes directamente si un numero es primo o no, y la de hacer el calculo para cada numero para saberlo. Por lo tanto hago mas calculos pero almaceno menos en memoria. Lo que hago es solo almacenar los primos, hasta el top del inverso calculado igual que tu. Para construir la lista de primos hago modulo el numero con todos los primos hasta numero/2 ( despues tambien cai de la burra y puse ceil(sqrt(numero)) ). Despues como tengo que saber si el inverso del primo tambien es primo, busco el inverso por busqueda binaria en la lista de primos que tengo. No se que opinas tu, las dos estan bien, pero espero que tu me digas tu opinion.

    El numero de digitos lo hago igual que tu con el length y despues 1 hago x10 hasta que sale el numero. Al final el Integer.parseInt hara tantas divisiones como multiplicaciones harias tu para saberlo. En mi solucion me olvide del StringBuffer.reverse para hacer el inverso y lo hice a mano. Kevin tiene razon diciendo que solo te ahorras 9 numeros, yo lo hice como tu.

    Ah, y si, yo lo hice tambien en java.

    Un saludo y espero leer otras de tu soluciones.

    • Hola Alvaro.

      Es una cuestión de qué límites te quieres poner, si de velocidad de ejecución o espacio en memoria. Es bastante libre la decisión aunque yo siempre que puedo me decanto por la primera opción. Luego, en la práctica te encontrarás con casos es que necesitas encontrar un punto intermedio, sacrificando ambas cosas.
      Ahora, siguiendo tu estrategia, veo que cuidaste muy bien que la verificación de primalidad se hiciera solo con los números necesarios y aprovechaste búsqueda binaria para los inversos. ¡Excelente! Me gusta tu implementación.

      Lo de buscar la potencia de 10, luego de leer a Kevin veo que me quedó ordinario y es más elegante su solución. El número de ceros es floor(log10(n)), que es mejor que pasar a String y ver la longitud. Y ya puestos lo que quedaba era elevar 10 a ese número en vez de concatenar ceros. Quedaría así:
      import static java.Math.*;
      top = (int)pow(10,floor(log(top)/log(10)));

      Lo de invertir, me encontré con una solución usando solos enteros pero aquí sí que prefiero el StringBuilder y su reverse.


  1. 1 Poesía binaria » Recopilación de soluciones para los retos de #tuentiContest . Challenge #3
  2. 2 Resolviendo el #TuentiContest: Problema 6 – The clock « lagunex

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

w

Conectando a %s


A %d blogueros les gusta esto: