CS 2102 B Term 2009
Object-Oriented Design Concepts

---

Project #1 - Travel graphs

Before you start

• E-mail me the name of your homework partner. My e-mail is gmarceau at cs.wpi.edu . If you do not have a homework partner, e-mail me so I may assign one to you. The deadline for this is Friday at 5pm.
  
  
• Boot DrScheme and set your language to ProfessorJ / Intermediate Language.
  
  
• Schedule your week so you have enough time to complete this project by the deadline, Monday, November 2, 2009, 11:59pm.
  
  

Scenario

An interactive directions application suggests travel routes using a combination of walking, trains, buses, and taxis. To help users choose suitable routes, the application asks users questions about their constraints and travel preferences. After asking a question, the application gives a sequence of travel instructions, perhaps ending in another question as needed to plan the next travel segment. The application uses the following data definitions, illustrated in the subsequent example for traveling between Boston and WPI.

Data Definitions

; A question is (make-question string steplist steplist)
(define-struct question (text yes no))

; A steplist is
; - (cons question empty)
; - (cons instruction empty)
; - (cons instruction steplist)

; An instruction is one of:
; - (make-walk-to string number number)
; - (make-train-to string number number)
; - (make-bus-to string number number)
; - (make-taxi-to string number number number)
; - (make-purchase string number)
(define-struct walk-to (where lat long))
(define-struct train-to (where lat long))
(define-struct bus-to (where lat long))
(define-struct taxi-to (where lat long expected-price))
(define-struct purchase (item expected-price))

Examples of data

(define south-station-to-wpi
  (make-question "Are you a long-distance hiker?"
                 (list (make-walk-to "WPI" 42.274334 -71.80822))
                 (list (make-purchase "MBTA zone 8 ticket" 7.75)
                       (make-train-to "Worcester" 42.261793 -71.793703)
                       (make-taxi-to "WPI" 42.274334 -71.80822 7))))

(define logan-to-WPI
  (make-question "Do you have a lot of luggage?"
                 (list (make-taxi-to "WPI" 42.274334 -71.80822 100))
                 (list (make-question "Do you like public transit?"
                                      (list (make-walk-to "Logan Silver Line Station" 42.366777 -71.017366)
                                            (make-purchase "Charlie ticket" 2.25)
                                            (make-bus-to "South Station" 42.352767 -71.055572)
                                            south-station-to-wpi)
                                      (list (make-walk-to "Logan Taxi Stand" 42.366422 -71.017201)
                                            (make-taxi-to "South Station" 42.352767 -71.055572 20)
                                            south-station-to-wpi)))))

Exercises

1. Convert these data definitions to a Java class definitions, following the coding style shown in class, then use those to write the rest of the program.
   
   
2. Write a method cheapestTrip on questions (such as logan-to-WPI) that produces a number indicating the cost of the cheapest route starting from that question. Assume that prices are computed from purchases and taxi fares encountered in steplists.
   
   
3. Write a method hasBusFreeRouteTo questions that produces a boolean indicating whether there exists a route starting from the question that does not involve taking a bus.
   
   
4. Write a method totalTime on steplists that consumes a current latitude and longitude (as numbers) and produces the number of minutes needed to perform all the instructions in the steplist. Assume that each purchase requires 2 minutes. Assume that walking covers 3 miles per hour, trains go 30 miles an hour and that buses and taxis go 45 miles per hour. The distance between two latitudes is their difference multiplied by 70. You may use the same formula for a very rough approximation of the longitude difference for purposes of this assignment. The pythagorean theorem can be used to compute the distance between the points defined by latitude and longitude.
   
   
5. One alternative design would have replaced walk-to, train-to, bus-to, and taxi-to with a single structure transit-to that also had a string field to indicate the type of transportation (i.e., "walk", "bus", etc). Which of these two designs is better and why?
   
   
6. In order to ask one question directly after another in the current data definition, we must wrap the inner question in a list (such as the question about public transport in logan-to-WPI above). We might prefer to write the examples more cleanly as

      (define logan-to-WPI
        (make-question "Do you have a lot of luggage?"
                       (list (make-taxi-to "WPI" 42.274334,-71.80822 100))
                       (make-question "Do you like public transit?"
                                      (list (make-walk-to "Logan Silver Line Station" 42.366777 -71.017366)
                                            ...)
                                      (list (make-walk-to "Logan Taxi Stand" 42.366422 -71.017201) ...))))
   

   In a separate file, provide a class definition for the data definition modified to accommodate this change. Specifically, the yes/no parts of a question can now contain a single question, a list of instructions, or a list of instructions with a single question at the end of the list (as in the current definition). You do not need to write any methods for this part.
   
   

Once you are done

Once you're done, name the two files Project-1.java and Project-1-q6.java, lists the name of all your homework partners at the top of the files, then submit it to Turnin.

Turning is at https://turnin.cs.wpi.edu:8088/servlets/turnin.ss

Remember, the deadline is Monday, November 2, 2009 at 11:59 PM.

The deadline to drop from the accelerated option is 24 hours after the homework deadline, Tuesday, November 3, 2009 at 11:59 PM. If you found the homework difficult and you want to drop, e-mail me. If you're not sure whether to stay or not, e-mail me as well. My e-mail is gmarceau at cs.wpi.edu







[CS2102]