Artículos sobre programación

¡Bienvenido a "Blog Con Clase"!

Desde aquí hay acceso a pequeños artículos sobre programación, algoritmos, teoría, programación de dispositivos, multimedia, juegos, etc.

Esta sección funciona como un blog, y está abierta para cualquiera que quiera colaborar.

Por supuesto, siempre agradeceremos tu colaboración, ya sea como alumno, como autor de programas, como articulista o como colaborador en la lista de correo.

Artículos

MSYS2 gestión de paquetes

MSYS2 es una colección de herramientas y librerías que proporcionan un entorno fácil de usar para crear, instalar y ejecutar software nativo de Windows.

Proporciona un terminal en línea de comandos, llamado mintty, control de versiones, herramientas como tar o awk. Hablaremos de estas herramientas en futuros artículos.

Formato MBTiles

El formato MBTiles es una base de datos SQLite, que se utiliza para guardar mapas. El mapa puede ser de tipo raster o vectorial. En esta sección explicaré la estructura de datos (tablas) y valores para obtener los mapas de tipo raster.

Compresión RLE

El algoritmo de compresión RLE fue muy utilizado en la época de los procesadores de ocho bits, y aún se usa para la compresión de imágenes en ciertos formatos como BMP, o PCX.

Combinaciones

Combinaciones sin repetición de n elementos tomados de r en r

Mientras escribía el código para buscar grupos de casillas para resolver sudokus me encontré ante el problema de generar sucesivamente todas las combinaciones de varias casillas que cumplieran ciertas condiciones. En el caso concreto de los sudokus siempre se trata de conjuntos de nueve casillas, y los grupos varían en tamaño entre dos y siete.

Librerías C/C++ para generar códigos QR

Generar códigos QR no es una tarea trivial. Existen varios formatos con muchas opciones diferentes.

Resolución de sudokus (15)

Bugs

Por desgracia ni nuestros algoritmos ni nuestro código está a salvo de errores. Lamentablemente, en algunos de los procedimientos que hemos visto he cometido algunos bastante serios.

Búsqueda binaria

Una de las tareas que nos solemos encontrar con cierta frecuencia al programar es la de buscar la posición de un valor en un array.

Resolución de sudokus (14)

Hilo de cometa y rectángulos eludibles

Hilo de cometa Este método probablemente sea más sencillo de aplicar y más intuitivo que otros que hemos visto, como es rascacielos o incluso que XY-Wing. No he encontrado ningún sudoku en el que se pueda aplicar éste método que aporte información que no hayan aportado alguno de los métodos que ya hemos visto. Pero como estos patrones pueden ser más fácil de detectar que otros, lo procesaremos antes que ellos.

Resolución de sudokus (13)

Rectángulos vacíos

Esta técnica consiste en encontrar una caja k, en las que un candidato solo aparezca en una fila y una columna. A continuación hay que localizar una fila en la que el candidato solo aparezca en dos casillas, un una de esas casillas coincida con la columna de candidatos de la caja k. En la casilla que esté en la intersección de la columna de la otra casilla y en la fila de la caja k se podrá eliminar el valor como candidato.

Resolución de sudokus (12)

Sashimi y rascacielos

Para comprender esta técnica hay que verla como un X-Wing con alas en el que falta el candidato en la casilla que tiene el o las alas.

Resolución de sudokus (11)

XYZ-Wing.

La idea de este método es relativamente sencilla, si comprendemos correctamente cómo funciona un patrón XY-Wing.

Resolución de sudokus (10)

Patrones de solución única.

Volvamos a este sudoku que nos quedó al aplicar el patrón X-Wing. Este tablero tiene una característica muy interesante: todas las casillas vacías tienen dos candidatos, excepto una que tiene tres.

Resolución de sudokus (9)

Pez espada.

Este método es una generalización del X-Wing. Consiste en encontrar tres filas o columnas en las que solo aparezca un candidato en tres casillas de esas tres filas y columnas en las mismas columnas o filas.

Resolución de sudokus (8)

X-Wing y X-Wing con alas.

Aún existen situaciones en las que ninguna de las técnicas anteriores nos puede ayudar a resolver el sudoku. Veamos ahora otra técnica que podemos probar.

Resolución de sudokus (7)

XY-Wing.

La idea de este método es sencilla, aunque localizar dónde aplicarla en un sudoku puede que no sea tan intuitivo.

Resolución de sudokus (6)

Parejas, trios y cuartetos ocultos.

Si hay que llegar a este punto para resolver un sudoku ya podemos considerarlo como difícil. El criterio es que hasta ahora hemos trabajado con bloques: filas, columnas y cajas, pero a partir de ahora tenemos que trabajar con casillas individuales de todo el tablero. La diferencia puede parecer sutil, pero se necesita más concentración y mas tiempo para localizar las relaciones entre casillas con los métodos que veremos a partir de ahora. Y eso irá en aumento a medida que tengamos que recurrir a métodos más complejos.

Resolución de sudokus (5)

Marcas de lápiz y parejas y trios punteros.

A partir de aquí será necesario hacer todas las marcas de lápiz en todas las casillas. Una vez hecho eso podemos volver a aplicar algunos métodos conocidos, como el de parejas desnudas, ya que puede que aparezcan algunas que no se habían revelado con los métodos anteriores.

Resolución de sudokus (4)

Parejas desnudas.

Veamos otro sudoku parcialmente solucionado con las técnicas que hemos incorporado hasta ahora, y fijémonos en la segunda fila.

Resolución de sudokus (3)

Candidatos únicos y solitarios.

Otra técnica que podemos considerar básica es localizar filas, columnas o cajas con un único candidato posible.

Fijémonos en la tercera columna, en la que sólo hay una casilla libre, y el único valor que falta es el 9. Esto nos proporciona algunos valores adicionales.

Resolución de sudokus (2)

Criba de casillas.

Empecemos a implementar algunos métodos de resolución.

El primero se conoce como "tres en raya" o "tic-tac-toe". Trabajaremos con filas y columnas, pero de cajas. Para cada una de esas filas y columnas buscaremos valores que estén presentes en dos de las cajas.

Resolución de sudokus

Reglas y Sudokus válidos

El sudoku es un juego, o pasatiempo, que se ha hecho muy popular. A mucha gente, yo incluido, le resulta muy entretenido.

Algoritmo Big Mod

Pongamos que tenemos que calcular el módulo o resto de la división de un número de muchas cifras entre otro más pequeño, lo suficiente para que pueda almacenarse en un int, o en un long int.

No es algo que no nos vayamos a encontrar nunca. De hecho, la razón de esta entrada es que he necesitado hacer estas operaciones, y pronto veremos un ejemplo en una entrada posterior.

Conectar y desconectar unidades de red

Algunas veces nos encontramos con la necesidad de que nuestra aplicación acceda a archivos almacenados en un ordenador diferente, aunque conectado a la misma red.

Recibir correo POP3

Ya vimos en una entrada anterior cómo podemos enviar mensajes de correo desde una aplicación Windows. En esta entrada veremos cómo podemos recibir correo usando el protocolo POP3.

Explicaré algo de teoría (no mucha), pero no te preocupes, verás que leer correos será realmente sencillo, otra tema muy diferente será procesar su contenido.

Codificación base64

Base 64 es un sistema de numeración, como el decimal, el binario o el hexadecimal, pero que usa 64 símbolos.

En la práctica no se usa tanto para codificar números, sino sobre todo para codificar datos binarios. El motivo es que usa 64 símbolos imprimibles: 62 de los símbolos consisten en el alfabeto en mayúsculas y en minúsculas y los dígitos 0 a 9. Para los otros dos se usan distintos caracteres, dependiendo de la versión particular del código. Los más habituales son el '+' y el '/'.

Validar datos en C++

En aplicaciones de consola C++, uno de los puntos más problemáticos es la lectura de datos por parte del usuario.

Las funciones de entrada C y los métodos del stream cin resultan poco potentes a la hora de hacer lecturas discriminadas de número enteros, o en coma flotante, fechas o cadenas que se ajuste a un formato determinado.

Acentos y eñes en programas de consola de Windows

Cuando creamos programas para consola de Windows hay algo que resulta muy frustrante: las eñes, cedillas y acentos no se muestran como debieran, y en su lugar se ven unos caracteres raros que dificultan la lectura de los textos y resultan muy antiestéticos.

Impedir que una aplicación se ejecute dos veces

¿Cómo podemos evitar que una aplicación se ejecute más de una vez de forma simultánea?

En Windows existe un método sencillo: usar un mutex.

El nombre mutex es una abreviatura de un algoritmo de exclusión mutua. Es un dispositivo que se usa normalmente para evitar concurrencia, es decir para controlar el acceso de determinadas zonas de código que tienen acceso a recursos compartidos.

Colocar un icono en el área de notificación

A veces puede ser interesante que nuestras aplicaciones coloquen un icono en el área de notificación.

Sin embargo, tampoco conviene abusar de esta técnica. El área de notificación se diseñó para proporcionar mensajes importantes al usuario, pero si se añaden demasiados iconos esta funcionalidad puede perder gran parte de su eficacia.

Envío de email desde C++

De nuevo, como necesidad de unos de los programas que tuve que escribir hace un tiempo, surgió el problema de enviar mensajes de correo electrónico desde un programa en C++.

Crear librerías .a a partir de librerías .lib

Con cierta frecuencia encontramos bibliotecas (o librerías) de funciones que nos pueden resultar útiles en nuestros programas. En este blog hablaremos de algunas de ellas.

Acceder a ficheros comprimidos desde C++

Hace unos meses me encontré con la necesidad de acceder a ciertos ficheros desde una aplicación C++.

Estos ficheros individuales están contenidos dentro de un fichero comprimido con la extensión ZIP.

El puerto serie en Windows

En Windows no es posible acceder a los dispositívos físicos directamente, a través de las direcciones de sus puertos. Por el contrario, todos los accesos (salvo que estemos programando un driver) deben hacerse a través de funciones del API.

Los puertos serie, por tratarse de dispositivos incluidos como parte de los PC desde sus comienzos, están muy bien integrados en el API de Windows, por lo tanto, tenemos un amplio repertorio de funciones para manejarlos.

Esperar a que terminen los hilos

La solución que hemos usado para asegurarnos de que los hilos han terminado antes de salir no es demasiado elegante. Sólo esperamos dos segundos, y damos por supuesto que en ese tiempo los hilos han tenido tiempo de sobra para terminar, lo cual es cierto, al menos en este ejemplo. Pero puede que en otros usos de hilos esto no sea tan simple, y de todos modos, no parece que esperar un tiempo fijo antes de cerrar sea la mejor forma de terminar un programa.

Hilos

Esto es una primera aproximación al uso de hilos en Windows. El tema es mucho más extenso y complejo de lo que se explica aquí, pero daremos algunas nociones para poder usarlos en nuestros programas y más concretamente, en juegos para la consola de Windows.

Arboles-B

Los árboles-B son árboles de búsqueda.

La "B" probablemente se debe a que el algoritmo fue desarrollado por "Rudolf Bayer" y "Eduard M. McCreight", que trabajan para la empresa "Boeing" aunque parece que "Karl Unterauer" desarrolló un algoritmo semejante en la misma época.

Algoritmo de compresión de Huffman

Se trata de un algoritmo que puede ser usado para compresión o encriptación de datos.

Este algoritmo se basa en asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión del fichero.