CS 106: Assignment 01

CS 106 Winter 2017

Assignment 01: Arrays and Strings

Due: Sunday January 22nd, 11:59pm

No starter code

Question 1 Nim

Nim is a simple abstract game, often used by mathematicians to study the logical rules that underlie games in general. You start with any number of "stacks", each containing any number of "tokens". Two players alternate turns, each taking as many tokens as they want from any one stack. The player who removes the last token wins. That's the whole game. Try it—grab a friend and play with the coins you've got in your pockets.

In this question you will create a Processing sketch that allows you to play Nim interactively. We will use a simple visualization in which each stack is a column of tokens drawn using Processing shapes like circles or squares (though you can choose any shape you want).

Base requirements

You should begin by constructing a Nim game that satisfies the following base requirements, which will earn you 80% of the correctness marks for the assignment:

Draw the game board as a sequence of vertical columns of tokens rising up from the bottom (or near the bottom) of the window. The individual tokens can be any shape, colour, or other graphic, but they can't touch or overlap, and must be fully visible in the sketch window. One stack should always be "active"—that's the one you'll take tokens from. The active stack should be clearly indicated in the sketch (by outlining it, or colouring it, or drawing an arrow under it, etc.).
Your game must use at least three, and not more than six stacks. There should be a predefined maximum height for the stacks; you can choose this height, but make it at least five, and not more than eight. When the game starts, initialize your stacks so each one has some random number of tokens in a range from one to the predefined maximum.
Use the arrow keys and number keys to control the game. The left and right arrow keys move the active stack indicator to the left and right. It should not be possible to use the arrow keys to move past the left or right edges of the board. The number keys 1 through 8 take some number of tokens from the active stack. If you ask to take more tokens than are in the active stack, nothing happens.
Somewhere in the sketch window, there should be text of the form "NN tokens remaining", where "NN" is the number of tokens left to be taken in the game. You can use any font, size, and placement, as long as the text doesn't overlap the rest of the game.

As an example, here is a lo-fi mock-up of one possible Nim interface. The third stack is the active one.

A Nim game implementing these base requirements can be written in about 70–80 lines of code, not counting comments. Here are a few hints and tips for keeping the code simple and tidy:

Use an array of integers to represent the current Nim board, where each element of the array is the number of tokens in a stack. For example, here's an array together with the stacks it represents. (Of course, your array won't have four fixed values in it, like this one.)

You can draw the tokens using nested loops, which you learned about in CS 105.
Use an integer global variable to keep track of the current active stack (the integer refers to the index of that stack in the array).
Use global constants at the top of your sketch for the number of stacks and maximum stack size. Use those constants by name throughout your code, instead of just using the numbers directly (it's good coding style, after all).
It's tempting to write a chain of eight if statements to check for presses of the eight number keys. It turns out there's a more concise way, which you should use, based on the fact that characters are represented internally by numbers:
```
if( (key >= '1') && (key <= '8') ) {
  // We get here only if a number between 1 and 8 was pressed.
  int numTokens = (key - '0');
  // numTokens is an int corresponding to the number key that was pressed.
} 
```
Detecting when the arrow keys are pressed is nearly as easy as detecting presses of other keys. See the online Processing reference for the keyCode variable for an example.

Final requirement

The base requirements above will produce a complete, working game. The game comes to a natural end when all of the stacks have been emptied, at which point no legal moves should remain. The base requirements are worth 80% of the correctness marks for the assignment. The other 20% are awarded for one final requirement:

When a stack is emptied, it is removed from the array. That is, the array of stacks is replaced by an array that's one element shorter, in which all non-empty stacks to the right of the just-emptied one are shifted to the left. That way, the board is always drawn as side-by-side non-empty columns, at least until the game is over.

Note that when you do this, you should make sure that the variable you're using to keep track of the active stack remains valid, and that it's disabled when the game ends.

Removing an element from an array can be tricky, so here are a few tips. Remember, your goal isn't to modify the original array in place. Instead, make a new array that's one element shorter and then copy the pieces you want from the original array into it. Then replace the old array by the new one. This can actually be done in a single, clever line of code containing one call to concat() and two to subset(); but it's entirely reasonable to construct the new array explicitly using a for loop.

Enhancements

Many enhancements are possible for this game, and we're interested in seeing what you come up with, which is why the base requirements do not spell out the look of the game in much detail. We will award bonus marks for sketches that demonstrate good design, novelty, or the use of advanced programming ideas. If there's anything you want to bring to our attention, or if you change the interface in a way that requires special documentation, please include a comment at the top of your sketch (under your name and ID) that tells us what to look for.

Here are a few enhancement suggestions.

Make it pretty. Devise a pleasing layout for the board, good colours and shapes, and any other eye candy you want to add.
Improve the playability. Add a way to restart the game. Maybe add a mouse-based interface for selecting tokens to remove.
Make it truly two-player. Add logic so that the sketch is aware that there are two players who alternate turns. Clearly indicate whose turn it is, and put up a message when the game ends to inform the players who won.
Add an AI player. A simple AI player would make random moves. But in Nim, it's possible to write an algorithm that can play perfectly (in fact, the formula is so rigorous that calling it an "AI" is probably an overstatement). Of course, perfect play requires some complicated math that's beyond the scope of CS 106.

Submission

When you are ready to submit, please follow these steps.

If necessary, review the Code Style Guide and use Processing's built-in auto format tool. You do not need to use the precise coding style outlined in the guide, but whatever style you use, your code must be clear, concise, consistent, and commented.
If necessary, review the How To Submit document for a reminder on how to submit to LEARN.
Make sure to include a comment at the top of all source files containing your name and student ID number.
Call your sketch Nim and place the sketch folder inside a folder called A01. Zip up that folder to create an archive called A01.zip. Do not deviate from any of these required file and folder names.
Upload A01.zip to LEARN. Remember that you can (and should!) submit as many times as you like. That way, if there's a catastrophe, you and the course staff will still have access to a recent version of your code.