The raw code for this Jupyter notebook is by default hidden for easier reading. The main focus of this particular page of the notebook is on the graphs and their interpretation. To toggle on/off the raw code, click below:

In [1]:

```
from IPython.paths import get_ipython_dir
from IPython.core.display import HTML
import os
HTML('''
<center><h3>
<a href="javascript:code_toggle()">Talk is cheap, show me the code.</a>
</center></h3>
<script>
var code_show=true; //true -> hide code at first
function code_toggle() {
$('div.prompt').hide(); // always hide prompt
if (code_show){
$('div.input').hide();
} else {
$('div.input').show();
}
code_show = !code_show
}
$( document ).ready(code_toggle);
</script>
''')
```

Out[1]:

In [2]:

```
# Setup notebook theme
from jupyterthemes import get_themes
from jupyterthemes.stylefx import set_nb_theme
set_nb_theme(get_themes()[1])
```

Out[2]:

Four people want to get to the other side of a river by crossing a very narrow tunnel that a maximum of two people may cross at a time. It is nighttime, so someone must carry the single flashlight during each crossing. One of them takes 1 minute to cross the tunnel, another takes 2 minutes, another takes 5 minutes, and the last takes 10 minutes to cross. Then, we name them persons 1, 2, 5, and 10, respectively. If two people cross the tunnel together, they must walk at the pace of the slower one. So, if persons 5 and 10 cross together, they take 10 minutes to get to the other side. (If person 5 crosses by himself, it takes 5 minutes.) How long does it take all four people to get to the other side? Of course, it depends on how they do it. From the initial state (1, 2, 5, and 10 on the same side with the flashlight) there are ten possible crossing actions: 1 crosses alone, 2 crosses alone, 5 crosses alone, 10 crosses alone, 1 and 2 cross, 1 and 5 cross, 1 and 10 cross, 2 and 5 cross, 2 and 10 cross, or 5 and 10 cross. (If two people cross, it doesn't matter which one holds the flashlight.)

Here is an example solution:

```
1 and 10 go across 10 minutes
1 goes back with light 1 minute
1 and 5 go across 5 minutes
1 goes back with light 1 minute
1 and 2 go across 2 minutes
Total 19 minutes
```

At first look the example solution above may appear to be optimal but it is not. A good question is whether any of the uninformed search algorithms can find a better solution. Running the algorithms on the same group of people in the order depth-first, breadth-first, then unifrom produces the following output.

In [3]:

```
from search import dfs, bfs, uniform
algorithms = [dfs, bfs, uniform]
people = [1, 2, 5, 10]
# Run each algorithm
for algorithm in algorithms:
print(algorithm(people))
```

In [4]:

```
people = [1, 2, 5, 10, 1]
print("Breadth first: ", bfs(people))
print("Uniform cost: ", uniform(people))
```

Each algorithm has different properties for execution time until a solution is found. This can be a major factor when selecting which algorithm to use.

Breadth-first search runs nicely until a group size of five people, then it sharply spikes on a group of six. After six people it runs too slow to be of any real use.

In [5]:

```
# Set up for graphing
import timeit
from random import seed, randint
seed(42)
# Get breadth-first search times
bfs_data = []
for i in range(6):
temp_list = []
for j in range(i):
temp_list.append(randint(1, 100))
bfs_data.append(temp_list)
bfs_times = []
for group in bfs_data:
start_time = timeit.default_timer()
bfs(group)
bfs_times.append(timeit.default_timer() - start_time)
```

In [6]:

```
# Graph
import plotly.plotly as py
import plotly.graph_objs as go
# Create traces
trace0 = go.Scatter(
x = [1, 2, 3, 4, 5, 6],
y = bfs_times,
mode = 'lines+markers',
name = 'Breadth-First',
hoverinfo='name',
line=dict(
shape='spline'
)
)
data = [trace0]
# Plot
data0 = [trace0]
layout = dict(
xaxis=dict(
title='People in Group'
),
yaxis=dict(
title='Time',
),
legend=dict(
y=0.5,
traceorder='reversed',
font=dict(
size=16
)
)
)
fig0 = dict(data=data0, layout=layout)
py.iplot(fig0, filename='breadth-first')
```

Out[6]:

Depth-first search on the other hand increases much more steadily in execution time for group size. While it can not find an optimal solution except by accident it can find a solution for a group size of about 60 in the same time it take breadth-first to find a solution for 6.

In [7]:

```
# Set up for graphing
seed(42)
# Get breadth-first search times
dfs_data = []
for i in range(60):
temp_list = []
for j in range(i):
temp_list.append(randint(1, 100))
dfs_data.append(temp_list)
dfs_times = []
for group in dfs_data:
start_time = timeit.default_timer()
dfs(group)
dfs_times.append(timeit.default_timer() - start_time)
```

In [8]:

```
# Graph
# Create traces
trace1 = go.Scatter(
x = list(range(60)),
y = dfs_times,
mode = 'lines+markers',
name = 'Depth-First',
hoverinfo='name',
line=dict(
shape='spline'
)
)
data1 = [trace1]
# Plot
data = [trace1]
layout = dict(
xaxis=dict(
title='People in Group'
),
yaxis=dict(
title='Time',
),
legend=dict(
y=0.5,
traceorder='reversed',
font=dict(
size=16
)
)
)
fig1 = dict(data=data1, layout=layout)
py.iplot(fig1, filename='depth-first')
```

Out[8]:

Uniform cost search runs only slightly slower than breadth-first search maxing out at a group size of five.

In [9]:

```
# Set up for graphing
seed(42)
# Get breadth-first search times
uniform_data = []
for i in range(6):
temp_list = []
for j in range(i):
temp_list.append(randint(1, 100))
uniform_data.append(temp_list)
uniform_times = []
for group in uniform_data:
start_time = timeit.default_timer()
uniform(group)
uniform_times.append(timeit.default_timer() - start_time)
```

In [10]:

```
# Graph
# Create traces
trace2 = go.Scatter(
x = list(range(6)),
y = uniform_times,
mode = 'lines+markers',
name = 'Uniform-Cost',
hoverinfo='name',
line=dict(
shape='spline'
)
)
data2 = [trace2]
# Plot
data = [trace2]
layout = dict(
xaxis=dict(
title='People in Group'
),
yaxis=dict(
title='Time',
),
legend=dict(
y=0.5,
traceorder='reversed',
font=dict(
size=16
)
)
)
fig2 = dict(data=data2, layout=layout)
py.iplot(fig2, filename='uniform-cost')
```

Out[10]:

It is obvious from the side-by-side comparison that depth-first search is many times faster than the others.

In [11]:

```
data = [trace0, trace1, trace2]
layout = dict(
xaxis=dict(
title='People in Group'
),
yaxis=dict(
title='Time',
),
legend=dict(
y=0.5,
traceorder='reversed',
font=dict(
size=16
)
)
)
fig3 = dict(data=data, layout=layout)
py.iplot(fig3, filename='uninformed-search-comparison')
```

Out[11]: