Prog 1: Toothpicks

1/27 Update: Submission instructions changed to indicate you must turn in a .cpp file that is not zipped.  This will allow us to edit it online within Blackboard.

Once while waiting for food to show up at a restaurant I was shown a puzzle using toothpicks. Write a C++ program that allows you to explore possible solutions to this puzzle. 

Sample Runs

See a video demo of running the program:

Running the program should look like the following, where user input is shown in bold letters:

Program #1: Toothpicks  Class: CS 141           Author: Dale Reed       Lab: Tues 5am           System:  C++ Mac Xcode   Welcome to the Toothpick Puzzle, where the goal is to get an equal     number of toothpicks in each stack, in three moves.                                      Stack:   A   B   C       Number of Toothpicks:  11   7   6      A move consists of moving toothpicks from one stack to a second stack,      where the number of toothpicks moved is exactly the number that is in the   destination stack.  In other words, to move from stack B (7 toothpicks)     to stack C (6) as shown above, we would move 6 from B to C, leaving us      with 1 in B and 12 in stack C.     Here we go...                      Stack:   A   B   C      Number of Toothpicks:  11   7   6  1. Enter FROM and TO stack letters: B C                   Stack:   A   B   C      Number of Toothpicks:  11   1  12  2. Enter FROM and TO stack letters: CA                   Stack:   A   B   C      Number of Toothpicks:  22   1   1  3. Enter FROM and TO stack letters: ab                   Stack:   A   B   C      Number of Toothpicks:  21   2   1  Nope, sorry, that's not it.  Try again. 

Note that when you run your program, input doesn't have to appear in bold. Your program must accept user input with and without spaces between the letters, and in upper or lower case.  Note that only valid moves are allowed, as shown below in step 2 when running your program again: 

Program #1: Toothpicks  Class: CS 141           Author: Dale Reed       Lab: Tues 5am           System:  C++ Mac Xcode   Welcome to the Toothpick Puzzle, where the goal is to get an equal     number of toothpicks in each stack, in three moves.                                      Stack:   A   B   C       Number of Toothpicks:  11   7   6      A move consists of moving toothpicks from one stack to a second stack,      where the number of toothpicks moved is exactly the number that is in the   destination stack.  In other words, to move from stack B (7 toothpicks)     to stack C (6) as shown above, we would move 6 from B to C, leaving us      with 1 in B and 12 in stack C.     Here we go...                      Stack:   A   B   C      Number of Toothpicks:  11   7   6  1. Enter FROM and TO stack letters: a c                   Stack:   A   B   C      Number of Toothpicks:   5   7  12  2. Enter FROM and TO stack letters: ab    Sorry, not enough toothpicks in A. Retry...  2. Enter FROM and TO stack letters: ca                   Stack:   A   B   C      Number of Toothpicks:  10   7   7  3. Enter FROM and TO stack letters: ab                   Stack:   A   B   C      Number of Toothpicks:   3  14   7  Nope, sorry, that's not it.  Try again. Ending program...  

What You Need to Know

• Environment:  How to use some environment to edit, compile and run a program

• C++ Language: simple input ( cin) and output (cout); Formatting the width of output numbers using setw( 4); Using variables; The assignment statement (=); Arithmetic operators (including +,-,*, /); Repeating a group of statements using a while loop; Using continue within a while loop; Choosing between alternatives using an if statement.

• Submitting: Zipping up your program; Turning in your program using Blackboard.

Notes

1. Read the parts of our online Zybook that you need to use in this program.

   1. See the sample program sample.cpp, which gives you a good starting point, as well as illustrates various programming concepts you need for this program. 

2. You may work ahead and use concepts we have not yet discussed in class if you would like to. Though not necessary, dividing up your code using functions would simplify your solution.

• 1. Make sure you read the syllabus regarding the grading criteria. Particularly on the first program, students tend to lose points for not documenting adequately, for not choosing meaningful variable names, and for not including the required header within their code.  Make your program output look exactly as specified. That way it makes it easier for us to give you a good grade. 

Steps

Work on your program one step at a time, following your own instincts on what those steps are.  If you get stuck then using the following sequence may be helpful:

• • 1.  Create a program with just an int main() function that prints out "Hello" using a cout statement.

    2. Add the header documentation, so you don't forget later!

    3. Add code inside main() to display your ID information (program, class, author, lab, etc).

    4. Add code inside main() to display the instructions.

    5. Inside main() declare two char variables that you will use to store which stack to move from, and which stack to move to.

    6. Declare three int variables and initialize them to have the starting number of toothpicks for each stack.

    7. Write the code to display the stacks, using the three stack variables.  Thus if the values in the variables were to be changed, the output would change as well.

    8. Prompt for user input for the source and destination stacks.  Use cin to read in the user input into the two char variables you previously declared to store which stack you are moving from and to.

    9. Create an if statement to check if the from stack is 'A' and the to stack is 'B'.  Inside that if statement ensure that the source stack has enough matches.  If it doesn't, display an error message.  If there are enough matches, make the move by updating the values in the two stacks.  Then again display the stacks, using the three stack variables, which should now reflect the move just made.

    10. Write similar code to handle moves between all the other stack combinations.

    11. Put a while loop around the code that makes moves, and have it loop three times.  Each time through the loop display the loop counter variable as the move number 1 - 3.

    12. Within each move, when there is an error, use the continue statement to jump back up to the top of the loop to retry a move.

    13. At the end of your program use the stack values to display an appropriate error message.

Turning In Your Program

The name of the program you will turn in should be prog1 followed by your netid and the .cpp file extension.  In other words, if your netid is reed then your program would be called prog1reed.cpp   

Blackboard considers program source code as a threat and sometimes replaces random parts of it.  To avoid this you must also zip up the code you turn in.  To zip a file right-click on the single .cpp file to be turned in (e.g. prog1reed.cpp) and select "Send To" and then select the "compress" menu option. On a Mac simply right-click and then select the "compress" option.  The resulting file (for instance) will then be called prog1reed.zip 

Only turn in this single file, turning it in on Blackboard into the Assignment Program1: Toothpicks.  

Failing to follow these naming conventions or failing to turn in a zip file will result in a 5 point deduction.  (Note that I am not requesting some compression, but specifically zip compression).  Questions about this?  Ask on Piazza, or see a member of the instructional staff.

You may turn in multiple versions, but only the latest version will be graded.

Extra Credit (10 points) 

Do not turn in a "regular" version of the program if you are planning on doing the extra credit.  If you turn in both, then you will not be eligible for any extra credit points.

For the extra credit version the program prompts for the number of toothpicks in each stack and then figures out the answer on its own, if there is one. If there is no solution it should print the message "No solution is possible." For this version the only user input is the number of initial toothpicks in the 3 stacks. Running this program would look like:

• • 1. Program #1: Toothpicks  Class: CS 141           Author: Dale Reed       Lab: Tues 5am           System:  C++ Mac Xcode   Welcome to the Toothpick Puzzle, where the goal is to get an equal     number of toothpicks in each stack, in three moves.                                      Stack:   A   B   C       Number of Toothpicks:  11   7   6      A move consists of moving toothpicks from one stack to a second stack,      where the number of toothpicks moved is exactly the number that is in the   destination stack.  In other words, to move from stack B (7 toothpicks)     to stack C (6) as shown above, we would move 6 from B to C, leaving us      with 1 in B and 12 in stack C.        In this version you choose the number of toothpicks in each stack and then  the computer figures out the answer for you.  Please enter the starting number of toothpicks in each stack: 3 24 9                   Stack:   A   B   C     Number of Toothpicks:   3  24   9     1. From B to A, giving:  6  21   9  2. From B to C, giving:  6  12  18  3. From C to A, giving: 12  12  12  Ending program...      

1. Turn in the extra credit version on Blackboard into the Assignment Program1 Extra Credit, otherwise using the same naming convention used for the regular version.  For the extra credit version the rubric for the 50 points for program execution will entirely be awarded on whether or not the program finds and displays the solution if there is one, or displays the appropriate message if there isn't one. (Added 1/24)

Grading Rubric

Inside your program itself you must include the following grading rubric, just below your header documentation, as shown below.  We will use this when grading your program as a place to annotate and list any deductions taken off within each category.  Note that this is in your code but is within a comment block so should not appear on the screen when you run your program.  

/* ------------------------------------------------    prog1toothpicks.cpp      Program #1: Toothpicks: Puzzle to equalize the number of toothpicks in three stacks.    Class: CS 141    Author: Dale Reed    Lab: Tues 5am    System:  C++ Mac Xcode     Grading Rubric:     50 Execution points          5 Displays header info on screen when run          5 Displays instructions          5 Output is formatted as shown in sample output          3 Handles both upper and lower case input          5 Input can be adjacent or have spaces between them         15 Makes moves correctly         10 Handles the specified error conditions          2 Gives appropriate end of program messages     45 Programming Style (Given only if program runs substantially correctly)          5 Program naming convention is followed         10 Meaningful identifier names         10 Comments: Has header.  Comments on each block of code         10 Appropriate data and control structures         10 Code Layout: Appropriate indentation and blank lines    ------------------------------------------------ */ 

Additional rubric deduction details are given below.

The 50 points for program execution will be allocated as follows:

1.      5 points:  Displays header information with program name, author name, lab, and system.

2.      5 points:  Displays game instructions

3.      5 points:  Output is spaced and lined up as shown in the sample output

4.      3 points:  Input of stack letters can be both upper and lower-case 

5.      5 points:  Input of stack letters can be adjacent or have one or more spaces between them

6.    15 points:  Program correctly updates stack values as determined by the input

7.    10 points:  Attempt to move smaller stack to a larger stack results in error message, no stack updates, 

8.                      and allows retrying move, with same move number

9.      2 points:  Appropriate message is given at end of game. 

10.                      If the three stacks do not have the same number of toothpicks, the message is:

11.                          Nope, sorry, that's not it. Try again.

12.                      If the three stacks do have the same number of toothpicks, the message is:

13.                         Congratulations!  You did it!  Great job!   

The 45 points for program style will be allocated as described below. (While your personal style may disagree with the standards shown, it is important that be able to follow a coding standard that is given to you.)

• 1. 5 points:  The name of the program you will turn in should be prog1 followed by your netid and the .cpp file extension.  In other words, if your netid is reed then your program would be called prog1reed.cpp. The name of the zip file must be prog1reed.zip

  2. 10 points:  Meaningful Identifier Names. Identifier names should indicate their purpose. Names should be in lowerCamelCase, where the first letter is lower-case and the first letter of each new word is upper case, and the words are concatenated together, e.g. gradesSum. 

     • 2 points penalty: Variable names are not all meaningful

     • 2 points penalty: User-defined function names (if other functions are used) are not written in lowerCamelCase

  3. 10 points: Comments. Every section of code (but not every line!) must have a short description stating its purpose.  Comments should be easily identifiable. A person should be able to understand your program by reading only the comments. 

     • 2 points penalty: You do not have at least one line of comments for each function, and do not have at least one comment for each principal section of your program

     • 4 point penalty:  If you do use functions, each function does not have documentation at the top indicating the purpose of the function, what it receives, and what it returns. 

  4. 10 points: Appropriate data and control structures: Appropriate looping and decision structures are used. 

     • 2 points penalty: You should not have any global variables (outside of main and outside of any other function) for this program.  All variables should be declared inside of main() unless used locally in a function.

     • 5 points penalty: You should be using a single loop to get user input and process it

     • 3 points penalty: Your code to display the stacks should occur at most in two places

  5. 10 points: Code Layout. Different nested levels should have different indentation, where statements at the same level should have the same indentation. Indent at least 3 spaces. Use either spaces or tabs consistently, otherwise printouts will be messed up.  Leave at most a single blank line between sections of code, and at most two blank lines between functions.

     • 1 point penalty: Indentation is not the same at the same logical level in your program

     • 3 point penalty: There are not two blank lines between functions or there are excessive (more than 3) adjacent blank lines

     • 2 point penalty: There are large sections of commented-out code that were part of the development process and should have been removed.

     • 2 points penalty: The explanatory header with identifying information is not present at the top of your program, as described in the syllabus.