Umich ENGR 101 Project 4 Overview (Summary)

[I. Project Roadmap]

1. Helper functions 

2. Checkpoints

(1) Read in data files: planet info

(2) Create a vector of vectors to represent the map 

(3) Place the planet symbols in the correct location 

3. Driver program

(1) Match planet names with their locations

(2) Fix the corrupted data 

(3) Implement the Nearest Neighbor algorithm to plan the route for the gLyft driver

(4) Verify : journey.txt file matches the journey_1.txt and journey_2.txt files 

(5) Style & comment 

(6) Submit planRoute.cpp file to the autograder

================================================

[II. Submission and Grading]

This project has one deliverable: planRoute.cpp. 

contains your main() function & helper functions or structs you implement to use in the driver program.

There is no starter code and no test programs.

1. 100 points: autograder

(1) Public test: the same as the test scripts provided in this project specification. It will give you your score on these tests & feedback 

(2) Hidden test: additional tests of your code (e.g. special cases). You still see your score on these tests, and you will receive some feedback on any cases that your code does not pass.

2. 10 points: style and comments

(1) 2 pts - Each submitted file has Name, Partner Uniqname (or “none”), Lab Section Number, and Date Submitted included in a comment at the top

(2) 2 pts - Comments are used appropriately to describe your code (e.g. major steps are explained)

(3) 2 pts - Indenting and white space are appropriate (including functions are properly formatted)

(4) 2 pts - Variables are named descriptively

(5) 2 pts - Other factors (Variable names aren’t all caps, etc…)

================================================

[III.Project Background] 

Traveling Salesperson Problem (TSP)

요약: 가장 짧은 무중복 라이딩 루트 짜는 프로그램

ex) Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? 

The “cities” and “distances” can have different definitions according to the application of the TSP algorithm. 

Project: Use the nearest neighbor algorithm to determine which planet to go to next. 

The nearest neighbor algorithm we will use is defined here as:

1. Start at a given location
2. Find the closest location that has not already been visited
3. Go to that location
4. Mark that this location has been “visited”
5. Repeat steps 2-4 until all locations have been visited
6. Go to the specified end location

(Step 6 above is required for our particular application in this project – it is not a necessary part of the nearest neighbor algorithm.)

Data Corruption

요약: 송신 시 손상된 데이터 고치는 프로그램

Data corruption occurs when data transmitted by one computer and received by a second computer does not match the actual data transmitted by the first computer. 

Data is stored in binary form: a collection of 0s and 1s. 

When these data are transmitted from one computer to another over a long distance, it is possible for a 0 to be received as a 1 or vice-versa due to noise in the system. 

This means some data may be corrupted and requires correction. Error detection and correction is a critical component of modern computing.

Project: We are going to work on some basic data correction based on known error effects as an introduction to the concept of data corruption. Some of the data that is used by our program has errors that need to be corrected. 

ex) a string that is read in as this:

HaiXXl_to_the_XXVictors_ValXXiant

needs to be corrected to this:

Hail to the Victors Valiant

================================================

[IV. Project Overview] 

Background

요약: 라이드 서비스 확장 예정으로 루트 최적화 필요 

CEO Uberwine von Lyften is looking to expand the service of the galactic ride-sharing company, gLyft, headquartered on Proxima b. gLyft currently serves three planets (including Proxima b) and the company wants to be able to plan routes between many more planets once their service is expanded to other nearby planets (Fig. 2).

Figure 2. A sketch of the current planets that gLyft serves and how many planets they want to expand their service to.

The original service range of three planets wasn’t too difficult to schedule routes through; there just aren’t that many different paths one can take between three locations. But with the proposed service expansion to many different planets, gLyft needs a more advanced route planning algorithm and program.

Job

Find a recommended path from each planet to the next within your gLyft driver’s range.

Data Sources/Files

There are two data files that your code needs to read data from:

1. A file containing the locations your gLyft driver is required to visit
2. A file containing the names of the planets with their ID numbers

Note: The actual names of these data files will be entered by the user via the terminal, but you can assume that any locations and names files that are used will follow the same format.

1. Location File

Each gLyft driver has a given range that they cover. The range is represented as a grid with a given number of rows and columns. If a planet is located within the driver’s range (i.e. the planet’s row and column are each within the driver’s grid), then the driver can take passengers to that planet.

The locations file contains information about the locations that the gLyft driver is assigned to visit. T sample locations files:

• locations_1.txt
• locations_2.txt

The file first lists information specific to the driver:

• Their driving range (a number of rows and a number of columns)
• Their starting position (a row and a column)
• Their ending position (a row and a column)

The file then lists all of the planets that the driver is supposed to take gLyft customers to:

• Planet 1’s row, column, map symbol, ID
• Planet 2’s row, column, map symbol, ID
• Planet 3’s row, column, map symbol, ID
• Planet 4’s row, column, map symbol, ID
• etc.

A locations text file will look like:

Here is a description for each of the fields in the schematic:

field	description
<Number of Grid Rows>	the number of rows there are in your grid
<Number of Grid Columns>	the number of columns there are in your grid
<Starting Row>	the starting point’s row number (not index number)
<Starting Column>	the starting point’s column number (not index number)
<Ending Row>	the ending point’s row number
<Ending Column>	the ending point’s column number
<Planet Row>	the planet’s row number
<Planet Column>	the planet’s column number
<Planet Symbol>	the symbol associated with the planet’s surcharge type (this will always be one character in length)
<Planet ID>	a unique integer ID that is associated with the planet

Read in all of the information in the file, no matter how many planets there are, and store the data in variables so you can use the information later.

Some planets will have coordinates that lie outside the driver’s grid, which means that the driver can’t take passengers to those planets. You’ll need to handle these cases specially: see the Get Planet Information section of the program algorithm for more details on what to do with out-of-range planets.

2. Names File

The locations that the gLyft driver needs to visit need to be cross-listed against a planet names file in order to look up the name of the planets that the driver is going to. The names file contains a database-type list of planet IDs and their corresponding planet names. Here are two sample names files (click the filenames to download):

• names_1.txt
• names_2.txt

The names file will contain the planet IDs that are in the locations file (e.g. locations_1.txt). However, the names file is a totally separate listing of information about the planets so the planets listed in the names file are not necessarily in the same order as the planets listed in the locations file… and there may be more planet IDs in the names file than in the locations file.

A names text file will look like:

Here is a description for each of the fields in the schematic:

field	description
<Planet ID>	a unique ID that is associated with the planet
<Planet Name>	a name that is a contiguous set of characters (i.e. no spaces)

 

You are guaranteed that all of the planet IDs in the locations file will be present in the names file, and each planet ID will have a corresponding planet name. 

The names file may have planet IDs and planet names that you don’t need for a given route, and that just means that information won’t be used for that route (which is totally fine).

The names file is particularly susceptible to data corruption and the gLyft team can’t figure out why. Unfortunately, the names of each of the planets need to be corrected after they are read into the program. There are two types of corruption that happen:

1. Pairs of Xs can be inserted into various locations in the planet’s name
2. Any spaces in the planet’s name get converted to underscores (_)

To correct the data, any double XXs need to be removed from the planet name, and the underscores (_) need to be replaced with spaces.

================================================

[V. Project Task Description] 

The gLyft driver needs two things before they start their route:

1. a “map” of their service range that includes symbols for the planets that they’re going to
2. a list of their stops in order: the starting location, each of the planets (as determined by the nearest neighbor algorithm), and the ending location

This project needs to create a journey.txt file that contains this information for the gLyft driver. An example of what a journey.txt file looks like is shown in Fig. 3.

Figure 3. An example of the journey.txt file with the "map" section and the "directions" sections labeled.

Description of planRoute.cpp

The driver program and all helper functions will be written in a C++ file named planRoute.cpp.

Algorithm

Determine a route for your gLyft driver using the nearest neighbor algorithm. 

The route : starting point > customers’ planets > endpoint. 

Read data from input files (correction) > determine the route > create an output file with a “map” of the planets & the route the gLyft driver needs to take to travel from the starting point to the end point. 

1. Read in Planet Data

Read in the planet location data & name data. To do this properly, you will need to:

• Get the filenames for each file from the user
• Open the files (gracefully exit the program if either/both of the files cannot be opened)
• Read in the information in the locations file
• Read in the information in the names file

(1) Get Filenames

Your program should prompt the user for the names of the two files with the planet data. Asking for the filenames, makes the program flexible – the person writing the files may name them whatever they want.

Ask the user for the locations file first using the following prompt:

Enter Locations Filename:

The user will then enter a filename (e.g. locations_1.txt or locations_2.txt).

Next, ask the user for the names file using the following prompt:

Enter Names Filename:

The user will then enter a filename (e.g. names_1.txt or names_2.txt).

(2) Open Files

Once both input filenames have been entered by the user, the program should open the files for reading. If either of the input files is not found or cannot be opened for reading, the program should output this message to the terminal:

Input file could not be opened

Include a newline after the message is printed. After printing this message, the program should exit with code return 1;.

Note: You do not need to print or determine which file caused the failure; simply print the above message and exit the program.

Note: The provided test cases do not test the error handling of input files. You should generate your own test case to ensure compliance. Do not submit your test case, just ensure your code satisfies this important required project specification.

(3) Get Planet Information and Correct Data Corruption

After the two files have been opened, read in the data from the files to your program. You can store the data in whatever types of data structures you think is best.

As you check each planet in the file, you need to check that the planet is in the driver’s range (their “grid”). If a planet’s row or column lies outside the rows and columns that define the driver’s grid, then that planet is out of range. If a planet is out of range, print a message to the terminal:

<Planet ID> out of range - ignoring

where <Planet ID> is the ID of the planet whose coordinates are not within the grid. For example, if a planet with ID 3092 is not in the driver’s range, then this message would be printed to the terminal:

3092 out of range - ignoring

Any out of range planets can be removed (or otherwise ignored) prior to using the nearest neighbor algorithm when planning the driver’s route.

The messages for the out of range planets should be printed to the terminal in the same order as the planets appear in the locations file.

The planet names will need to have their data corruption corrected as well. For each planet that is in the driver’s route, you will need to correct any errors in the planet’s name by:

• Finding and erasing all occurrences of XX from each name.
• Finding and replacing all underscore characters (_) with spaces ( ).

The corrections to the planet names should happen to the data stored in variables within your program; you should not modify the input files.

2. Create Location Grid

The gLyft driver needs a map of where they are supposed to be taking passengers. So, your program needs to create a grid of characters representing the “map” of locations within your gLyft driver’s range. The locations file indicates the number of rows and columns in the grid. The locations file also contains 1-character symbols representing each planet.

To create the grid that is the “map”:

• Place each planet’s symbol at its corresponding grid location (row, column)
• Place an S at the starting point and an E at the ending point
• Place a period (.) at any grid point that is not part of the route (planet location or starting/ending point)

For your grid that represents the map, the locations of the route (planets and starting/ending point) are all defined as row/column values starting at 1. For example, a starting point may be at the 3rd row and the 5th column. Watch your indexing!

The row numbers increase from the top row to the bottom row and column numbers increase from the left column to the right column. In other words, the upper left corner of the grid map corresponds to (row 1, column 1).

If you store your map in a vector of vectors, remember that C++ vector indices begin with index 0. 

3. Determine the Route

To schedule the gLyft driver’s route, implement the nearest neighbor algorithm. 

1. Start at a given location
2. Find the closest location that has not already been visited
3. Go to that location
4. Mark that this location has been “visited”
5. Repeat steps 2-4 until all locations have been visited
6. Go to the specified end location

The nearest neighbor algorithm will need to calculate which planet is “closest” to the current location. We will assume that the planets all lie in the (x,y) galactic plane and that we can use the following formula for distance:

where  x_current and y_current are the coordinates of the current location and 

x_potential and y_potential are the coordinates of the location of a potential candidate that we wish to visit.

Algorithm for implementing the nearest neighbor algorithm to determine the route for the gLyft driver:

1. The first location in the route is the starting point (row and column provided by the locations file)
2. The first location is now the current location
3. The next location is the planet closest to the current location. To find the next location:
4. Continue selecting the next location until all planets have been visited
5. The last location in the route is the ending point (row and column provided by the locations file)

Recommendation: Nested Loops

To establish the driver’s route, we strongly recommend that you use two nested loops:

• The inner loop iterates through all the locations that have not yet been visited to determine which planet is the closest to the current location, based on the nearest neighbor algorithm.
• The outer loop iterates while there are planets that have not yet been visited. This outer loop is also a good place to print the route information to the journey.txt file. See the Create a File to Document the Driver’s Journey and the Testing Your Program sections for examples and inspiration on how to print the information needed for the journey.txt file.

4. Create a File to Document the Driver’s Journey

Your program needs to create a file named journey.txt that contains all the information that the gLyft driver needs for their route. This file contains a grid map of the route and a list of all the planets to go to in the correct order based on the algorithm described in the Determine the Route Section.

A journey.txt file will look like:

Here is a description for each of the fields in the schematic:

field	description
<Map>	the grid with all of the "in range" planets' symbols on it, as well as the starting and ending points
<Starting Row>	the starting point’s row number (not index number)
<Starting Column>	the starting point’s column number (not index number)
<Planet Name>	the planet's name (with data corruption corrected)
<Planet Row>	the planet's row number
<Planet Column>	the planet's column number
<Ending Row>	the ending point's row number
<Ending Column>	the ending point's column number

Note: There should be a newline after the information about the ending point so that there is a blank line at the end of the file.

================================================

[VI. Compile & Run the Program] 

To compile the program, use the following compile command:

g++ -std=c++11 -Wall -pedantic planRoute.cpp -o planRoute

Notes about compiling this program:

• -std=c++11: vectors 등 Some of our common methods and patterns use features only available in C++11 
• -Wall flag: all warnings from the compiler-> catch bugs. Warnings are diagnostic messages that report things in your code that are not inherently erroneous but that are risky or suggest there may have been an error. 
•  -pedantic flag: tells the compiler to look for anything that you did that might not work on other people’s computer. Mostly, this will check to see if you forgot to initialize a variable because this may cause you to fail a test case on the Autograder.

Once compiled, the program can be run from the terminal like this:

$./planRoute

================================================

[VII. Testing Program] 

The two locations and names files provided in Data Sources/Files can be used to create two test cases.

Test Case 1

This test case uses the locations_1.txt and names_1.txt files.

If your program works correctly, your journey.txt file should look like this:

Test Case 2

This test case uses the locations_2.txt and names_2.txt files. Run Test Case #2 like this:

If your program works correctly, your journey.txt file should look like this:

 

Tips and Tricks

1. Place all data sources (.txt files) in the same directory as the planRoute.cpp file. 

2. Project 4 FAQ Piazza. 

3. Unit test each helper function &af test the driver program as you go. 

4. Use cout to check the names of planets after cleaning them and variables that you are using to track things in the program. Use cout to check the values of variables in a loop. (필요 없게 되면 삭제) 

5. Use a vector of structs to store the planetary data. (name, ID, location, etc.) 

6. Write functions which pass in large data structures, ex) vectors & structs, it is best to use pass-by-reference. (pass-by-value, pass-by-reference, and const pass-by-reference. 잘 구분하기) 

Warning : “comparison of integers of different signs”

1. compile using the -Wall and -pedantic flags to help you catch bugs. 

ex) if you have some code that uses a vector of ints like this:

compile using the -Wall and -pedantic flags, you might see an error that looks like this:

warn: you are comparing integers whose values might represent different things: 

a signed integer  i (a “regular” signed integer) vs. an _unsigned _integer. value that is returned by the vector’s .size() function (an “unsigned long” integer which has a different range of values than “regular” integers).

2. In this case of the “traversing a vector” pattern, you can safely ignore this warning because our vectors are small enough that comparing a signed integer to an unsigned integer will not cause us any problems. 

3. Options to resolve this error. 

(1) Option 1: The .size() vector function returns a value with type ‘size_t’ (this means it is an unsigned integer). So we need to compare the value returned by .size() to an unsigned integer, rather than our usual signed integer. So, we can declare i to be a size_t variable instead of an int variable:

(2) Option 2: We could also cast the value returned by .size() as an int so that we are comparing ints. Casting is explicitly converting a variable from one type to another.

 

Autograder: Test Case Descriptions and Error Messages

It’s checking to see if your programs can handle “special cases” of data, ex) corrupted data, choosing the correct path when multiple planets are the same distance away, etc.

1. Runtime Error -11: likely caused by indexing out-of-bounds when using [ ] to index into a vector. Check your indexing and vectors to see.

2. Runtime Error -6: likely caused by indexing out-of-bounds when using .at() to index into a vector. Check your indexing and vectors to see. 

3. Debugging out-of-bounds errors. 

Use cout statements inside of loops that transverse vectors to print out the index each time you go through it. Look at the last value that prints before the program crashes. Now you know that the next value causes the error. 

Common situations: 

(1) The index value that causes the crash is wrong: Is your loop going too many times? => Check the condition that ends the loop, maybe you have an error there.

(2) The index value is correct: Is your vector (or string) not long enough? 

=>Use additional cout statements to check the values of the vector/string when that vector/string is created. Check to make sure all elements are added correctly.

(3) No index values are printed out: This means your vector has a size of 0 – it’s empty! Trace back through your code to where the vector/string is created to find out why it’s not being created properly. Additional cout statements will be very useful here!

After running the test case, the Autograder will compare your code’s generated journey.txt file to what is expected. Within the Autograder tests, click to expand the “Check journey.txt” test and see a window that compares the expected output for the file (on the left) to your output file (on the right).

Every character and every whitespace must match – so beyond the map, be sure each word in your file is spelled correctly, has matching spaces and matching newlines. Lines that don’t correspond with the expected output will be highlighted, and you can click “Show Whitespace” to see the correct spacing and newline placement.