24 junio 2007

LaTeX en los blogs

Hace unos días encontré un artículo en un blog sobre como insertar fórmulas matemáticas en páginas web: Fórmulas matemáticas con mimeTeX.

Existe un lenguaje basado en XML llamado MathML, creado por el W3C. MathML es muy bonito y tal y cual, pero practicamente ningún navegador puede visualizarlo.

Konqueror me muestra bien las fórmulas en esta página. Firefox me da un aviso de que me faltan fuentes matemáticas y hace un intento de mostrarlas pero no salen del todo bien.

La wikipedia tiene una característica que está muy bien: puedes escribir fórmulas directamente en LaTeX utilizando la etiqueta math. Al guardar el artículo utiliza LaTeX para generar las imágenes correspondientes al código que has escrito y al visualizar la página se ven las fórmulas como imágenes. Ejemplo: Artículo sobre las integrales.

Pues algo parecido a lo que hace la wikipedia podemos conseguir con mimeTex. Nos proporciona un cgi que podemos colocar en nuestro servidor para generarnos las imágenes sobre la marcha.

Como blogger no permite subir CGIs pues podemos usar el CGI de la página de los creadores de mimeTex.

Ejemplo:

<img src="http://www.forkosh.dreamhost.com/mimetex.cgi?c=\sqrt{a^2+b^2}" >

Como vemos, escribiendo el código LaTeX después del símbolo ? nos genera una imagen con el resultado de ese código.

Resultado:



<img src="http://www.forkosh.dreamhost.com/mimetex.cgi?\mathcal{ADIOS}" >

23 junio 2007

Solución: El juego de las 10 y 10 piedras

Solución al problema El juegos de las 10 y 10 piedras.

Antes que nada decir que el título del problema es una puta mierda, pero no se me ocurrió uno mejor. El problema está inspirado en el capítulo de introducción del libro An Introduction to Bioinformatics Algorithms (el único que he leido, por cierto). En el libro lo llaman 10+10 game.

La solución más sencilla para encontrar una estrategia ganadora en este tipo de juegos suele ser la programación dinámica. Empezamos desde el caso más simple y vamos avanzando hacia casos más complicados.

En el juego 10+10 no empezaríamos en 10+10 si no en 0+0. Si te toca a ti jugar y quedan 0+0 piedras es obvia que has perdido. Si quedan 1+1, 1+0 o 0+1 siempre puedes ganar, porque al otro no le quedarán piedras para quitar. Si hay 2+0 piedras (o 0+2) y te toca jugar, sólo puedes hacer un movimiento posible y le lleva al otro jugador a 1+0 (o 0+1) en el que siempre gana.

Por tanto, cada pareja se numero x+y se le puede asociar un valor "puede ganar" o "siempre pierde". Podemos utilizar una matriz de 2 dimensiones. G indica "puede ganar" y P "siempre pierde". Si te toca jugar, puedes ver en que casilla estás para saber si puedes ganar o no la partida.

0 1 2
0 P G P
1 G G X
2 P X X

Estos son los valores que hemos calculado previamente para los casos más básicos. Vamos a calcular la posicion 1+2 utilizando la tabla. Desde la casilla (1,2) podemos ir hacia arriba (1, 1), diagonal arriba-izquierda (0, 1) o hacia la izquierda (0, 2). En los 2 primeros casos dejamos al otro jugador en una posicion "puede ganar" por lo tanto nosotros perderíamos, pero en el tercer caso le dejamos en "siempre pierde", por tanto la casilla en la que estamos es una casilla ganadora si vamos hacia la izquierda. Por tanto marcamos (1,2) con una G. (2,1) es equivalente así que también podemos marcarlo.

0 1 2 3 4 5 6 7 8 9 10
0 P G P
1 G G G
2 P G
3
4
5
6
7
8
9
10

A apartir de aqui podemos rellenar la tabla de izquierda a derecha y de arriba a abajo. En una casilla, si las casilla de arriba, izquierda y la diagonal son G, entonces esa casilla es P. En caso contrario es G.

0 1 2 3 4 5 6 7 8 9 10
0 P G P G P G P G P G P
1 G G G G G G G G G G G
2 P G P G P G P G P G P
3 G G G G G G G G G G G
4 P G P G P G P G P G P
5 G G G G G G G G G G G
6 P G P G P G P G P G P
7 G G G G G G G G G G G
8 P G P G P G P G P G P
9 G G G G G G G G G G G
10 P G P G P G P G P G P

Esta es la tabla completa para 10+10 gracias al copypaste. Como vemos si el primer jugador empieza en la casilla (10, 10) que está marcada como P, el jugador 2 siempre podrá realizar algún movimiento que le lleve a la victoria.

Muchas veces es mejor resolver un problema para casos muy básicos y cuando ya se domine, a partir de estos resolver los de mayor dificultad. Para esto sirve la programación dinámica.

21 junio 2007

Factoriales

El factorial de N es el producto de todos los números enteros desde 1 hasta N. Se escribe con el símbolo !:

N! = 1x2x3x...x(N-1)xN

Esto lo sabe todo el mundo. Ahora un problemilla para pensar un poco:

Tenemos un procesador que puede trabajar con números binarios de X bits. En los ordenadores normales X es potencia de 2: 4, 8, 16, 32, 64... pero en este problema eso no influye.

¿Cuál es el factorial máximo que podemos representar en ese procesador? Recuerdo que con X bits se puede representar desde el 0 a 2^X -1.

Con 4 bits podemos representar hasta el 15, por tanto el máximo factorial representable es 3! (1*2*3 = 6).
Con 5 bits el máximo es 31 así que sólo nos cabe 4! (1*2*3*4 = 24)

¿Cuál es la mejor manera de calcula el factorial máximo que cabe en esos bits?

20 junio 2007

El juego de las 10 y 10 piedras

Hay un juego (bastante aburrido por cierto) que consiste en hacer 2 montones de piedras. Cada uno ha de tener el mismo número de piedras (en este caso 10).

Hay 2 jugadores, por turnos cada uno tiene que quitar una piedra de uno de los montones (el que quiera) o una piedra de cada montón.

Gana el jugador que quita la última piedra.

La pregunta es: si eres el segundo jugador, ¿existe alguna estrategia para ganar siempre?

Ejemplo de juego de con 3 y 3 piedras.

1 - El jugador 1 quita una piedra del montón A (quedan 2 y 3 piedras)
2 - El jugador 2 quita una piedra de cada (quedan 1 y 2)
3 - El jugador 1 quita una piedra de cada (quedan 0 y 1)
4 - El jugador 2 quita una piedra de B y gana

Si queda en un momento 1 y 1 piedras el jugador puedes coger las 2 y ganar.

Solución: El tesoro

Voy a explicar la solución al problema El tesoro que puse el otro día por aquí.

Para saber la distancia mínima entre 2 puntos se utiliza el algoritmo de Dijkstra, este algoritmo obtiene la distancia mínima desde un punto de un grafo a todos los demás puntos. Cuando todos los pasos tiene el mismo coste se le suele llamar símplemente búsqueda en anchura.

Utilizando este conocido algoritmo se puede resolver fácilmente este problema. Lo única que hay que hacer es:

1 - Recorrer todo el mapa buscando los puntos (I)nicio y (F)in y guardarse en un array todos los puntos con (O)ro.
2 - Ejecutar el algoritmo de Dijkstra desde el punto I, a cada casilla del mapa se le asignará un coste CosteI(x,y) que es la distancia en casillas desde I a ese punto.
3 - Ejecutar el algoritmo de Dijkstra desde el punto F, a cada casilla del mapa se le asignará un coste CosteF(x,y) que es la distancia en casillas desde F a ese punto.
4 - Recorrer el array de oros, en cada posición de oros sumamos el valor de CosteI y CosteF para esa posición. La posición que tenga un valor CosteI+CosteF menor es el Oro que debe recoger el pirata en su camino.

Croe que esta es la solución más rápida, ya que sólo ejecuta 2 veces Dijkstra. Si alguien conoce una solución mejor que la comente...

16 junio 2007

El tesoro

Eres un pirata y has de viajar por un mapa desde I (de inicio) hasta F (de fin). El mapa es una cuadrícula y moverse hacia el norte, sur, este y oeste cuesta 1. No se puede ir en diagonal y los símbolos # son paredes por las que no se puede pasar. En el mapa hay varios tesoros marcados con O (de oro).

Ejemplo de mapa:

###############
# #
F # # O #
# #O ###### #
# #### O I
# # ######
# #
###############


¿Cuál es el camino mínimo para ir de I a F recogiendo al menos un tesoro?
No hace falta programarlo, simplemente decir cómo se podría obtener el mejor camino.

Ánimo.

15 junio 2007

Solución: Lista enlazada

Esta es la solución al problema del otro día.

Si la lista tiene punteros al elemento anterior, hay varias soluciones, pero si sólo hay punteros a "siguiente" creo que sólo hay una posible y es esta:

Inicialmente los 2 punteros apuntan al primer y segundo elemento de la lista. Entonces dentro de un bucle infinito vamos moviendo un puntero de uno en uno y el otro de dos en dos mirando si apuntan al mismo elemento.

El puntero que va de 2 en 2 llegará en la mitad de tiempo al final (si existe).

Si hay un bucle se pondrá a dar vueltas dentro de él, en algún momento el puntero lento llegará al bucle y en una o dos vueltas coincidirán.

En código creo es algo así, no lo he probado:

pLento = raiz
pRapido = raiz.siguiente
while (1) {
if (pLento == pRapido) {
printf("Tiene un bucle");
return 0;
}

if (pRapido == NULL) {
printf("Es finita");
return 0;
}

if (pRapido.siguiente != NULL)
pRapido = pRapido.siguiente.siguiente;
else
pRapido = pRapido.siguiente;
pLento = pLento.siguiente;
}

13 junio 2007

La lista enlazada

Este problema lo comentó un profesor un día en clase. Dicen que se lo preguntaron a un aspirante a ser contratado por una gran empresa. Supongo que también será de algún libro de programación.

El enunciado es muy simple:

Tienes una lista enlazada. La lista puede ser:

  • Finita

  • Infinita

  • Tener un bucle




class lista {
public int valor;
public lista siguiente;
}


Utilizando sólo 2 punteros y nada más ¿cómo podríamos saber de qué tipo de lista se trata? Inicialmente los 2 punteros apuntan al inicio de la lista.

A mí cuando me lo propusieron me salió una solución bastante cutre, a ver si alguien encuentra la guay. ¡ánimo!

Solución: Los números binarios

El otro día propuse un problemilla: Los números binarios. No lo inventé yo, lo leí en algún libro que ahora no recuerdo.

Vamos a ver la solución con la siguiente lista de números

1 1 1
0 0 0
1 0 0
1 0 1
0 1 0
0 0 1
0 1 1

¿Que número de 3 dígitos binarios falta?

La solución es:

Tienes un vector con tantos enteros como dígitos tienen los números, inicialmente en todas las posiciones ponemos 0.

Vector: 0 0 0

Ahora vamos leyendo los números uno a uno y sumamos 1 en las posiciones de nuestro vector para las que haya un 1 en el número que hemos leído.

Al leer los primeros números

Número: 1 1 1
Vector: 1 1 1

Número: 0 0 0
Vector: 1 1 1

Número: 1 0 0
Vector: 2 1 1

Cuándo hemos acabado de leer todos los números obtenemos el siguiente vector:

Vector: 3 3 4

Y cómo sabemos que tiene que haber en total igual número 1 en todas las posiciones deducimos que el número que falta es:

Número: 1 1 0




Pablo ha dado con una solución bastante buena que serviría para todo tipo de números, da igual si son o no binarios. Sólo hay que tener cuidado con un detalle: si empezamos a sumar muchísimos números grandes al final no cabrán en un entero y se desbordará.

11 junio 2007

Safari para Windows

Safari para Windows

los números binarios

Me he acordado de este problema a mitad de examen de ingeniería de la programación y aquí lo explico...

Tienes una lista de números binarios desde 0000000000 a 1111111111 (números de 10 digitos).

Algo así:
0000000000
0000000001
0000000010
...
1111111101
1111111110
1111111111

Pero no están todos, falta un sólo número en la lista. ¿cómo calcularías cuál falta?

Los números no están ordenados, así que no vale leer uno tras otro y ver si están seguidos.

Además, sólo puedes recorrer la lista una vez, y sólo tienes unos pocos KB de memoria para el programa, ¿cómo lo harías?

Ejemplo simple con 2 bits:

00
01
11

¿Cuál falta? El 10.

04 junio 2007

La letra del DNI en Python

Función de 2 líneas que devuelve la letra del número de DNI que le pasas.


def letraDNI(dni):
return "TRWAGMYFPDXBNJZSQVHLCKE"[dni%23]


Un ejemplo en la consola de python:


>>> def letraDNI(dni):
... return "TRWAGMYFPDXBNJZSQVHLCKE"[dni%23]
...
>>> letra = letraDNI(12345678)
>>> letra
'Z'

02 junio 2007

Trigrafos en C

Hoy he descubierto de casualidad una característica muy extraña de C (y totalmente inútil hoy en día). Resulta que cuando apareció C, no todos los teclados y los sistemas operativos soportaban los caracteres como #[]{}. Para poder escribir programas en C en estos sistemas se inventaron los trigrafos, que son combinaciones de 3 caracteres que representan esos símbolos.

Esta es una lista de trigrafos extraída de la wikipedia.


Trigraph Equivalent
======== ==========
??= #
??/ \
??' ^
??( [
??) ]
??! |
??< {
??> }
??- ~


A continuación pongo un Hola mundo creado por mí utilizando trigrafos para codificar algunos caracteres:

??=include <stdio.h>
int main(int argc, char argv??(??))
??<
printf("Hola mundo!!??/n");
??>

GCC no compila directamente este programa, hemos de pasarle -trigraphs como argumento para que compile correctamente.

gcc -trigraphs holamundotrigraph.c

Complejidad de Kolmogorov

La complejidad de Kolmogorov de una cadena S es el tamaño de la menor cadena de texto que permite definir S.

Tenemos esta cadena de 64 digitos:

S = 01010101010101010101010101010101
01010101010101010101010101010101

Se puede definir así: "escribe 32 veces 01". Tiene 19 letrás y por tanto el valor de la complejidad es 19.
K(S) = 19

Sin embargo esta cadena ¿cómo podría definirse?

S2 = 11001000011000011101111011101100
11111010010000100101011110010110

La mejor manera de definir esta cadena es símplemente escribir la cadena entera, por tanto:
K(S2) = 64.

Ninguna cadena puede tener un K mayor a su tamaño.

Las cadenas que tienen una K igual a el tamaño de la cadena original se llaman complejas. Porque no se conocen formas eficientes de definirlas.

Por ejemplo, que cuesta menos: ¿escribir los 1000 primeros números enteros o un programa en Python que cuando lo ejecutes te imprima los 1000 primeros números enteros?.

Imagina que quieres mandar todo tu disco duro a un amigo por el messenger, ¿podrías escribir un programa corto en algún lenguaje de programación que al ejecutarlo diera como resultado todo el contenido de tu disco duro? Se podría decir que ese programa sería todo tu disco duro "comprimido".

Bienvenidos al maravilloso mundo de la Algorithmic complexity theory. Dicen que es muy útil para ciertas cosas... yo pienso que...