Un problema de criptoaritmética diferente

 En la anterior entrada hablé sobre los criptoaritmos y cité el libro Ludopatía Matemática, de Mariano Mataix Lorda.

 En dicho libro aparece un criptoaritmo diferente a los habituales. Se trata del siguiente problema:

 Resulta que entre TEN y TWENTY hay ONE cuadrados perfectos. Por otra parte, TWO, TEN, TWELVE y TWENTY son pares, con la particularidad de que tanto el último como el primer dígito de TWENTY son pares. Por último, TEN no es divisible por 3. ¿Cuánto vale NOW?

Imagen extraída de www.conmishijos.com

  Aquí está mi propuesta de resolución con Python, utilizando la estrategia del método exhaustivo (comprobar todas las posibles soluciones).

 

 

Criptoaritmos con Python

El otro día abrí el libro Ludopatía Matemática, de Mariano Mataix Lorda. En este libro se pueden encontrar diferentes pasatiempos, juegos y curiosidades relacionadas con las matemáticas.

Imagen extraída de goodreads.com

 

Algunos de ellos son los conocidos criptoaritmos. Podemos decir, de manera simple, que un criptoaritmo (o criptograma aritmético) es una operación aritmética en la que han cambiado los dígitos de los números implicados en la operación por letras y debemos averiguar qué dígito le corresponde a cada letra para que la operación se cumpla.

Por ejemplo (número 1 del citado libro y que aparece en la portada):

Las cifras han sido cambiadas en la siguiente suma
    YZRM
    BRCP
    TPRM
    BTCP
    XLXX

 Las condiciones más habituales en este juego son las siguientes:

- Cada letra corresponde a un dígito diferente.
- Por tanto, no puede haber más de 10 letras diferentes.
- El primer carácter de cada número no puede equivaler a 0.

Hay diferentes maneras de plantear matemáticamente estos problemas, pero hoy no quiero entrar en esa parte sino en que es un problema que puede resolverse "fácilmente" probando posibilidades hasta que una cuadre.

Imagen extraída de fotogramas.es

¿Cómo vamos a probar posibilidades hasta encontrar la correcta? ¿Eso no es demasiado trabajo? Bueno, tampoco hace falta que las probemos manualmente. Es decir, podemos desarrollar un programa que compruebe todas las soluciones por nosotros. Y, además, que nos sirva no sólo para resolver el criptoaritmo del ejemplo sino cualquier criptoaritmo que cumpla las condiciones dadas.

Y ya que estamos, que no sólo resuelva criptoaritmos de sumas sino también criptoaritmos que utilicen suma, resta, multiplicación y/o división.

Imagen extraída de lamardemates.blogspot.com

Para ello he desarrollado en Python dos versiones de un "resolutor de criptoaritmos", siguiendo dos estrategias:

- Una que he llamado probabilística: consiste en ir asignando al azar valores a las letras hasta encontrar la que hace que se cumpla la operación. Código aquí.

- Otra que he llamado exhaustiva: consiste en ir comprobando todas las posibles asignaciones de valores a las letras hasta encontrar la que hace que se cumpla la operación. Código aquí.

Nota: a nivel de programación, en los códigos se pueden mejorar varias cosas, pero para el objetivo que persigo en esta entrada lo doy por bueno.

¿Qué ventajas puede tener la estrategia probabilística?

- No es necesario programar una estrategia de combinatoria.

- Puede haber suerte y que al azar encuentre la solución más rápido.

¿Qué desventajas tiene?

- Si no tiene solución entramos en un bucle infinito (se puede poner un número máximo de bucles y decir que es probable que no tenga solución).

- Puede repetir más de una vez la misma combinación, por lo que estaría haciendo cálculos repetidos innecesarios.

- Igual que puede haber suerte y encontrar rápido la solución, también puede tardar más en encontrar la solución. Es una cuestión de azar.

Imagen extraída de es.123rf.com

¿Por qué es útil entonces conocer la estrategia probabilística? Porque en ocasiones no conocemos el patrón que rige el problema, no sabemos implementar correctamente la estrategia exhaustiva o no tenemos tiempo/ganas para implementarla. No me refiero sólo a criptoarimética, sino como estrategia general de resolución de problemas mediante computación.

Python: dos maneras de calcular la cantidad de cifras de un número natural

Hace muchos años escribí una entrada titulada ¿Cuántas cifras tiene un número? Por ejemplo, el factorial de 1.000.000

Por aquel entonces seguía programando principalmente en lenguaje C++ y profundizaba en software matemático, como wxMaxima, Mathematica, Sage, etc.

Empezaba a hacer alguna cosita en Python y ahora el lenguaje que más utilizo, por diferentes motivos que ahora no vienen al caso.

 

El tema es que resolviendo el problema 11 del Advent of Code 2024 hay que calcular la cantidad de cifras de números. Lo primero que pensé es utilizar la función len() sobre la conversión del número a cadena de caracteres:

len(str(natural))

Pero es cierto que, como comentaba en la entrada antigua, podemos calcular la cantidad de cifras de un número utilizando el logaritmo en base 10 (quedándonos la parte entera):

from math import log10

int(log10(natural))

Si sólo tenemos que calcular la cantidad de cifras de unos pocos números es prácticamente indiferente utilizar una manera u otra. Tal vez yo opte por la primera por no tener que importar funciones de librerías.

Sin embargo, si hay que realizar ese cálculo muchas muchas veces, ¿cuál será más rápido? Para contestar dicha pregunta he hecho dos programas sencillos para calcular el tiempo de ejecución.

    - Versión len

import time
inicio = time.time()
for i in range(1,100000000):
    len(str(i))
fin = time.time()
print(fin-inicio)

    - Version log10

from math import log10
import time
inicio = time.time()
for i in range(1,100000000):
    int(log10(i))
fin = time.time()
print(fin-inicio)

En mi ordenador el tiempo de ejecución del primer programa ronda los 11 segundos, mientras que el del segundo no llega a los 9 segundos.

Por tanto, en las condiciones planteadas, el logaritmo es la opción más rápida. Por otra parte, ¿qué pasa si el número puede ser 0? Dicho método no sirve. Si añadimos un condicional dentro del bucle, ¿seguirá siendo el método más rápido?

Lo dejo como ejercicio para quien quiera averiguarlo y compartir su respuesta :-)