[LUG.ro Mix] Teseo y el Minotaruro Geeks

[Horacio Castellini]

Teseo y el Minotaruro Geeks
Estaba Teseo murmurando en el laberinto
construido por Dédalo a la caza del Minotauro
- La próxima vez que vea a Ariadna, le
diré que debería haberme dado un ovillo más largo. Llevo cinco
encrucijadas y el ovillo se ha terminado.-
Enojado arroja el ovillo al suelo;
luego se puso a debatir entre seguir adelante sin cuerda o regresar y
enfrentar la burla del público que lo esperaban afuera. Pasado un
tiempo de duda tomó valor, desenfundó su espada y avanzó con todos
sus sentidos alertas a espera de enfrentar al terrible Minotauro.
Pasado un tiempo percibe un olor a
excremento de vaca, avanzó cada vez más por el laberinto,
lamentando - ¡Todos los túneles parecen iguales-
De repente escucha una voz que retumba
en el túnel -¿Perdido?, -Si- le responde y al darse vuelta ve una
sombra que no distingue bien que le contesta -Yo también estoy
atrapado aquí desde hace siglos- Teseo le pregunta -¿Cazando
también al Minotauro, no?- a que responde -Epa hombre, yo soy el
Minotauro, aparta esa espada que si hubiera querido comerte ya lo
habría hecho hace tiempo- De pronto una luz de fuente desconocida
invade el laberinto y Teseo pudo ver a su compañero de infortunio,
-¿Pero que te ha sucedido?, pregunta Teseo a lo que el Minotauro
responde -Y mi madre Pasífae le gustaba la zoofilia y tuvo
relaciones con el toro de Creta, de esa unión salí yo, por suerte
cuando Dédalo construyó el laberinto me dejó una biblioteca mas
completa que la de Alejandría; así que no soy ninguna bestia
salvaje- y replicó -¿sos bueno resolviendo laberintos?-, -No soy
bueno entrando en ellos- dijo Teseo, -Supongo que el truco es
invertir el proceso, pero la inepta de tu hermana me dio un hilo
demasiado corto y ahora no sé donde está la punta del ovillo-, -Si
la verdad que ni para aperitivo sirven estas mujeres cretenses-
replicó en Minotauro, a lo que acotó -He ensayado un montó de
algoritmos pero al no tener un mapa del laberinto ninguno me sirvió,
¿Tienes un mapa supongo?- -Amigo Minotauro, si tuviera un mapa no
hubiera necesitado un ovillo, ahora bien se podría usar el truco de
pezuña a la izquierda- a lo que el Minotaturo refuta - Macho, ese
truco funciona si lo utilizas desde la entrada al laberinto y que yo
sepa tus dos manos siempre enfundaron la espada- A lo que luego de
rascarse el cuerno con su pezuña izquierda reflexiona -Lo importante
para resolver un laberinto es conocer sus encrucijadas y no la
longitud de los túneles-; -Me temo que no estoy de acuerdo- dijo
Teseo mientras se rascaba un callo. -Lo que quiero decir es que
podemos representar los elementos topológicos escenciales mediante
un grafo conexo; donde los vértices corresponden a las encrucijadas
y las aristas a los túneles. Entonces el problema de resolver un
laberinto se reduce a hallar un circuito de Ëuler- responde el
Minotauro. -Creo que cualquiera sabe eso- dijo Teseo, -Sí, pero hay
un teorema que dice cuando es posible- dijo el Minotauro a lo que
Teseo responde -Adodoro los teoremas, Pitágoras me contó uno
realmente sorprendente sobre hipopótamos cuadrados-, -No seas bruto
Teseo, al que me refiero es un teorema sobre grafos, si un grafo
conexo tiene más de dos vértices de grado impar no es posible
hallar un circuito de Ëuler. Y el muy hijo de prostituta de Dédalo
ya lo pensó para que no me escape y construyó varias encrucijadas
con 5 túneles-. -La única pista que me dejó es un algoritmo dado
en un lenguaje dado por un tal pitón, nunca imaginé que un ofidio
fuera tan inteligente-. -Brillante- replicó Teseo, -muéstrame el
algoritmo que te ha dejado, yo cuando vivía en Trecén era
programador en lenguaje python!, gracias a eso me pude pagar el viaje
a Creta-. Entonces el Minotaturo saca un papiro medio amarillento
donde se puede leer:

import numpy as np
from numpy.random import random_integers as rnd
import matplotlib.pyplot as plt def maze(width=81, height=51, complexity=.75, density =.75): # Only odd shapes shape = ((height//2)*2+1, (width//2)*2+1) # Adjust complexity and density relative to maze size complexity = int(complexity*(5*(shape[0]+shape[1]))) density    = int(density*(shape[0]//2*shape[1]//2)) # Build actual maze Z = np.zeros(shape, dtype=bool) # Fill borders Z[0,:] = Z[-1,:] = 1 Z[:,0] = Z[:,-1] = 1 # Make isles for i in range(density): x, y = rnd(0,shape[1]//2)*2, rnd(0,shape[0]//2)*2 Z[y,x] = 1 for j in range(complexity): neighbours = [] if x > 1:           neighbours.append( (y,x-2) ) if x < shape[1]-2:  neighbours.append( (y,x+2) ) if y > 1:           neighbours.append( (y-2,x) ) if y < shape[0]-2:  neighbours.append( (y+2,x) ) if len(neighbours): y_,x_ = neighbours[rnd(0,len(neighbours)-1)] if Z[y_,x_] == 0: Z[y_,x_] = 1 Z[y_+(y-y_)//2, x_+(x-x_)//2] = 1 x, y = x_, y_ return Z plt.figure(figsize=(10,5))
plt.imshow(maze(80,40),cmap=plt.cm.binary,interpolation='nearest')
plt.xticks([]),plt.yticks([])
plt.show()
-Estamos salvados!!- respondió Teseo a lo que continuó -para
resolver este laberinto debemos usar una búsqueda en profundidad!-
Pero el Minotauro no estaba tan entusiasta y le replica -Todo muy
lindo Teseo, pero para aplicar una búsqueda en profundidad es
necesario marcar cada encrucijada para saber que estuviste ahí y no
repetirla, ¿por casualidad mi hermana no te dio una tiza?-
Teseo luego de revisar su mochila se da
cuenta que Ariadna le había sacado la tizza, y se empezó a dar
cuenta que las intenciones de esta chica era que él nunca saliera
del laberinto. Pero se dio cuenta que con la espada podía rayar cada
encrucijada. Pero antes de emprender tamaña empresa para que ambos
salieran del laberinto el Minotauro le cuestiona -No se como es la
complejidad computaciónal de dicho algoritmo, por ahí podríamos
pasar una eternidad tratando de salir del túnel- -Eso sería si
fuera un problema NP-completo pero nadie lo pudo demostrar. Además
como el laberinto tiene al menos una estrada que es la salida seguro
que la vamos a encontrar- Trascurrido 15 días de intentos fallidos
ambos, Teseo y el Minotaturo pudieron salir del laberinto. Como
trascurrió tanto tiempo no había nadie esperando, pero a Teseo le
aquejaba una duda -Hermano Minotauro, debo matarte sino mi reputación
se irá a la zanja-, -Mira hermano Teseo, nadie sabe como soy en
realidad, podemos matar a aquel toro, lo decapitamos nos hacemos un
asadodito como despedida, y vos vas a Creta con la cabeza del toro le
dices a los Cretences que es mi cabeza, yo me voy a pasar un tiempo a
los burdeles que seguro debe andar mi madre por ahí. -Brillante-
repondió Teseo, -Hagámoslo- dijo el Minotauro.
Así es que hoy no llega la falsa
historia que Teseo mató al Minotauro, cuando en realidad ambos
cooperaron para salir del laberinto.