Algoritmo de Babai con Python

 En la entrada anterior expliqué y ejemplifiqué el Algoritmo de Babai para encontrar el vértice del n-paralelepípedo más cercano a un punto.

Podemos realizar un script en Python para dicho algoritmo. Utilizando la librería NumPy queda muy sencillo:

 

import numpy as np

def babai(B, w):
    # Calculamos los coeficientes del vector w en la base B
    v = np.linalg.solve(B, w)
    # Devolvemos el producto matricial de B por las coordenadas de v redondeadas
    return B @ np.round(v).astype(int) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

PD: Podéis encontrar en uno de mis repositorios de Github un script para probar el Algoritmo de Babai y la razón de Hadamard. 

Razón de ortogonalidad de Hadamard con Python

 En una entrada anterior hablé sobre la razón de ortogonalidad de Hadamard:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Podemos realizar un script en Python para calcular dicha razón, utilizando la librería NumPy:

import numpy as np

def razon_hadamard(B):
    # Calculamos el valor absoluto del determinante de la matriz
    det = np.abs(np.linalg.det(B))
    # Si el determinante es 0 la matriz no es una base y la función devuelve 0
    if not det:
        return 0
    n = len(B)
    # Definimos una variable prod_norm que calcula el producto de la norma de cada vector (columna)
    prod_norm = np.prod(np.linalg.norm(B, axis=0))
    # Devolvemos la razón
    return (det / prod_norm) ** (1/n) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

Advent of Code 2025

Cada diciembre, desde 2015, sale una nueva edición de Advent of Code. Es una web en la que proponen diariamente unos retos de programación, como si fuera un calendario de adviento.

 

 Este año la novedad es que sólo habrá 12 retos, en lugar de los 25 que había en las ediciones anteriores. Una de las características de dichos retos es que plantean problemas que puedes resolver utilizando cualquier lenguaje. Cada usuario tiene un conjunto de datos que debe tratar para dar solución a la pregunta planteada.

La falta de tiempo para dedicarle hizo que el año pasado me quedara en el día 15 de los 25 propuestos. Este año como son menos a ver si consigo acabarlos todos.

Iré subiendo en este repositorio de GitHub mis propuestas de resolución utilizando Python. Y cuando aparezca algo que me parezca interesante haré una entrada aparte en el blog para comentarlo.

El código del día 1 ya está subido :-) 

Sacar la bola "n" en la extracción número "n" (soluciones y sorpresa matemática)

En una entrada anterior se planteaba el siguiente problema:

Tenemos una urna con 5 bolas numeradas del 1 al 5. Hay que sacarlas de una en una al azar, sin mirar. Se pierde el juego si sacamos la bola "n" en la extracción número "n".

Abordar dicho problema con un enfoque de probabilidad clásica realizando el diagrama de árbol es factible pero muy tedioso, teniendo en cuenta que con 5 bolas el árbol completo tiene 5! = 120 ramas. En realidad, dicho proceso no dista mucho de calcular todas las permutaciones y comprobar cuáles cumplen las condiciones (método exhaustivo).

Si aumentamos el número de bolas en la urna olvidémonos del método exhaustivo manual. Podemos utilizar programación para que realice dicho método exhaustivo. El problema es el tiempo de computación. Para hacernos una idea, con 13 bolas en la urna tenemos 6.227.020.800 permutaciones diferentes que crear y comprobar si cumplen o no la condición del enunciado (aproximadamente 52 minutos con mi ordenador).

Muchos problemas no tienen mucho interés desde el punto de vista algorítmico-teórico porque es fácil definir el algoritmo que resuelve el problema, pero llevado a la práctica con los ordenadores de los que disponemos actualmente el tiempo de computación de dicho algoritmo puede hacer inviable su resolución en un tiempo "razonable". Y esto obliga a tener que optimizar los algoritmos o buscar alternativas a los mismos.

Volviendo al problema, he creado un programa en Python que resuelve la generalización del problema con N bolas. Como se planteaba al final de la entrada anterior.

He utilizado dos métodos. Empiezo por el segundo, método exhaustivo. Se calculan todas las permutaciones con la librería itertools de Python y se recorren comprobando si cumplen o no la condición de que ninguna bola salga en la posición que indica su número. Para N pequeño (<10) el tiempo de ejecución es razonable, no así conforme se aumenta el número de bolas.

El primer método utilizado es matemáticamente mucho más interesante. Hace uso del concepto de desarreglo, que expliqué en la entrada anterior.

No es difícil ver la relación de los desarreglos con el problema planteado de las bolas numeradas. Que ninguna bola salga en el orden que indica su número equivale a decir que en la permutación del conjunto {1, 2, 3, 4, 5} ningún elemento coincida con su posición original. Por tanto, si calculamos el número de desarreglos del conjunto {1, 2, ..., N} la probabilidad de ganar el juego será: número de desarreglos / permutaciones totales. Es decir, el subfactorial dividido entre el factorial.

p(ganar juego con N bolas) = !N / N! 

Una fórmula muy bonita y computacionalmente mucho más rápida que el método exhaustivo.

Nota: Para calcular el factorial y el subfactorial en Python he utilizado la librería SymPy.

 

En el caso del problema original, N = 5, la probabilidad de ganar es aproximadamente 0.36666666666666664. Por lo que tenemos la probabilidad cuantificada y podemos decir que es más fácil perder el juego que ganarlo.

Además se planteaba la pregunta de si nos parecía lucrativo que nos doblaran la apuesta en caso de ganar, teniendo en cuenta el riesgo que se asume. La respuesta es negativa, dado que a la larga ganaremos aproximadamente un 36'67% de las veces que juguemos y si sólo nos doblan la apuesta lo más probable es acabar perdiendo dinero en dicho juego.

Por último, se planteaba la siguiente pregunta:

Conforme aumentamos el número de bolas, ganar el juego ¿es más fácil, más difícil o va variando?

He creado otro programa en Python que devuelve las probabilidades de ganar el juego variando el número de bolas. El resultado obtenido se recoge en la siguiente tabla: 

N	Probabilidad de ganar
2	0.5
3	0.3333333333333333
4	0.375
5	0.36666666666666664
6	0.3680555555555556
7	0.3678571428571429
8	0.36788194444444444
9	0.36787918871252206
10	0.3678794642857143
11	0.3678794392336059
12	0.3678794413212816
13	0.36787944116069116
14	0.3678794411721619
15	0.3678794411713972
16	0.367879441171445
17	0.36787944117144217
18	0.36787944117144233
19	0.36787944117144233
20	0.36787944117144233
21	0.36787944117144233
22	0.36787944117144233
23	0.36787944117144233
24	0.36787944117144233
25	0.36787944117144233
26	0.36787944117144233
27	0.36787944117144233
28	0.36787944117144233
29	0.36787944117144233
30	0.36787944117144233

Vemos que en las primeras N la probabilidad una veces sube y otras baja pero que conforme aumenta N la probabilidad se va estabilizando en torno a un valor: 0.36787944117144233. Podríamos decir que a nivel práctico a partir de 5 bolas la probabilidad de ganar el juego no cambia demasiado.

Y aquí podría acabar esta entrada. Pero las matemáticas están repletas de conexiones sorprendentes y en ocasiones inesperadas. ¿Alguien al leer el problema de las bolas numeradas pensó en el famoso número e?

Pues aquí va su aparición estelar: ese número al cual tiende la probabilidad conforme aumentamos el número de bolas, 0.3678794411714423..., es exactamente el inverso del número e.

1/e =  0.3678794411714423...

Dejo como ejercicio a quien quiera la explicación de este hecho (pista: mirar en la entrada anterior la fórmula del subfactorial).

Matemática recreativa: capicúa de 6 cifras impares y divisible entre todas sus cifras

Vamos a por otro problema (n. 97) del libro "Ludopatía Matemática" de Mariano Mataix. Tiene el siguiente enunciado:

Veamos, una vez más, cómo está su teoría de números. Han de determinarse dos números, cada uno de 6 cifras impares. Ambos son capicúas y cumplen la condición de que ninguna cifra se repite más de dos veces. Además, cada número es divisible por cada una de sus cifras.

Imagen creada con IA

 

Como en entradas anteriores (1, 2, 3, 4, 5, 6) donde abordé otros problemas del libro, he construido un algoritmo en Python para resolver el problema. El nivel del problema es fácil para resolver, utilizando la función permutations del módulo itertools.

Ver código en repositorio de GitHub.

Problema: siguiente, mitad y conserva cifra final 10 veces.

El problema 27 del libro "Ludopatía Matemática" de Mariano Mataix tiene el siguiente enunciado:

Hay que hallar un número tal que si le sumamos una unidad y lo dividimos por 2, el número que resulta termina en la misma cifra que el original.

Repitiendo la operación con el resultado obtenido ocurre lo mismo, es decir, el nuevo número acaba en la misma cifra. Siguiendo así, durante 10 veces se obtiene siempre la misma cifra, pero en la undécima vez ya la terminación es diferente. Un dato más: el número buscado ha de ser el más pequeño que cumple la condición.

Así que igual que en entradas anteriores (1, 2, 3, 4, 5) he construido un algoritmo en Python para resolver el problema. El nivel del problema es facilito para resolver mediante algoritmo.

Ver código en repositorio de GitHub.

El problema 31 plantea una variante del anterior:

Hay que hallar un número tal que si le sumamos una unidad y lo dividimos por 2, el número que resulta termina en una cifra diferente que el original. Repitiendo la operación con el resultado obtenido ocurre lo mismo, es decir, el nuevo número acaba en una cifra diferente. Siguiendo así, durante 10 veces se obtiene siempre una última cifra diferente, pero en la undécima vez ya la terminación es igual. Un dato más: el número buscado ha de ser el más pequeño que cumple la condición.

Ver código en repositorio de GitHub.

Menor número con un número exacto de divisores

El problema 24 del libro Ludopatía Matemática, de Mariano Mataix Lorda, es el siguiente:

¿Cuál es el menor número con exactamente 100 divisores?

Una vez resuelto con Python podemos aprovechar para generalizar el problema al siguiente:

¿Cuál es el menor número con exactamente m divisores?

He subido a mi repositorio de matematica-recreativa en GitHub una solución utilizando la librería sympy, que calcula los divisores de un número dado (también se puede implementar dicha función fácilmente).

Imagen extraída de joguiba.com

La pregunta es ¿siempre existirá dicho número? Es decir, dado cualquier número natural positivo m, ¿podemos encontrar un natural con exactamente m divisores?

La respuesta es que sí. Si tenemos la factorización en números primos de un número, podemos calcular sus divisores como el producto de los exponentes aumentados en una unidad.

Por ejemplo, el número 18 factoriza de la siguiente manera 18 = 2^1 · 3^2. Si aumentamos los exponentes en una unidad y los multiplicamos obtenemos (1+1) · (2+1) = 2 · 3 = 6. Por lo que el número 18 tiene 6 divisores.

Div(18) = {1, 2, 3, 6, 9, 18}

Por tanto, a la pregunta de si siempre existirá dicho número con exactamente m divisores debemos contestar que sí porque una cota superior siempre será 2^(m-1), que por lo anterior sabemos que tiene m divisores.

¿Podríamos utilizar esto para abordar la programación de la solución desde otro enfoque? ¿Será más rápido, más lento o dependerá del caso?

Si alguien se anima a implementar las dos formas (calculando divisores o utilizando los exponentes de la factorización) para comparar casos que nos cuente sus resultados en los comentarios.

Reto de "vibe coding" para matemática recreativa: potencias de 10 como suma de números con cifra 8

Imagen creada con IA

 En los últimos meses se habla y escribe mucho acerca del "vibe coding", incluso llevado a su extremo en el que una persona que no tiene ningún conocimiento sobre Programación puede realizar programas funcionales pidiendo a herramientas de inteligencia artificial que construya el código, únicamente escribiendo en lenguaje natural lo que quiere que haga el programa.

Así que he aprovechado este boom mediático para proponer un reto, tanto a los "vibe coders" con pocos o sin conocimientos en Programación como a los programadores más expertos.

De nuevo saco un problema del libro Ludopatía Matemática, de Mariano Mataix Lorda.

ENUNCIADO DEL PROBLEMA

Queremos conocer las primeras dos potencias de 10 que pueden escribirse como sumandos cumpliendo las siguientes condiciones:

• Cada sumando debe estar formado sólo por la cifra 8 (ejemplos: 8, 88, 888, ...)
• El total de ochos utilizados en todos los sumandos debe ser también un número formado sólo por la cifra 8 (ejemplos: 8, 88, 888, ...)

La primera solución es 10^3:
    1000 = 888 + 88 + 8 + 8 + 8
Está escrito como suma de números formados sólo con la cifra 8 y el total de ochos utilizados es igual a 8.

¿Cuál es la siguiente potencia de 10 que cumple las condiciones impuestas por el enunciado?

Imagen creada con IA

Lo que me parece más interesante es que por favor pongáis en los comentarios si habéis hecho vibe coding y en caso afirmativo que pongáis aquí qué herramienta de inteligencia artificial habéis utilizado, el código creado y la solución del problema.

¡Os leo!

 

 

Python: listas VS conjuntos

Imagen creada con IA

En Python, una de las diferencias fundamentales entre los tipos de datos lista (list) y conjunto (set) es que el segundo no puede tener duplicados. De hecho cuando queremos eliminar los duplicados de una lista, una de las maneras de hacerlo es transformar la lista en conjunto y luego volver a pasar el conjunto a lista.

No entro aquí en el tipo de datos que puede contener cada uno de ellos. Si mi variable debe admitir datos duplicados necesariamente debo utilizar una lista. Pero si hay la certeza de que no habrá ningún dato duplicado (o no queremos almacenarlo más de una vez) podemos elegir entre usar una lista o un conjunto. Lo cierto es que la versatilidad de las listas hace que muchas veces nos decantemos por estas, pero no siempre es la mejor opción como mostraré a continuación.

Cuando la cantidad de datos con los que voy a trabajar es considerable, los tiempos de ejecución de los programas puede variar muy significativamente si utilizo listas o si utilizo conjuntos (cuando pueda hacerlo).

¿Hay diferencia en tiempo de ejecución al recorrer una lista y al recorrer un conjunto, ambos con los mismos elementos?

Imagen creada con IA

He hecho una prueba en el ordenador en el que me encuentro escribiendo esta entrada. He creado una lista y un conjunto con los números del 0 al 100000000, este último sin incluir. Recorriendo ambos con un bucle "for ... in" he obtenido los siguientes tiempo de ejecución:

    Tiempo de recorrido en lista: 5.245566 segundos

    Tiempo de recorrido en conjunto: 5.883574 segundos

El tiempo de recorrido sobre el conjunto es aproximadamente un 12% superior al tiempo de recorrido sobre la lista.

Además, en el mismo programa he buscado el elemento 99999999 en la lista (if ... in) y los tiempos de ejecución han sido los siguientes:

    Tiempo de búsqueda en lista: 1.093401 segundos

    Tiempo de búsqueda en conjunto: 0.000001 segundos

El tiempo de búsqueda en el conjunto es muchísimo más corto que el tiempo de búsqueda en la lista y aunque no busquemos el último elemento los tiempos siguen siendo significativamente muy inferiores. Esto en programas con gran cantidad de datos o que debemos realizar muchas búsquedas en una colección de datos puede suponer la diferencia entre un programa con un tiempo de ejecución aceptable o uno de esos que dejas el ordenador encendido y al cabo de muchas horas vuelves para mirar si con suerte ya ha acabado (a mi me pasó con el problema de los cartones del bingo).

A continuación incluyo el código del programa utilizado:

import time

n = 100000000

elementos = list(range(n))

elementoZ = n-1

mi_lista = elementos

mi_conjunto = set(elementos)

# Medir tiempo de recorrido en lista

inicio = time.time()

for elemento in mi_lista:

next

tiempo_lista = time.time() - inicio

# Medir tiempo de recorrido en conjunto

inicio = time.time()

for elemento in mi_conjunto:

next

tiempo_conjunto = time.time() - inicio

print(f"Tiempo de recorrido en lista: {tiempo_lista:.6f} segundos")

print(f"Tiempo de recorrido en conjunto: {tiempo_conjunto:.6f} segundos")

# Medir tiempo de búsqueda en lista

inicio = time.time()

if elementoZ in mi_lista:

tiempo_lista = time.time() - inicio

# Medir tiempo de búsqueda en conjunto

inicio = time.time()

if elementoZ in mi_conjunto:

tiempo_conjunto = time.time() - inicio

print(f"Tiempo de búsqueda en lista: {tiempo_lista:.6f} segundos")

print(f"Tiempo de búsqueda en conjunto: {tiempo_conjunto:.6f} segundos")

Referencia externa sobre el tema: en la documentación de Python, apartado TimeComplexity, se muestra que de promedio una búsqueda "in" en listas tiene orden O(n) y en conjuntos O(1).

Problema de los cartones de bingo especiales: una solución con Python

 En la entrada anterior puse un problema en el que teníamos que contar cuántos cartones de bingo diferentes podíamos construir siguiendo unas reglas dadas: sin que se repita ninguna fila, columna o diagonal.

 Que ninguna pareja de cartones tenga alguna fila igual se entiende perfectamente. Lo mismo con columnas. Pero, ¿qué se entiende por diagonal del cartón? Si vemos el cartón como una matriz de 5x5, ¿hablamos sólo de la diagonal principal de la matriz? ¿también la diagonal secundaria (antidiagonal)? En este sentido el enunciado me genera dudas de interpretación. Así que desarrollaré un programa que pueda contestar a la pregunta interpretando ambas opciones.

El código en Python puede encontrarse en el repositorio de Matemática Recreativa que creé en GitHub.

Si queremos quitar la condición de la antidiagonal podemos comentar las líneas:

    if antidiagonal in antidiagonales:
        continue

 De hecho, el resultado no varía. Pero es que tampoco lo hace si quitamos la condición de las diagonales. Y aún más "sorprendente" es que tampoco varía si quitamos la condición de que no pueda haber dos matrices con alguna fila común.

Imagen extraída de https://www.youtube.com/watch?v=aumxFs2DO5o

 Pero eso no lo explica el algoritmo, sino que lo hacen las Matemáticas. La columna con menos combinaciones es la tercera, dado que hay una casilla negra a la que no hay que asignarle un número. Como en dicha columna podemos poner números en orden ascendente desde el 31 al 45 incluidos y sin poder repetirlos, tenemos el número combinatorio 15C4 que da 1365. Por tanto, tenemos una cota superior del número de soluciones al problema dado que podríamos tener cartones/matrices dentro de esas combinaciones con filas, diagonales o antidiagonales en común.

 Lo que pasa es que la solución al problema es exactamente 1365. ¿Por qué la restricción de la tercera columna es la más restrictiva sobre las condiciones de filas, diagonal y antidiagonal? Es decir, ¿por qué podemos asegurar que para cada una de las 1365 combinaciones para la tercera columna podemos rellenar un cartón completo que no comparta alguna fila, diagonal ni antidiagonal con el resto de cartones?

 La justificación no me parece tan fácil como podría pensarse en un principio. ¿Cuál es tu justificación?

Problema de Matemática Recreativa: cartones de bingo especiales

En entradas anteriores (1, 2) he resuelto problemas contenidos en el libro Ludopatía Matemática, de Mariano Mataix Lorda.

Imagen extraída de goodreads.com

El problema 19 se titula Cartones de bingo.

"La figura representa un cartón de bingo algo diferente de los acostumbrados, pero para el caso es igual. Los números de la primera columna se toman de los que existen entre el 1 y el 15, cambos comprendidos; los de la 2.ª, entre el 16 y el 30; los de la 3.ª, entre el 31 y el 45; los de la 4.ª, entre el 46 y el 60; y los de la 5.ª, entre el 61 y el 75.

¿Cuál es el máximo número de tarjetas que pueden hacerse sin que se repita ninguna fila, columna o diagonal?

NOTA: Hay que tener en cuenta que en cada columna el orden de los números va de acuerdo con su magnitud. Es decir, que si, por ejemplo, los números elegidos para la primera columna fuesen 1, 2, 3, 4 y 5, irían en este orden de arriba a abajo, no pudiendo ir nunca un número antes de otro menor que él."

En la próxima entrada pondré mi solución utilitzando Pyhton para continuar con la serie de problemas de matemática recreativa resueltos con programación informática.

Un problema de datos numéricos con Python y numpy para pensar (solución)

  Esta entrada es la continuación de Un problema de datos numéricos con Python y numpy para pensar (enunciado). Si todavía no lo has leído y quieres pensar por ti mismo el problema estás a tiempo :-)

 Resumiendo la entrada anterior: tenemos unos datos en csv, los importamos y los mostramos por pantalla. Observamos en pantalla varios datos que tienen valor 9. pero al contar la cantidad de datos que son mayores o iguales que 9 el programa devuelve 0.

 Quedó la pregunta abierta para que quien quisiera pensara el posible motivo y en esta entrada explico lo que estaba sucediendo.

Imagen de centrotadi.com

 La importación desde el csv es correcta, así como también la definición del array/matriz. El problema es que al mostrarlo por pantalla los datos se desvirtúan y pierden precisión.

El csv en realidad contiene la siguiente información:

1.999999999999990,7.999999999999990,7.999999999999990,1.999999999999990,8.999999999999989,3.999999999999990,0.999999999999990,1.999999999999990,1.999999999999990,0.999999999999990
6.999999999999990,6.999999999999990,1.999999999999990,7.999999999999990,5.999999999999990,5.999999999999990,3.999999999999990,2.999999999999990,7.999999999999990,8.999999999999989
4.999999999999990,3.999999999999990,5.999999999999990,1.999999999999990,0.999999999999990,5.999999999999990,1.999999999999990,5.999999999999990,5.999999999999990,2.999999999999990
3.999999999999990,6.999999999999990,5.999999999999990,0.999999999999990,0.999999999999990,8.999999999999989,8.999999999999989,4.999999999999990,5.999999999999990,5.999999999999990
1.999999999999990,3.999999999999990,5.999999999999990,7.999999999999990,0.999999999999990,6.999999999999990,5.999999999999990,3.999999999999990,7.999999999999990,6.999999999999990
7.999999999999990,0.999999999999990,5.999999999999990,2.999999999999990,4.999999999999990,6.999999999999990,8.999999999999989,4.999999999999990,3.999999999999990,0.999999999999990
6.999999999999990,2.999999999999990,6.999999999999990,0.999999999999990,0.999999999999990,3.999999999999990,4.999999999999990,8.999999999999989,2.999999999999990,6.999999999999990
5.999999999999990,3.999999999999990,5.999999999999990,0.999999999999990,6.999999999999990,1.999999999999990,8.999999999999989,4.999999999999990,2.999999999999990,5.999999999999990
6.999999999999990,7.999999999999990,2.999999999999990,1.999999999999990,7.999999999999990,2.999999999999990,0.999999999999990,4.999999999999990,1.999999999999990,1.999999999999990
2.999999999999990,3.999999999999990,7.999999999999990,2.999999999999990,6.999999999999990,6.999999999999990,1.999999999999990,0.999999999999990,5.999999999999990,8.999999999999989

 Y podemos observar que en realidad no hay ningún dato mayor o igual que 9, por lo que el programa no estaba fallando. Lo que fallaba era nuestra visualización de los datos.

Esto me sucedió realizando otro programa más complejo y me costó dar con la clave. Para centrarme en el problema real he diseñado este otro programa mucho más sencillo, que se puede utilizar a modo de problema.

 ¡Ojo! Otro fallo que se puede cometer es al ver por pantalla que los datos se muestran como float pero vemos que son enteros trabajar con ellos pasándolos a enteros con int. El resultado de hacer eso cambiaría completamente los datos, dado que al hacer int truncamos el número y por ejemplo 1.999999999999990 pasa a ser 1.

 En este caso, si queremos hacer una conversión a entero, lo correcto es utilizar redondeo (round). Podríamos modificar el código de la siguiente manera:

import numpy as np
from random import choice

# Importamos los datos del archivo CSV
M = np.genfromtxt("datos-ir.csv", delimiter = ",")

print("La matriz importada es: ")
print("M =\n" , M)

print("\nCreamos una matriz donde cada elemento es True si el correspondiente")
print("elemento de la matriz original es mayor o igual que 9 y False en otro caso")

N = (np.round(M,0) >= 9)

print("N =\n", N)
print("\nLa cantidad de True en la nueva matriz es: ", N.sum())

Un problema de datos numéricos con Python y numpy para pensar (enunciado)

Tenemos unos datos numéricos en un archivo CSV. Importamos dichos datos y los mostramos por pantalla:

[[2. 8. 8. 2. 9. 4. 1. 2. 2. 1.]
[7. 7. 2. 8. 6. 6. 4. 3. 8. 9.]
[5. 4. 6. 2. 1. 6. 2. 6. 6. 3.]
[4. 7. 6. 1. 1. 9. 9. 5. 6. 6.]
[2. 4. 6. 8. 1. 7. 6. 4. 8. 7.]
[8. 1. 6. 3. 5. 7. 9. 5. 4. 1.]
[7. 3. 7. 1. 1. 4. 5. 9. 3. 7.]
[6. 4. 6. 1. 7. 2. 9. 5. 3. 6.]
[7. 8. 3. 2. 8. 3. 1. 5. 2. 2.]
[3. 4. 8. 3. 7. 7. 2. 1. 6. 9.]]
 

Vemos que se trata de una matriz de 10x10 con números entre 1 y 9 (incluidos).

Creamos otra matriz de manera que un elemento es True si el correspondiente elemento de la matriz original es mayor o igual que 9 y False en caso contrario. Finalmente contamos la cantidad de True en la nueva matriz.

Es decir, en realidad con el procedimiento anterior estamos contando cuántos elementos de la matriz original son iguales o mayores que 9.

En la pantalla vemos que hay varios 9 en los datos originales, sin embargo la matriz creada no tiene ningún True (ver más abajo la salida del programa). Es decir, el procedimiento concluye que en la matriz original no hay ningún 9. ¿Cómo es esto posible? ¿Dónde está el fallo?

La respuesta la subiré próximamente en otra entrada. Mientras tanto podéis poner vuestras hipótesis en los comentarios.

 

El código del programa es el siguiente

import numpy as np
# Importamos los datos del archivo CSV
M = np.genfromtxt("datos-ir.csv", delimiter = ",")
print("La matriz importada es: ")
print("M =\n" , M)
print("\nCreamos una matriz donde cada elemento es True si el correspondiente")
print("elemento de la matriz original es mayor o igual que 9 y False en otro caso")
N = (M >= 9)
print("N =\n", N)
print("\nLa cantidad de True en la nueva matriz es: ", N.sum())

 

La salida del programa es la siguiente:

La matriz importada es:  
M =
[[2. 8. 8. 2. 9. 4. 1. 2. 2. 1.]
[7. 7. 2. 8. 6. 6. 4. 3. 8. 9.]
[5. 4. 6. 2. 1. 6. 2. 6. 6. 3.]
[4. 7. 6. 1. 1. 9. 9. 5. 6. 6.]
[2. 4. 6. 8. 1. 7. 6. 4. 8. 7.]
[8. 1. 6. 3. 5. 7. 9. 5. 4. 1.]
[7. 3. 7. 1. 1. 4. 5. 9. 3. 7.]
[6. 4. 6. 1. 7. 2. 9. 5. 3. 6.]
[7. 8. 3. 2. 8. 3. 1. 5. 2. 2.]
[3. 4. 8. 3. 7. 7. 2. 1. 6. 9.]]

Creamos una matriz donde cada elemento es True si el correspondiente
elemento de la matriz original es mayor o igual que 9 y False en otro caso
N =
[[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]
[False False False False False False False False False False]]

La cantidad de True en la nueva matriz es:  0

 

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 :-)