CSCI2110
Assignment 6
Due: 12:00 noon, Monday, April 8, 2019
The purpose of this assignment is to get you to create and use graphs, implement various
algorithms on graphs, and further improve your programming skills.
As discussed in class and the first tutorial, for each problem you will be provided with
a description of the problem and a set of tests. These tests can be run on the submission
system (Mimir) or on the unix server for this course. You can also use these tests on your
own computer as illustrated in the first tutorial. Your code must compile. If it does not
compile, you will receive a 0 on the assignment.
Figure 1: https://meepletown.com/wp-content/uploads/2011/03/TTR.jpg (Retrieved
on February 12, 2019)
Background: Ticket to Ride, the Board Game
In a popular board game, called“Ticket to Ride”1
, the goal of the game is to build a rail
network that covers the routes each player is given. A route is specified by the end-point
cities, and is constructed by building segments illustrated on the game board above. For
example, to build a route between Boston and Winnipeg, a player may choose to build the
segments: Boston to Montreal, Montreal to Toronto, Toronto to Duluth, and Duluth to
Winnipeg. The longer the segments the more expensive they are to build, and routes with
more segments take longer to build. Thus, it is in the player’s interest to build the routes
she is allocated in the most efficient way possible.
1Published by Days of Wonder
1
CSCI2110 Winter 2019 Assignment 6
Problem: Minimize Network Length
Given a game board of rail segments and a list of routes, your task is to compute the total
cost of building a network of prescribed routes, assuming that the shortest distance for each
route is chosen.
For example, given the following game board and routes:
Boston 2 Montreal
Boston 2 New_York
Chicago 4 Toronto
Chicago 3 Pittsburgh
Montreal 3 New_York
Montreal 3 Toronto
New_York 2 Washington
New_York 2 Pittsburgh
Pittsburgh 2 Toronto
Pittsburgh 2 Washington
done
Washington Montreal
Chicago New_York
done
Figure 2: Sample of possible rail segments and two routes.
The resulting cost computation would be:
The rail network consists of:
Chicago 3 Pittsburgh
Montreal 3 New_York
New_York 2 Pittsburgh
New_York 2 Washington
The total cost is: 10
Figure 3: Segments and total cost of building a rail network for the specified routes and
game board in Figure 2
Your task is to create a program that reads a game board and routes, and computes
which segments should be constructed and the total cost.
Write a program called RouteCost.java that reads in a game board and routes from the
console (System.in) and outputs the set of segments to be built and the total cost.
2
CSCI2110 Winter 2019 Assignment 6
Input
Your program should read in the input using a Scanner object, which is instantiated with
System.in. The input will comprise two sections with one or more lines in each section. The
first section contains the game board and comprises zero or more lines of the form
C1 L C2
where C1 and C2 are the end-points of a segment on the game board and L is the length
of the segment. E.g.,“Toronto 3 Montreal”. The section is terminated by a single word
“done”.
The second section contains the routes and comprises zero or more lines of the form
C1 C1
where C1 and C2 are the end-points of a route, comprising one or more segments. E.g.,
“Montreal Washington”. The section is terminated by a single word“done”.
Hint: All you need to use are the next() and nextInt() methods of the Scanner object.
Semantics
The game board is connected and all the city names are single words, e.g.,“Las_Vegas”.
You may assume that all game boards and all routes will be valid. All routes will have
distinct end-points (no cycles or 0-length routes).
The segments are bidirectional, i.e., can be used in either direction, and the game board
represents a weighted undirected graph. Routes may intersect and may share segments.
Segments need only be counted once though.
The cost of a route is the sum of the lengths of the segments in the route. A rail network
is considered minimal if each route has minimum cost.
Output
Your program should output to System.out. Each line should be terminated by a new line
character. The output should begin with the line:
The rail network consists of:
followed by the list of segments used in the rail network. Each segment should be indented
two (2) spaces, and the segments should be in sorted order, where the (C1, L, C2) precedes
(C if C1 lexically precedes C01, or if C1 equals C01, then C2 must lexically precede C02.
The format of the segments is the same format as the input.
The list of segments should be followed by the line
The total cost is: T
where T is the sum of lengths of the segments. See Figure 3 for an example.
3
CSCI2110 Winter 2019 Assignment 6
Example
Sample Input Sample Output
Charleston 2 Raleigh
Chicago 3 Pittsburgh
Chicago 2 Saint_Louis
Chicago 4 Omaha
Chicago 3 Duluth
Dallas 2 Little_Rock
Dallas 2 Oklahoma_City
Denver 4 Omaha
Denver 4 Kansas_City
Denver 4 Oklahoma_City
Denver 2 Santa_Fe
Denver 3 Salt_Lake_City
Duluth 2 Omaha
Duluth 6 Helena
Helena 4 Winnipeg
Helena 5 Omaha
Helena 4 Denver
Helena 3 Salt_Lake_City
Kansas_City 2 Saint_Louis
Kansas_City 2 Oklahoma_City
Kansas_City 1 Omaha
Las_Vegas 3 Salt_Lake_City
Little_Rock 3 Nashville
Little_Rock 2 Oklahoma_City
Little_Rock 2 Saint_Louis
Nashville 3 Raleigh
Nashville 2 Saint_Louis
Nashville 4 Pittsburgh
New_York 2 Washington
New_York 2 Pittsburgh
Oklahoma_City 3 Santa_Fe
Pittsburgh 2 Washington
Pittsburgh 2 Raleigh
Pittsburgh 5 Saint_Louis
Raleigh 2 Washington
Saint_Louis 2 Chicago
done
Denver Washington
Chicago Oklahoma_City
done
The rail network consists of:
Chicago 2 Saint_Louis
Denver 4 Kansas_City
Kansas_City 2 Saint_Louis
Little_Rock 2 Oklahoma_City
Little_Rock 2 Saint_Louis
Nashville 3 Raleigh
Nashville 2 Saint_Louis
Raleigh 2 Washington
The total cost is: 19
4
CSCI2110 Winter 2019 Assignment 6
Hints and Suggestions
Use a 2-phase algorithm: Create a weighted graph representing the game board. Then,
use Dijkstra’s shortest weighted path algorithm to find the shortest routes.
The sample solution is under 200 lines of code.
Your code must be well commented and indented. Please see the Assignments section
for this course on Brightspace for Code Style Guidelines.
You may assume that all input will be correct.
Be sure to test your programs using the provided tests or Mimir.
Grading
The assignment will be graded based on three criteria:
Functionality“Does it work according to specifications?”. This is determined in an automated
fashion by running your program on a number of inputs and ensuring that the
outputs match the expected outputs. The score is determined based on the number
of tests that your program passes. So, if your program passes t
T
tests, you will receive
that proportion of the marks.
Quality of Solution“Is it a good solution?”This considers whether the solution is correct,
efficient, covers boundary conditions, does not have any obvious bugs, etc. This is
determined by visual inspection of the code. Initially full marks are given to each
solution and marks are deducted based on faults found in the solution.
Code Clarity“Is it well written?”This considers whether the solution is properly formatted,
well documented, and follows coding style guidelines.
If your program does not compile, it is considered non-functional and of extremely poor
quality, meaning you will receive 0 for the solution.
Marks
Functionality 20
Quality of Solution 20
Code Clarity 10
Total 50
Table 1: Marking scheme for Assignment 6.
What to Hand In
Submit the source files for your program via Mimir as described in the first tutorial. A
link to Mimir is available on Brightspace. At least one of the submitted files must be
RouteCost.java, which is where the main program starts to run. If you have more than
one Java file to submit, place them all in a zip file and submit that.
WX：codehelp