2011
03.26

This week’s math challenge of El País (Spanish video) is again about a graph. In this case, the graph is a cube (8 vertex, 12 edges) numbered as shown in the video.

An ant starts walking from vertex #1 and changes it direction at random on each vertex (might even turn back from the same edge it came from). Vertex #7 and #8 are poisoned. If the ant happens to walk into one of them it will die. The challenge consist in find out the probabilities of the ant dying or not and in which vertex (#7 or #8) when it does.

This program uses the previous one (which already defines a Graph class) to make a simple statistical simulation of the problem and give you an answer of what to expect. Obviously, the result by itself is not the entire solution: you also have to give a theoretical demonstration of such result 😉

Share
  1. Hola,

    La verdad es que vuestra discusion me ha parecido muy interesante. No conozco Python ni Lisp pero me han llamado la atención, sobre todo Python. Me parece muy sencillo y estructurado. He instalado Python 3.2 y Geany en WindowsXP y estoy leyendo manuales por internet. No creo que sea muy dificil aprender, por lo menos lo básico para empezar a trastear.
    Sin embargo cuando intento ejecutar el primer código que has puesto, me aparece un mensaje tipo ‘module grafo not found’. He buscado como instalar modulos adicionales en Python pero no
    doy con la tecla. Tampoco encuentra el modulo ‘grafo’. ¿Me podrías echar un cable? Gracias

    Like or Dislike: Thumb up 0 Thumb down 0

    • Perdon, quería decir “Tampoco encuentra el modulo ‘Numeric’…”

      Like or Dislike: Thumb up 0 Thumb down 0

    • Lo primero de todo, gracias, Juan Carlos y me alegro de que te embarques en python.
      El primer programa es el una solución que aporté yo, pero necesitas el script grafo.py que se encuentra en el artículo de la solución anterior. Cópialo y guárdalo como grafo.py en el mismo directorio que el otro, y dime si te funciona.

      Al solución aportada por al es una aproximación distinta y necesita un módulo llamado Numeric para trabajar matrices en python. Si estás en debian o en ubuntu el paquete del módulo de llama python-numeric o algo así. Dime si lo puedes instalar.

      Like or Dislike: Thumb up 0 Thumb down 0

  2. Resolución a lo bestia en lisp, ejecutando (res n) con n de unas decenas de millones sale con bastante precisión en pocos segundos

    Like or Dislike: Thumb up 0 Thumb down 0

    • 😮 Woow! Jo, gracias por compartirlo!! Me encanta. En qué intérprete lo ejecutas??

      Like or Dislike: Thumb up 0 Thumb down 0

      • Con el SBCL va bastante bien, se cepilla medio millón de hormigas por segundo en mi pobre Macbook pelao del 2008 :mrgreen:

        Like or Dislike: Thumb up 0 Thumb down 0

        • Hola,

          Perdona pero estoy intentando compilar con SBCl 1.0.37 y me devuelve error ‘fun oneof’ desconocida…

          saludos
          JC

          Like or Dislike: Thumb up 0 Thumb down 0

          • El problema está en la función walk, los paréntesis detrás de los 8 están duplicados. Debe ser que entre el parseo de smileys y el coloreador se han liado.

            Like or Dislike: Thumb up 0 Thumb down 0

          • Lo he corregido. Tal como ha dicho Catalan, es un fallo de los smileys, ya que el 8 seguido de paréntesis forma esto: 8)

            Like or Dislike: Thumb up 0 Thumb down 0

          • Hola,

            No creo que sea eso porque de ese
            detalle ya me habia dado cuenta y puse
            los parentesis bien.

            Sigue dando el mismo error con la
            funcion ‘oneof’…

            Gracias por al ayuda.
            JC

            Like or Dislike: Thumb up 0 Thumb down 0

  3. Gracias por el post y los comentarios.
    Me llevo un buen rato resolver el problema asi que pense en verificarlo con una simulacion
    y que casualidad que encontre este post usando mi codigo preferido! Y luego doble alegria
    al ver que la simulacion confirma el resultado analitico!
    Ah, por cierto, que diferencia de nivel comparando con la semana pasada!

    Like or Dislike: Thumb up 0 Thumb down 0

    • Gracias! Esa era la idea. Este parece mucho más complejo que el anterior (al menos para mí), pero fíjate que suelen buscar “soluciones ingeniosas” que requieran poco conocimiento matemático. A lo mejor hay alguna idea sencilla para dar con la solución.
      Lo sabremos mañana!

      Like or Dislike: Thumb up 0 Thumb down 0

  4. Para calcular las probabilidades de estar en un vértice dado en O(log t) se puede hacer como he esbozado antes (con la matriz o con divide and conquer, aunque son lo mismo en realidad), es eso lo que decía. El código está abajo (se puede interpretar de las dos maneras); como ejemplo lo he puesto con un hipercubo de dimensión 5 y un millón de pasos, aunque claro está que es más útil con otros grafos donde la respuesta no converja tan rápidamente.

    No hace falta codificar la fórmula, el mismo algoritmo vale para cualquier grafo en O(V^3 * log t) (creo que puse algo como V^2 por error en mi anterior mensaje). Calcularlas paso a paso como en la solución que puse es O(E * t), donde E es el número de aristas del grafo (supongamos que es conexo), que para grafos densos (aunque no es el caso en el hipercubo) es O(V^2 * t). La solución de simular es O(V + t) por experimento porque sólo vas pillando una arista cada vez. Cuántos experimentos haya que hacer para obtener buenas aproximaciones ya depende del grafo en concreto, pero si mal no recuerdo hay grafos que requieren V^3 movimientos ya sólo para llegar a visitar algunos de los vértices desde uno dado de esta manera (esto es el hitting time de los random walks), así que si queremos tener probabilidades de llegar a cada uno de los vértices en t pasos habrá que hacer al menos V^3 experimentos para estos grafos, y seguramente más para tener una precisión aceptable.

    Like or Dislike: Thumb up 0 Thumb down 0

    • Me parece increíble!!! 😯 Sin duda este es el mejor programa. Es más, con los comentarios que has puesto creo que se entiende perfectamente. Muchas gracias por compartir!!!

      Like or Dislike: Thumb up 0 Thumb down 0

  5. Una última cosa, el código que puse calcula las probabilidades al cabo de t pasos en un hipercubo de n dimensiones en O(t · n · 2^n); en nuestro caso es O(t) al ser n constante (y pequeño). Se puede mejorar la dependencia con t y calcularlas en O(log(t) · 2^(2n)), aunque esto sí que haría la solución más complicada (pero se obtienen mejores aproximaciones mucho más rápidamente). La cuestión es que la transformación que manda las probabilidades en el tiempo t – 1 a las probabilidades en el tiempo t es lineal (sólo hay sumas y divisiones), así que representando las probabilidades por un vector v_t de 2^n elementos, podemos escribir una matriz M tal que v_t = M · v_{t-1}. Así que v_t es M^t · v_0, M^t se puede calcular con O(log t) multiplicaciones de matrices elevando al cuadrado cada vez p.ej. M^8=((M^2)^2)^2). Seguramente las multiplicaciones se pueden acelerar porque la matriz M tiene sólo n · 2^n entradas no nulas (el doble del número de aristas del grafo), pero eso no lo he pensado de momento.

    Otra manera de ver una solución básicamente equivalente sería pensar en un array A_t[v][w] que da la probabilidad de acabar en w partiendo de v al cabo de t pasos, y notar que el array A_t[][] se puede calcular a partir de A_{t/2}[][] (A_t[v][w] = suma de z de A_{t/2}[v][z] * A_{t/2}[z][w]).
    Aquí z representaría el vértice intermedio, a mitad de camino entre v y w. Esto da lugar a una solución de divide and conquer (por supuesto hay que tener en cuenta qué pasa si t es impar y tal).

    Like or Dislike: Thumb up 0 Thumb down 0

    • La solución Divide & Conquer me resulta más familiar. 8) Si tuviera tiempo le dedicaría un rato, ya que es lo primero que se me ocurrió (aunque tampoco sería muy ‘didáctica’). No entiendo lo otro que comentas de la transformación ❗ pero bueno, lo pensaré.

      Ambas soluciones que hemos puesto tienen complejidad polinómica O(T) (en mi caso, la hormiga da 100 pasos independientemente de la dimensión del grafo). Sería interesante alcanzar Log T, pero lo veo difícil como no sea usando alguna fórmula directa (e.g. la solución del problema).

      Like or Dislike: Thumb up 0 Thumb down 0

  6. Gracias por cambiar mi mensaje para que se vea el código con lo del Syntex Higlighter, ¿cómo se hace eso?

    Sí, una iteración es el paso de una hormiga. f[t][v] es la probabilidad de que la hormiga esté en el vértice v al cabo de exactamente t pasos, donde la representación binaria de v da las coordenadas del punto en el cubo (e.g. 0 = 000 es el punto (0, 0, 0), 5 = 110 es el punto (1, 1, 0), etc.). Cuando t = 0, está con probabilidad 1 en el origen (f[0][0] = 1). Moverse por el cubo equivale a cambiar una de las 3 coordenadas posibles, i.e. hacer un xor con 001, 010 o 100 (en binario). La probabilidad de estar en w en el tiempo t es la suma, para sus vecinos v, de un tercio de la probabilidad de estar en v en el tiempo t – 1. Esto se calcula en el último bucle. Las líneas que copian f[t – 1][6] y f[t – 1][7] están porque la hormiga se queda quieta en esos vértices.

    En cuanto a lo de la legibilidad no estoy de acuerdo con lo que dices, pues creo que mi código es muy legible (y no hay nada “ofuscado”). Sinceramente creo que se entiende más rápidamente que el otro y con igual facilidad, para alguien que sepa programación dinámica y lo que significan las operaciones con bits <<, ^. (Eso sí, a quien no lo sepa eso le puede parecer misterioso). Lo único que mejoraría la legibilidad sería cambiar el nombre del array f a prob o algo así, y poner algún comentario, pero el código se explica por sí mismo. Cambiar el grafo no cambiaría mucho el código, sólo ligeramente el bucle más interno. Y es mucho más cómodo moverse por el grafo de un hipercubo de n dimensiones considerando los vértices como números de n bits que escribiendo explícitamente la matriz de adyacencia como en el caso original. Por otra parte se calculan correctamente las probabilidades al cabo de t pasos, no se hace una simulación. Con un hipercubo de un número mayor dimensiones funcionaría todo igual, pero la simulación necesitaría mucho más tiempo para lograr una precisión decente. Cierto que lo que no se calcula exactamente tampoco son las probabilidades de acabar en esos vértices alguna vez, en vez de al cabo de t pasos. También se puede hacer, pero poner eso sería básicamente poner la solución al problema 😉

    Like or Dislike: Thumb up 0 Thumb down 0

    • No queria decir que lo hubieras ofuscado adrede, sino que la linea
      f[t][v ^ (1 << i)] += f[t - 1][v] / 3

      me parece compleja de entender (otra cosa es que a tí te resulte sencilla :)) porque usas aritmética binaria para generar no sólo los vértices, sino los adyacentes a éste, y eso implica que tanto el grafo como la numeración de los vértices requieren una disposición determinada. Es más, la solución es correcta pero incluso en tu caso, la numeración de vértices que empleaste es distinta a la expuesta en el vídeo.

      Si el grafo fuera el mismo, pero eliminando la arista (1, 2) y/o añadiendo otra en (2, 4), no veo cómo modificar tu programa brevemente para que funcionara (en el mío la modificación es evidente). Creo que tu rutina si es generalizable a hipercubos. Aclaro que no estoy criticando tu solución, solo haciendo una observación que es inherente a todas las optimaciones: son soluciones específicas (y es lógico que sean así).

      Por último quisiera aclarar que conozco programación dinámica y aritmética binaria (aunque no te lo parezca :-D) y no creo que sea éso lo (único) que hace misterioso el programa que has puesto, sino la implementación de la solución en sí (por ej. pasar del grafo a una programación dinámica de grafo en un vector). Estoy por hacer una encuesta, a ver quiénes entienden mejor una solución u otra, dando sólo la explicación del vídeo y ambas soluciones. Sólo quizá si lo hubiera hecho en C habría pensado en una implementación similar. De mi solución, la parte que no me gusta es la del if que calcula la posición en el vector acumulador stats, aunque se puede generalizar fácilmente y quitar dicho if.

      La legibilidad de la mía se debe, siempre en mi opinión, a que es una implementación casi literal: “usar un objeto Grafo, añadirle objetos Vértice, señalar cuáles tienen insecticida y decirle a la hormiga que lo recorra” (de hecho tiene muchos comentarios). Digamos que sólo me faltó representarlo gráficamente; ya que de resto casi está simulando lo que pasa.

      También puedes poner directamente la fórmula de probabilidad (yo creo que podría hacerse resolviendo el límite de una serie, es más tu solución si da una pista valiosa y va muy encaminada a eso!) y tendrías una solución en O(1).

      Cuando termine una cosa que estoy trabajando, la pondré en el blog, y me gustaría que me dieras tu opinión. ❗

      Like or Dislike: Thumb up 0 Thumb down 0

  7. Se me olvidó poner los tags:

    [code lang=”python”]
    from Numeric import *

    if __name__ == ‘__main__’:
    num_iter = 100
    f = zeros([num_iter, 8], Float)
    f[0][0] = 1
    for t in range(1, num_iter):
    f[t][7] = f[t – 1][7]
    f[t][6] = f[t – 1][6]
    for v in range(0, 6):
    for i in range(0, 3):
    f[t][v ^ (1 << i)] += f[t - 1][v] / 3 print (f[num_iter - 1][7], f[num_iter - 1][6]) [/code]

    Like or Dislike: Thumb up 0 Thumb down 0

  8. Hombre, si lo que querías era calcular las probabilidades al cabo de cierto número de pasos, bastaba con esto (para calcularlas exactamente, sin simular):

    Like or Dislike: Thumb up 0 Thumb down 0

    • Bueno, no sé si “podría”, pero en cualquier caso, hace tiempo que dejé de programar así ❗ De hecho lo que me gusta de python es la legibilidad del código (Incluso me sugirieron que hiciera aún más legible el anterior). Estoy seguro que lo que puse es muy fácil de comprender incluso por gente que desconozca python.

      Tu programa da el resultado esperado, pero sin embargo no entiendo bien como funciona. 😳

      Esto es lo que he sacado en conclusión (ya que no pusiste comentarios ni nombres significativos). Tu aproximación es distinta (no conozco Numeric, pero entiendo que creas una matriz de 100 filas por 8 columnas rellenas de 0).

      * Utilizas una fila por iteración (no sé si una iteración es un experimento o un paso de la hormiga, pero me parece que es por paso de hormiga).

      * Copias siempre las columnas 6 y 7 que imagino que son las que representan los vértices con insecticida -7 y 8- en cada iteración, para ir acumulando el resultado.

      * Supongo igualmente que 0..5 es la numeración de los vértices “seguros” para la hormiga.

      * La línea que me parece más ofuscada es la de la suma, ya que la expresión v^(1<<i) es un XOR entre v = [0..5] y [1, 2, 4], que da una matriz de valores {(1, 2, 3), (0, 3, 5), etc…} Esa expresión no da una numeración de vértices equivalente a la que pintan en la pizarra 😉 aunque para este problema el grafo al final si lo sea. En cualquier caso, es una propiedad interesante! 💡

      * Finalmente en cada iteración sumas 1/3 del contenido de los vértices adyacentes al vértice dado en la iteración anterior.

      La única duda que me asalta es que en tu caso la hormiga que haya pasado por los vértices envenenados en la iteración anterior no contribuyen en la siguiente de alguna manera? Es decir, las columnas 6 y 7 no deberían contribuir a las sumas de sus adyacentes en cada iteración, ya que se supone que la hormiga murió al pasar por ellos. ❓

      Sólo una pega: si la topología del grafo cambiara igual tendrías que reescribir el código por completo, y en mi caso tan sólo añadir los vértices necesarios en la inicialización.

      En cualquier caso, me parece muy optimizada. Gracias por compartirlo!
      😉 (para ver el comentario antes de enviar hay un botón de vista previa, por si quieres poner más código).

      Like or Dislike: Thumb up 0 Thumb down 0

      • Al poco de enviar el comentario anterior se depejó mi duda, ya que el bucle for con v es sólo para los vértices 0 .. 5 🙄

        En cualquier caso, de nuevo muchas gracias por tu solución! He aprendido mucho de ella.

        Like or Dislike: Thumb up 0 Thumb down 0