CS 302, Program 4

Program 4, Spring 2015: AsTheCrowFlies

  P4 TEAMS DUE before 12:00 PM (Noon) on Friday, May 1st
  P4 CODE DUE before 12:00 PM on Friday, May 8th
  NO LATE PROGRAMS WILL BE ACCEPTED!

[ P4 Announcements | Overview | Program Components | Classes | GettingStarted | Sample Files | Data String Format | Specifications | Milestones | Testing | Submission | Testing Server ]

[+] P4 Announcements

Tip: Don't save a copy of this write-up, you'll miss updates.

Corrections, clarifications, and other announcements regarding this programming assignment will be found in this section:

[+] Overview

Assignment Goals

Description

The Traveling Salesman (person) is a well known computer science problem.  Simply stated, the goal is to find the shortest path between cities (nodes) on a graph.  For relatively few numbers of cities or nodes, this is easy, simply enumerate all possible paths, compute the total distance to travel to all nodes for each path and choose the path with the smallest total distance.  Sales people solve this problem every day.

However, the shortest path through all nodes is useful for many more types of problems than just sales people trying to visit their clients in the shortest (cheapest) way possible. This concept of nodes and distances (or cost) between nodes can be used to model many types of optimization problems, like how to best arrange components on a chip for best performance or cheapest cost; or how to choose the order of picking items to fulfill an order of many items in a large warehouse to name a couple. 

The traveling salesman problem (TSM) is interesting because there is no known polynomial time solution for it.  From Wikipedia: In the general case, finding a shortest travelling salesman tour is NPO-complete. That means that as the number of cities (nodes) increases the time it takes to find a solution grows at a greater factor than simple polynomial factor of steps. For example, if you have twice as many cities (nodes), it may be at best 2^N times as costly to find a solution as compared to the original problem with n nodes.  See http://en.wikipedia.org/wiki/Travelling_salesman_problem for more information about this interesting problem.

For this program, we will NOT find the shortest path as good solutions require algorithms that are better suited to later programming courses.  Rather, we require that your program will manage a simple database (list) of Cities (with their locations lat/long), and be able to read in city information (state, city name, latitude, longitude) in from a file, and display to the console as well as write trip distances to a file. 

Your program will do this by allowing the user to choose cities to visit on a trip by selecting available cities in the order they will be travelled to.  Once cities have been selected, the distance between each segment of the trip is displayed in both meters and miles.  Then, the user is prompted to see if they wish to write their trip details to a file.  The user may also choose to clear the current trip and then choose cities again or continue adding cities to the existing trip. See sample runs for examples of this control flow.

We provide a few city data files as examples of the format that your program must be able to read. See Sample Files. The format for city information in a file is that each line describes one city as shown here:
State Name, City Name, latitude, longitude

The latitude and longitude for cities can be found at: http://www.latlong.net/

We provide and require that you use The Haversine formula for computing distances across the globe.  A version suitable for programming is described here: Haversine.html

 

[+] The Program

Main Menu of the main class

AsTheCrowFlies is the main class and it contains the main method that gets the program going displaying a title and then a functioning main menu as described here. At the start, display the title As The Crow Flies, then the main menu.

The Main Menu

The main menu includes options for maintaining a database (list) of Cities, and an option for the user to choose files for a trip.  Each option is outlined here.  Your program must implement each option according to its function, and the prompt examples in the sample run files.

1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]:

1. Load available cities from a file

Prompts the user for a filename, connects a Scanner to that file, then reads that file, and reports on the number of cities read and added to the available cities list.  Each line of a data file represents a single City and each City is created and used to represent different locations. Each city is added to an available list of cities. Lines in the file that do not contain the correct format, are read and ignored.

   1. Load available cities from a file
   2. Display available cities
   3. Create a trip
   4. Add a city to available cities
   5. Exit Program
   Enter choice as integer [1-5]: 1
   Enter the filename: cities_01.txt
   4 cities added  

2. Display available cities

Displays list of all city information for cities that are in the current available cities list.  Cities get added to the available list by reading their data from a file (OPTION 1) and by manually entering data for each city (OPTION 4). Once a city is added to the list, it is not removed.  Duplicate cities can be added, though this is not recommended as there is no specification for this program that will allow the user to get any City match except for the first city that matches the city name given.  For example, if the program's available cities list has the cities (Madison (WI), Milwaukee (WI), Chicago (IL), Madison (VA) and Minneapolis (MN)), only the Madison (WI) city would be available.  The Madison (VA) can not be chosen, because "Madison" will always match the first one :

  1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]: 2 WISCONSIN,MADISON,43.074722,-89.384444 WISCONSIN,MILWAUKEE,43.038902,-87.906471 ILLINOIS,CHICAGO,41.881832,-87.623177 MINNESOTA,MINNEAPOLIS,44.986656,-93.258133
If there are no available cities and the user chooses 2 to display available cities.   No cities are displayed, main menu is repeated, and the user is prompted to enter a new integer choice.

3. Create a trip

Prompt user for cities to visit on their trip in the order that they plan to visit those cities. When the user is done adding cities, they press Enter (with no city entry). After cities are entered, display the distance between each city to city segment, and the Total Distance (in meters and miles) for the entire trip. 

If there were at least two cities (making a valid trip), prompt user to learn if they wish to save the results to a file.  If they answer with a string that starts with 'y', then prompt for filename and save the trip details to that file.  The trip details that were displayed to console are the same as those that must be written to the file.

If the user "chooses" a City that does not exist in the available cities, just do not include that city in the trip. No other message is displayed to the user.

1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]: 3
There are 4 cities to choose from.
New trip created, needs at least two cities.
Enter next city name (or enter to end): madison
Enter next city name (or enter to end): milwaukee
Enter next city name (or enter to end): 
There are 2 cities in this trip.
MADISON to MILWAUKEE as the crow flies is about 120146 meters (~74 miles)
MILWAUKEE to MADISON as the crow flies is about 120146 meters (~74 miles)
Total Distance: 240292 meters (~148 miles)
Write trip details to file (y/n)? n

1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]: 

Note: This trip (list of Cities is the trip) is persistent while the program is running. The next time the user chooses (3), they are asked if they wish to add cities to the trip (at the end).  If they say 'no', a new trip is created. After each trip, the user is prompted to save or not save the details to a file. If they choose 'y' or 'yes' or anything that starts with 'y' or 'Y', overwrite the file.

1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]: 3
There are 4 cities to choose from.
Add to current trip (y/n)? y
Enter next city name (or enter to end): chicago
Enter next city name (or enter to end): 
There are 3 cities in this trip.
MADISON to MILWAUKEE as the crow flies is about 120146 meters (~74 miles)
MILWAUKEE to CHICAGO as the crow flies is about 130742 meters (~81 miles)
CHICAGO to MADISON as the crow flies is about 196097 meters (~121 miles)
Total Distance: 446985 meters (~277 miles)
Write trip details to file (y/n)? y
Enter filename: mad_mil_chi.trip

4. Add a city to available cities

Cities can be added by reading data from a file (Option 1--described above), or by prompting the user for City details (this option, Option #4).  When a city is added to the available cities list in this option, the user enters four items: the state name (or territory), the city's name, the latitude (in degrees), and the longitude (in degrees). There is no validation on the state and city user input values. But, the latitude must be within -90 to 90, inclusive; and the longitude must be within -180 and 180, inclusive.  As long as the user input is the right data types (String,String,double,double) and the latitude and longitude are within range, the "city" will be created and added to the available cities list.  A confirmation message is displayed to the user.

1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]: 4
Enter state name: disney world
Enter city name: epcot center
Enter latitude as double (-90.0 to 90.0): 28.3774061
Enter longitude as double (-180.0 to 180.0): -81.5401091
Added: DISNEY WORLD,EPCOT CENTER,28.3774061,-81.5401091

5. Exit Program

When the user chooses 5 to exit the program.  Display the thank you message (shown below) and save the list of available cities to a file named available_cities.txt.  Simply overwrite this file on each exit from the program.

1. Load available cities from a file
2. Display available cities
3. Create a trip
4. Add a city to available cities
5. Exit Program
Enter choice as integer [1-5]: 5
Thank you for your business.
Saved available cities to available_cities.txt

See Sample Files for correct prompts and responses.

 

[+] Classes

Main Class: Required to Implement

AsTheCrowFlies (the main class)

The AsTheCrowFlies class must have the following and use this to launch the program.

public static void main(String [] args) { ... }
The main method used to launch your application.

Your class AsTheCrowFlies may also be instantiable (but this is not required).

Instantiable Classes: We Recommend you Define (you need at least two instantiable classes anyway)

City

An instantiable class that knows the state, city name, latitude, and longitude for a city, or point on the globe.  Latitudes are between -90 and 90 and valid longitudes are between -180 and 180.  It may have a way to display its information and a way to calculate the distance between itself and another city.  See the section on computing the distance "as the crow flies" using the Haversine formula.

Trip (or Route or Path)

A class that stores a current list of cities as selected by the user.  Can be used to get a string describing the trip segments.  It should have a way to display its information and a way to calculate the distance between each city and the next city in the trip as well as the return trip to the first city.  See the section on computing the distance "as the crow flies" using the Haversine formula.

Pre-defined Classes: You Will Likely Want to Import and Use (you are not limited to these classes)

java.io.File - abstract representation of a file (for reading or writing)
java.io.FileNotFoundException - thrown when a file does not exist
java.io.IOException - thrown when a file can not be read
java.util.ArrayList - can keep expandable lists of filenames, and shape information
java.util.Scanner - for console input from the keyboard and for reading shape information from a file

 

[+] Getting Started

Outline the data and methods that you will need to represent a City in your program. Write some demo code that writes data of a City to the console window, and to a file in the format required for cities. 

Outline the data and methods that you will use to represent a Trip (a list of cities).  Write some demo programs that create a Trip (by adding Cities one at a time), and then printing the details of the trip to the screen.

Outline the methods you will use to implement the main class, AsTheCrowFlies.  Write some demo code to create an instance of the City class, and add instances of the City class to an instance of the Trip class.  Then, print the trip details to the console.

Add a main menu loop to the main class and continue with the milestones.

 

[+] Sample Files

misc-src Directory (sample city data files that can be read by program to the available cities list)

cities_01.txt
capitol_cities.txt
vacation_cities.txt

bad_city_data_file.txt (some cities have invalid format strings -- only the last three lines contain valid formats and thus should be added to program)

sample-runs Directory (Sample runs showing prompts and responses while program is running -- additional samples may be added. See announcements for notices of additions or changes.)

sample_run_01.txt (standard example of the menu options)
sample_run_02.txt (example of adding a file via menu with some bad latitude and longitud values)

error_run_01.txt (main menu error examples)
error_run_02.txt (bad city data filenames)
error_run_03.txt (valid filename, but not all lines are valid city descriptions)
error_run_04.txt (empty string state and city names)
error_run_05.txt (display when 0 available cities and choose trip with less than 2 available cities)

mad_mil_chi_min.trip (example of saved trip file)
mad_oco.trip (example of saved trip file)

provided-src Directory No sample Java source code is provided. The main method for your p4 solution must be in a class named AsTheCrowFlies, in a file named AsTheCrowFlies.java file. 

We do provide a jar (Java archive) file with a working distanceBtw() method.  You may add this jar file to your project for development and testing purposes.  You can call this method and compare your results to the results of the distanceBtw() method call.  Studemts are required to write their own implementation of this method or similar.  A distance within 2% of the distance returned by this method will be considered correct.

Add the haversine.jar file to your Eclipse project, and call the public static distanceBtw() method as follows:

     double madisonLat = 43.074722, madisonLong = -89.384444;
     double milwaukeeLat = 43.038902, milwaukeeLong = -87.906471;
     double distanceBtwMadisonMilwaukee = Haversine.distanceBtw( 
          madisonLat, madisonLong, milwaukeeLat, milwaukeeLong );
     System.out.println("distance btw Madison and Milwaukee is " +
          distanceBtwMadisonMilwaukee + " meters");
Before you handin your p4 program, be sure to remove the haversine.jar library from your project, and test to ensure that your program works without this external method.

[+] Data File Line formats

The program must be able to read a text-only file that contains city information. All city data files will have lines of this exact format.  If any line is not valid, it should be scanned and ignored so that city information on remaining lines may be read into your program. 

  1. Each line of the file describes one city.
  2. Duplicate cities may be added, but only the first city will be used when that city name is chosen by the user.
  3. Each city must have:
    1. a state (or territory name)
    2. a city name
    3. the latitude in degrees (-90 to 90)
    4. the longitude in degrees (-180 to 180).
  4. There will be no empty lines in any shape file we try, but there may be lines with invalid formats.  Use exception handling try/catch to catch exceptions caused by those lines (and ignore those lines of the file being read).

Example City Line formats (actual values for the cities shown)

WISCONSIN,MADISON,43.074722,-89.384444
WISCONSIN,MILWAUKEE,43.038902,-87.906471
ILLINOIS,CHICAGO,41.881832,-87.623177
MINNESOTA,MINNEAPOLIS,44.986656,-93.258133
WI,OCONOMOWOC,43.111673,-88.499266

[+] Program Specifications

Requirements

  1. Your main class that launches your program must be named AsTheCrowFlies.
  2. Your program must get all user input (keyboard) from a single Scanner instance. 
  3. Your program must not crash.  See samples for the user input conditions you must handle.  In general if you need an int in a given range, repeat prompt until int in that range has been entered.  If a filename is not found, reprompt for a new file name.  If a line of the file can not be interpreted correctly, because it is an invalid format, skip that line and continue with remaining lines in the file.
  4. Your program must maintain a dynamic list (array or ArrayList) of available cities and the user must be able to add cities to a trip.
  5. Your program must use the Haversine.html for computing the distance as the crow flies between two cities (with given latitude and longitude values). Distances are computed and totaled as doubles, but are rounded and displayed to the user (and in the written files) as ints.
  6. Distances must be shown in meters and miles and computed via the Haversine formula.  However, student's final code submission may not use or require that haversine.jar has been added to the build and runtime environment. 
  7. All user input prompts and output message must be as shown in write-up and sample files.  Let us know via private Piazza post if you find inconsistencies, so they may resolved.
  8. The program must not crash if user input is of the wrong type, or the file name is not valid for reading or writing from a file.  The sample error_run_xx.txt files give examples of most (maybe all) of the types of errors we will check.

[+] Development Milestones

We suggest that you incrementally develop this program by following the milestones in the order listed below. This order will make it easy for you to check that each milestone is working properly before you move on to the next one. Don't move on to a new milestone until you can convince yourself that the current milestone is working correctly. The further along you get, the harder it will be to detect errors in code you developed early on.

Note. In order to get any milestone working, you may have to edit classes not mentioned in the milestone description.

Hint. In addition to getting specific functionality in your program.  Think about the design choices you are making, would a method help, or a new class?  Having all code in a single main method (like program 1) will lose 5 points of design, but can otherwise get full credit.  Having all code in a single class, with no instances created (like program 2) will lose you 3 points of design, but can otherwise get full credit.  Having all code in one class, with many methods, and only one instance of your own class created will lose 2 points of design.  To get all 5 points of design, you must have a main class and at least two instantiable classes that are used to create multiple instances.  We suggest a City class to store the data values of a single city, and a Trip (or Route or Path or CityList) class to store an expandable list of City instances and provide some helper methods for computing things like the distance between two cities and the total distance of a trip.  Each instantiable class should override the toString() method for use during testing and development or the program itself.

[+] Testing

You should test your program by running and testing individual methods frequently as you develop. For example, writing methods for each option and unit testing them separately will help ensure that they work together when needed in later parts of the program.

It is to your advantage to always have a compiling program so that you can run it and see what it does. If you follow the milestones outlined above, you should be able to verify whether you have completed each milestone by running your program and interacting with it.

[+] Submission

Before handing in your program, check that you've done the following:

Use the CS302 Forms Page to electronically submit and backup your work:

Submit these files:

© 2015 Deb Deppeler (deppeler@cs.wisc.edu)