Assignment 7

CMU 15-211 Fundamental Structures of Computer Science I

Assignment #7

Due: Monday April 29, 1996, 11:59 PM

Unlike previous assignments, on this assignment you may work in pairs. If you choose to work with a partner, the handin procedures are as follows:

Only one of your pair should hand in the assignment, the other person should leave his/her handin directory empty.
The handin should clearly state the name and andrew-ID of the other person (so that we can be sure to give that person credit!) You will both receive the same grade.

If you choose to work by yourself, the handin procedures are as usual. Note: the collection software has been modified to no longer give the usual warning if it does not find a handin.

Guidelines for working in pairs: If you choose to work in pairs, you may split up the effort as you wish. However, each person should contribute some significant part of the work, and you should say how you decided to split things up in your handin. (E.g., I did part X, my partner did part Y, and we did part Z together.) Here are some suggestions for splitting up work (some of these will make more sense after you've read the rest of the handout):

One person can be in charge of creating the priority queue and the other person can be in charge of writing the code that uses the priority queue. The person creating the pqueue can, for starters, whip up a simple but slow implementation using an unsorted array or a linked list. This can then be used by the other partner while the faster but more complicated heap-based implementation is being developed. Remember, the point of an ``abstract data type'' (like a priority queue) is that you can separate the interface from the implementation.
The part of the code that handles the input from the user (deciding if the user has typed in a place name or a street address, and checking for partial matches, etc.) is pretty much independent of the rest and either partner can be in charge of that. While that is being developed, you can still work on Tasks 2 and 3 but only allowing the user to type in street addresses like on assignment 6.
The part of your code that handles the output of Task 3 is also pretty much independent from the rest - you just need to decide in advance what the interface between your routines will be.

Introduction

You may have noticed in assignment 6 that the notion of a place being ``10 blocks away'' is not a great measure of how far away the place really is. For instance, some streets are broken into lots of tiny little blocks because of alleyways and such, and some streets have very long blocks. In this assignment you will fix this problem by taking actual distances into account in your computation. The specific problem you will solve on this assignment is finding and printing out shortest paths between starting and ending locations specified by a user. So, you'll never get lost in Pittsburgh again. :-)

This assignment consists of three tasks. The Task 1 is worth 20 points, Tasks 2 is worth 60 points, and task 3 is worth 20 points. 40 out of the 60 points for Task 2 are for getting a working heap-based implementation of a priority queue.

Task1

For this task, the user will input something that is either a prefix of a place name or a prefix of a street address. If it was an address, the program responds by saying

    <address> is <N1> feet from intersection <I1> and <N2>
    feet from intersection <I2>.

If it was a place name, the program responds by saying

    <place name> is at <address>
    <address> is <N1> feet from intersection <I1> and <N2>
    feet from intersection <I2>.

(The actual syntax is not important, and you can provide more information if your choose.) Furthermore, if the thing the user entered is ambiguous, the program should list the possible choices just like on Task 1 of assignment 6. You can run the executable we have provided for specific examples.

The way you will estimate the distance of the address to each intersection is by interpolation. For instance, if the block has street numbers 5100 to 5199, and is 550 feet long, then:

Address 5100 is 0 feet from the first intersection and 550 feet from the second.
Address 5101 is 5 feet (5.556 but let's round down) from the first and 545 feet from the second.
Address 5130 is 166 feet from the first and 384 feet from the second.
Address 5199 is 550 feet from the first and 0 feet from the second.

(It's not important if or exactly how you round the numbers to integers.)

As a special case, if the minimum and maximum street addresses on the block are the same, then say that the address is halfway between the two.

Note: one thing you will need to do is to determine if the user is giving you a place name or a street address. One way to do that is to read in a string, and then see if the string begins with a digit. If it does not begin with a digit, then this string is a place name (you can assume that no place names begin with digits). Otherwise, if the string does begin with a digit, then this means the string is a street number and you want to read in a second string to get the street name. One thing you will need to do is to convert your first string into a number. A convenient way to do that is to use the atoi function defined in <stdlib.h>. E.g., street_number = atoi(string); where street_number is an int and string is a character array. You can also use sscanf.

Task 2

For this task you will allow a user to input two locations: a starting location (a place name or street address) and an ending location. Your program will compute the shortest path between the two and then print out the result as a sequence of intersection numbers. If you want, you can print out extra information too (like street names) to help you in debugging. For instance:

    Enter a place name or street address: Blu
      Blum's_Barbeque is at address 355 S_Highland_Ave
    Enter a place name or street address: Bru
      Bruce's_Beach_Party is at address 711 Copeland_St

    Starting at 355 S_Highland_Ave, go to
    intersection 179, then on Elwood_St to
    intersection 192, then on Elwood_St to
    intersection 206, then on Elwood_St to
    intersection 217, then on Elwood_St to
    intersection 227, then on Elwood_St to
    intersection 268, then on Elwood_St to
    intersection 284, then on Elwood_St to
    intersection 295, then on Summerlea_St to
    intersection 275, then on Elmer_St to
    intersection 294, then on Elmer_St to
    intersection 314, then on Elmer_St to
    intersection 320, then on Elmer_St to
    intersection 330, then on Elmer_St to
    intersection 340, then on Elmer_St to
    intersection 348, then on Elmer_St to
    intersection 354, then on Elmer_St to
    intersection 359, then on Elmer_St to
    intersection 365, then on Copeland_St to
    711 Copeland_St
    Total distance traveled: 3578 feet.

(Your code may produce a total distance that differs by a foot or so from our code depending on how you do the rounding of Task 1.)

You may wish to treat the case in which the start and end are on the same block as a special case. For instance:

   Enter a place name or street address: Ali
     Ali_Baba is at address 404 S_Craig_St
   Enter a place name or street address: Sta
     Star_Of_India is at address 412 S_Craig_St

   Just walk down the block!

Your program should run in time O(m logm) where m is the total number of edges in your graph. In order to do this, your program should use a heap-based implementation of a priority queue. This priority queue should allow one to insert an item with a priority value, to perform a remove_min operation to remove the item with the smallest priority value, and perhaps to perform a decrease_value operation to decrease the priority value of some item already inside the pqueue as well. (The last feature is not necessary - it depends on your search routine).

Your program should use interpolation (as in Task 1) to figure out the distances from the start and end locations to the ends of their respective blocks.

A programming hint: if you put print statements into your insert and remove functions that let you know what you're inserting and what you're removing, it will help you debug your code. Also, you will need to decide on an interface between your path-finding code and your path-printing code. One nice way to do this is to have your path-finding code return its parent array, where you may wish to have each element of this array contain more information than just the parent.

A good test case on the small database is to start at 5070 Forbes and go to 5300 Wilkins, and then try from 5080 Forbes to 5300 Wilkins. These should take different routes.

Task 3

Now that you've got Task 2 working, Task 3 is to print out the path produced by your searching algorithm in a more useful form. In particular, your code should (a) print out street names, (b) say how long to travel on that street before turning onto the next street, and (c) say whether you're turning right or left when you change streets. Also, for the very first street you should say which way to go (increasing or decreasing street number?) For instance, your code might produce output like this:

    Enter a place name or street address: Blu
      Blum's_Barbeque is at address 355 S_Highland_Ave
    Enter a place name or street address: Bru
      Bruce's_Beach_Party is at address 711 Copeland_St


    Starting at 355 S_Highland_Ave head in the direction of increasing street number
    Go for 367 feet
     Turn right onto Elwood_St
    Go for 1604 feet
     Turn right onto Summerlea_St
    Go for 156 feet
     Turn left onto Elmer_St
    Go for 1394 feet
     Turn left onto Copeland_St
    Go for 57 feet
     and stop at number 711
    Total distance traveled: 3578 feet.

This is a bit trickier than it looks. For instance, how can you tell if you are making a right turn or a left turn? Below is a fragment of code that you can use or modify that will help you do that.

    /* Suppose that xcoords is an array of all the x coordinates and ycoords is
       an array of all the y coordinates.  This routine, given a start, middle,
       and end intersection (e.g., 284, 295, and 275) figures out what
       kind of turn (right or left)  was made at the middle intersection. 
       
       Here's the idea: we want to tell if the angle between two vectors 
       is < or > 180 degrees. So, rotate the first vector by 90 degrees and 
       then see if the dot prodoct is postive. */
    char *which_way(int start, int middle, int end)
    {
      /* these are the rotated ones (which is why they look weird) */
      int x0 = ycoords[middle] - ycoords[start];
      int y0 = xcoords[start] - xcoords[middle];
    
      int x1 = xcoords[end] - xcoords[middle];
      int y1 = ycoords[end] - ycoords[middle];
    
      int result = x0*x1 + y0*y1;
      
      if (result > 0) return "right";
      else return "left";
    }

For debugging purposes you might want to make your code output the intersections numbers too, while you're getting it working. We have placed executables into the assign7 directory that you can use to help you test out your program.

Good luck!