This week's El País math challenge (Spanish video) is once again about a graph. In this case, the graph is a cube (8 vertices, 12 edges), with vertices numbered as shown in the video.
An ant starts walking from vertex #1 and randomly changes direction at each vertex—it might even turn back along the same edge it came from. Vertices #7 and #8 are poisoned: if the ant enters either of them, it dies.
The challenge is to determine the probabilities of the ant:
- Dying or surviving.
- If it dies, which poisoned vertex (#7 or #8) it ends up in.
This program uses a previously defined Graph class that is listed in the Hamiltonian Path challenge to perform a Monte Carlo simulation of the problem and provides an empirical answer. However, the result alone is not a complete solution: you must also provide a theoretical proof to justify it. 😉
#!/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 that may contain a poison trap."""
def __init__(self, *args):
Vertex.__init__(self, *args)
self.poisoned = False
def __str__(self):
tmp = '*' if self.poisoned else ''
return f'<{tmp}{self.i}>'
class Cube(Graph):
"""A Graph subclass where each vertex (Point) may or may not be poisoned."""
def add(self, node, *node_list):
vertex = Point(node, *node_list)
self.vList[node] = vertex
def run(self, N):
"""Simulates an ant starting at vertex #1 and walking for N random steps.
Stops if the ant enters a poisoned vertex or completes N steps.
Returns the ant's final position.
"""
i = 0
pos = 1 # Initial ant position
while i < N:
i += 1
pos = choice(self.vList[pos].nodeList)
if self.vList[pos].poisoned:
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)
# Mark vertices 7 and 8 as poisoned
G.vList[7].poisoned = True
G.vList[8].poisoned = True
# Run statistical simulation
stats = [0, 0, 0] # Counters: [survived, died at #7, died at #8]
for _ in range(1000000): # Total number of experiments
pos = G.run(100) # Simulate 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 # Increment corresponding counter
total = sum(stats) # Total experiments (should match the loop count)
print(stats) # Absolute frequencies
print([100 * float(x) / total for x in stats]) # Relative frequencies (%)