CSE Programming & Algorithms for Engineers Spring 2018 Programming Assignment 5: Putting it all together 1 Setting up the Programming Environment 1. Create a new directory (folder) called hw5 and move to that directory. 2. Copy the ?le discs_solution.exe from the directory /class/cse1222/24924/hw5 into the current directory. Copy the ?le discs_template.cpp and rename it discs.cpp using the following command: cp /class/cse1222/24924/hw5/discs_template.cpp discs.cpp 2 Work by Yourself All lab and programming assignments are to be done by yourself. You may discuss labs or assignments with other students in the class but DO NOT LOOK AT ANYONES CODE OTHER THAN YOUR OWN. Needless to say, you should not share or copy anyone elses code. 3 Program Requirements E?ective commenting and tabbing will a?ect your grade. The style of your program should follow the style of the sample programs in the course notes. Your program should have the ?le name, your name, creation and last modi?cation dates and a brief description of the program in the comments at the top of the program. The declaration of every variable should have a comment. You will use functions in your program. Write a program for playing the game of NIM. Our version of the game starts with up to 20 pegs and up to 10 discs in each peg. Two players take turns removing discs from the pegs. On a players turn, she chooses a peg and removes one or more discs from that peg. She can remove all discs from the peg. The player who takes the last disc from the pegs (so that all pegs are empty) loses. This version of the game is called misere. Run the solution disc_solution.exe to play the game. Your program must produce exactly the same output as this solution. DO NOT delete the code already given to you in the code template. You must use the code given to you in the template in your solution. The algorithm for the game is provided below. Most steps in the algorithm should be implemented as function calls. You need to implement the algorithm and the functions as described below. You may implement additional functions to help you in writing your solution. Though, in order to receive full 1 credit you must follow the instructions in this assignment and de?ne these functions exactly as indicated. You will implement the following algorithm in the main function. Each line in the algorithm will correspond to a function call. Important! Write your code incrementally. This means you should write each function one at a time, check that it compiles and runs properly, test it, and then implement the next function. i. Prompt and read the number of pegs ii. Prompt and read the number of discs in each peg; iii. Draw the pegs with percentages; iv. Display statistics; v. while (some peg is NOT empty) do vi. Prompt and read the next players move (Prompt and read the peg to modify and the number of discs to remove from the peg); vii. Remove the speci?ed number of discs from the speci?ed peg; viii. if (all pegs are empty) then ix. Print a message congratulating the winning player. x. else xi. Redraw the pegs with percentages; xii. Display statistics; xiii. Change to the other player; xiv. end xv. end 1. All functions should be written AFTER the main procedure. 2. All function prototypes should be written for each function and placed BEFORE the main procedure. 3. Each function should have a comment explaining what it does. 4. Each function parameter should have a comment explaining the parameter. 2 5. Your program MUST NOT use any global variables nor any global constants. 6. In addition to implementing the above algorithm in the main function, you must de?ne the following constants and variables in the main function: - De?ne two constants to hold the maximum number pegs (20) and the maximum number of discs per peg (10). - The list of pegs will be stored in an array of integers, where each integer represents the number of discs in that peg. De?ne a pointer variable for this array (see the lecture notes on Arrays and Pointers). Also de?ne an integer to hold the size of this array. - De?ne a variable that represents the current player (1 or 2). 7. Important: PLEASE READ! The following description provides speci?cations for the functions you will write that includes input parameters and return values. You are responsible for implementing these functions as described in these speci?cations in order to receive full credit. These functions may call additional helper functions that you de?ne. You must determine good function names as well as good variable names for your function parameters and local variables. You must correctly identify whether a function parameter should be passed by value or passed by reference. In addition you must correctly determine whether a function parameter should be declared with the const speci?er. Remember, const is used to indicate that the function parameter is not modi?ed in the function (see the lecture notes). It may be applied to a parameter that is either passed by value or passed by reference. It allows code developers to better undertand your code and ensure that they (and you) adhere to your speci?cations if they want to modify the code. 8. Write a function to implement step (i) of the algorithm. De?ne the function to have one input parameter that holds the maximum number of pegs (see the constant de?ned above) and return an integer. Prompt the user for the number of pegs used in the game. If the number entered is not between 1 and the maximum number of pegs then display a warning message and prompt again. This is called input validation on the users input. 9. In the main function, allocate an array in the declared array pointer representing the list of pegs (see description above) to have the same size as the number of pegs returned from the function in step (i). 10. Write a procedure (this is a function that does not return a value and so is declared with a return type of void) that implements step (ii) of the algorithm. De?ne the procedure to have three input parameters: the array of pegs, the size of the array, and the maximum number of discs per peg (see the constant de?ned above). This procedure will traverse the array of pegs and call the following helper procedure for each peg in the list. 3 - Write a helper procedure that will prompt the user for the number of discs to place on this peg. If the number of discs entered for the peg is not between 1 and the maximum number of discs allowed then display a warning message and prompt again. De?ne this helper procedure to have three input parameters: the array entry for this peg (use pass by reference), the array index for this peg, and the maximum number of discs per peg. Important: Again, a procedure is a function that has no return value. You must de?ne these functions as procedures by de?ning their return type as void. 11. Write a procedure to draw the pegs to implement steps (iii) and (xi) of the algorithm. Draw each peg on its own row. In the row for peg i, there is a label peg i: followed by n %s where n is the number of discs in peg i. The procedure should output an empty line before and after the ?rst and last rows, respectively. For instance if peg 0 has 3 discs, peg 1 has zero discs, and peg 2 has 8 discs, the procedure (and helper procedures) should output: Peg 0: %%% (27.273%) Peg 1: (0.000%) Peg 2: %%%%%%%% (72.727%) De?ne the procedure to have two input parameters: the array of pegs and the size of the array. First, calculate the total number of discs in the array of pegs. Next, traverse the array of pegs and call a helper procedure to display each complete row. - Write the helper procedure to have three input parameters: the array index for this peg, the number of discs for this peg, and the total number of discs in the array of pegs. The percentage displayed at the end of each row is the fraction of discs on this peg given the total number of discs in the array of pegs (you just computed). Format each row using setw in iomanip and avoid using hard coded spaces. When there are ten or more pegs to display, your output must align the labels peg ?: and peg ??: appropriately, where ? is a digit. Use setw to format the text between peg and the :. Using setw, format the %s in a column of size ten that is left justi?ed (look up the left speci?er under iomanip). There needs to be ?ve spaces between the column of %s and the percentage. Do NOT hard code these ?ve spaces. Instead, use setw to format the last column for the percentage. Look up how to use the right speci?er in iomanip to help you solve this problem. Also, format the percentage to show three digits after the decimal place. Decide if additional helper functions/procedures would be useful here. 12. Write a procedure to display the statistics for the list of pegs that will be called in steps (iv) and (xii) of the algorithm. The statistics are 1) The pegs with the smallest number of discs, 2) The pegs with the largest number of discs, and 3) The average number of 4 discs per peg taking into account only pegs with discs. De?ne the procedure to have two input parameters: the array of pegs and the size of the array. This procedure will call three helper procedures. - Write a helper procedure to display the pegs with the smallest number of discs. This procedure will have two input parameters: the array of pegs and the size of the array. Note that there may be more than one peg with the smallest number of discs. - Write a helper procedure to display the pegs with the largest number of discs. This procedure will have two input parameters: the array of pegs and the size of the array. Note that there may be more than one peg with the largest number of discs. - Write a helper procedure to display the average number of discs per peg, but only taking into accout pegs with at least one disc. The average must be formatted to display two digits after the decimal place. 13. Write a function which returns true (boolean) if all the pegs have zero discs and returns false otherwise. Call this function to implement steps (v) and (viii) of the algorithm. Note that the same function will be used for both steps. 14. Write a procedure to implement step (vi) of the algorithm where the current player makes her next move. De?ne the procedure to have ?ve input parameters: the array of pegs, the size of the array, player id, which peg chosen by the player on this turn, and how many discs the player would like to remove from this peg. The player id is either the integer 1 or 2 to indicate which player is taking a turn. This procedure will perform two steps with the help of helper functions/procedures as speci?ed below: 1) Using the following helper functions and procedures, prompt and read for the peg from which to remove discs. If the player inputs an invalid peg id or chooses a peg with no discs then display a warning message and prompt again. These three helper functions/procedures will be called from this procedure. In addition, the last two helper procedures will call the ?rst helper function. - First, write a helper function to have one input parameter, the player id. Prompt the player to choose a peg (peg id) and then return this value. Thus, this helper function has a return type that is NOT void. Do not perform any input validation in this function. - Next, write a second helper procedure to have three input parameters: the player id, the peg selected by this player, and the total number of pegs (i.e., the size of the array of pegs). This procedure will validate the peg selected by this player, i.e. the peg selected must be between 0 and n - 1 where n is the total number of pegs. If the peg selected is invalid then the procedure displays a warning message and prompts for peg selection again by calling the ?rst helper function. - Finally, write a third helper procedure to have three input parameters: the array of pegs, the player id, and the peg selected by this player. This procedure will validate 5 whether the peg selected has at least one disc. If the peg selected is invalid then the procedure displays a warning message and prompts for peg selection again by calling the ?rst helper function. 2) Using the following helper function, prompt and read how many discs to remove from the chosen peg. If the player inputs an invalid number of discs then display a warning message and prompt again. The number of discs to remove must be positive and must not exceed the number of discs on the chosen peg. The following helper function will be called from this procedure and will perform the following task described below. This procedure will check if the returned value from the helper function is valid and prompt the user again if necessary. - Write a helper function to have two input parameters: the number of discs on the chosen peg and the peg id. The function will prompt the player for the number of discs to remove from the indicated peg and returns this value. Note this helper function will NOT perform any input validation checks. Instead the calling procedure will perform validation on the returned value from this helper function. 15. Write a procedure to implement step (vii) of the algorithm. De?ne the procedure to have three input parameters: the array of pegs, the peg id of the chosen peg, and the number of discs to remove. This function will modify the array of pegs by subtracting the speci?ed number of discs from the chosen peg. 16. Write a procedure to implement step (ix) of the algorithm. De?ne the procedure to have a single input parameter that holds the player id of the current player. The procedure will print a message congratulating the winning player. The message should identify who won (player 1 or player 2). 17. Write a procedure to implement step (xiii) of the algorithm. De?ne this procedure to have a single input parameter that holds the player id. This procedure will switch the turn to the other player. In other words, if the player indicated in the input parameter is 1, then the procedure should change this value to 2. If the player indicated in the input parameter is 2, then the procedure should change this value to 1. 18. Be sure to modify the header comments File, Created by, Creation Date, and Synopsis at the top of the ?le. Each synopsis should contain a brief description of what the program does. 19. Be sure that there is a comment documenting each variable. 20. Be sure that your if statements, for and while loops and blocks are properly indented.