Software Design and Implementation
Objectives
- Practice breaking a larger problem down into smaller "mental chunks"using functions
- Gain practice using loops and modulus (%)
Introduction to Top-Down Design
A good way to design large programming problems is to use functions to break them down into a series of smaller sub-problems, which can be solved somewhat independently and then combined to arrive at a complete solution. You can first essentially focus your attention on solving each piece and not get confused with the parts of the program. After checking that each function works correctly (for a set of inputs, it produces the expected output), you can then start to stitch the pieces together, now factoring in how they interlock. Such a process is methodical and reduces the chances of unexpected errors appearing because something you for one function has unintended consequences when working with another one.This technique which is called top-down-design, in which the programmer breaks the algorithm down into smaller and sub-algorithms. A solution derived from such a planned-out design will tend to be composed of small, manageable code segments which :
- tackle a specific smaller task
- are self-contained, meaning they can be understood like a black-box
- will likely be easier to write
- will be easier to test and debug, so will save you time in the long run!
Pseudocode is an outline of the logic a program in regular English. It uses the structural conventions of a programming language but is intended for a human, not a machine, to read. In the process of creating the pseudocode, the comments describing each function will be easier for others to understand and later modify the code as necessary (a vital skill in the programming industry!)
In addition to these good programming practices, this lab is designed to reinforce many of the ideas already introduced in the class such as looping and the remainder or modulus (%) function.
The Game of Nim
Nim is a game of logic and strategy. The goal of Nim is to be the player who removes the last of some group of items like balls or protons from a pile. A player must remove some number during their turn. The player who removes the last one wins. You can try a version of the game at: http://education.jlab.org/nim/index.html against the computer. In this version, there are 10 protons in a pile, and you and the computer are each allowed to take either 1 or 2 protons each time. The player who takes the last proton wins!The instructions
You may work alone or with a partner.A key idea in this teamwork is to use fruitful functions for for returning values. Note that when a function returns a value, it is typical to put the value into a variable or use it directly.
The following examples illustrate these ideas and also utilize modulus:
Your task is to create the game of Nim that works as follows:
- The human player will give the program the number of balls to start (this number is 15 or higher).
- The player will then play against the computer with the human player going first.
- The player and the computer will then take turns removing 1 to 4 balls from the pile.
- During the human player's turn, your program will need to ask the human player to input the number of balls which is to be removed.
- The player who takes the last ball wins!
Note that for all labs in addition to writing the program, you must also do a short lab write-up.
Hints and Requirements:
- Use functions to break code into smaller logical groupings for
easier debugging.
- After asking the human player for the number of balls to start, test it to make sure it is 15 or larger. Use a loop to allow the player reenter the number until it is 15 or larger.
- You will also need to use a loop in order to have play continue until the last ball is picked up.
- In the loop, you will need to alternate between the human player and the computer, but you may assume the human always plays first.
- When it is the human player's turn, your program will ask him/her to input the number of balls they wish to remove. Test this input to make sure it is between 1 and 4, using a loop to continually ask for the number of balls until it is valid (i.e. between 1 and 4).
- Create a fruitful function which determine how many balls the
computer will pick up using the following strategy:
- An optimal strategy for this version of Nim is to try to
make sure that it will be the opponent's turn to play when the
number of balls in the pile becomes 5. Thus, if the computer
will play so that a multiple of 5 balls is always left in the
pile, then the computer will win.
How can one implement this?
The computer should take sufficiently many balls from the pile each time to leave the opponent with a multiple of 5 balls. (Hint: use the modulus % function here! See example programs above.) - If it is not possible to leave the opponent with a pile of balls that is a multiple of 5, then the computer is going to lose unless the human player makes a mistake. In this case, have the computer take a randomly chosen number of balls from the pile, since any strategy is as good as another.
- Return the number of balls the computer will take.
- An optimal strategy for this version of Nim is to try to
make sure that it will be the opponent's turn to play when the
number of balls in the pile becomes 5. Thus, if the computer
will play so that a multiple of 5 balls is always left in the
pile, then the computer will win.
- Be sure to announce who has won!
- Be sure to include our standard header at the top of your program with name, username, assignment number, purpose and acknowledgements.
- You may optionally use graphics, but please make the logic work first because debugging with graphics is harder.
- Also, please be sure to include comments for the sections in your code which draws the different shapes.
- As stated above, you must also complete and submit a short lab write-up in addition to the program.
When you are finished writing and testing your program, drop your source code, username(s)-L1.py, and your Microsoft Word Lab write-up username(s)-L1.doc into the L1 dropbox in Moodle.