alt text

The Bridge Problem

In [1]:
#Import Youtube Video
from IPython.display import YouTubeVideo
YouTubeVideo('7yDmGnA8Hw0')
Out[1]:

Any solution to this problem must involve five steps, as in the animation below:

Step 1: Two people cross the bridge.

Step 2: One person goes back.

Step 3: Two people cross the bridge.

Step 4: One person goes back.

Step 5: Two people cross the bridge.

In [2]:
%%html
<iframe src="files/BridgeAnimation.mp4"></iframe>

We just discovered two possible "algorithms" to solve this problem:

Option 1: Always sending the fastest person

Option 2: Combining the two slowest people

In [2]:
def CalculateTime(A, B, C, D):
    t=[A,B,C,D]
    t.sort()
    A=t[0] 
    B=t[1] 
    C=t[2] 
    D=t[3]
    print('Sending Fastest Person solves the problem in', B+A+C+A+D, 'minutes')
    print('Combining Two Slowest solves the problem in', B+A+D+B+B, 'minutes')
    return

Let's compare our algorithms, and see which one is faster.

Let's experiment by trying different input values for A, B, C, and D.

In [3]:
from ipywidgets import interact
import ipywidgets as widgets
interact(CalculateTime,
A=widgets.IntSlider(min=1, max=20),
B=widgets.IntSlider(min=1, max=20),
C=widgets.IntSlider(min=1, max=20),
D=widgets.IntSlider(min=1, max=20))
Out[3]:
<function __main__.CalculateTime(A, B, C, D)>

Two Challenge Questions

For which values of (A,B,C,D) do the above solutions result in the same total time?

How many different ways can the four people cross the bridge? (Hint: the answer is more than 100!)

alt text