Bridge-Finding-Robots

Bridge-Finding Robots compares two algorithms for solving a cool thinking problem.

The Problem (credit: Gr. 12 CS class)

Problem: Let's say you were a robot trying to find a bridge at night. You can only see a tiny bit ahead of you, and you know that the bridge is either straight east or straight west of your current position.

How do you go about finding the bridge? Here are two ways.

Way 1: Constant growth in both directions

Using this method, or algorithm, you would go 1 step east, then 2 steps west, then 3 steps east, then 4 steps west etc until you have reached the bridge.

Way 2: Exponential growth in both directions

Using this algorithm, you would go 1 step east, then 2 steps west, then 4 steps east, then 8 steps west etc until you have reached the bridge.

Which way is better?

Bridge-Finding Robots provides a side by side comparison of the two algorithms. It demonstrates algorithm analysis visually. The top robot uses the Constant Growth algorithm while the bottom robot uses the Exponential Growth algorithm.

Features

The program enables you to set each robot's starting distance from the bridge, walking speed, and step size. You can also use the Sync feature to sync the robots' arrivals.

Demo

As you can see, in the first run, the top robot embarasses the bottom robot. In the second run, the Sync feature is activated, which raises the speed of the bottom robot to make up for its inefficient algorithm.