Karel's GPS

Note: Although Karel’s world is used as the setting for this problem, you don’t have to know anything about Karel programming to solve it.

As many of you know, Karel the Robot lives in a world composed of horizontal streets and vertical avenues laid out in a regular rectangular grid that looks like this:

karel.png

Karel moves by taking a step in one of the four cardinal directions (NSEW). In the diagram above, Karel is sitting on the intersection of 3rd Street and 2nd Avenue. Karel's goal is to move to the origin at 1st Street and 1st Avenue taking the fewest number of steps. There are three routes tied for the shortest, these are marked in the diagram below (red, green, and blue):

paths.png

Karel doesn't have a built-in GPS, so they are calling on you to help with this task. You are to use recursion to count the number of distinct routes Karel could follow back to the origin, subject to the condition that Karel only wants to take one of the shortest possible routes and can therefore only move west or south (i.e., left or down in the diagram) in each step.

To see the recursive structure of the problem, consider Karel's options when starting from an arbitrary intersection. The first step must either be west or south; in either case, that step brings Karel closer to the goal. Counting the available routes from that corner represents a simpler case of the original problem. The count of routes from a given intersection is the combined total of the available routes from the corner to the west and the corner to the south. To complete the algorithm, you also need to identify the base case(s) – the simple cases at which no further choices remain, i.e. there is only one route from here to the origin.

Write the recursive function

int countRoutes(int street, int avenue)

that uses the above recursive strategy to count the routes Karel can follow back to the origin.

Notes

  • The function returns the count of distinct paths from the specified intersection to the origin. In the example diagram above, the count of paths (3) happens to also be the length of the paths, but that is just a coincidence.
  • You do not need to print or display the paths, just count them.

Testing

  • Add student test cases of your own to confirm the correctness of your function.
  • For small inputs, you can diagram by hand and tally the expected count. If your function returns the correct result for location {m-1,n} and location {m,n-1}, then it should also work correctly for location {m,n} through the power of induction (which is really just recursion in disguise…)
  • The inputs to countRoutes are expected to be >= 1. Nothing good will come of a call that violates this precondition. Rather than blunder on to trouble, add a check that calls error if the starting location is invalid. Add student tests that use EXPECT_ERROR to confirm your error-handling is working as intended.