domingo, 29 de diciembre de 2024

Euler #37 - "Truncatable Primes" - los algoritmos todavía importan

Retomando problemas del proyecto Euler, este en principio es bastante fácil.

https://projecteuler.net/problem=37



Es relativamente fácil, por ejemplo, con Python, convertir el número a string, ir quitando caracteres por la derecha y comprobando cada vez si el número que queda es primo. Luego, lo mismo por la izquierda. 

Mi primera implementación no tuvo en cuenta que no se considera "truncatable" si terminas con un 1. Lo mismo deberían decirlo en el enunciado, lo mismo es falta de cultura matemática por mi parte.

La función is_truncable, que se muestra a continuación, utiliza una función is_prime para trabajar. Va probando casos para probar que los números que van quedando son primos o no. Si después de analizar por la derecha y la izquierda todos han resultado ser primos, asume que es "truncable".


def is_truncable(number):
str_number = str(number)
# 2, 3, 5, 7 no son truncables
if number < 11:
return False
# si empieza o acaba en 1, no es truncable
elif str_number[0] == '1' or str_number[-1] == '1':
return False
else:
# Por la derecha
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[:-1]
# Por la izquierda
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[1:]

return True

Antes de eso, hemos hecho una pequeña función para generar una lista de números primos:


def next_prime(start):
next = start + 1
while not is_prime(next):
next += 1
return next

Y una función main() que monta todo el proceso:


def main():
truncables = []
next = 10;
# nos piden los 11 primeros truncables
while len(truncables) < 11:
next = next_prime(next, is_prime)
if (is_truncable(next, is_prime)):
truncables.append(next)
print("Truncables:", truncables)
print("Sum. truncables =", sum(truncables))

1ª versión malísima

En la primera implementación de is_prime() que hice, sin ninguna optimización, propia de un estudiante de ESO, simplemente iba dividiendo el número en cuestión por todos los números más pequeños que él mismo, si encontraba algún divisor, entonces no era primo.


def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
number_test = number - 1;
while number_test > 1:
resto = number % number_test
if resto == 0:
return False
number_test -= 1;
return True


Los problemas que plantean en proyecto Euler están muy bien pensados. Usando esta implementación ingenua, al llegar al 10º número truncable de la lista, se quedaba el problema clavado. 

4ª versión, usando librerías externas


Nos vamos al extremo contrario, usamos alguna librería existente (que seguramente esté bien optimizada y programada) para saber si un número es primo o no. El módulo sympy define una función isprime().


import sympy
def is_prime(number):
return sympy.isprime(number)


Con esta implementación, el problema se resuelve en un tiempo más que razonable, pero no vale, estamos haciendo trampa. 

2ª versión: mejor, pero sigue siendo mala


Esta implementación trata de ser un poco mejor: solo comprueba divisores hasta la mitad del número y hace una comprobación previa para los pares:


def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
for n in range(2, int(number/2)):
if number % n == 0:
return False
return True


Tampoco consigue resolver el problema en un tiempo razonable.

3ª versión: razonablemente buena


La siguente implementación de is_prime(), sin ser un prodigio, ya es bastante más óptima:
  • Hace una primera prueba contra los divisores más pequeños que ya sabemos que son primos.
  • Si es par, no es primo.
  • Para números mayores que 5, solo hace las comprobaciones hasta la raíz cuadrada + 1 del número + 1 en cuestión, y sólo comprueba con divisores impares.

def is_prime(number):
if number <= 3 or number == 5:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0:
return False;
for n in range(5, int(math.sqrt(number)) + 1, 2):
if number % n == 0:
return False
return True


Con esta implementación un poco mejorada, ya tenemos tiempos de resolución del problema razonables y del mismo orden de magnitud que usando la librería sympy.


Para poder hacer todas las diferentes pruebas, he metido todo el código común en un módulo y desde el script principal, pasamos la función is_prime correspondiente.



# Fichero euler37lib.py

def next_prime(start, is_prime):
next = start + 1
while not is_prime(next):
next += 1
return next

def is_truncable(number, is_prime):
str_number = str(number)
# 2, 3, 5, 7 no son truncables
if number < 11:
return False
# Si empieza o acaba en 1, no es truncable
elif str_number[0] == '1' or str_number[-1] == '1':
return False
else:
# Por la derecha
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[:-1]
# Por la izquierda
str_number = str(number)
while len(str_number) >= 1:
if not is_prime(int(str_number)):
return False
str_number = str_number[1:]

return True

def main(is_prime):
truncables = []
next = 10;
# Nos piden los 11 primeros truncables
while len(truncables) < 11:
next = next_prime(next, is_prime)
if (is_truncable(next, is_prime)):
truncables.append(next)
print("Truncables:", truncables)
print("Sum. truncables =", sum(truncables))

Y aquí están las cuatro diferentes implementaciones. Primero, haciendo trampa.

# Fichero 037-sympy.py

import sympy
import euler37lib


def is_prime(number):
return sympy.isprime(number)

if __name__ == '__main__':
euler37lib.main(is_prime)




Refinando un poco el algoritmo:

# Fichero 037-refinado.py


import math
import euler37lib

def is_prime(number):
if number <= 3 or number == 5:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0:
return False;
for n in range(5, int(math.sqrt(number)) + 1, 2):
if number % n == 0:
return False
return True



if __name__ == '__main__':
euler37lib.main(is_prime)



Implementación ligeramente mejor a la ingenua, pero aún así impracticable:

# Fichero 037-pasable.py

import euler37lib

def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
for n in range(2, int(number/2)):
if number % n == 0:
return False
return True

if __name__ == '__main__':
euler37lib.main(is_prime)




Implementación ingenua:

# Fichero 037-ingenuo.py

import euler37lib

def is_prime(number):
if number in (2,3):
return True
if number % 2 == 0:
return False
number_test = number - 1;
while number_test > 1:
resto = number % number_test
if resto == 0:
return False
number_test -= 1;
return True

if __name__ == '__main__':
euler37lib.main(is_prime)




Comparativa de rendimiento

Usando librería: 


Implementación "refinada"


Nuestra implementación "refinada" tiene tiempos comparables a la implementación usando el módulo sympy.

Implementación mala:



Esta otra pasa de apenas un segundo de las anteriores a 9 minutos. Es 540 veces más lenta.

Implementación inservible:


5.100 segundos. Las dos primeras implementaciones tardaban como 1 segundo. Un algoritmo 5.000 veces más lento.

Conclusiones

  1. Los algoritmos sí que importan. Si este programa, por ejemplo, fuese código para producción, ninguna de las dos implementaciones sencillas sería aceptable.
    1. Con matices: si en el problema se nos garanzizase que, por ejemplo, siempre tendremos datos de entrada con números por debajo de 100, no hay ninguna mejora apreciable en el rendimiento por usar una u otra versión de is_prime()

  2. Si existe una librería o módulo que hace lo que necesitas y es de pago, cómpralo o convence a tu jefe/cliente para que lo compre [*]:
    1. Funcionará mejor. 
    2. Tendrá soporte.
    3. A la larga será más económico.
[*] Es una generalización un poco burda, tampoco vamos a estar metiendo librerías o código de terceros para todo, pero es un poco la idea: los "vendor" suelen hacer las cosas mejor que lo que tú puedas hacer.

Un año entero sin escribir en el blog

¿Es este el fin del formato blog? ¿Les pasa lo mismo a otras personas que llevan años manteniendo un blog prácticamente sin actualizar?

En mi caso tampoco es que lo haya desplazado por otras plataformas: tampoco escribo en redes sociales o formatos similares. No tiene pinta de que en 2025 vaya a darme por escribir mucho más. 

Propósitos tecnológicos para 2025: 

- Aprender algún lenguaje compilado más o menos moderno (cacharrearé con Go).

- Seguir con los ejercicios del proyecto Euler, que vienen muy bien para mantener las neuronas engrasadas.

- Seguir desempolvando Python, es una pena, que, teniendo un buen nivel de Python hace unos años -en 2012 estuve unos meses ganándome las lentejas desarrollando en Python-, ahora que es mainstream, lo tenga un poco oxidado.


viernes, 22 de diciembre de 2023

Configurando Elasticsearch para que no distinga tildes o eñes

Típico problema, indexamos un documento con el texto "Menganita conduce un camión", buscamos "camion", sin la tilde, y no aparece el documento.

Basado en este artículo: https://sacavix.com/2020/10/elasticsearch-para-espanol-acentos-y-raiz-de-palabras/


Receta rápida

1. Reconfiguramos el índice que nos interese:

curl -XPUT http://localhost:9200/_template/miindicetemplate -H "Content-Type: application/json" -d '
{
  "index_patterns": "miindice",
  "settings": {
    "number_of_shards": 2,
    "number_of_replicas": 1,
    "analysis": {
      "analyzer":{
      "mianalizador": {
          "tokenizer": "standard",
          "filter":  [ "lowercase", "asciifolding", "default_spanish_stopwords", "default_spanish_stemmer" ]
      }
    },
    "filter" : {
        "default_spanish_stemmer" : {
            "type" : "stemmer",
            "name" : "spanish"
        },
        "default_spanish_stopwords": {
            "type":        "stop",
            "stopwords": [ "_spanish_" ]
        }
    }
   }
  },
  "mappings": {
      "properties": {
        "title": {
          "type": "text",
          "analyzer": "mianalizador",
          "fields": {
            "keyword": {
              "type": "keyword",
              "ignore_above": 256
            }
          }
        },
        "leadIn": {
          "type": "text",
          "analyzer": "mianalizador",
          "fields": {
            "keyword": {
              "type": "keyword",
              "ignore_above": 256
            }
          }
        },
        "author": {
          "type": "text",
          "analyzer": "mianalizador",
          "fields": {
            "keyword": {
              "type": "keyword",
              "ignore_above": 256
            }
          }
        },
        "pretitle": {
          "type": "text",
          "analyzer": "mianalizador",
          "fields": {
            "keyword": {
              "type": "keyword",
              "ignore_above": 256
            }
          }
        }
      }
    }
}'

2. Borramos el índice

curl -X DELETE http://localhost:9200/miindice



3. Indexamos de nuevo el contenido. Si es un proyecto Symfony con FOSElastica:

symfony console fos:elastica:reset
symfony console fos:elastica:populate

domingo, 1 de octubre de 2023

No pasan más cosas no sé porqué...

 Supermercado en Madrid, en el vestíbulo tienen una pantalla con autopromos, etc... y una ventana de TeamViewer en la que se ve el ID del equipo.


¿A quién no se le ocurrirían varias maldades, llamando a la tienda e identificándote como del "departamento de informática"?



martes, 23 de mayo de 2023

No, no le voy a decir a ChatGTP que escriba el blog

Si ya la web estaba llena de basura pensada para el bot de Google, ahora se le va a unir la basura generada por ChatGPT 🤦🤦🤦