Solution: The Drunkard’s Walk#

Functions definition#

Step simulator#

Write a function that works as a single step simulator.

  1. Function returns a string value between forward, left and right.

  2. Step is not “fair”:

    • 50% forward

    • 25% left

    • 25% right

  3. You can use any random function from the random module.

from random import choices

def step_simulator():
    step = choices(['forward','left','right'], weights=[50, 25, 25])
    return step[0]

Walk simulator#

Write another function (walk simulator) that calls the single step simulator several times to simulate an entire Sailor’s trajectory, which can end with the sailor falling into the water or reaching the ship

  1. Function returns a string value between water and ship.

  2. You should call the step_simulator() function.

Variables:

  • Bridge Length (x direction) = 70 m

  • Bridge Width (y direction) = 14 m

  • Sailor’s Step length: 70 cm

  • Sailor’s starting x position: 0

  • Sailor’s starting y position: Width/2

  • open y boundaries (the sailor may fall off the bridge)

Option 1: Readable solution#

In this solution we use an if/elif/else statement block to associate the step direction (forward, left, right) with a change in position.

def walk_simulator():
    step_length = 0.7 # m
    bridge_x = 70 # m
    bridge_y = 14 # m
    x = 0
    y = bridge_y / 2
    
    while True:
        step = step_simulator()

        if step == 'forward':
            x += step_length
        elif step == 'left':
            y += step_length
        else:
            y -= step_length

        if (y<0) or (y > bridge_y):
            return 'water'
        elif (x >= bridge_x):
            return 'ship'

Option 2: Using a Dictionary#

In this solution we use a Dictionary to associate the step direction (forward, left, right) with a change in position.

def walk_simulator():
    step_length = 0.7 # m
    bridge_x = 70 # m
    bridge_y = 14 # m
    
    x = 0
    y = bridge_y/2

    add_step = {
        'forward': [step_length,0],
        'left': [0,step_length],
        'right': [0,-step_length]
    }

    while True:
        step = step_simulator()
        x += add_step[step][0]
        y += add_step[step][1]

        if (y<0) or (y > bridge_y):
            return 'water'
        elif (x >= bridge_x):
            return 'ship'

Probability calculator#

Finally, write a probability function that calls the walk simulator several times to determine the approximate probability that the sailor will arrive on the ship.

  1. Function returns a float value between 0 and 1.

  2. Avoid using any knowledge of combinatorics to solve this problem. Instead, take advantage of the fact that the machine can simulate millions of steps/walks in a very short time.

Since this is based on random draws, the probability will be slightly different each time the code is run.

Option 1: Readable solution#

def get_probability():
    N = 10_000
    p = 0
    for _ in range(N):
        walk = walk_simulator()
        if walk == 'ship':
            p += 1

    return(p/N)

Option 2: Using List Comprehension, if and sum()#

def get_probability():
    N = 10_000
    walk = [1 for _ in range(N) if walk_simulator()=='ship']  # list of ones
    p = sum(walk)

    return(p/N)

Option 3: Using List Comprehension and count()#

def get_probability():
    N = 10_000
    walk = [walk_simulator() for _ in range(N)]  # list of "ship" and "water"
    p = walk.count('ship')

    return(p/N)

Testing#

Check if your function returns the expected value using the cell below.

import unittest

class UnitTests(unittest.TestCase):

    def setUp(self):
        self.N = 1000
        self.step = step_simulator()
        self.steps = [step_simulator() for _ in range(self.N)]

        self.walk = walk_simulator()
        self.walks = [walk_simulator() for _ in range(100)]


    def test_step_type(self):
        self.assertTrue(isinstance(self.step, str), 'The function should return a string')
    def test_step_value(self):
        self.assertTrue(sorted(set(self.steps)) == ['forward','left','right'], 'The function should return `forward`,`left` or `right`.')
    def test_step_forward(self):
        counts = self.steps.count('forward')/self.N
        self.assertAlmostEqual(counts, 0.5, places=1, msg=f'The drunk should have 0.50 chance to step forward.')
    def test_step_left(self):
        counts = self.steps.count('left')/self.N
        self.assertAlmostEqual(counts, 0.25, places=1, msg=f'The drunk should have 0.25 chance to step left.')
    def test_step_right(self):
        counts = self.steps.count('right')/self.N
        self.assertAlmostEqual(counts, 0.25, places=1, msg=f'The drunk should have 0.25 chance to step right.')

    def test_walk_type(self):
        self.assertTrue(isinstance(self.walk, str), 'The function should return a string')
    def test_walk_value(self):
        self.assertTrue(sorted(set(self.walks)) == ['ship', 'water'], 'The function should return `ship` or `water`.')

    def test_probability_ship(self):
        self.assertAlmostEqual(get_probability(), 0.4, places=1, msg='The function should return around 0.4 of success.')          


unittest.main(argv=[''], verbosity=2,exit=False)

test_probability_ship (__main__.UnitTests) ... 

ok
test_step_forward (__main__.UnitTests) ... 

ok
test_step_left (__main__.UnitTests) ... 

ok
test_step_right (__main__.UnitTests) ... 

ok
test_step_type (__main__.UnitTests) ... 

ok
test_step_value (__main__.UnitTests) ... 

ok
test_walk_type (__main__.UnitTests) ... 

ok
test_walk_value (__main__.UnitTests) ... 

ok

----------------------------------------------------------------------
Ran 8 tests in 3.932s

OK

<unittest.main.TestProgram at 0x7f42b0a61390>