This lab will have you and your lab partner implement an advanced game advisor for the game Ticket To Ride. In Part A, you finished implementing key graph algorithms that will prove essential to completing this week's lab. Many of the implementation details will be left to you, but this document will provide a general outline of game play.

To prevent confusion, here is some terminology used below:

• Route - a direct connection between two cities (i.e., an edge)
• Destination Ticket - a card specifying two cities in the graph that are not necessarily connected
• Resource Card or Train card - see a description of the game. This is required to claim routes, but not necessary for your implementation

A game of Ticket to Ride contains the following elements (We have bolded the elements you will have to represent in your game):

• A Game Board
• A deck of tickets to draw from
• Player 1's tickets
• Player 2-5's tickets
• A deck of colored train cards to draw from
• Player 1-5's held train cards
• Player 1's claimed routes
• Player 2-5's claimed routes (only in aggregate)
• Player 1's score
• Player 2-5's score

Note that based on these requirements, you are simply creating a game advisor for a single player. A single player can keep track of his/her status (except for held train cards) and also what routes remain on the board.

You will not be able to simulate the complete game from these requirements. Attending extensions for these elements is feasible, highly encouraged, but not required. Also, for claimed routes, you will only need to know what routes are no longer available for Player 1, not who actually owns them.

At a high level, your Ticket To Ride assistant will be able to:

• Load a map of the game board and deck of destination tickets from file
• Display a map of the game board as well as a map of the user's claimed routes
• Print available routes
• Claim routes (i.e., edges) when a user makes a play
• Draw three tickets and advise the user on which to select (e.g., it's point value and difficulty to complete)
• Show the status of held tickets
• Calculate a user's score

This week's lab will emphasize creativity, design, and efficiency. We have provided you some sample code to help get started, but you should not feel locked into using them as is. Your rough grade break down for this week's lab is:

1. 30% Part A requirements
2. 30% Part B requirements (i.e., satisfying the list above)
3. 30% Design/efficiency (is your design easy to follow? Are your choices for algorithms/implementation justified?)
4. 10% Creativity (going beyond the requirements)

#1 and #2 can be satisfied by simply following the instructions. #3 requires you to bring in concepts from other labs to make good choices. For example, how will you represent your map? tickets? How will you represent the user's claimed routes and the opponents claimed routes? How will you keep your main program clean (e.g., can you encapsulate the game as an object? Or use auxiliary header files as with Lab 4?). #4 requires you to go above and beyond. This includes adding functionality that is not specified, or making those functions required even more useful. Can you color the map? Can you make the game multi-player? How about representing a deck of train cards and the resources a user currently has? Can you advise a ticket by calculating connected components so a user knows what cities are already connected with one other, or ones that are not possible to reach no matter what the user does? Can you advise what route to grab next based on the tickets?

All initial files were released with part A. The relevant starting files for part B are listed below.

• ticketToRide.cpp - the main program
• ticket.h/.cpp - a class for representing a single destination ticket
• inputs/ - a folder containing files for defining your board as well as deck of tickets
• Makefile - you should remove your existing Makefile before running update35

As stated above, you can and should add your own files and you can and should modify existing code to meet your design.

This section details the behavior of the main menu.

Load a map and tickets

A function for loading a map has been provided. You should use this as a template for loading tickets, which is similar except there is no weight provided. Each line is formatted as:

City A:City B

Note that each vertex may contains spaces. Using the >> makes this tricky since it will only grab the string "City". On the other hand, getline grabs all inputs until it hits a new line character and puts into a string, e.g., "City A: City B". You can than parse this string as you see fit. See online documents or the given code for help.

Display a map

At a minimum, the user should be able to print a text as well as display a graphical representation of their board game. The map can either be the original game board or just the user's claimed routes. A possible implementation has been provided; feel free to modify this. Note that displaying the graph requires the GraphViz package. If you are working from home, comment these lines out or install the package.

Example:

Menu:
	(0) Exit
	(1) Print/display game board
	(2) Print/display my routes
	(3) Print available routes
	(4) Claim route for self
	(5) Claim route for opponent
	(6) Draw and select tickets
	(7) Print tickets and their status
	(8) Calculate current score

Enter Choice: 1

Saint Louis: {Little Rock, Nashville}
Little Rock: {Oklahoma City, Saint Louis, Nashville}
Oklahoma City: {Little Rock}
Nashville: {Little Rock, Saint Louis}

Your map should look similar to the following:

Print available routes

Print in text all of the unclaimed routes (i.e., edges) on the original map. That is, if the user or one of the opponents has already claimed an edge, it should not be printed here. At a minimum, you should provide the cities at the ends of the edge as well as the number of cars needed to build the route (i.e., the edge length). This will help a user see what the possible plays are.

Example (note: the menu will be omitted from the remaining examples to save space, but should appear in your program):

MENU
Enter choice: 3

Available Routes: 
-----------------

	Saint Louis --- Little Rock : 2 Train Cars
	Saint Louis --- Nashville : 2 Train Cars
	Little Rock --- Oklahoma City : 2 Train Cars
	Little Rock --- Nashville : 3 Train Cars

Claim route

Either the main player or one of their opponents can claim an available route. You should ask the player which cities are to be connected by the route. (ask the player directly; do not offer a list of options to select from) If (a) one of the cities is not in the map, (b) the main player owns the route, (c) an opponent owns the route, or (d) the route never existed, you should print a detailed error and return to the main menu (i.e., do not crash). You should also print the number of resources required (i.e., the edge weight) as well as the point value of the route (see "Calculating Scores"). See below for an example user interface experience.

Example:

Enter choice: 4   

Enter city: St. Louis
Error: That city does not exist.  Returning to main menu.

MENU
Enter choice: 4

Enter city: Saint Louis
Enter city: Oklahoma City
Error: Route is not available.  Returning to main menu.

MENU
Enter choice: 4

Enter city: Little Rock
Enter city: Nashville
You successfully claimed the route for 4 points. Please discard 3 train cards.

MENU
Enter choice: 5

Enter city: Nashville 
Enter city: Little Rock
Error: Route is not available.  Returning to main menu.

MENU
Enter choice: 2

Little Rock: {Nashville}
Nashville: {Little Rock}

MENU
Enter choice: 5

Enter city: Little Rock
Enter city: Saint Louis
Your opponent successfully claimed the route for 2 points.

MENU
Enter choice: 3

Available Routes: 
-----------------

	Saint Louis --- Nashville : 2 Train Cars
	Little Rock --- Oklahoma City : 2 Train Cars

Draw Tickets

This option will bring in many of your graph algorithms. Your method should:

1. Draw (upto) 3 tickets randomly from the deck of tickets
   For each ticket:
   
2. calculate its point value (the minimum cost path on the original board)
3. print whether the two cities can still be connected by the user - that is, given the claimed routes by the user and available routes, can the user even find a path?
4. compute the quickest number of plays required to complete - that is, for the original board, what is the shortest length path to connect the cities
5. calculate the minimum resources to complete - that is, given the user's claimed routes and available routes, how many resources (train cards) does this user need at a minimum to complete the path. Note that the edge weights correspond to the resources needed, and a user's claimed routes don't need any more resources (i.e., have a cost of 0).
6. Lastly, have the user select at least one of the three tickets and add it to the hand of tickets
7. Recommended extension: Before the game starts, you should require the user to pick at least two tickets out of three drawn. After that, you only need to draw tickets when the user requests, and they are only required to select at least 1.

Note that each of these corresponds to a graph algorithm covered in class. But your inputs may require some thought, in particular for the minimum resources to complete (#5). #4 is tricky to do with the current board, so you are required to only do it for the original board. You must print the actual path. As an extension, think of how to solve this problem on the current board.

Also, you should recall how to use randomness from earlier labs. It may be easier to shuffle the deck when reading the file and then simply add "discarded" tickets to the bottom of the pile. SEE BELOW FOR EXAMPLE.

Show ticket status

For each ticket in the user's hand:

1. Print out the two cities on the ticket and its point value
2. Print whether the user has satisfied the ticket
3. If not, print whether the user can still complete the path
4. If it can be reached, print the number of resources needed to complete the path (the same as #4 in the previous list)

An example of this is shown below. As an extension, consider printing the routes needed to complete the path with the fewest number of resources.

Calculate user's score

Given the user's claimed routes and destination tickets, calculate their current score. You should print out all claimed routes and their point value. A route's weight translates into points as follows:

• 1 resource : 1 point
• 2 resources : 2 points
• 3 resources : 4 points
• 4 resources : 7 points
• 5 resources : 10 points
• 6 resources : 15 points

That is, higher cost edges lead to more points. Next you should print out each ticket and its point value. If a ticket was completed, the user adds the point value. If not completed, you subtract the points. The following is an example run that demonstrates drawing tickets, printing ticket status, and calculating the final score:

GraphViz. In this lab, you'll use neato and the graphViz package to generate your map board. You're not required to change much about the board generation, but it is a good area for creativity. Here is some documentation on graphViz:

• GraphViz website.
• The neato user's manual.

See the provided code for a specific example.

Below is a sample run of what your user interface might look like.

$ ./ticketToRide inputs/smallBoard inputs/smallTickets 

Select a ticket to add to your hand: 
  1) Saint Louis to Oklahoma City for 4 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 4
  2) Nashville to Oklahoma City for 5 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 5
  3) Little Rock to Nashville for 3 points
		Achievable.
		Fewest routes needed (original board): 1.
		Fewest train cars needed (current board): 3

Enter choice or 0 to discard remaining tickets: 0
You are required to select at least 2 more tickets

Select a ticket to add to your hand: 
  1) Saint Louis to Oklahoma City for 4 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 4
  2) Nashville to Oklahoma City for 5 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 5
  3) Little Rock to Nashville for 3 points
		Achievable.
		Fewest routes needed (original board): 1.
		Fewest train cars needed (current board): 3

Enter choice or 0 to discard remaining tickets: 3

Select a ticket to add to your hand: 
  1) Saint Louis to Oklahoma City for 4 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 4
  2) Nashville to Oklahoma City for 5 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 5

Enter choice or 0 to discard remaining tickets: 1

Select a ticket to add to your hand: 
  1) Nashville to Oklahoma City for 5 points
		Achievable.
		Fewest routes needed (original board): 2.
		Fewest train cars needed (current board): 5

Enter choice or 0 to discard remaining tickets: 0

MENU

Enter choice: 7


Your current destination tickets and their status: 
0) Little Rock to Nashville for 3 points
	Ticket not punched, but path still exists
	You need at least 3 cars to complete the path
1) Saint Louis to Oklahoma City for 4 points
	Ticket not punched, but path still exists
	You need at least 4 cars to complete the path

MENU

Enter choice: 4

Enter city: Little Rock
Enter city: Saint Louis 
You successfully claimed the route for 2 points. Please discard 2 train cards.

MENU

Enter choice: 7


Your current destination tickets and their status: 
0) Little Rock to Nashville for 3 points
	Ticket not punched, but path still exists
	You need at least 2 cars to complete the path
1) Saint Louis to Oklahoma City for 4 points
	Ticket not punched, but path still exists
	You need at least 2 cars to complete the path

MENU

Enter choice: 5

Enter city: Saint Louis
Enter city: Nashville
Your opponent successfully claimed the route for 2 points.

MENU

Enter choice: 7


Your current destination tickets and their status: 
0) Little Rock to Nashville for 3 points
	Ticket not punched, but path still exists
	You need at least 3 cars to complete the path
1) Saint Louis to Oklahoma City for 4 points
	Ticket not punched, but path still exists
	You need at least 2 cars to complete the path

MENU

Enter choice: 4

Enter city: Little Rock
Enter city: Nashville
You successfully claimed the route for 4 points. Please discard 3 train cards.

MENU

Enter choice: 7


Your current destination tickets and their status: 
0) Little Rock to Nashville for 3 points
	Ticket punched
1) Saint Louis to Oklahoma City for 4 points
	Ticket not punched, but path still exists
	You need at least 2 cars to complete the path

MENU

Enter choice: 5

Enter city: Little Rock
Enter city: Oklahoma City
Your opponent successfully claimed the route for 2 points.

MENU

Enter choice: 7


Your current destination tickets and their status: 
0) Little Rock to Nashville for 3 points
	Ticket punched
1) Saint Louis to Oklahoma City for 4 points
	It is impossible to punch this ticket

MENU

Enter choice: 6


Select a ticket to add to your hand: 
  1) Nashville to Oklahoma City for 5 points
		Ticket cannot be completed

Enter choice or 0 to discard remaining tickets: 0
You are required to select at least 1 more tickets

Select a ticket to add to your hand: 
  1) Nashville to Oklahoma City for 5 points
		Ticket cannot be completed

Enter choice or 0 to discard remaining tickets: 1

MENU

Enter choice: 8

Your current score breakdown: 
-----------------------------

Routes: 
	Saint Louis -- Little Rock: +2 points
	Little Rock -- Nashville: +4 points

Destination tickets: 
	Little Rock --- Nashville: +3 points
	Saint Louis --- Oklahoma City: -4 points
	Nashville --- Oklahoma City: -5 points

Total: +0 points

MENU

Enter choice: 0

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.