PA3: FoneDrone

A clear solution to PA3

An elegant solution to PA3

The base case is when there is no direction to search in. Then, the only thing the Drone has to do is check for the phone and return. Nothing could be easier than that. So, letting an X denote a space where the Drone has already been, the following is a base case:

 | X |
—     —
X  *  X
—     —
 | X |

and the following is not:

 |   |
—     —
   *   
—     —
 |   |

Given this definition of the base case, to refine difficult cases you need to eliminate directions to search in, recurse, and move in the opposite direction. So what the refinement process needs to do is:

• Move forward, search, and move backward;
• Move right, search, and move left;
• Move backward, search, and move forward;
• Move left, search, and move right.

It’s important to note that there is no reason to keep track of where the Drone has been and write code to return to the starting location. The Drone will return to the starting location because it always moves back to where it was.