# Ants

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
'''
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.vList.poisoned = True
G.vList.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)
```