CSCI 102 - Fall 2023 Fundamentals of Computation

HW 10

You will write a program that utilizes functions. However, this assignment is also a cumulative assignment that should push you to use all of what you have learned over the semester. It can be difficult so please start early and DO NOT succumb to any temptation to look for solutions or share code with others.

Writing Your Code

This assignment will again be submitted through Vocareum. To develop your code you can use any text editor/compiler you like. We recommend you use the virtual machine and get used to using Linux and developing, compiling and testing code on it. However, you can use the web-based editors/compilers we have referenced in the past.

3x3 (and eventually NxN) Tic-Tac-Toe

Description & Requirements

In this program, you will write a program to allow two players to play the classic game of Tic-Tac-Toe. The first player will be represented with Xs and the second player with Os. In this program we will provide you a correct and complete implementation of main(). As you study it you will see that main simply implements the high-level logic for the game but leaves the basic tasks to various functions (e.g. printTTT(), checkForWinner(), getInputAndUpdateGrid(), and checkForDraw()). Your only task in this assignment is to complete the 7 functions prototyped below. The main() function is complete and should NOT be changed.

void printTTT(char grid[], int dim);
int checkForWinner(char grid[], int dim);
bool getInputAndUpdateGrid(char grid[], int dim, char player);
bool checkForDraw(char grid[], int dim);

// 3 small helper functions for converting 1D <=> 2D indices
char getRCEntry(char grid[], int dim, int r, int c);
int idxToRow(int idx);
int idxToCol(int idx);

In all these functions, we pass the array (named tttdata in main() but named grid in all the input arguments) storing the Xs, Os, and blanks spots so that the functions can examine the game state and modify it if needed (e.g. getInputAndUpdateGrid() will actually change the contents of grid). Remember, you can modify the value of an array directly, unlike trying to modify a primitive like an int (which is passed by value). Refer to the class notes or your lab exercises for more details. We will use the character ? to represent blank spots, so that the user sees they are available. You must follow the guidelines and produce the return values that are provided in the comments above each prototype in the skeleton code. Those comments act as requirements just as much as this webpage does.

Getting the skeleton

We have provided a starter/skeleton code on Vocareum.

Winning

To win, a player must completely fill any row, column, or one of the two diagonals with their symbol (i.e. Xs or Os). As soon as this condition occurs for any player, the program should stop and print the correct message, either:

X player wins!

or

O player wins!

The program should then immediately exit.

Draws

We want to determine if the game will end in a draw and potentially end early, declaring a draw, without needing all squares to be filled in. We will define a draw as occurring when each row, column, and each of the two diagonals have at least one X and one O. This should be checked after each turn and, if satisfied, the game should stop and the following message should be printed:

Draw...game over!

The program should then immediately exit.

Importnat: While we could determine a draw even earlier (before one of each symbol exists in each row/column/diagonal), please just implement this algorithm as described above.

Parts of the Program & Grid Size

To start you can attempt to write the code for only a 3x3 tic-tac-toe grid. Get this working first. However, this part will only be worth 14 of 20 points. To be eligible for the full 20 points you must make your code work for a generic n x n tic-tac-toe grid (where n is an odd integer from the set 3, 5, 7, 9, or 11). The largest grid will be 11x11 and thus we will need an array of at most 121 locations (this array of 121 locations is declared at the start of main()).

Grid size

We want you to try the n x n version of the program to have you practice developing loops that generalize patterns. We will use the variable name dim to specify n, which stands for the dimension of one side of the square grid. And all of your code should be generalized to work for a given value of dim. Thus, a majority of your code will use values that are some function of dim.

While we allocate the tttdata/grid array for size 121 (i.e. 11x11), we will not use the entire array for smaller dimensions. The user will enter the dimension via cin at the start of the program and then main will create the initial array contents for that size. For example, if the user enters a dimension of 3 then your could should only use entries 0 through 8 in the tttdata/grid array. When you test your code you will always need to enter that dimension value first before the game can truly start.

Output

Your grid must be drawn according to the examples shown below:

• Sample 3x3 Grid Output format:

 X | O | ?
-----------
 ? | O | X
-----------
 ? | ? | X

• Sample 5x5 Grid Output format:

 X | O | ? | ? | ?
-------------------
 ? | O | X | X | ?
-------------------
 ? | ? | X | O | ?
-------------------
 ? | X | O | O | ?
-------------------
 ? | ? | X | O | ?

1D to 2D Array access

The grid argument to each function is a 1D array. However, we can visualize it as a 2D array if we let the first dim elements be the first row, the next dim elements be the 2nd row, and so on. For a 3x3 grid, the array contents:

would correspond to a tic-tac-toe grid of:

 X | O | ?
-----------
 ? | O | X
-----------
 ? | ? | X

Put more concretely, below we show the array index correspondence to the given locations in a 3x3 grid:

 0 | 1 | 2
-----------
 3 | 4 | 5
-----------
 6 | 7 | 8

A 5x5 grid would have this correspondence to the 1D-array of 25 elements:

  0 |  1 |  2 |  3 |  4
------------------------
  5 |  6 |  7 |  8 |  9
------------------------
 10 | 11 | 12 | 13 | 14
------------------------
 15 | 16 | 17 | 18 | 19
------------------------
 20 | 21 | 22 | 23 | 24

Getting Input

At each turn you should prompt the user to enter the square number that they want to choose for their location. Use the corresponding indices shown above (i.e. 0 is the upper-left corner, etc.).

Important: If they type in a value that is out of range (i.e. not between 0 to dim^2-1) then return true from the getInputAndUpdateGrid function (and false otherwise). Similarly, if they type in a square that is already occupied with an X or O, then ask the user to choose again (and continue doing so until they choose a blank square or given an invalid location). Read the comments for getInputAndUpdateGrid.

Using math to determine row and column indexing

1. Consider the problem of iterating through row 0 of the grid. (Let us assume we count rows and columns starting at 0 like an array not 1).

For a 3x3 grid:

• the 0th row starts at grid[0]
• the 1st row starts at grid[3]
• the 2nd row starts at grid[6]

For a 5x5 grid:

• the 0th row starts at grid[0]
• the 1st row starts at grid[5]
• the 2nd row starts at grid[10]
• the 3rd row starts at grid[15]
• the 4th row starts at grid[20]

1. Can you generalize the pattern to enumerate the array indices that form the i-th row? The i-th row starts at what index in the grid array? Put your answer in terms of i and dim.

Now consider the problem of iterating down a column of the grid.

• For a 3x3 grid, iterating down column 0 would mean visiting indices: 0, 3, 6
• For a 3x3 grid, iterating down column 1 would mean visiting indices: 1, 4, 7

• For a 3x3 grid, iterating down column 2 would mean visiting indices: 2, 5, 8

• For a 5x5 grid, iterating down column 0 would mean visiting indices: 0, 5, 10, 15, 20
• For a 5x5 grid, iterating down column 1 would mean visiting indices: 1, 6, 11, 16, 21
• For a 5x5 grid, iterating down column 2 would mean visiting indices: 2, 7, 12, 17, 22
• and so on…

Can you generalize the pattern? To iterate down column i, we should start at what index in the array? Then we should take steps of what size? Put your answer in terms of i and dim.

1. Finally, consider how, if you had a given row and column location (i.e. row and col) you might determine what index in the 1D-array corresponds to that location.

• For a 3x3 grid, row=0, col=1 corresponds to index 1
• For a 3x3 grid, row=1, col=0 corresponds to index 3
• For a 3x3 grid, row=1, col=1 corresponds to index 4
• For a 3x3 grid, row=1, col=2 corresponds to index 5
• For a 3x3 grid, row=2, col=0 corresponds to index 6
• For a 3x3 grid, row=2, col=1 corresponds to index 7

• For a 3x3 grid, row=2, col=2 corresponds to index 8

• For a 5x5 grid, row=0, col=1 corresponds to index 1
• For a 5x5 grid, row=1, col=0 corresponds to index 5
• For a 5x5 grid, row=1, col=1 corresponds to index 6
• For a 5x5 grid, row=1, col=2 corresponds to index 7
• For a 5x5 grid, row=1, col=3 corresponds to index 8
• For a 5x5 grid, row=1, col=4 corresponds to index 9
• For a 5x5 grid, row=4, col=0 corresponds to index 20
• For a 5x5 grid, row=4, col=1 corresponds to index 21
• For a 5x5 grid, row=4, col=2 corresponds to index 22
• For a 5x5 grid, row=4, col=3 corresponds to index 23
• For a 5x5 grid, row=4, col=4 corresponds to index 24

Can you generalize the pattern? Given row and col numbers could you find a mathematical expression to convert to the 1D index of the square that corresponds to that row and column? Note that this relationship should help you visit the diagonals because it might be easier to consider generating two separate indices: row and col and then converting those two values to the corresponding 1D array index.

1. To summarize you should be able to complete the following conversions using simple mathematical expressions:

• Given a 1D array index, call it i, (e.g. for a 5x5 grid suppose you are given an index between 0-24), the row and column corresponding to that location, i, can be found as:

  • row = __________________ (in terms of i and dim)
  • col = __________________ (in terms of i and dim)

Use the answers you found above to complete the functions idxToRow(int i, int dim); and idxToCol(int i, int dim);. With those functions, you can call them anywhere in your code that you may want to conver a 1D index to a 2D row/column index, if it is helpful.

• Given a row and column index and the dimension of the board dim we can convert to the 1D array index, call it i, by performing:

  • i = ____________________ (in terms of row, col, and dim)

Use the answer you just found to complete the function getRCEntry(char grid[], int dim, int r, int c);. Call this function anywhere you might find it convenient to generate two separate indices (row, column) and then to access the corresponding character (X, O, etc.) from the grid at that row/column index.

Be sure to indent your code correctly and add comments describing major chunks of your code.

Hints

• For the void printTTT(char grid[], int dim) you can use past exercises or HWs that required you to print things in a 2D grid fashion. It will likely be useful to use nested loops (one loop generating a row index and the other a column index). Remember, if you correctly completed the getRCEntry(char grid[], int dim, int r, int c) function described above you can use your row, column indices to get the corresponding character from the grid array. Take care of spacing and printing the | and - (vertical and horizontal separators). You must match the spacing format shown in this document.

• For int checkForWinner(char grid[], int dim); there are several possible approaches but the easiest is likely to write one set of loops to walk down each row and see if all the locations have the same X or O character. Again, nested for loops can help generate the row, column indices and the getRCEntry function can retrieve the corresponding character. It is probably easiest to just check all the rows for a winner first. Only then would you need to walk down each of the columns to see if any column has all the same player letters. Finally, you can use one loop to walk each diagonal (first the top-left to bottom-right diagonal, followed by the top-right to bottom-left diagonal). Don’t try to check everything at once but break the code into portions: first check rows, then columns, then diagonal 1, then diagonal 2. In some ways this is similar to the Distributed-OR (Succeed Early / Fail Late) Idiom in that if you find just one row, column OR diagonal with all Xs or all Os, we have a winner and can return our answer.

• For bool checkForDraw(char grid[], int dim) you should likely use a similar strategy as checkForWinner. Remember, to be a draw each row, each column, and each diagonal must have 1 of each player letter: X and O. IN some ways this is similar to the Distributed-AND (Fail Early / Succeed Late) Idiom in that we have to prove ALL rows, columns and diagonals have at least 1 X and 1 O. If we find any row that doesn’t have any Os or any Xs we can stop early and it is NOT a draw yet. So you can iterate down each row looking for a row that proves it is not a draw. Then you can iterate down each column looking for a column that proves it is not a draw. Finally, you can iterate down the two diagonals separately.

Build and Run

Since we have taught you to compile your code using g++ and run your code on the command line, we have removed the Build and Run Scripts. You will need to compile and test your code on your own in the Terminal window/area at the bottom of the Vocareum Editor window. The executable program must be named tttn. The Submit button will also NOT compile your code but expect that it is already compiled successfully.

Testing for 5x5 and Beyond

When you click Submit we will not run any tests for 5x5 or above when you submit, only when we grade. So that means you must test these larger (5x5 and greater) cases yourselves for the various options such as X winning, O winning, draws, etc.

Submitting your code

When you believe your program is finished login to Vocareum, start the assignment, and in the upper-left of the resulting window, click New..File. A textbox will appear where you can type in the filename (leave the work/ portion there and) just type tttn.cpp. In the left window pane you should now see tttn.cpp appear (it must be named tttn.cpp) and you can click on it to open it. A blank window should appear on the right. Cut/paste your code from your other tab/window to this window and you can click Submit. Alternatively, rather than clicking New..File, you can just use the Upload button to upload the file if you have it on your VM (but the file must be named tttn.cpp).

When you click submit it should run a few automated tests to let you know if it compiled and passed some basic sanity checks. Look at the output to ensure things are working. If not, you’ll need to modify your code in Vocareum or back in your VM/PC and then re-upload or update the code back in Vocareum.

Be sure you click submit otherwise your code will just be saved, but not submitted!!

Please post any questions about using Vocareum on EdStem.