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-, dijo Teseo 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 nos llega la falsa historia que Teseo mató al Minotauro, cuando en realidad ambos cooperaron para salir del laberinto.