This week's El País' math challenge (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 ;-)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# vim:ts=4:et:sw=4:
from random import choice
from grafo import Graph, Vertex
class Point(Vertex):
'''A vertex which can have a poison trap
'''
def __init__(self, *args):
Vertex.__init__(self, *args)
self.poisoned = False
def __str__(self):
tmp = '*' if self.poisoned else ''
return '< ' + tmp + str(self.i) + '>'
class Cube(Graph):
''' A Graph derived class in which each vertex (Point)
may contain a poison trap or not
'''
def add(self, node, *nodelist):
vertex = Point(node, *nodelist)
self.vList[node] = vertex
def run(self, N):
""" Puts an ant on vertex #1 and let it run for N
random steps. Stops when the ant enters a poisoned
vertex or it has run N steps. Returns ant's last position.
"""
i = 0
pos = 1 # Initial ant position
while i < N:
i += 1
pos = choice(self.vList[pos].nodeList)
if self.vList[pos].venenoso:
break
return pos
if __name__ == '__main__':
G = Cube()
G.add(1, 2, 4, 5)
G.add(2, 1, 3, 6)
G.add(3, 2, 4, 7)
G.add(4, 1, 3, 8)
G.add(5, 1, 6, 8)
G.add(6, 2, 5, 7)
G.add(7, 3, 6, 8)
G.add(8, 4, 5, 7)
G.vList[7].poisoned = True
G.vList[8].poisoned = True
# Carry out simple statistics
stats = [0, 0, 0] # Counters
for i in xrange(1000000): # Total number of experiments (runs)
pos = G.run(100) # make the ant to run 100 steps
if pos > 6: # Map 0..6 => 0, 7 => 1, 8 => 2
pos -= 6 # 7 = 1, 8 = 2
else:
pos = 0
stats[pos] += 1 # Increase corresponding counter
tot = sum(stats) # Total #number of experiments (must be the same number as above)
print stats # Absolute Frequencies
print [100 * float(x) / tot for x in stats] # Relative frequencies (percentage)