bridges.py

#!/usr/bin/env python
# Simulation of the 'Can you cross the river' riddler problem:
# https://fivethirtyeight.com/features/night-falls-a-storm-rolls-in-can-you-cross-the-river/
#
#      n   
#   /  |  \ 
#  a - b - c
#  |   |   |
#  d - e - f
#   \  |  / 
#      s  
#
#           0
#  (0,0)  (1,0)  (2,0)
#
#  (0,1)  (1,1)  (2,1)
#
#  (0,2)  (2,1)  (2,2)
#           2

from __future__ import division, print_function
import random
from collections import defaultdict

class SelfCountingClass(object):
    instance_count = 0
    def __init__(self):
        self.id = self.__class__.instance_count
        self.__class__.instance_count += 1

    def __hash__(self):
        return self.id

    def __eq__(self, other):
        return self.id == other.id

class Vertex(SelfCountingClass):
    def __init__(self):
        super(Vertex, self).__init__()
        self.bridges = set()

    def add_bridge(self, bridge):
        self.bridges.add(bridge)
        bridge.verties.add(self)

class Bridge(SelfCountingClass):
    def __init__(self):
        super(Bridge, self).__init__()
        self.vertices = set()

    def add_vertices(self, *vertices):
        for vertex in vertices:
            self.vertices.add(vertex)
            vertex.bridges.add(self)

    def destroy(self):
        for vertex in self.vertices:
            vertex.bridges.remove(self)

def build_bridges(width=3, height=2):
    """
    Construct a fully-connected bridge network with a south shore, and 
    """
    north_shore = Vertex()
    south_shore = Vertex()
    islands = {}
    bridges = []
    for x in range(0, width):
        for y in range(0, height):
            islands[(x,y)] = Vertex()
    for (x,y), island in islands.items():
        if (y == 0):
            north_shore_bridge = Bridge()
            north_shore_bridge.add_vertices(north_shore, island)
            bridges.append(north_shore_bridge)
        # only do forward neighbors (down-right), the backward (up-left) neighbors
        # are gotten by previous iterations.
        neighbors = [(x,y+1),(x+1,y)] 
        for x1, y1 in neighbors:
            if x1 == width:
                continue
            bridge = Bridge()
            bridge.add_vertices(island)
            if y1 == height:
                bridge.add_vertices(south_shore)
            else:
                bridge.add_vertices(islands[(x1,y1)])
            bridges.append(bridge)
    return north_shore, south_shore, bridges

def find_path(north_shore, south_shore):
    visited = set([north_shore])
    stack = [north_shore]
    while len(stack):
        node = stack.pop()
        children = set()
        for bridge in node.bridges:
            for vertex in bridge.vertices:
                if vertex == south_shore:
                    return True
                elif vertex not in visited:
                    visited.add(vertex)
                    stack.append(vertex)
    return False

def game(size=2, count=1000, catastrophe_threshold=0.5):
    successes = 0
    for i in range(count):
        north_shore, south_shore, bridges = build_bridges(size+1, size)
        for bridge in bridges:
            if random.random() > catastrophe_threshold:
                bridge.destroy()
        if find_path(north_shore, south_shore):
            successes += 1
    return successes / count

def plot(probs):
    try:
        import pylab
    except ImportError:
        print("Can't plot pretty pictures, pylab isn't installed")
        print(probs)
        return
    pylab.plot(probs)
    pylab.show()
    return

if __name__ == "__main__":
    probs = []
    for size in range(2, 102, 10):
        prob = game(size=size)
        print(size, prob)
        probs.append(prob)
    plot(probs)