Probando el marco digital Parrot DF3120 (parte 2)

Proyectos 14 Comentarios

En el anterior artículo explicaba cómo instalar linux en el marco digital Parrot DF3120. En este explicaré cómo generar el toolchain para poder crear programas que funcionen en el marco digital. De paso crearemos una versión de la imagen más moderna para nuestro marco. El artículo original que lo explicaba es este, pero está desfasado y hay que hacer retoques para que funcione bien.

Lo voy a hacer todo desde mi linux Ubuntu 11.10, por lo que es posible que algunas cosas haya que modificarlas si usáis otra distribución.

Lo primero es instalarse usa serie de paquetes que son necesarios para que todo el proceso sea correcto:

sudo apt-get install git-core
sudo apt-get install tig
sudo apt-get install lzop
sudo apt-get install uboot-mkimage
sudo apt-get install libelf-dev
sudo apt-get install libncurses-dev
sudo apt-get install gtk-doc-tools
sudo apt-get install checkinstall
sudo apt-get install e2fsprogs
sudo apt-get install libglib2.0-dev
sudo apt-get install libxml2-dev
sudo apt-get install genext2fs
sudo apt-get install lzma
sudo apt-get install subversion
sudo apt-get install cvs
sudo apt-get install gawk
sudo apt-get install bison
sudo apt-get install flex
sudo apt-get install automake
sudo apt-get install gcc
sudo apt-get install build-essential
sudo apt-get install texinfo
sudo apt-get install curl

Después hay que bajarse minifs con el git:

git clone http://oomz.net/git/minifs.git minifs

A continuación hay que hacer un par de modificaciones:

  • Edita el fichero minifs/conf/board/df3120/config_busybox.conf y reemplaza la línea # CONFIG_CHMOD is not set por CONFIG_CHMOD=y
  • Edita el fichero minifs/conf/packages/05crosstools.sh y reemplaza la línea hset libtool url “http://ftp.gnu.org/gnu/libtool/libtool-2.4.2.tar.gz” por hset libtool url “http://ftp.gnu.org/gnu/libtool/libtool-2.4.tar.gz”

Después ya podemos ejecutar el script de la siguiente forma (Puede tardar varios minutos):

cd minifs
export MINIFS_BOARD=df3120
./minifs_build.sh

Ahora vemos que entre otras cosas se han creado dos ficheros en el directorio build-df3120, un .img y un .plt. Pues bien con ellos hay que volver a hacer lo mismo que comentaba en el anterior artículo. Si todo ha ido bien veremos la nueva versión del firmware donde lo más destacado es que aparecen los mensajes de arranque:

Ahora vamos a compilar nuestro primer programa, y cómo no, tenía que ser un Hola Mundo:

#include <stdio.h>
 
void main(void)
{
 printf("Hola Mundo.\n");
}

Copiamos el código que aparece arriba y lo guardamos en un fichero llamado holamundo.c. Después ejecutamos el siguiente comando:

toolchain/arm-v4t-linux-uclibcgnueabi/bin/arm-v4t-linux-uclibcgnueabi-gcc holamundo.c -o holamundo

Esto habrá generado un fichero ejecutable llamado holamundo, pero ¿cómo lo subimos al marco para ejecutarlo?. Pues bien entre otros comandos el marco tiene dos, el tftp y wget para descargar ficheros mediante el protocolo tftp y http respectivamente, por tanto hay que instalar un servidor web o tftpd en nuestra máquina linux.

Servidor web apache:

sudo apt-get install apache2

Servidor tftp: Instrucciones

Si hemos optado por el servidor web sólo hay que copiar el fichero holamundo al directorio /var/www. Si la elección ha sido tftpd entonces hay que copiar el fichero holamundo al directorio que se haya configurado.

Ahora tenemos que descargarlo desde el marco digital. Hacemos un telnet como explicaba en el anterior artículo. En el firmware actual todo el disco está montado como sólo lectura, por lo que tendremos que remontarlo como escritura también de la siguiente forma:

mount / / -o remount,rw

Ahora nos vamos al directorio /tmp y descargamos el programa.

Para tftp el comando sería:

tftp -g -r holamundo <IP DEL SERVIDOR TFTP>

Para wget el comando sería:

wget http://<IP DEL SERVIDOR WEB>/holamundo

Ahora que tenemos el fichero, hay que darle permisos de ejecución y finalmente ejecutarlo:

chmod a+x holamundo
./holamundo

Obtendremos esto:

Ya hemos compilado nuestro primer programa y lo hemos hecho funcionar, pero claro, nos interesa que se pueda dibujar en la pantalla algo para ver cómo se ve en el marco. Lo primero que hay que saber es que la pantalla tiene asignado el dispositivo /dev/fb0 y que lo que tenemos que conseguir es acceder a su memoria para escribir directamente los colores. Esto se consigue de la siguiente forma:

Con la función open abrimos el dispositivo como lectura/escritura:

int g_fb = open("/dev/fb0", O_RDWR);

Con la función ioctl recibimos en una estructura información sobre la pantalla:

struct fb_var_screeninfo var_info;
ioctl(g_fb, FBIOGET_VSCREENINFO, &var_info);

Con la función mmap obtenemos el buffer de la memoria de vídeo para leerlo y escribir en el:

char *buffer = (char *)mmap(0, 153600, PROT_READ|PROT_WRITE, MAP_SHARED, g_fb, 0);

Ahora sólo queda dibujar los bytes en la memoria para que se vean reflejados como pixeles en la pantalla. Al poder representar la pantalla 64k colores estos se codifican a RGB mediante 16 bit con el formato 5-6-5 (rrrrrggggggbbbbb). Así el rojo es 1111100000000000 (0xF800), el verde es 0000011111100000 (0x07E0) y el azul es 0000000000011111 (0x001F). Por tanto cada pixel en la pantalla ocupa 16 bits.

Para probar todo esto he creado un programa que muestra un cuadro verde rebotando por el marco usando la técnica de doble buffer para evitar parpadeos:

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <linux/fb.h>
#include <sys/mman.h>
#include <sys/ioctl.h>
 
 
char *inicializa(int *cuantos)
{
  char* buffer;
  int g_fb;
  struct fb_var_screeninfo var_info;
 
  g_fb = open("/dev/fb0", O_RDWR);
  if (g_fb == -1)
  {
    printf("No se puede abrir /dev/fb0\n");
    _exit(1);
  }
 
  printf("/dev/fb0 abierto con el handle 0x%x\n", (unsigned)g_fb);
 
  if (ioctl(g_fb, FBIOGET_VSCREENINFO, &var_info))
  {
    printf("No se puede obtener la información variable de la pantalla\n");
    _exit(1);
  }
 
  printf("xres: %d\n", var_info.xres);
  printf("yres: %d\n", var_info.yres);
  printf("bpp: %d\n", var_info.bits_per_pixel);
  *cuantos = var_info.xres * var_info.yres * var_info.bits_per_pixel /8;
 
  printf("El tamaño del buffer de pantalla es de %d bytes\n", *cuantos);
 
  buffer = (char *)mmap(0, *cuantos, PROT_READ|PROT_WRITE, MAP_SHARED, g_fb, 0);
 
  if ((int)buffer == -1) 
  {
    printf("falló mmap().\n"); 
    exit(1);
  }
  printf("Pantalla devuelta\n");
  return buffer;
}
 
void cuadro(int x, int y, short int *buffer, int color)
{
 int anchura;
 int altura;
 short int *puntero;
 
 for(altura = 0; altura < 50; altura++)
 {
  puntero = buffer + ((y + altura) * 320);
  for(anchura = 0; anchura < 50; anchura++)
  {
   *(puntero + x + anchura) = color;
  }
 }
}
 
void main(void)
{
 int indice;
 int cuantos;
 int x = 0;
 int y = 0;
 int suma_x = 1;
 int suma_y = 1;
 
 short int *buffer = (short int *)inicializa(&cuantos);
 short int *ventana = (short int *)malloc(cuantos);
 
 if (ventana == NULL)
 {
  printf("No se puede crear el doble buffer\n");
  _exit(1);
 }
 // fondo negro
 for(indice = 0; indice < (cuantos / 2); indice++)
 {
  buffer[indice] = 0; 
 }
 
 for(;;)
 {
  usleep(10000);
  cuadro(x, y, ventana, 0);
  x += suma_x;
  y += suma_y;
  if(x > 269 || x < 0)
  {
   suma_x *= -1;
   x += suma_x;
  }
  if(y > 189 || y < 0)
  {
   suma_y *= -1;
   y += suma_y;
  }
  cuadro(x, y, ventana, 0x7E0);
  memcpy(buffer, ventana, cuantos);
 }
}

Que ejecutándolo quedaría así:

En un próximo artículo explicaré como acceder a la interfaz con SDL, comunicarse con bluetooth mediante RFCOMM y obtener los valores de los botones traseros y del inclinómetro.

Probando el marco digital Parrot DF3120 (parte 1)

Electrónica, Proyectos, Reseñas 17 Comentarios

He adquirido el marco digital de fotos Parrot DF3120. Es un marco que por menos de 20€ puede representar fotografías en una pantalla de 320×240 (3.5″). Sus puntos fuertes es que tiene bluetooth para poder subir las imagenes desde, por ejemplo, un móvil y una entrada para tarjetas SD con la misma función.

Este marco ha sido hackeado y se le puede instalar un linux, con las ventajas que ello representa. El objetivo de este primer artículo es mostrar el proceso de instalación de linux y cómo acceder a este de una forma sencilla.

Lo primero es hacer un duplicado de disco del siguiente fichero: minifs-full-ext.img. Esto en linux, siendo root, se consigue con el siguiente comando (disco SD es el nombre que le haya asignado el sistema):

dd if=minifs-full-ext.img of=/dev/<disco SD>

Lo siguiente es actualizar el firmware del marco. Para ello hay que encender el marco sin ninguna tarjeta SD insertada y enchufar el cable usb. Cuando podamos acceder al contenido del disco, crear una carpeta llamada update y dentro de esta copiar el fichero parrotDF3120.plf. Después sacar el usb de forma segura y veremos que aparecen 4 cuadros en la pantalla (uno azul y el resto verde), momento en el cual ya se ha actualizado el firmware.

Ahora tenemos un modo de arranque dual. Por un lado si encendemos el marco sin más veremos su funcionalidad de siempre, es decir, se visualizarán las imágenes que tengamos almacenadas una detrás de otra. Pero si metemos la tarjeta SD y antes de encenderlo pulsamos los botones izquierdo y central de la parte de atrás y, sin soltarlos, encendemos el marco, se arrancará  linux y busybox.

Finalmente para acceder a la consola en el modo linux podemos hacerlo de dos formas (la dificil y la fácil):

La dificil es sacar todos los tornillos para quedarnos con la placa y la pantalla. A continuación soldamos en los agujeros del J4 (la consola serie) los tres pines (1: GND, 2: RX, 3: TX) y nos buscamos un conversor TTL a puerto serie o a usb para poder comunicarnos con el dispositivo usando los siguientes parámetros de conexión: 115200 8,N,1 (recomiendo screen en linux o mac y putty en windows). Esta es la consola serie donde se ven los mensajes de estado del arranque y luego se obtiene una shell donde interactuar con linux:

La fácil es simplemente conectar el cable usb al marco y a nuestro ordenador, lo que nos configurará una conexión ethernet por usb llamada Ethernet Gadget, la cual será una tarjeta de red que debemos configurar con la IP 172.16.61.2 y la máscara de red 255.255.255.0. Si todo ha ido bien y hacemos un ping a la dirección 172.16.61.1 el marco nos debería responder. Finalmente para acceder a una shell sólo hay que hacer un telnet a la IP comentada.

Edición 22/01/2011:
En el marco vienen unos programas para probar la pantalla gráfica. Podeis ejecutar cualquiera de ellos:
/usr/bin/plasma: Una bonita demo sobre el efecto plasma.
/usr/bin/newvox: Un paisaje que si tuvieramos teclado podríamos recorrerlo.

He publicado un segundo artículo que explica cómo crear programas que se ejecuten en el marco.

Por fin se puede programar la cámara IP Zaapa CIPRW (ZA-CIPRW) fácilmente

Informática, Proyectos, Reseñas Sin comentarios

Hacía tiempo que no volvía a escribir sobre la cámara ip Zaapa CIPRW. Escribí dos artículos: Uno sobre la descripción de la cámara en septiembre de 2008 y otro sobre cómo programarla en .NET en Agosto de 2009.

Lo cierto es que desde entonces dejé abandonado el tema y por necesidades he tenido que retomarlo para poder interactuar con ella. Poco tiempo después de escribir el último artículo se publicó en la página de Gadget Victims información sobre un nuevo firmware para las cámaras Foscam FI908W (La de Zaapa es la FI8901W) en septiembre de 2009 donde entre otras cosas se habla de la documentación oficial de FOSCAM para sus cámaras IP. Lo mejor de esto es que en esta documentación hay dos textos que pueden servirnos a los programadores para interactuar definitivamente con la cámara Zaapa y a los usuarios para poder ver sus cámaras en navegadores como Firefox, Chrome, Safari, etc.

Se trata del IPCAM CGI SDK 2.1 y del IPCAM Protocol. El primero es un documento PDF donde se explica cómo haciendo peticiones HTTP se puede descargar la imagen de la cámara y enviar ordenes a esta. El segundo es un documento de Word donde se explica el protocolo de la cámara para comunicarse con ella mediante socket. En este artículo me centraré en el primero por su facilidad de uso.

En el primer documento se explica qué peticiones hay que hacer para interactuar con la cámara. Se trata de acceder a páginas web CGI pasándole normalmente los parámetros mediante el método GET, que es como en realidad nosotros hacemos las llamadas desde un navegador web normalmente.

Antes de empezar a probar hay que cerciorarse de que la cámara Zaapa tiene el último firmware y el último Embeded Web UI. Si en la sección Device Info del panel del administrador son distintos de 11.4.1.40 y 2.0.0.16 respectivamente, hay que actualizar. En la página del producto se pueden descargar pero hay que introducir el número de serie que aparece como código de barras en la parte inferior de la cámara. Una vez que empieza la descarga empieza lo gracioso y es que veremos algo raro en el fichero que descargamos pues no tiene extensión y que no sirve para actualizar ya que no es un .bin. Pues bien el fichero es un archivo .rar por lo que hay que renombrarlo, ponerle esa extensión y ya podemos abrirlo. Dentro de este veremos dos ficheros .bin y aquí esta lo segundo más gracioso ¡¡¡ están al revés !!! Embeded Web UI 11.4.1.40.bin tendría que ser Firmware 11.4.1.40.bin y Firmware 2.0.0.16.bin tendría que ser Embeded Web UI 2.0.0.16.bin. Una vez arreglado ese desaguisado ya podemos actualizarlo desde la sección Upgrade Device Firmware del panel de administrador y actualizar el firmware primero y el Web UI después (en ambos casos se reinicia la cámara).

Hay unos cuantos CGI y lo mejor es leerse la documentación, pero voy a explicar 3 de ellos que me parecen fundamentales:

    • El primero de ellos es el snapshot.cgi. Sirve para capturar una imagen estática de la cámara. Si ponemos en un navegador web http://ip de la cámara/snapshot.cgi nos pedirá un usuario y una contraseña. Cuando la hayamos introducido veremos la imagen jpg. Podemos evitar que salga el recuadro que nos pide el usuario y la contraseña simplemente añadiendo los parámetros user y pwd a la url de la siguiente forma http://ip de la cámara/snapshot.cgi?user=usuario&pwd=contraseña para que ya directamente nos muestre la imagen. Tiene otro parámetro llamado next_url para indicar el nombre del fichero pero no lo veo útil.
    • El segundo de ellos son en realidad dos: videostream.cgi y videostream.asf. Sirven para mostrar un flujo continuo de imagenes a modo de vídeo. El que tiene extensión .cgi envía imágenes jpg sucesivas (ideal para verlas con una navegador), el que tiene extensión asf envía las imágenes con el formato Advanced Streaming Format (ideal para verlas con el VLC o con el MPlayer). Si ponemos en un navegador web http://ip de la cámara/videostream.cgi?user=usuario&pwd=contraseña podemos ver el flujo continuo de lo que la cámara está enfocando en ese momento. Tiene otro parámetro llamado resolution para indicar con un 8 o un 32 si queremos que la imagen tenga de tamaño 320×240 o 640×480 respectivamente.
    • El tecero de ellos es el decoder_control.cgi. Sirve para interactuar con la cámara. Si ponemos en el navegador web http://ip de la cámara/videostream.cgi?user=usuario&pwd=contraseña&command=comando donde comando sea un número que indica qué hacer a la cámara (0 = empezar a mover hacia arriba, 1 = parar de mover hacia arriba, 2 = empezar a mover hacia abajo, etc) veremos como se mueve esta.

Finalmente he creado una página HTML para probar los dos últimos CGIs que he explicado. La página muestra la sucesión de imágenes de la cámara y tiene unos botones que permiten mover la cámara. Para adecuarlo a la vuestra sólo teneis que cambiar en la sección javascript el usuario, la clave y la ruta a vuestra cámara:

<html>
<head>
	<style type="text/css">
		.comando {background-color:#FFFF00; border-radius: 10px; font-family:Arial; font-size:10pt; font-weight:bold; width:70px; text-align:center}
		#imagen {visibility:hidden; width:640px; height:480px;}
		#marco {visibility:hidden;}
	</style>
	<script type="text/javascript">
		var usuario = "usuario";
		var clave = "clave";
		var ruta = "http://192.168.0.12/";
 
		function cargado()
		{
			var imagen = document.getElementById("imagen");
			imagen.src = ruta + "videostream.cgi?user=" + usuario + "&pwd=" + clave + "&resolution=32";
			imagen.style.visibility = "visible";
		}
 
		function empieza_arriba()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=0";
		}
 
		function termina_arriba()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=1";
		}
 
		function empieza_abajo()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=2";
		}
 
		function termina_abajo()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=3";
		}
 
		function empieza_izquierda()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=4";
		}
 
		function termina_izquierda()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=5";
		}
 
		function empieza_derecha()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=6";
		}
 
		function termina_derecha()
		{
			var marco = document.getElementById("marco");
			marco.src = ruta + "decoder_control.cgi?user=" + usuario + "&pwd=" + clave + "&command=7";
		}
 
 
	</script>
</head>
<body onload="cargado()">
<img id="imagen">
<table>
<tr><td>&nbsp;</td><td class="comando" onmousedown="empieza_arriba()" onmouseup="termina_arriba()">Arriba</td><td>&nbsp;</td></tr>
<tr><td class="comando" onmousedown="empieza_izquierda()" onmouseup="termina_izquierda()">Izquierda</td><td>&nbsp;</td><td class="comando" onmousedown="empieza_derecha()" onmouseup="termina_derecha()">Derecha</td></tr>
<tr><td>&nbsp;</td><td class="comando" onmousedown="empieza_abajo()" onmouseup="termina_abajo()">Abajo</td><td>&nbsp;</td></tr>
</table>
<iframe id="marco" src=""></iframe>
</body>
</html>

El funcionamiento es muy sencillo. Una etiqueta img muestra el CGI videostream.cgi. Las celdas de la tabla tienen los eventos onmousedown y onmouseup para detectar cuando se pulsan y cargar en el marco oculto el CGI decoder_control.cgi con la orden correspondiente. Así es como se ve funcionando en un MAC y Safari:

Y de paso pongo otro vídeo de cómo se puede usar esta cámara con un móvil con las múltiples aplicaciones que hay en android market y en app store simplemente eligiendo en estas como marca de cámara la FOSCAM:

Fuerza bruta en .net para resolver las cifras del concurso cifras y letras

Informática, Proyectos 4 Comentarios

Hacía tiempo que no me ponía a mi mismo un reto de programación y el otro día viendo en la tele el programa cifras y letras me animé a hacer una aplicación que resolviese la sección de cifras. Primero me leí las normas y luego empecé a pensar cómo resolver este tipo de problema. Buscando por Internet encontré estos artículos: (uno, dos y tres) donde de 30.965.760 combinaciones posibles entre los 6 números y sus cuatro operaciones se reduce a 488.642 combinaciones. Además me encontré con dos páginas que resuelven el problema on-line: esta y esta (ambas usando la técnica de backtracking).

Como mi objetivo era hacerlo mediante fuerza bruta, la técnica de backtracking me pareció lo mejor para abordar el problema. Se crea un árbol donde cada nodo contendrá los números con los que se operan, la operación que ha generado ese nodo y el resultado de la misma (excepto el primer nodo que sólo contiene el conjunto de números original).

Vamos combinando uno por uno todos los números con todas las operaciones para encontrar el resultado que buscamos. El orden de las operaciones es suma, resta, multiplicación y división. Como esto puede generar una ingente cantidad de cálculos, podemos podar (acotar) el árbol para reducir estos y el tiempo empleado. Esto se consigue eliminando aquellos casos que no deben darse: En la resta que el resultado sea 0, en la división que el divisor sea 1 o que el resto sea distinto de 0 y que en la multiplicación uno de los factores sea 1. Para evitar números negativos en la resta o que el divsor sea mayor que el dividendo ponemos primero el mayor y después el menor en la operación.

A medida que vamos avanzando en la profundidad del árbol, el conjunto de números con los que operar se irá reduciendo ya que cada pareja de números se convertirá en uno por la operación matemática que se les aplique, siendo esto así recursivamente hasta que sólo haya un número, momento en el cual si el resultado no coincide con el esperado, se retrocede un nodo y se continúa con las siguientes combinaciones.

Para entenderlo mejor un gráfico donde dado un conjunto de tres números (1, 2 y 3) debemos operar con ellos hasta que obtengamos 7 como resultado:


En el ejemplo después de buscar varias combinaciones entre sumas y restas (puntos suspensivos en el gráfico) hemos llegado a las combinaciones de multiplicaciones. Existen tres combinaciones de multiplicaciones: Op: 1 * 2 (que no he puesto en el gráfico por simplificarlo), Op: 1 * 3 y Op: 2 * 3.

  • En el nodo de la multiplicación de 1 * 3 el resultado (Res:) es 3 y no 7 como andamos buscando por lo que hay que seguir calculando. El conjunto de números de este nodo se ha reducido de Nu: 1, 2, 3 a Nu: 2, 3.
    • A continuación hay que crear otro nodo con la suma de los únicos números que quedan: 2 + 3, pero el resultado es 5 con lo que volvemos al nodo anterior.
    • Vamos a hacer la resta: 3-2, pero sigue sin servirnos el resultado, por tanto volvemos al nodo anterior.
    • Hacemos la multiplicación: 2 * 3, pero seguimos igual, por lo que nos vamos al nodo anterior.
    • La división se descarta porque 3 / 2 no dá como resto 0, con lo que no se crea ese nodo y se vuelve al anterior (que en este ejemplo es el principal).
  • Continuamos con la creación del nodo de la multiplicación de 2 * 3 donde el resultado (Res:) es 6 y no 7 como andamos buscando por lo que hay que seguir calculando. El conjunto de números de este nodo se ha reducido de Nu: 1, 2, 3 a Nu: 1, 6.
    • Hay que crear otro nodo con la suma de los únicos números que quedan: 1 + 6, y como el resultado es 7, que es el que buscábamos, ya no hacemos ninguna operación más y vamos retrocediendo por todo el árbol (que os recuerdo que se ha construido mediante una función recursiva) hasta salir de la función que lo ha generado.

El nivel de profundidad de los árboles depende de la cantidad de números inicial. Si son un conjunto de 3 números la profundidad será de 3 niveles, si es de 6 pues … ya sabeis la respuesta :)

Como se trata de una estructura de árbol, cada nodo debe tener un puntero al siguiente nodo para trazar un camino desde el nodo inicial hasta el nodo que contiene el resultado que buscamos (en el cual el puntero estará vacío).  Dado que hemos aplicado la técnica de backtracking los nodos que previamente hayamos calculado y no pertenezcan a ese camino desaparecerán porque no nos sirven. Finalmente mediante un bucle recorreremos todos los nodos del camino mostrando por pantalla la operación que lo ha creado hasta el nodo final. Así en el ejemplo quedaría:

3 * 2 = 6
6 + 1 = 7

Sin embargo en el juego de cifras y letras si no se encuentra el número exacto se puntúa el número que más se acerque a este. La problemática aquí es que con el bactracking, si no se encuentra el número exacto, el camino que se habrá generado cuando retorne la función es el de la última operación, que con toda probabilidad no será el camino hacia el número que más se aproxime al original.

En este caso tenemos dos posibles formas de solucionarlo:

  • A medida que vamos generando los nodos debemos comparar el resultado con el número que buscamos, si se acerca más que el anterior valor que hayamos comparado guardamos este resultado como el número que más se aproxima al buscado. Después cuando haya salido de la función y no se haya encontrado el exacto, se vuelve a llamar a esta misma pero buscando en esta ocasión el resultado aproximado (ya que tenemos la certeza de que se puede calcular) obteniendo así el camino hasta llegar al que más se acerca.
  • El problema de la solución anterior es que tenemos que llamar dos veces a la función que genera el árbol: una para buscar el exacto y otra para buscar el aproximado. Lo ideal es ir guardando un camino alternativo hacia el número aproximado, para que, en caso de no hallar el exacto, recorrer el camino alternativo mediante un bucle para mostrar las operaciones que obtengan el número aproximado. Todo desde la misma llamada a la función. Esto provoca que también se necesite un puntero al nodo anterior.

Aquí dejo el código fuente en C# que pone en práctica todo lo comentado. Se trata de una aplicación de consola donde como parámetros se le pasa todo el conjunto de números separados por espacio y como último número el resultado que se desea averiguar.

Program.cs:

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
 
namespace Cifras
{
    class Program
    {
        static int Main(string[] args)
        {
            // Ncesitamos como mínimo dos números para operar y un resultado
            if (args.Length < 3)
            {
                Console.Write("La sintaxis es " + System.AppDomain.CurrentDomain.FriendlyName + " <número 1>...<número n> <número buscado>");
                return 1;
            }
            Console.Write("Set de números: ");
            ArrayList posibilidades = new ArrayList();
            int indice = 0;
            // Creamos el conjunto de números a partir de la línea de comandos.
            for (; indice < args.Length - 1; indice++)
            {
                Console.Write(args[indice] + " ");
                posibilidades.Add(Int32.Parse(args[indice]));
            }
            int descubre = Int16.Parse(args[indice]);
            Console.WriteLine("\nNúmero buscado: " + descubre + "\n");
            // Creamos el primer nodo del árbol.
            Nodo encuentra = new Nodo(posibilidades, descubre);
            // Creamos un contador
            DateTime hora = DateTime.Now;
            TimeSpan tiempo;
            // Si se ha encontrado el exacto
            if (encuentra.busca() == true)
            {
                tiempo = DateTime.Now - hora;
                Console.WriteLine("Se encontró el exacto.\n");
            }
            // En caso de no encontrarse el exacto
            else
            {
                tiempo = DateTime.Now - hora;
                Console.WriteLine("No se ha encontrado el exacto.\n");
                // Sustituimos el camino original por el camino del aproximado
                encuentra = Nodo.Cercano;
            }
            Console.WriteLine("Número de nodos calculados: " + Nodo.NumeroNodos);
            Console.WriteLine("Tiempo en calcularlo: " + tiempo.TotalMilliseconds + " ms.\n");
            Console.WriteLine("Operaciones:");
            // Recorremos todos los nodos del camino para mostrar las operaciones que se han ido ejecutando.
            while (encuentra.Hijo != null)
            {
                encuentra = encuentra.Hijo;
                Console.WriteLine(encuentra.Valor1 + encuentra.Signo + encuentra.Valor2 + "=" + encuentra.Resultado);
            }
            return 0;
        }
    }
}

Nodo.cs:

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
 
namespace Cifras
{
    class Nodo
    {
        private enum OPERACIONES { SUMA, RESTA, MULTIPLICACION, DIVISION };
        private static int buscado; // El número exacto que debemos encontrar.
        private ArrayList numeros; // El conjunto de números con los que pueden operar los hijos del nodo.
 
        private Nodo padre; // El nodo padre del nodo actual.
 
        private Nodo hijo; // El nodo hijo del nodo actual.
 
        public Nodo Hijo
        {
            get { return hijo; }
        }
 
        private int valor1; // El primer operando.
 
        public int Valor1
        {
            get { return valor1; }
        }
        private int valor2; // El segundo operando.
 
        public int Valor2
        {
            get { return valor2; }
        }
 
        private string signo; // El signo de la operación.
 
        public string Signo
        {
            get { return signo; }
        }
 
        private int resultado; // El resultado de la operación.
 
        public int Resultado
        {
            get { return resultado; }
        }
 
        private static Nodo cercano; // Camino donde se llega al número más aproximado al buscado.
 
        public static Nodo Cercano
        {
            get { return Nodo.cercano; }
        }
 
        private static int aproximado; // Variable que va guardando qué número es el más aproximado.
 
        private static int numeroNodos; // Número total de nodos creados.
 
        public static int NumeroNodos
        {
            get { return Nodo.numeroNodos; }
        }
 
        // Contructor para crear el primer nodo del arbol
        public Nodo(ArrayList numeros, int buscado)
        {
            this.numeros = numeros;
            Nodo.buscado = buscado;
            padre = null;
            hijo = null;
            Nodo.cercano = null;
            Nodo.aproximado = 0;
            Nodo.numeroNodos = 0;
        }
 
        // Constructor para crear los restantes nodos del arbol.
        private Nodo(ArrayList numeros, int valor1, int valor2, int resultado, string signo, Nodo padre)
        {
            this.numeros = numeros;
            this.valor1 = valor1;
            this.valor2 = valor2;
            this.resultado = resultado;
            this.signo = signo;
            this.padre = padre;
            this.hijo = null;
            // Para saber cuantos nodos se han creado.
            Nodo.numeroNodos++;
            // Vamos guardando el número cercano más próximo al buscado.
            if (Math.Abs(buscado - resultado) < Math.Abs(buscado - aproximado))
            {
                // Creamos un camino alternativo duplicando los nodos.
                // Esto es necesario porque en backtracking los nodos que no sirven se eliminan y necesitamos
                // tener un camino hacia el resultado aproximado que perdure en toda la ejecución de la función.
                Nodo historico = this;
                Nodo copia = (Nodo)this.MemberwiseClone();
                while (historico.padre != null)
                {
                    copia.padre = (Nodo)historico.padre.MemberwiseClone();
                    copia.padre.hijo = copia;
                    historico = historico.padre;
                    copia = copia.padre;
                }
                cercano = copia;
                aproximado = resultado;
            }
 
        }
 
        // La función principal que busca el resultado combinando el conjunto de números del nodo con las
        // operaciones de suma, resta, multiplicación y división.
        public bool busca()
        {
            // Si el nodo actual contiene el número buscado ya no hacemos más búsquedas
            if (resultado == buscado)
            {
                return true;
            }
 
            // Vamos recorriendo cada elemento del conjunto de números operándolo con los demás.
            for (int indice1 = 0; indice1 < numeros.Count; indice1++)
            {
                for (int indice2 = indice1 + 1; indice2 < numeros.Count; indice2++)
                {
                    if (calculos(indice1, indice2, OPERACIONES.SUMA) == true)
                    {
                        return true;
                    }
                    if (calculos(indice1, indice2, OPERACIONES.RESTA) == true)
                    {
                        return true;
                    }
                    if (calculos(indice1, indice2, OPERACIONES.MULTIPLICACION) == true)
                    {
                        return true;
                    }
                    if (calculos(indice1, indice2, OPERACIONES.DIVISION) == true)
                    {
                        return true;
                    }
                }
            }
            // Si llegamos aquí es que todos los cálculos en esta rama del arbol han sido infructuosos.
            return false;
        }
 
        // Esta función crea un nuevo nodo después de operar los números. Le asigna un nuevo conjunto de números, 
        // el resultado de la operación, y los números involucrados.
        private bool calculos(int indice1, int indice2, OPERACIONES operacion)
        {
            int resultado = 0;
            string signo = "";
            int valor1 = (int)numeros[indice1];
            int valor2 = (int)numeros[indice2];
 
            // Hacemos que en la resta, división y multiplicación el primer operando sea mayor que el segundo
            if ((operacion == OPERACIONES.RESTA) || (operacion == OPERACIONES.DIVISION) || (operacion == OPERACIONES.MULTIPLICACION))
            {
                if (valor1 < valor2)
                {
                    int valor3 = valor1;
                    valor1 = valor2;
                    valor2 = valor3;
                }
            }
            // Calculamos la operación con los números, haciendo la poda del arbol si es necesario.
            switch (operacion)
            {
                case OPERACIONES.SUMA:
                    resultado = valor1 + valor2;
                    signo = "+";
                    break;
                case OPERACIONES.RESTA:
                    if ((valor1 - valor2) == 0) // Un número que da cero no sirve para seguir
                    {
                        return false;
                    }
                    resultado = valor1 - valor2;
                    signo = "-";
                    break;
                case OPERACIONES.MULTIPLICACION:
                    if (valor2 == 1) // Una multiplicación que por 1 da el mismo resultado no sirve
                    {
                        return false;
                    }
                    resultado = valor1 * valor2;
                    signo = "*";
                    break;
                case OPERACIONES.DIVISION:
                    if ((valor2 == 1) || ((valor1 % valor2) != 0)) // Un división que por 1 da el mismo resultado o que tiene decimales no sirve
                    {
                        return false;
                    }
                    resultado = valor1 / valor2;
                    signo = "/";
                    break;
            }
            // Generamos el nuevo conjunto de números sobre los que operar.
            ArrayList posibilidades = new ArrayList();
            posibilidades.Add(resultado);
            for (int indice = 0; indice < numeros.Count; indice++)
            {
                // No permitimos que se incluyan los números que ya se han operado.
                if ((indice != indice1) && (indice != indice2))
                {
                    posibilidades.Add(numeros[indice]);
                }
            }
            // Creamos el nuevo nodo.
            Nodo opcion = new Nodo(posibilidades, valor1, valor2, resultado, signo, this);
            // Hacemos la búsqueda recursiva. Si lo encontramos vamos generando el camino hacia el nodo con el
            // número exacto.
            if (opcion.busca() == true)
            {
                hijo = opcion;
                return true;
            }
            else
            {
                return false;
            }
        }
 
    }
}

También podéis descargaros el ejecutable del programa para poder hacer las pruebas.

Así por ejemplo este reto:

Se resuelve como:

Microchip va a sacar microcontroladores PIC de 32 bit con encapsulado DIP

Proyectos Sin comentarios

El hecho de que Microchip saque al mercado PICs de 32 bit con encapsulado DIP va a revolucionar el mundo de los aficionados a la electrónica. Un simple chip con 28 pines tan potente como el primer 386 de intel (salvando las arquitecturas Harvard y von Neumann) que podemos poner en nuestras protoboards. Puede correr hasta 80 Mhz., 512KB de Flash (donde se almacena el código), 128KB. de SRAM (donde se almacenan los datos) y la posibilidad de conectar con periféricos mediante DMA.

Se pueden pedir samples, pero pueden tardar 42 días en enviarlos.

Descansa en paz Dennis MacAlistair Ritchie

Informática 1 Comentario

Todo el mundo ha hablado de la reciente muerte de Steve Jobs. Sin embargo también recientemente ha fallecido una persona que ha contribuido enormemente al desarrollo de la informática: Dennis Ritchie. Este hombre fue el creador junto a Ken Thompson del sistema operativo Unix (en el cual está basado GNU/Linux de Richard Stallman y Linus Torvalds) pero su mayor aportación fue crear el lenguaje de programación C, quizá el más usado de la historia y del que derivan otros tantos como objective-c, java y c#. Hasta siempre Dennis.

int *born1941 = malloc(70);
int *die2011 = born1941;
free(die2011);
printf("bye world\n");

(Fuente: chw.net)

Mi charla de telemetría

Electrónica, Informática, Proyectos Sin comentarios

Ya han publicado el vídeo de la charla de telemetría que di en la OSHWCON 2011.

Toda la documentación de mi charla (presentación, código fuente, esquemáticos, etc.) lo podeis descargar aquí.

Agradecer a los organizadores su tiempo, esfuerzo y ganas por sacar adelante algo tan novedoso y pionero. También dignos de mención son los ponentes que de forma altruista hemos hecho realidad este fantástico evento. Por supuesto no nos olvidemos de los patrocinadores que han permitido que este evento tuviese un nivel alto y de calidad.

A todos, nos vemos en la OSHWCON 2012.

¿Dónde estoy?

Proyectos 1 Comentario

Hace tiempo que no escribo en el blog y esto es debido al nacimiento de mi hija. Pero tengo pendientes varios proyectos que iré publicando a lo largo del año. Ahora me he dado de alta en twitter como @sistemasorp donde escribiré también mis ideas, acciones, inquietudes, etc en 140 caracteres.

Open Source Hardware Con

Electrónica 1 Comentario

Los días 23,24 y 25 de Septiembre se va a celebrar en Madrid el OSHWCon. Un evento organizado por el colectivo Synusia donde se promociona el hardware libre, la afición a la electrónica, el DIY, etc.

La entrada es gratuita, pero hay que inscribirse. Habrá charlas, talleres, mesas redondas y proyectos personales. En mi caso he creido interesante dar una charla sobre telemetría.

Si os gusta la electrónica y la robótica no os podeis perder este evento único que hará las delicias de todos los aficionados a la electrónica, robótica y cacharreo en general.

Calculadora on-line de timers del PIC

Electrónica Sin comentarios

Hace tiempo hice una calculadora para mi uso interno la cual calculaba los valores que había que poner a un timer de un microcontrolador PIC (con su preescaler, su frecuencia, etc) para llegar a un retardo determinado, o viceversa, dado un valor del timer calcular qué retardo provoca. Es muy sencilla y está hecha integramente en html y javascript:

http://www.sistemasorp.es/blog/temporizadores_pic.html

« Artículos anteriores